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

Re: [RFC] Generation Number v2

From
Derrick Stolee <stolee@gmail.com>
Date
Oct 29, 2018, 20:25 UTC
Message-ID
<3576719c-3cfb-547a-3548-3aaebfe6e8a2@gmail.com>
In-Reply-To
<6367e30a-1b3a-4fe9-611b-d931f51effef@gmail.com>

Here is a re-formatted version of the tables I introduced earlier. The tables were too wide for public-inbox to render correctly (when paired with my email client). Hopefully this bulleted-list format works better. Thanks, Stefan, for pointing out the rendering problems!

### Test 1: `git log --topo-order -N`

This test focuses on the number of commits that are parsed during a `git log --topo-order` before writing `N` commits to output.

You can reproduce this test using `topo-order-tests.sh` and see all the data in `topo-order-summary.txt`. The values reported here are a sampling of the data, ignoring tests where all values were the same or extremely close in value.

android-base, N = 100
     V0: 5487
     V1: 8534
     V2: 6937
     V3: 6419
     V4: 6453
android-base, N = 1000
     V0: 36029
     V1: 44030
     V2: 41493
     V3: 41206
     V4: 45431
chromium, N = 100
     V0:    101
     V1: 424406
     V2:    101
     V3:    101
     V4:    101
gerrit, N = 100
     V0: 8212
     V1: 8533
     V2:  164
     V3:  159
     V4:  162
gerrit, N = 1000
     V0: 8512
     V1: 8533
     V2: 1990
     V3: 1973
     V4: 3766
Linux, N = 100
     V0: 12458
     V1: 12444
     V2: 13683
     V3: 13123
     V4: 13124
Linux, N = 1000
     V0: 24436
     V1: 26247
     V2: 27878
     V3: 26430
     V4: 27875
Linux, N = 10000
     V0: 30364
     V1: 28891
     V2: 27878
     V3: 26430
     V4: 27875
electron, N = 1000
     V0: 19927
     V1: 18733
     V2:  1072
     V3: 18214
     V4: 18214
Ffmpeg, N = 10000
     V0: 32154
     V1: 47429
     V2: 10435
     V3: 11054
     V4: 11054
jgit, N = 1000
     V0: 1550
     V1: 6264
     V2: 1067
     V3: 1060
     V4: 1233
julia, N = 10000
     V0: 43043
     V1: 43043
     V2: 10201
     V3: 23505
     V4: 23828
odoo, N = 1000
     V0: 17175
     V1:  9714
     V2:  4043
     V3:  4046
     V4:  4111
php-src, N = 1000
     V0: 19014
     V1: 27530
     V2:  1311
     V3:  1305
     V4:  1320
rails, N = 100
     V0: 1420
     V1: 2041
     V2: 1757
     V3: 1428
     V4: 1441
rails, N = 1000
     V0:  7952
     V1: 10145
     V2: 10053
     V3:  8373
     V4:  8373
swift, N = 1000
     V0: 1914
     V1: 4004
     V2: 2071
     V3: 1939
     V4: 1940
tensorflow, N = 1000
     V0: 10019
     V1: 39221
     V2:  6711
     V3: 10051
     V4: 10051
TypeScript, N = 1000
     V0:  2873
     V1: 12014
     V2:  3049
     V3:  2876
     V4:  2876
### Test 2: `git log --topo-order -10 A..B`

This test focuses on the number of commits that are parsed during a `git log --topo-order A..B` before writing ten commits to output. Since we fix a very small set of output commits, we care more about the part of the walk that determines which commits are reachable from `B` but not reachable from `A`. This part of the walk uses commit date as a heuristic in the existing implementation.

You can reproduce this test using `topo-compare-tests.sh` and see all the data in `topo-compare-summary.txt`. The values reported here are a sampling of the data, ignoring tests where all values were the same or extremely close in value.

_Note:_ For some of the rows, the `A` and `B` values may be swapped from what is expected. This is due to (1) a bug in the reference implementation that doesn't short-circuit the walk when `A` can reach `B`, and (2) data-entry errors by the author. The bug can be fixed, but would have introduced strange-looking rows in this table.

android-base 53c1972bc8f 92f18ac3e39
   OLD: 39403
    V0:  1544
    V1:  6957
    V2:    26
    V3:  1015
    V4:  1098
gerrit c4311f7642 777a8cd1e0
   OLD:  6457
    V0:  7836
    V1: 10869
    V2:   415
    V3:   414
    V4:   445
electron 7da7dd85e addf069f2
   OLD: 18164
    V0:   945
    V1:  6528
    V2:    17
    V3:    17
    V4:    18
julia 7faee1b201 e2022b9f0f
   OLD: 22800
    V0:  4221
    V1: 12710
    V2:   377
    V3:   213
    V4:   213
