git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [WIP PATCH 6/6] notes: add notes-index for a substantial speedup.

From
Johannes Schindelin <johannes.schindelin@gmx.de>
Date
Jul 15, 2007, 23:33 UTC
Message-ID
<Pine.LNX.4.64.0707160031040.14781@racer.site>
In-Reply-To
<Pine.LNX.4.64.0707160025480.14781@racer.site>
Hi,
[this explains what Patch 6/6 is all about:]
If GIT_NOTES_TIMING_TESTS is set, t3302 will output some timing data.

It will create three repositories, the first with 10 commits and a commit note for each, the second with 100, the third with 1000.

For each repository, it times "git log" 100 times in several modes:
- with GIT_NOTES_REF set to a non-existing ref (should be equivalent to
  the timings without this patch series),
- with no .git/notes-index,
- recreating .git/notes-index as a hash map _every_ time,
- creating .git/notes-index as a hash map, and using it the rest of the time,
- recreating .git/notes-index as a sorted list _every_ time, and
- creating .git/notes-index as a sorted list only the first time, and then
  using it to find the notes by binary search.
Here is the output:
* expecting success: create_repo 10
*   ok 1: setup 10
* expecting success: test_notes 10
diff --git a/expect b/output
*   ok 2: notes work

* expecting success: time_notes 100
no-notes
0.13user 0.08system 0:00.22elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+45271minor)pagefaults 0swaps
no-cash
0.14user 0.13system 0:00.28elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+49421minor)pagefaults 0swaps
hash-cache-create
0.16user 0.24system 0:00.41elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+73111minor)pagefaults 0swaps
hash-cache
0.10user 0.08system 0:00.18elapsed 101%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+45660minor)pagefaults 0swaps
sorted-list-cache-create
0.23user 0.17system 0:00.40elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+72056minor)pagefaults 0swaps
sorted-list-cache
0.12user 0.08system 0:00.20elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+46854minor)pagefaults 0swaps
*   ok 3: notes timing

* expecting success: create_repo 100
*   ok 1: setup 100

* expecting success: test_notes 100
diff --git a/expect b/output
*   ok 2: notes work

* expecting success: time_notes 100
no-notes
0.38user 0.18system 0:00.56elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+54386minor)pagefaults 0swaps
no-cash
1.45user 0.66system 0:02.13elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+93980minor)pagefaults 0swaps
hash-cache-create
1.56user 0.98system 0:02.56elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+132604minor)pagefaults 0swaps
hash-cache
0.38user 0.17system 0:00.56elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+54785minor)pagefaults 0swaps
sorted-list-cache-create
1.56user 0.88system 0:02.47elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+124215minor)pagefaults 0swaps
sorted-list-cache
0.44user 0.23system 0:00.68elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+64952minor)pagefaults 0swaps
*   ok 3: notes timing

* expecting success: create_repo 1000
*   ok 1: setup 1000

* expecting success: test_notes 1000
diff --git a/expect b/output
*   ok 2: notes work

* expecting success: time_notes 100
no-notes
2.95user 1.19system 0:04.18elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+144766minor)pagefaults 0swaps
no-cash
23.05user 5.86system 0:33.06elapsed 87%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+639774minor)pagefaults 0swaps
hash-cache-create
23.86user 7.21system 0:32.67elapsed 95%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+710958minor)pagefaults 0swaps
hash-cache
3.16user 1.18system 0:04.35elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+145160minor)pagefaults 0swaps
sorted-list-cache-create
23.22user 7.32system 0:31.66elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+686007minor)pagefaults 0swaps
sorted-list-cache
3.74user 1.81system 0:05.77elapsed 96%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+241987minor)pagefaults 0swaps
*   ok 3: notes timing

Results:

These timings were taken from a desktop machine with a few background
processes running, so take them with a grain of salt.

As expected, without a .git/notes-index, it scales pretty badly.  Creating
.git/notes-index is slightly worse than that, but it typically happens
much less often than looking at a commit message.  Therefore the work is
worth it, since the lookup _with_ .git/notes-index is in the same ball park
as no notes at all, with the hash map being better than the sorted
list lookup.

Therefore I will go with the hash map approach, when cleaning up patch 6/6.
But not tonight.

Ciao,
Dscho
Previous: Johannes SchindelinNext: Shawn O. Pearce
Message 35 of 42 in “Introduce commit notes”
  1. 0/6 Introduce commit notesJohannes Schindelin, Jul 15, 2007
  2. 1/6 Rename git_one_line() to git_line_length() and export itJohannes Schindelin, Jul 15, 2007
  3. 2/6 Introduce commit notesJohannes Schindelin, Jul 15, 2007
  4. Junio C HamanoJul 15, 2007
  5. Johannes SchindelinJul 15, 2007
  6. Junio C HamanoJul 16, 2007
  7. Junio C HamanoJul 16, 2007
  8. 2/6 Introduce commit notesJohannes Schindelin, Jul 19, 2007
  9. Linus TorvaldsJul 19, 2007
  10. Junio C HamanoJul 19, 2007
  11. Junio C HamanoJul 19, 2007
  12. Adam HayekJul 19, 2007
  13. Andy ParkinsJul 19, 2007
  14. Johannes SchindelinJul 19, 2007
  15. Andy ParkinsJul 19, 2007
  16. Linus TorvaldsJul 19, 2007
  17. Junio C HamanoJul 20, 2007
  18. Shawn O. PearceJul 20, 2007
  19. Linus TorvaldsJul 19, 2007
  20. Johannes SchindelinJul 19, 2007
  21. Olivier GalibertJul 19, 2007
  22. Linus TorvaldsJul 19, 2007
  23. Wincent ColaiutaJul 19, 2007
  24. Johannes SchindelinJul 19, 2007
  25. Sven VerdoolaegeJul 19, 2007
  26. 3/6 Add git-notesJohannes Schindelin, Jul 15, 2007
  27. Junio C HamanoJul 16, 2007
  28. 3/6 Add git-notesJohannes Schindelin, Jul 19, 2007
  29. Johannes SchindelinJul 19, 2007
  30. 4/6 Add a test script for "git notes"Johannes Schindelin, Jul 15, 2007
  31. Junio C HamanoJul 16, 2007
  32. 4/6 Add a test script for "git notes"Johannes Schindelin, Jul 19, 2007
  33. 5/6 Document git-notesJohannes Schindelin, Jul 15, 2007
  34. 6/6 notes: add notes-index for a substantial speedup.Johannes Schindelin, Jul 15, 2007
  35. Johannes SchindelinJul 15, 2007
  36. Shawn O. PearceJul 16, 2007
  37. Johannes SchindelinJul 16, 2007
  38. Andy ParkinsJul 16, 2007
  39. Junio C HamanoJul 16, 2007
  40. Johannes SchindelinJul 16, 2007
  41. Junio C HamanoJul 16, 2007
  42. Johannes SchindelinJul 19, 2007

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.