All of lore.kernel.org
 help / color / mirror / Atom feed
From: Johan Herland <johan@herland.net>
To: git@vger.kernel.org
Cc: gitster@pobox.com, Johannes.Schindelin@gmx.de,
	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: Tue, 08 Sep 2009 05:12:34 +0200	[thread overview]
Message-ID: <200909080512.34634.johan@herland.net> (raw)
In-Reply-To: <1252376822-6138-1-git-send-email-johan@herland.net>

[-- Attachment #1: Type: Text/Plain, Size: 4066 bytes --]

On Tuesday 08 September 2009, Johan Herland wrote:
> I have some performance numbers that I will send in a separate email.

Ok, here we go:

Test scenario:
Linux kernel repo with 157118 commits, 1 note per commit, with notes
organized into various fanout schemes.
Hardware is Intel Core 2 Quad with 4GB RAM.

The tests were done on the following algorithms:

- "before": This is the state of the notes code after applying patches 1-9.
  It uses the original notes-in-hash-map implementation, and does not grok
  any fanout scheme.

- "16tree": This is the state of the notes code after applying patch 10.
  It uses the 16-tree data structure that parses the SHA-1 based fanout
  schemes.

- "flexible": This is the state of the notes code after applying the entire
  patch series. This code parses a variety of date- and SHA1-based fanout
  schemes.

Furthermore, the following notes tree structures were tested:

- "no-notes": Testing without any notes at all. This is only present as a
  baseline, and to verify that the notes code does not negatively affect
  performance when not in use.

- "no-fanout": All notes stored directly inside the root notes tree object.

- "2_38": All notes stored in a SHA1-based 2/38 fanout scheme.

- "2_2_36": All notes stored in a SHA1-based 2/2/36 fanout scheme.

- "ym": Notes are organized within "yYYYYmMM"-named subtrees, where "YYYY"
  and "MM" are the year and month (respectively) from the annotated commit's
  commit date.

- "ym_2_38": Same as above, but with a 2/38 SHA1-based fanout scheme within
  the "yYYYYmMM"-named subtrees.

- "ymd": Notes are organized within "yYYYYmMMdDD"-named subtrees.

- "ymd_2_38": Same as above, but with a 2/38 SHA1-based fanout scheme within
  the "yYYYYmMMdDD"-named subtrees.

- "y_m": Notes are organized within two-level "yYYYY/mMM" subtrees.

- "y_m_2_38": Same as above, but with a 2/38 SHA1-based fanout scheme within
  the "yYYYY/mMM"-named subtrees.

- "y_m_d": Notes are organized within three-level "yYYYY/mMM/dDD" subtrees.

- "y_m_d_2_38": Same as above, but with a 2/38 SHA1-based fanout scheme
  within the "yYYYY/mMM/dDD"-named subtrees.


Here are the runtime numbers, the first column shows the runtime for 100
repetitions of "git log -n10" (which we assume to be a common use case),
and the second column shows the runtime from a single run of
"git log --all" (which is somewhat closer to a worst case).


Algorithm / Notes tree   git log -n10 (x100)   git log --all
------------------------------------------------------------
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


Finally, I have also looked at the memory consumption of the various
algorithms and fanout schemes:

The memory usage was measured by calculating the #bytes dynamically
allocated for the notes data structure, and printing the current
usage every time get_commit_notes() was called during a complete run
of "git log --all".

The results are attached as two gnuplot graphs, one with regular
axes, and one with logarithmic axes.


Have fun! :)

...Johan

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

[-- Attachment #2: memusage_gnuplot.png --]
[-- Type: image/png, Size: 18323 bytes --]

[-- Attachment #3: memusage_gnuplot_log.png --]
[-- Type: image/png, Size: 28646 bytes --]

  parent reply	other threads:[~2009-09-08  3:17 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 ` Johan Herland [this message]
2009-09-08  4:16   ` [PATCHv5 00/14] git notes 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
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=200909080512.34634.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.