Re: [PATCH] Introduce light weight commit annotations

[Junio C Hamano <gitster@pobox.com>]

Johannes Schindelin <Johannes.Schindelin@gmx.de> writes:

> I do not understand... the entries of a tree object are sorted 
> alphabetically, right? Including the convention that if one is a prefix of 
> another, it is "smaller".
>
> While I think that the length would not be any problem, the entries' names 
> of refs/annotations/commit^{tree} are _all_ of length two, and point to 
> other tree objects. _Those_ tree objects contain _only_ entries whose 
> names contain exactly 38 characters.

That is ONLY true if you are introducing a specialized tree
object parser that knows it is dealing with the tree used in
your annotation scheme that has entries of uniform size.  In
such a tree parser, you could bisect or Newton-Raphson a tree
object data to find an entry more efficiently than for normal
trees with enries of variable size.

But I do not think you are planning to do that (nor I would
recommend you to).  With the normal tree parser, the lookup for
"refs/annotations/commit:??/?{38}" you have in your code would
open one tree (the commit's tree), find the one with leading 2
hexdigits you would want among up to 256 entries with linear
search (see tree-walk.c::find_tree_entry()), open that entry
which is another tree, and do the same linear search to find the
entry with the remaining 38 hexdigits.  Finding annotation for
commit 0000abcd... is much less expensive than ffff4567...

>> It will hurt _if_ we introduce a new tree object format that would give 
>> you a quick random-access at an entry, but it is premature to worry 
>> about that now.
>
> I do not see that. Care to enlighten me?

At some point (probably git v3.0.0) we _might_ enhance/extend
the tree object format so that it has an auxiliary hash table to
help you look up an arbitrary entry in a huge tree object (huge
in the sense that readdir(3) returns many entries, not in the
sense that find(1) returns many results) more efficiently. Pack
v4 is rumored to have something like that for in-pack trees.

If that happens, "refs/annotations/commit:?{40}" format would
let you look up an annotation for a given commit much more
efficiently than "refs/annotations/commit:??/?{38}", because it
would have to open only one tree object, instead of two.