julia ae69259cd9 c8b5402afc
   OLD:  1864
    V0:  1859
    V1: 13287
    V2:    12
    V3:  1859
    V4:  1859
Linux 69973b830859 c470abd4fde4
   OLD: 111692
    V0:  77263
    V1:  96598
    V2:  80238
    V3:  76332
    V4:  76495
Linux c3b92c878736 19f949f52599
   OLD: 167418
    V0:   5736
    V1:   4684
    V2:   9675
    V3:   3887
    V4:   3923
Linux c8d2bc9bc39e 69973b830859
   OLD: 44940
    V0:  4056
    V1: 16636
    V2: 10405
    V3:  3475
    V4:  4022
odoo 4a31f55d0a0 93fb2b4a616
   OLD: 25139
    V0: 19528
    V1: 20418
    V2: 19874
    V3: 19634
    V4: 27247
swift 4046359efd b34b6a14c7
   OLD: 13411
    V0:   662
    V1:   321
    V2:    12
    V3:    80
    V4:   134
tensorflow ec6d17219c fa1db5eb0d
   OLD: 10373
    V0:  4762
    V1: 36272
    V2:   174
    V3:  3631
    V4:  3632
TypeScript 35ea2bea76 123edced90
   OLD:  3450
    V0:   267
    V1: 10386
    V2:    27
    V3:   259
    V4:   259
### Test 3: `git merge-base A B`

This test focuses on the number of commits that are parsed during a `git merge-base A B`. This part of the walk uses commit date as a heuristic in the existing implementation.

You can reproduce this test using `merge-base-tests.sh` and see all the data in `merge-base-summary.txt`. The values reported here are a sampling of the data, ignoring tests where all values were the same or extremely close in value.

android-base 53c1972bc8f 92f18ac3e39
   OLD:  81999
    V0: 109025
    V1:  81885
    V2:  77475
    V3:  81999
    V4:  82001
gerrit c4311f7642 777a8cd1e0
   OLD: 6468
    V0: 7995
    V1: 6566
    V2: 6478
    V3: 6468
    V4: 6468
electron 7da7dd85e addf069f2
   OLD: 18160
    V0: 19871
    V1: 18670
    V2:  2231
    V3: 18160
    V4: 18160
julia 7faee1b201 e2022b9f0f
   OLD: 22803
    V0: 42339
    V1: 42212
    V2:  6803
    V3: 22803
    V4: 22803
julia c8b5402afc ae69259cd9
   OLD:  7076
    V0: 42909
    V1: 42770
    V2:  2690
    V3:  7076
    V4:  7076
Linux 69973b830859 c470abd4fde4
   OLD: 44984
    V0: 47457
    V1: 44679
    V2: 38461
    V3: 44984
    V4: 44984
Linux c3b92c878736 19f949f52599
   OLD: 111740
    V0: 111027
    V1: 111196
    V2: 107835
    V3: 111771
    V4: 111368
Linux c8d2bc9bc39e 69973b830859
   OLD: 167468
    V0: 635579
    V1: 630138
    V2:  33716
    V3: 167496
    V4: 153774
odoo 4a31f55d0a0 93fb2b4a616
   OLD: 25150
    V0: 27259
    V1: 23977
    V2: 24041
    V3: 23974
    V4: 26829
swift 4046359efd b34b6a14c7
   OLD: 13434
    V0: 13254
    V1: 13940
    V2: 16023
    V3: 13127
    V4: 15008
tensorflow ec6d17219c fa1db5eb0d
   OLD: 10377
    V0: 10448
    V1: 10377
    V2:  8460
    V3: 10377
    V4: 10377
TypeScript 35ea2bea76 123edced90
   OLD: 3464
    V0: 3439
    V1: 3464
    V2: 3581
    V3: 3464
    V4: 3464
Previous: Jakub NarebskiNext: Jakub Narebski
Message 7 of 17 in “[RFC] Generation Number v2”
  1. Derrick StoleeOct 29, 2018
  2. Stefan BellerOct 29, 2018
  3. Derrick StoleeOct 29, 2018
  4. Jakub NarebskiNov 1, 2018
  5. Jakub NarebskiNov 2, 2018
  6. Jakub NarebskiNov 3, 2018
  7. Derrick StoleeOct 29, 2018
  8. Jakub NarebskiNov 1, 2018
  9. Junio C HamanoOct 30, 2018
  10. Derrick StoleeOct 31, 2018
  11. Jakub NarebskiNov 2, 2018
  12. Ævar Arnfjörð BjarmasonOct 31, 2018
  13. Derrick StoleeOct 31, 2018
  14. Jakub NarebskiNov 2, 2018
  15. Jakub NarebskiNov 1, 2018
  16. Derrick StoleeNov 1, 2018
  17. Jakub NarebskiNov 3, 2018

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.