Optimize and Cleanup CScript::FindAndDelete #7907

pull pstratem wants to merge 4 commits into bitcoin:master from pstratem:2016-04-17-findanddelete changing 2 files +129 −3

pstratem commented at 6:01 AM on April 19, 2016: contributor

This PR improves the worst-case behavior of CScript::FindAndDelete.

I have emphasized the obvious correctness of the algorithm in this commit.

Additionally I have done extensive fuzzing to ensure the result is identical to the current implementation.
pstratem force-pushed on Apr 19, 2016
laanwj added the label Validation on Apr 19, 2016
laanwj added the label Resource usage on Apr 19, 2016
Replace memcmp with std::equal in CScript::FindAndDelete
Function is stl; std::equal just makes more sense.
ec9ad5f199
Replace c-style cast with c++ style static_cast. c0f660c3a3
Unit test for CScript::FindAndDelete e2a30bc9a9
pstratem force-pushed on Apr 19, 2016
TheBlueMatt commented at 10:38 PM on April 20, 2016: member

I highly prefer this to #7884...the original is kinda hard to read, but #7884 is impossible to reasonably convince yourself works, even if it probably does. I benchmarked syncing on tmpfs with the final call to VerifySignature in CheckSig() disabled on this and #7884 and couldn't detect any difference in sync time through about 280k (just happened to be some blk* flies I had lying around went until there).

in src/script/script.h:None in 3322744ab5 outdated

 588 | +            pc2 = pc;
 589 |          }
 590 |          while (GetOp(pc, opcode));
 591 | +
 592 | +        result.insert(result.end(), pc2, end());
 593 | +        *this = result;

TheBlueMatt commented at 10:39 PM on April 20, 2016:

You should gate this and the last insert on an if(nFound)

pstratem force-pushed on Apr 20, 2016
dcousens commented at 2:29 AM on April 21, 2016: contributor

utACK 6443169, but I'd prefer benchmarks before merge.

edit: To clarify: benchmarks that show an improvement
sipa commented at 5:03 AM on April 21, 2016: member

@kazcw @dcousens It is only intended to improve the worst case behaviour, and @TheBlueMatt already benchmarked that it does not measurably affect the average case. @pstratem If, after including Matt's suggestion, you drop the result.reserve() call, I think this will run with zero heap effect for non-match situations.
pstratem force-pushed on Apr 21, 2016
pstratem commented at 5:22 AM on April 21, 2016: contributor

@sipa indeed you're right I've made that change

Improve worst-case behavior of CScript::FindAndDelete

Thanks to Sergio Lerner for identifying this issue and suggesting this kind of solution.

d1d7775587

pstratem force-pushed on Apr 22, 2016
dcousens commented at 12:27 AM on April 22, 2016: contributor

utACK d1d7775, looks good to merge
laanwj commented at 10:11 AM on April 28, 2016: member

utACK d1d7775
sipa commented at 4:58 PM on May 5, 2016: member

utACK d1d7775587473410a107e7079616b9ecaae8dd06
laanwj merged this on May 5, 2016
laanwj closed this on May 5, 2016
laanwj referenced this in commit 006cdf64dc on May 5, 2016
svost referenced this in commit eff0cd3a46 on May 10, 2016
random-zebra referenced this in commit fbcc5305d6 on Feb 17, 2020
DrahtBot locked this on Sep 8, 2021

Contributors

Labels

Validation Resource usage