…ature)

This replaces the existing LIMO linearization algorithm (which internally uses
ancestor set finding and candidate set finding) with the much more performant
spanning-forest linearization algorithm.

See https://delvingbitcoin.org/t/spanning-forest-cluster-linearization/1419

…nup)

This removes the candidate set finding classes, as well as related tests
and benchmarks for them.

…imization)

This avoids the need for a loop over all parents of a transaction while walking
a chunk, and removes the need to store the set of parent dependencies explicitly.

This introduces the notion of gain to the SFL algorithm. Given a chunk c,
an active dependency d in it, and the chunks (t, b) that c would split into
if d were deactivated, the gain is defined as either (they are equivalent):

  (feerate(t) - feerate(b)) * size(t) * size(b)
  fee(t) * size(b) - fee(b) * size(t)

It happens to also be equal to these:

  (feerate(t) - feerate(c)) * size(t) * size(c)
  fee(t) * size(c) - fee(c) * size(t)

Its relevance is that this metric is proportional to a lower bound on the area
under the fee-size diagram which would be gained IF a deactivation of d does not
result in a self-merge of t and b again.

This commit adds logic to find, within each chunk, the dependency with the highest
gain. In benchmarks, this appears to be a very good heuristic for deciding which
splits are worth making.

…r (optimization)

This reduces the number of allocations required inside the SFL algorithm, and works
because the number of dependencies per transaction is at most n-1.

To minimize the memory usage from this pre-allocation (which might impact memory locality),
change the data type of DepIdx from uint32_t to uint8_t or uint16_t when possible.

…ptimization)

Within the per-transaction child dependency list, keep the active ones before all
inactive ones. This improves the complexity over iterating over active dependencies
from O(m) to O(n), as at most n-1 dependencies can be active within any given chunk
at any given time.

This distributes the work over the various chunks fairly, and simultaneously
avoids retrying chunks over and over again which are already known to be optimal.

Out of an abundance of caution that adversarially-constructed clusters might
reliably result in bad chunk split decisions with the maximum-gain strategy,
make every third consecutive attempt to split the same chunk use a random
strategy instead.

We do not need to actually keep track of whether a dependency is active
or not; it is implied by whether or not it appears within the active
prefix of its parent's child_deps, and its child's parent_deps.

Just remove setting and checking it.

This adds a rough estimate of algorithm runtime, so it can be interrupted if no
solution is found in time. Due to inherent differences between platforms, this
will not be extremely accurate, but it is preferable over directly measuring
time for consistency.