Skip to content

ancestors: use leap-based iterator for leap computations

Switch to the leap-based OrderedAncestorIterator instead of the naive recursive implementation, which allows working on bigger graphs by avoiding hitting the call stack limit.

Benchmark (limited to the first 10k nodes because the previous implementation is limited by the call stack):

TEST_GRAPH="vcsgraph-reference/graph/mercurial-2018-08-01-b2561d4a.graph"
HEAD="f91e5630ce7e29a8d15db54415482cb0f4f1b9c1"
TEST_CMD="head -n10000 $TEST_GRAPH | cargo run --release --example cli -- ordered-ancestor $HEAD"
hyperfine --runs 4 \
  --prepare "hg update 06f4a298ca13; cargo build --release --example cli" "$TEST_CMD" \
  --prepare "hg update leaps_with_ordered_ancestors_iterator; cargo build --release --example cli" "$TEST_CMD"

Result: the new version runs 1.48 ± 0.05 times faster than the previous one.

Edited by Pacien TRAN-GIRARD

Merge request reports