The DAG range computation often needs to get back to very old

revisions, and turns out to be disproportionately long, given

that the end goal is to remove the descendents of the given

missing revisons from the undecided set.

The fast iteration capabilities available in the Rust case make

it possible to avoid the DAG range entirely, at the cost of

precomputing the children cache, and to simply iterate on

children of the given missing revisions.

This is a case where staying on the same side of the interface

between the two languages has clear benefits.

On discoveries with initial undecided sets

small enough to bypass sampling entirely, the total cost of

computing the children cache and the subsequent iteration

becomes better than the Python + C counterpart, which relies on

reachableroots2.

For example, on a repo with more than one million revisions with

an initial undecided set of 11 elements, we get these figures:

Rust version with simple iteration

addcommons: 57.287us first undecided computation: 184.278334ms first children cache computation: 131.056us addmissings iteration: 42.766us first addinfo total: 185.24 ms

Python + C version

first addcommons: 0.29 ms addcommons 0.21 ms first undecided computation 191.35 ms addmissings 45.75 ms first addinfo total: 237.77 ms

On discoveries with large undecided sets, the initial price paid

makes the first addinfo slower than the Python + C version,

but that's more than compensated by the gain in sampling and

subsequent iterations.

Here's an extreme example with an undecided set of a million revisions:

Rust version:

first undecided computation: 293.842629ms first children cache computation: 407.911297ms addmissings iteration: 34.312869ms first addinfo total: 776.02 ms taking initial sample query 2: sampling time: 1318.38 ms query 2; still undecided: 1005013, sample size is: 200 addmissings: 143.062us

Python + C version:

first undecided computation 298.13 ms addmissings 80.13 ms first addinfo total: 399.62 ms taking initial sample query 2: sampling time: 3957.23 ms query 2; still undecided: 1005013, sample size is: 200 addmissings 52.88 ms