Re: [PATCHv5 00/14] git notes

[Johan Herland <johan@herland.net>]

Hi,

On Tuesday 08 September 2009, Johannes Schindelin wrote:
> On Tue, 8 Sep 2009, Johan Herland wrote:
> > Algorithm / Notes tree   git log -n10 (x100)   git log --all
> > ------------------------------------------------------------
> > next / no-notes                4.77s              63.84s
> >
> > before / no-notes              4.78s              63.90s
> > before / no-fanout            56.85s              65.69s
> >
> > 16tree / no-notes              4.77s              64.18s
> > 16tree / no-fanout            30.35s              65.39s
> > 16tree / 2_38                  5.57s              65.42s
> > 16tree / 2_2_36                5.19s              65.76s
> >
> > flexible / no-notes            4.78s              63.91s
> > flexible / no-fanout          30.34s              65.57s
> > flexible / 2_38                5.57s              65.46s
> > flexible / 2_2_36              5.18s              65.72s
> > flexible / ym                  5.13s              65.66s
> > flexible / ym_2_38             5.08s              65.63s
> > flexible / ymd                 5.30s              65.45s
> > flexible / ymd_2_38            5.29s              65.90s
> > flexible / y_m                 5.11s              65.72s
> > flexible / y_m_2_38            5.08s              65.67s
> > flexible / y_m_d               5.06s              65.50s
> > flexible / y_m_d_2_38          5.07s              65.79s
>
> It's good to see that the no-notes behaves roughly like baseline.

Agreed.

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

1. Looking up a few (1 - 10) notes on an individual basis. In this case, 
performance will always be "good enough", and I don't believe it's 
worth spending much time optimizing for this case.

2. Looking up many notes in a sequence based on the chronology of the 
objects (commits) they annotate. This is what 'git log' does, and I 
believe this is the case we should optimize for.

Once you work from this assumption, it is clear that date-based fanout 
beats pure SHA1-based fanout, because it changes the notes lookup 
process from random-access to near-streaming. This is clearly reflected 
in the memory usage graphs I posted.

Also note that the "flexible" code to some degree resolves the whole 
date-based fanout vs. SHA1-based fanout discussion: We are now free to 
choose -- at runtime -- which notes tree structure is more optimal for 
a given collection of notes.

> and the date-based fan-out is rather limiting in certain respects:
>
> - for the typical nightly-build-generated notes, this fan-out is
> pretty inefficient memory-wise.

Yes and no. A y/m/d/40 structure with 1 note for every y/m/d is indeed 
wasteful, but using a y/40 structure instead creates a much better 
situation with a "healthy" ~365 notes per year level. And the y/40 
still preserves some of the 'streaming' aspects mentioned above.

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

In any case, the flexible lookup code still allow us to organize notes 
purely by SHA1-based fanout, so annotated trees/blobs could still be 
supported by the same code (modulo a small s/struct commit/struct 
object/ patch) provided that they are stored in a notes tree that 
simply does not use date-based fanout.

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

In the SHA1-based case, each notes lookup does indeed start at the root 
of the data structure (corresponding to the top-level tree), but in the 
date-based case, we keep a pointer (cur_node) to the innermost 
date-based tree that was most recently used. Thus, if the next note is 
within the same date-based tree (which I assume is the common case), 
then we don't need to look at the root of the data structure.

>   Maybe a finer-grained fan-out (finer than 16-bits) could help. 
> After all, if you have 16 different notes, chances are that they have
> 16 different first letters, but all have the same commit year. 
> That's where the top-level notes with a fan-out perform incredibly
> bad.

Not really, the first lookup would start at the root node, and navigate 
into the year node, but all subsequent lookups would start directly at 
the year node (and only backtrack if the commit year doesn't match the 
year node).

BTW, when you mention "finer than 16-bits", do you mean moving from a 
16-tree to a, say, 32-tree or 64-tree structure? That will complicate 
the tree navigation somewhat, and increase memory waste. (Remember, I 
started out with a 256-tree idea, but scrapped it because of memory 
waste).

>   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

> would _outperform_ the date-based one, at least with less than 1
> note/commit (and maybe even then, because the year-based fan-out
> results in pretty varying entropies per fan-out depth).
>
>   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)

Yes, the challenge is indeed striking the correct balance. I believe 
that the notes code should be taught to write (and automatically 
re-organize) the notes tree so that it is optimized for the current 
collection of notes.

> - related to the previous point is my gut feeling that the date-based
>   fan-out has nothing to do with any theoretical optimum.  I am
> pretty certain that the optimal fan-out strategy depends heavily on
> the SHA-1s of the annotated objects (if you have 10,000 notes in
> 2009, but only 1 in 2008, the year-based fan-out _must_ be
> suboptimal)  and maybe is something like a sibling to the Fibonacci
> heap.

Yes, it is trivial to create scenarios where any rigid date-based fanout 
is suboptimal. However, it is equally trivial to create scenarios where 
any SHA1-based fanout will perform worse than a carefully chosen 
date-based fanout. I believe the best way forward is to design for 
flexibility in the notes tree structure, and then teach the notes 
_writing_ code to choose a notes tree structure that is good/optimal 
for the given set of notes.

> - I'd love to see performance numbers for less than 157118 notes. 
> Don't get me wrong, it is good to see the worst-case scenario in
> terms of notes/commits ratio.  But it will hardly be the common case,
> and I very much would like to optimize for the common case.
>
>   So, I'd appreciate if you could do the tests with something like
> 500 notes, randomly spread over the commits (rationale: my original
> understanding was that the notes could amend commit messages, and
> that is much more likely to be done with relatively old commits that
> you cannot change anymore).

Ok. I will try to test that.

> Please understand that I might not have the time to participate in
> this thread as much as I would like to.  The next 4 days will be
> especially hard.

Thanks for the feedback! I appreciate any time you're able to spend on 
this. And I don't mind waiting for a few days for more feedback.


Have fun! :)

...Johan

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