Pieter Wuille

Rebased on top of #30285 as it looks like that is closer.

Unsure where this should live, but I have a Python reimplementation of the depgraph serialization code + mermaid formatter: https://gist.github.com/sipa/822f60db6608a26bb4aae75fd31bcb12

(Reposting at PR level instead of review level) @glozow Cool, building on that: ``` $ git rebase --exec='F=$(mktemp) && make -j -C src bench/bench_bitcoin >/dev/null && src/bench/bench_bitcoin -filter=Linearize64TxWorstCase.* -min-time=60000 -output-json=$F...

> I'm surprised at the lack of (significant) per-iteration time reduction for: > > * clusterlin: reduce computation of unnecessary pot sets (optimization) > * clusterlin: avoid recomputing potential set...

> On that note I think we'll need some diagram-quality style benchmarks to make informed decisions in the future, otherwise it makes ongoing changes difficult to justify. FWIW, the two...

@ismaelsadeeq I believe you're triggering integer overflows in your code (`1

@sdaftuar Added your benchmarks as a commit to this PR (I've reworked it to auto-detect the transaction count).

@gmaxwell I've just pushed a new set of example benchmark clusters, with the property that they need between 100k and 1M iterations to linearize optimally sometimes and never more than...

Thanks for the graphs, @glozow. That confirms the impression we got: 16-19 seem to just be really hard, and the later optimizations just don't help with it (and increase per-iteration...

Example cluster 18:  From a fee-optimization perspective it's a remarkably uninteresting graph: individual transaction feerates range from ~78 sat/vB to ~84 sat/vB. (created with newly-added DOT support in https://gist.github.com/sipa/822f60db6608a26bb4aae75fd31bcb12)