Subject: Re: [PATCH v3 2/4] path: optimize common dir checking

From: Junio C Hamano <[email-masked]>
Date: Wed, 12 Aug 2015 15:48:25 -0700

David Turner <[email-masked]> 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 <[email-masked]>
> ---
>
> 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 ;-).