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.
Function is stl; std::equal just makes more sense.
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).
588 | + pc2 = pc; 589 | } 590 | while (GetOp(pc, opcode)); 591 | + 592 | + result.insert(result.end(), pc2, end()); 593 | + *this = result;
You should gate this and the last insert on an if(nFound)
utACK 6443169, but I'd prefer benchmarks before merge.
edit: To clarify: benchmarks that show an improvement
@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.
Thanks to Sergio Lerner for identifying this issue and suggesting this kind of solution.
utACK d1d7775, looks good to merge
utACK d1d7775
utACK d1d7775587473410a107e7079616b9ecaae8dd06