Re: [PATCH] Introduce light weight commit annotations

Johannes Schindelin [off-list ref] 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...

quoted

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.

Hi,

On Sun, 10 Jun 2007, Junio C Hamano wrote:

Johannes Schindelin [off-list ref] writes:

quoted

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.

Ouch. That is a real flaw in my proposal. It completely destroys my "I 
think this will scale just fine" argument.

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.

Let me think that one through. At the moment I cannot think of an easy 
fix.

Ciao,
Dscho

Hi,

On Sun, 10 Jun 2007, Junio C Hamano wrote:

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...

Okay, I did not find a proper solution. commit->file name via "s/../&\//g" 
is too ugly. But then, I really hope that packv4 becomes unvapourware at 
some stage (for other reasons), and that _should_ help these issues.

Hmm.

Ciao,
Dscho