initial merge-base support

[Byron]

Translate tests from the Git test suite and assure that we produce the same results.

Tasks

• [x] Git baseline tests
• [x] implementation that can pass the baseline tests (needs handling of redundant commits)
• [x] borrowed cache for performance in multi-queries
• [x] more baseline tests
• [x] permutation tests to really hit it
• [x] Repository::merge_base()
• [x] gix merge-base for real-world scenarious
  • Test git merge-base --independent 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e on the linux kernel

FollowUp

• Optimize graph usage so that multiple merge-base runs can re-use each others graphs and thus save a lot of time for performance improvements.

Research

The commit-graph greatly accelerates the operation.

❯ hyperfine -w2 'git -c core.commitgraph=false merge-base --independent 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e' 'git merge-base --independent 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e'
Benchmark 1: git -c core.commitgraph=false merge-base --independent 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e
  Time (mean ± σ):     953.6 ms ±  10.8 ms    [User: 903.0 ms, System: 45.9 ms]
  Range (min … max):   942.5 ms … 980.0 ms    10 runs

Benchmark 2: git merge-base --independent 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e
  Time (mean ± σ):      21.8 ms ±   1.4 ms    [User: 7.3 ms, System: 12.3 ms]
  Range (min … max):    19.5 ms …  27.7 ms    119 runs

Summary
  git merge-base --independent 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e ran
   43.68 ± 2.85 times faster than git -c core.commitgraph=false merge-base --independent 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e

Performance Comparison

gix without commit-graph is exactly as fast as Git. however, with commit-graph Git is 1.6x faster.

❯ hyperfine -w2 'git -c core.commitgraph=false merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e' 'git merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e' 'gix -c core.commitgraph=false merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e' 'gix merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e'
Benchmark 1: git -c core.commitgraph=false merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e
  Time (mean ± σ):     641.8 ms ±   6.4 ms    [User: 600.6 ms, System: 36.9 ms]
  Range (min … max):   631.4 ms … 651.6 ms    10 runs

Benchmark 2: git merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e
  Time (mean ± σ):      62.4 ms ±   3.2 ms    [User: 45.2 ms, System: 14.7 ms]
  Range (min … max):    58.0 ms …  74.1 ms    49 runs

Benchmark 3: gix -c core.commitgraph=false merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e
  Time (mean ± σ):     643.7 ms ±   6.1 ms    [User: 600.6 ms, System: 39.3 ms]
  Range (min … max):   636.8 ms … 657.7 ms    10 runs

Benchmark 4: gix merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e
  Time (mean ± σ):      99.2 ms ±   1.4 ms    [User: 83.2 ms, System: 13.1 ms]
  Range (min … max):    96.0 ms … 101.9 ms    30 runs

Summary
  git merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e ran
    1.59 ± 0.08 times faster than gix merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e
   10.28 ± 0.54 times faster than git -c core.commitgraph=false merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e
   10.31 ± 0.54 times faster than gix -c core.commitgraph=false merge-base 2ecedd756908 d2360a398f0b 1253935ad801 160bab43419e 0e2209629fec 1d0e16ac1a9e