git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
Junio C Hamano <gitster@pobox.com>
Date
Aug 12, 2015, 22:48 UTC
Message-ID
<xmqqio8kjf7q.fsf@gitster.dls.corp.google.com>
In-Reply-To
<1439416645-19173-2-git-send-email-dturner@twopensource.com>
David Turner <dturner@twopensource.com> writes:
Show 10 quoted lines
> 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 ;-).

Previous: David TurnerNext: Michael Haggerty
Message 3 of 24 in “refs: clean up common_list”
  1. 1/4 refs: clean up common_listDavid Turner, Aug 12, 2015
  2. 2/4 path: optimize common dir checkingDavid Turner, Aug 12, 2015
  3. Junio C HamanoAug 12, 2015
  4. Michael HaggertyAug 13, 2015
  5. Junio C HamanoAug 14, 2015
  6. David TurnerAug 14, 2015
  7. Junio C HamanoAug 14, 2015
  8. David TurnerAug 14, 2015
  9. Michael HaggertyAug 15, 2015
  10. Michael HaggertyAug 15, 2015
  11. Junio C HamanoAug 17, 2015
  12. Duy NguyenAug 15, 2015
  13. David TurnerAug 16, 2015
  14. Duy NguyenAug 16, 2015
  15. 3/4 refs: make refs/worktree/* per-worktreeDavid Turner, Aug 12, 2015
  16. Eric SunshineAug 13, 2015
  17. David TurnerAug 13, 2015
  18. Michael HaggertyAug 13, 2015
  19. David TurnerAug 13, 2015
  20. Michael HaggertyAug 14, 2015
  21. Junio C HamanoAug 14, 2015
  22. Duy NguyenAug 15, 2015
  23. 4/4 bisect: make bisection refs per-worktreeDavid Turner, Aug 12, 2015
  24. Duy NguyenAug 15, 2015

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.