I cleaned up my implementation a bit, and pushed it here, replacing the Linearize() function currently merged in Bitcoin Core.
Here are benchmarks with the existing examples in the codebase. These are the timing for full, optimal, linearizations from scratch, for a rather arbitrarily-selected collections of “hard” clusters actually seen on the network. “hard”, of course, is based on examples that were hard with the existing approach, by a few different metrics, but this may not carry over to the new approach. I entirely expect that these are not anywhere close to the worst cases for the spanning-forest algorithm.
| µs (master) | µs (this) | #tx | benchmark | |
|---|---|---|---|---|
| 70.6 | 21.1 | 71 | LinearizeOptimallyExample00 |
|
| 94.9 | 30.4 | 81 | LinearizeOptimallyExample01 |
|
| 55.3 | 29.5 | 90 | LinearizeOptimallyExample02 |
|
| 54.7 | 31.1 | 87 | LinearizeOptimallyExample03 |
|
| 2.3 | 4.1 | 35 | LinearizeOptimallyExample04 |
|
| 12.6 | 9.7 | 60 | LinearizeOptimallyExample05 |
|
| 37.2 | 35.6 | 99 | LinearizeOptimallyExample06 |
|
| 8.7 | 7.5 | 52 | LinearizeOptimallyExample07 |
|
| 67.5 | 22.0 | 69 | LinearizeOptimallyExample08 |
|
| 15.2 | 24.9 | 77 | LinearizeOptimallyExample09 |
|
| 9.8 | 9.6 | 48 | LinearizeOptimallyExample10 |
|
| 371677.6 | 24.1 | 77 | LinearizeOptimallyExample11 |
|
| 491.4 | 7.2 | 40 | LinearizeOptimallyExample12 |
|
| 59.5 | 32.9 | 96 | LinearizeOptimallyExample13 |
|
| 361.3 | 34.6 | 93 | LinearizeOptimallyExample14 |
|
| 14003.9 | 9.7 | 55 | LinearizeOptimallyExample15 |
|
| 10864.3 | 43.4 | 76 | LinearizeOptimallyExample16 |
|
| 13992.6 | 50.6 | 98 | LinearizeOptimallyExample17 |
|
| 14029.4 | 45.4 | 99 | LinearizeOptimallyExample18 |
|
| 15198.4 | 32.6 | 78 | LinearizeOptimallyExample19 |