All of lore.kernel.org
 help / color / mirror / Atom feed
From: Johan Herland <johan@herland.net>
To: Johannes Schindelin <Johannes.Schindelin@gmx.de>
Cc: git@vger.kernel.org, Junio C Hamano <gitster@pobox.com>,
	trast@student.ethz.ch, tavestbo@trolltech.com,
	git@drmicha.warpmail.net, chriscool@tuxfamily.org,
	spearce@spearce.org
Subject: Re: [PATCHv5 00/14] git notes
Date: Thu, 10 Sep 2009 11:25:35 +0200	[thread overview]
Message-ID: <200909101125.35451.johan@herland.net> (raw)
In-Reply-To: <200909081436.30761.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

  parent reply	other threads:[~2009-09-10  9:25 UTC|newest]

Thread overview: 58+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2009-09-08  2:26 [PATCHv5 00/14] git notes Johan Herland
2009-09-08  2:26 ` [PATCHv5 01/14] Introduce commit notes Johan Herland
2009-09-08  2:26 ` [PATCHv5 02/14] Add a script to edit/inspect notes Johan Herland
2009-09-08  2:26 ` [PATCHv5 03/14] Speed up git notes lookup Johan Herland
2009-09-08  2:26 ` [PATCHv5 04/14] Add an expensive test for git-notes Johan Herland
2009-09-08  2:26 ` [PATCHv5 05/14] Teach "-m <msg>" and "-F <file>" to "git notes edit" Johan Herland
2009-09-08  2:26 ` [PATCHv5 06/14] fast-import: Add support for importing commit notes Johan Herland
2009-09-08  2:26 ` [PATCHv5 07/14] t3302-notes-index-expensive: Speed up create_repo() Johan Herland
2009-09-08  2:26 ` [PATCHv5 08/14] Add flags to get_commit_notes() to control the format of the note string Johan Herland
2009-09-08  2:26 ` [PATCHv5 09/14] Add '%N'-format for pretty-printing commit notes Johan Herland
2009-09-08  2:26 ` [PATCHv5 10/14] Teach notes code to free its internal data structures on request Johan Herland
2009-09-08  2:26 ` [PATCHv5 11/14] Teach the notes lookup code to parse notes trees with various fanout schemes Johan Herland
2009-09-08  2:27 ` [PATCHv5 12/14] Selftests verifying semantics when loading notes trees with various fanouts Johan Herland
2009-09-08  2:27 ` [PATCHv5 13/14] Allow flexible organization of notes trees, using both commit date and SHA1 Johan Herland
2009-09-08  2:27 ` [PATCHv5 14/14] Add test cases for date-based fanouts Johan Herland
2009-09-08  3:12 ` [PATCHv5 00/14] git notes Johan Herland
2009-09-08  4:16   ` Junio C Hamano
2009-09-08  8:54     ` Johan Herland
2009-09-08  9:32       ` Johannes Schindelin
2009-09-08 12:36         ` Johan Herland
2009-09-08 15:53           ` Johannes Schindelin
2009-09-08 22:46             ` Johan Herland
2009-09-10  6:23               ` Stephen R. van den Berg
2009-09-10  9:25           ` Johan Herland [this message]
2009-09-08 20:31         ` Junio C Hamano
2009-09-08 21:10           ` Shawn O. Pearce
2009-09-08 21:36             ` Sverre Rabbelier
2009-09-08 21:39               ` Shawn O. Pearce
2009-09-08 21:57                 ` Sverre Rabbelier
2009-09-08 21:40           ` Johan Herland
2009-09-12 15:50   ` Johan Herland
2009-09-12 18:11     ` Shawn O. Pearce
2009-09-12 18:35       ` Johan Herland
2009-09-10 14:00 ` Geert Bosch
2009-09-10 14:09   ` Michael J Gruber
2009-09-10 14:12     ` Geert Bosch
2009-09-12  0:11 ` Junio C Hamano
2009-09-12 15:52   ` Johan Herland
2009-09-12 16:08     ` [PATCHv6 " Johan Herland
2009-09-12 16:08     ` [PATCHv6 01/14] Introduce commit notes Johan Herland
2009-09-12 16:08     ` [PATCHv6 02/14] Add a script to edit/inspect notes Johan Herland
2009-09-12 16:08     ` [PATCHv6 03/14] Speed up git notes lookup Johan Herland
2009-09-12 16:08     ` [PATCHv6 04/14] Add an expensive test for git-notes Johan Herland
2009-09-12 16:08     ` [PATCHv6 05/14] Teach "-m <msg>" and "-F <file>" to "git notes edit" Johan Herland
2009-09-12 16:08     ` [PATCHv6 06/14] fast-import: Add support for importing commit notes Johan Herland
2009-09-12 16:08     ` [PATCHv6 07/14] t3302-notes-index-expensive: Speed up create_repo() Johan Herland
2009-09-12 16:08     ` [PATCHv6 08/14] Add flags to get_commit_notes() to control the format of the note string Johan Herland
2009-09-12 16:08     ` [PATCHv6 09/14] Add '%N'-format for pretty-printing commit notes Johan Herland
2009-09-12 16:08     ` [PATCHv6 10/14] Teach notes code to free its internal data structures on request Johan Herland
2009-09-12 18:40       ` Junio C Hamano
2009-09-12 22:21         ` Johan Herland
2009-09-12 16:08     ` [PATCHv6 11/14] Teach the notes lookup code to parse notes trees with various fanout schemes Johan Herland
2009-09-12 16:08     ` [PATCHv6 12/14] Selftests verifying semantics when loading notes trees with various fanouts Johan Herland
2009-09-12 16:08     ` [PATCHv6 13/14] Allow flexible organization of notes trees, using both commit date and SHA1 Johan Herland
2009-09-12 18:41       ` Junio C Hamano
2009-09-12 22:33         ` Johan Herland
2009-09-12 23:37           ` Junio C Hamano
2009-09-12 16:08     ` [PATCHv6 14/14] Add test cases for various date-based fanouts Johan Herland

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=200909101125.35451.johan@herland.net \
    --to=johan@herland.net \
    --cc=Johannes.Schindelin@gmx.de \
    --cc=chriscool@tuxfamily.org \
    --cc=git@drmicha.warpmail.net \
    --cc=git@vger.kernel.org \
    --cc=gitster@pobox.com \
    --cc=spearce@spearce.org \
    --cc=tavestbo@trolltech.com \
    --cc=trast@student.ethz.ch \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.