ancestors: add merge node rank computation based on leaps
It is not necessary to build the whole ancestor set of a merge node if we already have the leaps on its exclusive part. This gives the size of the exclusive part, to sum with the distinct and already known ancestors of the common part.
This gives a speedup of around 45% on the two reference graphs below. The computation of the leap is still essentially visiting all ancestors of each merge nodes.
./utils/benchmark.sh ../vcsgraph-reference/graph/mercurial-2018-08-01-b2561d4a.graph
Before:
Time (mean ± σ): 8.062 s ± 0.168 s [User: 8.027 s, System: 0.035 s]
Range (min … max): 7.921 s … 8.249 s 3 runs
After:
Time (mean ± σ): 4.535 s ± 0.127 s [User: 4.512 s, System: 0.023 s]
Range (min … max): 4.411 s … 4.664 s 3 runs
./utils/benchmark.sh ./vcsgraph-reference/graph/pypy-2018-08-01-8e256678-reference.graph
Before:
Time (mean ± σ): 109.524 s ± 6.063 s [User: 109.438 s, System: 0.068 s]
Range (min … max): 102.765 s … 114.481 s 3 runs
After:
Time (mean ± σ): 58.583 s ± 2.143 s [User: 58.544 s, System: 0.030 s]
Range (min … max): 57.321 s … 61.057 s 3 runs