Block template fees are calculated by looping over new_tmpl->vTxFees and return (early) once the fee_threshold is exceeded.
This left an edge case when the mempool is empty, which this commit fixes and adds a test for.
Also update test/functional/interface_ipc.py to reflect the new behavior,
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/33566.
See the guideline for information on the review process.
| Type | Reviewers |
|---|---|
| ACK | sipa, optout21, cedwies |
| Concept ACK | zaidmstrr |
| Stale ACK | TheCharlatan |
| User requested bot ignore | Raimo33 |
If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.
Reviewers, this pull request conflicts with the following ones:
BlockTemplateCache by ismaelsadeeq)If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.
Concept ACK. this is a subtle bug which would result in an infinite loop. Approach NACK. the proposed solution adds branching complexity for a case which is extremely unlikely.
allow me to propose a more elegant and modern solution: c23a65414f239c0d867d13f1be02a232096c1f9d
Block template fees are calculated by looping over new_tmpl->vTxFees
and return (early) once the fee_threshold is exceeded.
This left an edge case when the mempool is empty, which this commit
fixes and adds a test for. It does so by using std::accumulate instead
of manual loops.
Also update interface_ipc.py to account for the new behavior.
Co-authored-by: Raimo33 <claudio.raimondi@protonmail.com>
Concept ACK
Maybe add the new test in a first commit (showing how it fails), and then the fix in a new commit? For test change without fix, and fix in see commits 3a7e58ec81fb2caeef1cf369d47b0a247d923180 and 3220ce81b1df090895daa32dfb5a1af003d6d88b
@optout21 the test-each-commit job enforces that each commit has a passing test.
I’m not sure I understand this correctly, but if you mean that all tests should pass with each commit – yes, first commit has test checks matching the non-fixed code (i.e. BOOST_REQUIRE(should_be_nullptr == nullptr);), and fix commit also adapts this one check. It’s more clear looking at the fix commit what is the change in behavior, if adding the test and fix are separated.
Leaving in one commit is also fine in this PR IMHO.
535- new_fees += fee;
536- Assume(options.fee_threshold != MAX_MONEY);
537- if (new_fees >= current_fees + options.fee_threshold) return new_tmpl;
538- }
539+ // Check if fees increased enough to return the new template
540+ const CAmount new_fees = std::accumulate(new_tmpl->vTxFees.begin(), new_tmpl->vTxFees.end(), CAmount{0});
std::accumulate in line 526 seems good, but using it in line 530 has some performance impact. std::accumulate search for the whole vector despite the condition already being met. With this it increases the best-case time complexity and some average-case complexity from Ω(k) (where k <= n) to Ω(n). Any caller calling this with frequent polling might face some milliseconds of performance issues in some cases.
I feel like the approach in commit 2e8fff3 is more optimal than this one with the constant work of O(1).
you’re talking about theoretical complexity. but I’m almost certain that the std::accumulate approach is orders of magnitude faster in practice when you measure absolute time. this is because avoiding a branch at every iteration allows for optimizations such as SIMD vectorization, or even simply a better data access pattern which is more cache friendly.
I’d love to see some benchmarks!
I ran a small external python simulation to get a rough sense of how often the early-exit fee loop would actually stop much earlier than a full sum under realistic mempool conditions.
Using a model with 3000 txs (fees = feerate × vsize, realistic feerate ranges, small per-tick mempool drift, and occasional high-fee arrivals), the results were:
– threshold=0: median touch fraction ≈ 0.97, meaning in a typical run the loop still scans about 97% of transactions before returning; about 43 % of trials didn’t beat the old total at all.
– threshold=100.000: median = 1.0, early exit never triggered within a tick.
On my machine (Apple M2 Max), summing all 3000 fees takes about 0.4 µs, so the median time saved by early-exit was around 0.01 µs (10 ns) (essentially negligible).
This could suggest that early-exit almost never helps in practice, while the std::accumulate has the benefits already discussed.
tACK 8f76732
Reviewed and tested. The empty mempool case (fee_threshold==0) now behaves as expected and is covered by tests.
