Re: [PATCHv5 00/14] git notes

From: Johan Herland <johan@herland.net>
Date: Sep 8, 2009, 22:46 UTC
Message-ID: <200909090046.45213.johan@herland.net>
In-Reply-To: <alpine.DEB.1.00.0909081741590.4330@intel-tinevez-2-302>

On Tuesday 08 September 2009, Johannes Schindelin wrote:

Show 12 quoted lines

> On Tue, 8 Sep 2009, Johan Herland wrote:
> > On Tuesday 08 September 2009, Johannes Schindelin wrote:
> > > I can see that some people may think that date-based fan-out is the
> > > cat's ass, but I have to warn that we have no idea how notes will be
> > > used,
> >
> > I don't agree. Although we will certainly see many more use cases for
> > notes, I believe that the vast majority of them can be placed in one of
> > two categories:
> 
> My experience with Git is that having beliefs how my work is used was a
> constant source of surprise.

And you believe that a system that only allows SHA1-based fanout schemes is better equipped to tackle such surprises than a system that provides both date-based and SHA1-based fanout schemes?

Show 7 quoted lines

> > > - I find the restriction to commits rather limiting.
> >
> > I see your point, but I don't agree until I see a compelling case for
> > annotating a non-commit.
> 
> My point is that it is too late by then, if you don't allow for a
>  flexible and still efficient scheme.

As I replied to Junio, we could use the epoch as a "commit date" for tree and blob objects, thus making them representable in a date-based fanout scheme (although if there are a signficant number of non-commit notes, the code should be smart enough to find a better (SHA1-based probably) fanout scheme for those notes).

Show 16 quoted lines

> > > - most of the performance difference between the date-based and the
> > >   SHA-1 based fan-out looks to me as if the issue was the top-level
> > >   tree. Basically, this tree has to be read _every_ time _anybody_
> > >   wants to read a note.
> >
> > Not sure what you're trying to say here. The top-level notes tree is
> > read (as in fill_tree_descriptor()) exactly _once_. After that, it is
> > cached by the internal data structure (until free_commit_notes() or
> > end-of-process).
> 
> By that reasoning, we do not need any fan-out scheme.
> 
> Keep in mind: reading a large tree object takes a long time.  That's why
> we started fan-out.  Reading a large number of tree objects also takes a
> long time.  That's why I propagated flexible fan-out that is only read-in
> on demand.

Not sure where you're going with this. Of course we want to strike an optimal balance between the size of tree objects and the number of tree objects. Nobody is arguing about that. Both SHA1-based and (in the most common cases) date-based schemes can be used to achieve this balance. But using date-based fanout has the added advantage of providing better performance (both runtime- and memory-wise) when looking up notes in a chronological order.

Show 16 quoted lines

> > > But I think that having a dynamic fan-out that can even put blobs
> > > into the top-level tree (nothing prevents us from doing that, right?)
> >
> > Well, the "flexible" code does add the new requirement that all entries
> > in a notes (sub)tree object must follow the same scheme, i.e. you
> > cannot have:
> >
> >   /12/34567890123456789012345678901234567890
> >   /2345/678901234567890123456789012345678901
> >
> > but you can have
> >
> >   /12/34567890123456789012345678901234567890
> >   /23/45/678901234567890123456789012345678901
> 
> Umm, why?  Is there any good technical reason?

In the date-based parts of notes tree, there are very good reasons for doing so: The code peeks at the first tree entry in order to determine what kind of date-based fanout is used in the current tree object. Subsequent entries (in that tree object) that do not follow the same format are skipped/ignored.

The SHA1-based fanout code has not changed since the last iteration, so this extra requirement is not absolutely necessary for the SHA1-based parts of the notes tree. However, the extra requirement does guarantee that commit notes have exactly one unique location in the notes tree, and thus relieves us of having to keep searching for alternative notes locations, and concatenate the notes found.

Show 11 quoted lines

> > > The real question for me, therefore, is: what is the optimal way to
> > > strike the balance between size of the tree objects (which we want to
> > > be small, so that unpacking them is fast)  and depth of the fan-out
> > > (which we want to be shallow to avoid reading worst-case 39 tree
> > > objects to get at one single note).
> >
> > s/39/19/ (each fanout must use at least 2 chars of the 40-char SHA1)
> 
> That is another unnecessary restriction that could cost you dearly.  Just
> think what happens if it turns out that the optimal number of tree items
> is closer to 16 than to 255...

The code can easily be rewritten to allow for "odd" fanouts (1/39, 1/1/38, etc.). Feel free to submit a patch.

I was, however, naive enough to assume that when git.git decided on using 2/38 fanout for its loose objects, then some performance-related thoughts went into that decision. If there are indications that multiple-of-2-type fanouts are not optimal, we should probably reconsider.

Have fun! :)

...Johan

-- 
Johan Herland, <johan@herland.net>
www.herland.net