Re: [PATCHv5 00/14] git notes

[Johan Herland <johan@herland.net>]

On Tuesday 08 September 2009, Johan Herland wrote:
> 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

[snip]

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

Here are the results of the 500-notes-in-kernel-repo test:

Algorithm / Notes tree   git log -n10 (x100)   git log --all

next / no-notes                 4.83s             64.78s

before / no-notes               4.84s             64.76s
before / no-fanout              4.98s             64.89s

16tree / no-notes               4.84s             64.61s
16tree / no-fanout              4.92s             64.68s
16tree / 2_38                   4.85s             64.45s
16tree / 2_2_36                 4.85s             64.63s

flexible / no-notes             4.84s             64.82s
flexible / no-fanout            4.91s             65.01s
flexible / 2_38                 4.85s             64.93s
flexible / 2_2_36               4.85s             64.63s
flexible / ym                   4.83s             64.63s
flexible / ym_2_38              4.86s             64.72s
flexible / ymd                  4.91s             64.74s
flexible / ymd_2_38             4.91s             64.56s
flexible / y_m                  4.86s             64.76s
flexible / y_m_2_38             4.86s             64.71s
flexible / y_m_d                4.86s             64.73s
flexible / y_m_d_2_38           4.84s             64.50s

I don't like the noise level in the second column ('git log --all'). Then 
again, I don't find that column very interesting (it's mostly there to 
verify that we don't have any abysmal worst-case behaviours in the notes 
code).

The first column is fairly nice and tidy, though. At a first glance it shows 
pretty much the same results as the 157000-notes table previously posted. 
Obviously the abysmal performance of no-fanout is gone (500 notes in a 
single tree object is not _that_ bad), although a 2/38-fanout is still a 
better choice for 500 notes (but 2/2/36 does not provide any additional 
improvement).

>From this we can start to guess that the threshold for moving from no fanout 
to 2/38 is somewhere below 500 notes, while the theshold for moving from 
2/38 to 2/2/36 is between 500 and ~157000 notes (probably much closer to 
157000 than to 500; I wouldn't be surprised if ~256 entries per level turns 
out to be good a threshold).

The date-based fanout performs on par with the SHA1-based fanout, although 
it's hard to say anything conclusively when the numbers are as close as 
this. However, the ymd and ymd_2_38 fanout probably show signs of too much 
overhead (too many levels) at only 500 notes. This is not surprising.

My gut feeling tells me that moving from 'no-fanout' to either '2_38' or 
'ym' is a good idea at ~256 notes. Then, if we went with '2_38', we'd have 
to switch to '2_2_36' at ~64K notes (i.e. when each /38 level reaches ~256 
notes) However, it seems that with 'ym', we could stick with it for much 
longer before having to consider switching to a different fanout alternative 
(probably 'ym_2_38' or 'y_m_d').


Have fun! :)

...Johan

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