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

Re: [PATCH 00/28] Store references hierarchically in cache

From
Ramkumar Ramachandra <artagnon@gmail.com>
Date
Oct 28, 2011, 13:07 UTC
Message-ID
<CALkWK0=Hsq_yg1Vyr-3_jf9n=WcB_XNYRQa0SEhSWD5VxKBXQg@mail.gmail.com>
In-Reply-To
<1319804921-17545-1-git-send-email-mhagger@alum.mit.edu>
Hi Michael,
Michael Haggerty writes:
Show 5 quoted lines
> Therefore, this patch series changes the data structure used to store
> the reference cache from a single array of pointers-to-struct into a
> tree-like structure in which each subdirectory of the reference
> namespace is stored as an array of pointers-to-entry and entries can
> be either references or subdirectories containing more references.
Very nice! I like the idea. Can't wait to start reading the series.
>  * refs/replace is almost *always* needed even though it often
>    doesn't even exist.  Thus the presence of many loose references
>    slows down *many* git commands for no reason whatsoever.
Was this one of your primary inspirations for writing this series?
Show 8 quoted lines
>  * When a new reference is created, is_refname_available() is called
>    to see whether there is another another reference whose name
>    conflicts with the new one.  Currently this loads and iterates
>    through *all* references.  But there are only a few refnames that
>    can possibly conflict; for example, given the refname
>    "refs/heads/foo/bar", the only possible conflicts are with
>    "refs/heads/foo" and "refs/heads/foo/bar/*".  Therefore it is
>    silly to load and iterate through the whole refname hierarchy.

Hm, the original design does sound quite sub-optimal. I suppose it was written when Git didn't have so many refs in so many subdirectories.

>  * "git for-each-ref" is capable of searching a subtree of the
>    references.  But currently this causes all references to be
>    loaded.

Ah. I was using git for-each-ref to write a filter-branch like thing earlier, and I was wondering why it was so slow.

> * the time to create a new branch goes from 180 ms to less than 10 ms
>  (my test resolution only includes two decimal places) and the time
>  to checkout a new branch does the same.

I'm interested in seeing how the callgraph changed. Assuming you used Valgrind to profile it, could you publish the outputs?

> * the time for a "git filter-branch" of all commits (which used to
>  scale like N^2) goes from 4 hours to 13 minutes.  (Since
>  filter-branch necessarily *creates* lots of loose references, the
>  savings are also there if the references are originally packed.)
This is seriously awesome.
> The efficiency gains are such that some operations are now faster with
> loose references than with packed references; however, some operations
> with packed references slow down a bit.

Curiously, why do operations with packed references slow down? (I'll probably find out in a few minutes after reading the series, but I'm asking anyway because it it's very non-obvious to me now)

Show 7 quoted lines
> These changes do not increase the amount of space per reference needed
> for the reference cache, but they do add one similarly-sized entry for
> each subdirectory (for each of loose and packed).  I don't think that
> the space increase should be significant in any reasonable situation.
>
> After these changes, there is a benefit to sharding the reference
> namespace, especially for loose references.
Hm, I wonder what this means for Git hosting services.
Show 7 quoted lines
> Patches 11-24 change most of the internal functions to work with
> "struct ref_entry *" (namely the kind of ref_entry that holds a
> directory of references) instead of "struct ref_dir *".  The reason
> for this change it to allow these functions access to the "flag" and
> "name" fields that are stored in ref_entry and thereby avoid having to
> store redundant information in "struct ref_dir" (which would increase
> the size of *every* ref_entry because of its presence in the union).

Hm, I was wondering why the series was looking so intimidating. Is it not possible to squash all (or atleast some) of these together?

> From: Michael Haggerty <mhagger@alum.mit.edu>
Nit: Can't you configure your email client to put this in the "From: "
header of your emails?
Thanks for the interesting read.
-- Ram
Previous: mhagger@alum.mit.eduNext: Michael Haggerty
Message 34 of 36 in “Store references hierarchically in cache”
  1. 00/28 Store references hierarchically in cachemhagger@alum.mit.edu, Oct 28, 2011
  2. 01/28 refs.c: reorder definitions more logicallymhagger@alum.mit.edu, Oct 28, 2011
  3. 02/28 free_ref_entry(): new functionmhagger@alum.mit.edu, Oct 28, 2011
  4. 03/28 check_refname_component(): return 0 for zero-length componentsmhagger@alum.mit.edu, Oct 28, 2011
  5. 04/28 struct ref_entry: nest the value part in a unionmhagger@alum.mit.edu, Oct 28, 2011
  6. 05/28 refs.c: rename ref_array -> ref_dirmhagger@alum.mit.edu, Oct 28, 2011
  7. 06/28 refs: store references hierarchicallymhagger@alum.mit.edu, Oct 28, 2011
  8. 07/28 sort_ref_dir(): do not sort if already sortedmhagger@alum.mit.edu, Oct 28, 2011
  9. 08/28 refs: sort ref_dirs lazilymhagger@alum.mit.edu, Oct 28, 2011
  10. 09/28 do_for_each_ref(): only iterate over the subtree that was requestedmhagger@alum.mit.edu, Oct 28, 2011
  11. 10/28 get_ref_dir(): keep track of the current ref_dirmhagger@alum.mit.edu, Oct 28, 2011
  12. 11/28 refs: wrap top-level ref_dirs in ref_entriesmhagger@alum.mit.edu, Oct 28, 2011
  13. 12/28 get_packed_refs(): return (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  14. 13/28 get_loose_refs(): return (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  15. 14/28 is_refname_available(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  16. 15/28 find_ref(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  17. 16/28 read_packed_refs(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  18. 17/28 add_ref(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  19. 18/28 find_containing_direntry(): use (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  20. 19/28 search_ref_dir(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  21. 20/28 add_entry(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  22. 21/28 do_for_each_ref_in_dir*(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  23. 22/28 sort_ref_dir(): take (ref_entry *) instead of (ref_dir *)mhagger@alum.mit.edu, Oct 28, 2011
  24. 23/28 struct ref_dir: store a reference to the enclosing ref_cachemhagger@alum.mit.edu, Oct 28, 2011
  25. 24/28 read_loose_refs(): take a (ref_entry *) as argumentmhagger@alum.mit.edu, Oct 28, 2011
  26. 25/28 refs: read loose references lazilymhagger@alum.mit.edu, Oct 28, 2011
  27. 26/28 is_refname_available(): query only possibly-conflicting referencesmhagger@alum.mit.edu, Oct 28, 2011
  28. Fix "is_refname_available(): query only possibly-conflicting references"mhagger@alum.mit.edu, Nov 15, 2011
  29. Junio C HamanoNov 15, 2011
  30. Michael HaggertyNov 15, 2011
  31. Junio C HamanoNov 15, 2011
  32. 27/28 read_packed_refs(): keep track of the directory being worked inmhagger@alum.mit.edu, Oct 28, 2011
  33. 28/28 repack_without_ref(): call clear_packed_ref_cache()mhagger@alum.mit.edu, Oct 28, 2011
  34. Ramkumar RamachandraOct 28, 2011
  35. Michael HaggertyOct 28, 2011
  36. Michael HaggertyNov 16, 2011

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.