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

[Johannes Schindelin <Johannes.Schindelin@gmx.de>]

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