Skip to content

ancestors: add merge node rank computation based on leaps

Euxane TRAN-GIRARD requested to merge topic/default/rank-with-leaps into branch/default

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

Merge request reports