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$(echo .)com \
--cc=chriscool@tuxfamily$(echo .)org \
--cc=dturner@twopensource$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=mhagger@alum$(echo .)mit.edu \
--cc=pclouds@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox