consensus: remove redundant checks in merkle root computation #22046

In ComputeMerkleRoot, the mutated flag is only set to true but never becomes false thereafter. Therefore all following tests after it became true are wasted computation. Fix this by doing the tests only while the flag is false.

While at that, drop the temporary local variable and use the provided parameter in place.

Signed-off-by: Zefir Kurtisi zefir.kurtisi@gmail.com

<!-- *** Please remove the following help text before submitting: *** Pull requests without a rationale and clear improvement may be closed immediately. GUI-related pull requests should be opened against https://github.com/bitcoin-core/gui first. See CONTRIBUTING.md -->

<!-- Please provide clear motivation for your patch and explain how it improves Bitcoin Core user experience or Bitcoin Core developer experience significantly: * Any test improvements or new tests that improve coverage are always welcome. * All other changes should have accompanying unit tests (see `src/test/`) or functional tests (see `test/`). Contributors should note which tests cover modified code. If no tests exist for a region of modified code, new tests should accompany the change. * Bug fixes are most welcome when they come with steps to reproduce or an explanation of the potential issue as well as reasoning for the way the bug was fixed. * Features are welcome, but might be rejected due to design or scope issues. If a feature is based on a lot of dependencies, contributors should first consider building the system outside of Bitcoin Core, if possible. * Refactoring changes are only accepted if they are required for a feature or bug fix or otherwise improve developer experience significantly. For example, most "code style" refactoring changes require a thorough explanation why they are useful, what downsides they have and why they *significantly* improve developer experience or avoid serious programming bugs. Note that code style is often a subjective matter. Unless they are explicitly mentioned to be preferred in the [developer notes](/doc/developer-notes.md), stylistic code changes are usually rejected. -->

<!-- Bitcoin Core has a thorough review process and even the most trivial change needs to pass a lot of eyes and requires non-zero or even substantial time effort to review. There is a huge lack of active reviewers on the project, so patches often sit for a long time. -->

Personally I find the existing version easier to reason about. I think I'd prefer leaving this as-is, especially considering that this is consensus critical code :)

Did you compare the benchmark before and after?

Does this improve IBD speed significantly? Otherwise it might not be worth it the review effort.

Does this improve IBD speed significantly? Otherwise it might not be worth it the review effort.

I reduced the change to the relevant (one-line) part, which should be trivial to review.

Maybe the overall speed improvement is not significant, but the local is obvious: if the rightest-most bottom-leaf is a copy, the flag becomes true immediately, but the (then waste) checks continue for every next level up to the root.

As kernel developer I might be more waste sensitive than required here, so if you think it is not worth it, I'm fine with closing - and sorry for noise.

I don't see significant gains. I've even tried other tweaks with the same result:

tweak 1 - break loop if more iterations aren't needed

                  if (hashes[pos] == hashes[pos + 1]) {
                      mutation = true;
                      break;
                  }

tweak 2: - check mutated once:

    if (mutated) {
        while (hashes.size() > 1) {
            // …
        }
    } else { 
        while (hashes.size() > 1) {
            // …
        }
    }

I don't see significant gains. I've even tried other tweaks with the same result:

Thanks, the hashing cost in fact is so dominant that the comparison operation remains below measurement accuracy:

|             ns/leaf |              leaf/s |    err% |     total | benchmark
|--------------------:|--------------------:|--------:|----------:|:----------
|               60.88 |       16,424,775.25 |    0.1% |      0.04 | `MerkleRoot`
|               60.30 |       16,584,351.40 |    0.0% |      0.04 | `MerkleRoot_no_mutation`
|               60.71 |       16,471,608.02 |    0.1% |      0.04 | `MerkleRoot_patch`

... not worth it.