From: Junio C Hamano <gitster@pobox.com>
To: David Turner <dturner@twopensource.com>
Cc: git@vger.kernel.org, mhagger@alum.mit.edu,
chriscool@tuxfamily.org, pclouds@gmail.com
Subject: Re: [PATCH v3 2/4] path: optimize common dir checking
Date: Wed, 12 Aug 2015 15:48:25 -0700 [thread overview]
Message-ID: <xmqqio8kjf7q.fsf@gitster.dls.corp.google.com> (raw)
In-Reply-To: <1439416645-19173-2-git-send-email-dturner@twopensource.com> (David Turner's message of "Wed, 12 Aug 2015 17:57:23 -0400")
David Turner <dturner@twopensource.com> writes:
> Instead of a linear search over common_list to check whether
> a path is common, use a trie. The trie search operates on
> path prefixes, and handles excludes.
>
> Signed-off-by: David Turner <dturner@twopensource.com>
> ---
>
> Probably overkill, but maybe we could later use it for making exclude
> or sparse-checkout matching faster (or maybe we have to go all the way
> to McNaughton-Yamada for that to be truly worthwhile).
This is why I love this list. A mere mention of "something better
than linear list" immediately is answered by a trie and a mention of
McNaughton-Yamada ;-).
next prev parent reply other threads:[~2015-08-12 22:48 UTC|newest]
Thread overview: 24+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-08-12 21:57 [PATCH v3 1/4] refs: clean up common_list David Turner
2015-08-12 21:57 ` [PATCH v3 2/4] path: optimize common dir checking David Turner
2015-08-12 22:48 ` Junio C Hamano [this message]
2015-08-13 9:05 ` Michael Haggerty
2015-08-14 17:04 ` Junio C Hamano
2015-08-14 20:04 ` David Turner
2015-08-14 20:27 ` Junio C Hamano
2015-08-14 20:54 ` David Turner
2015-08-15 18:20 ` Michael Haggerty
2015-08-15 18:12 ` Michael Haggerty
2015-08-17 15:55 ` Junio C Hamano
2015-08-15 7:59 ` Duy Nguyen
2015-08-16 5:04 ` David Turner
2015-08-16 12:20 ` Duy Nguyen
2015-08-12 21:57 ` [PATCH v3 3/4] refs: make refs/worktree/* per-worktree David Turner
2015-08-13 17:15 ` Eric Sunshine
2015-08-13 17:41 ` David Turner
2015-08-13 20:16 ` Michael Haggerty
2015-08-13 20:32 ` David Turner
2015-08-14 8:18 ` Michael Haggerty
2015-08-14 17:10 ` Junio C Hamano
2015-08-15 8:04 ` Duy Nguyen
2015-08-12 21:57 ` [PATCH v3 4/4] bisect: make bisection refs per-worktree David Turner
2015-08-15 7:44 ` [PATCH v3 1/4] refs: clean up common_list Duy Nguyen
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=xmqqio8kjf7q.fsf@gitster.dls.corp.google.com \
--to=gitster@pobox.com \
--cc=chriscool@tuxfamily.org \
--cc=dturner@twopensource.com \
--cc=git@vger.kernel.org \
--cc=mhagger@alum.mit.edu \
--cc=pclouds@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.