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
42@@ -43,11 +43,11 @@
43
44
45 uint256 ComputeMerkleRoot(std::vector<uint256> hashes, bool* mutated) {
46- bool mutation = false;
47+ if (mutated) *mutated = false;
48 while (hashes.size() > 1) {
49- if (mutated) {
&& !mutation here?
There are two optimizations included here:
While the second saves one compare+assign operation and might be insignificant, the first effectively saves useless processing as the result is already known.
To me it is not only optimization but causing a trigger that something was forgotten when reading the code. @practicalswift : would you support @promag’s suggestion to limit the proposal to include only the first part, which would limit the change to one line and gain the most potential savings, or do you oppose the change generally?
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.
Signed-off-by: Zefir Kurtisi <zefir.kurtisi@gmail.com>
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
0 if (hashes[pos] == hashes[pos + 1]) {
1 mutation = true;
2 break;
3 }
tweak 2: - check mutated once:
0 if (mutated) {
1 while (hashes.size() > 1) {
2 // …
3 }
4 } else {
5 while (hashes.size() > 1) {
6 // …
7 }
8 }
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:
0| ns/leaf | leaf/s | err% | total | benchmark
1|--------------------:|--------------------:|--------:|----------:|:----------
2| 60.88 | 16,424,775.25 | 0.1% | 0.04 | `MerkleRoot`
3| 60.30 | 16,584,351.40 | 0.0% | 0.04 | `MerkleRoot_no_mutation`
4| 60.71 | 16,471,608.02 | 0.1% | 0.04 | `MerkleRoot_patch`
… not worth it.