Optimize CHECKSIGADD Script Validation

JeremyRubin commented at 8:52 pm on January 19, 2022: contributor

This is a mild validation improvement that improves performance by caching some signature data when you have a Taproot script fragment that uses CHECKSIGADD Multisignatures with sighash single. In some basic testing I showed this to have about a 0.6% speedup during block validation for a block with a lot of CHECKSIGADDs, but that was with the entirety of block validation so the specific impact on the script interpreter performance should be a bit more once you subtract things like coin fetching. If desired I can produce a more specific/sharable bench for this, the code I used to test was just monkey patching the existing taproot tests since generating valid spends is kinda tricky. But it’s sort of an obvious win so I’m not sure it needs a rigorous bench, but I will tinker on one of those while the code is being reviewed for correctness.

The overhead of this approach is that:

ScriptExecutionData is no longer const
around 32 bytes of extra stack space
zero extra hashing since we only cache on first use

JeremyRubin force-pushed on Jan 19, 2022

in src/script/interpreter.h:221 in 4a8fd0af4e outdated

215@@ -215,6 +216,9 @@ struct ScriptExecutionData
216     bool m_validation_weight_left_init = false;
217     //! How much validation weight is left (decremented for every successful non-empty signature check).
218     int64_t m_validation_weight_left;
219+
220+    //! The hash of the corresponding output
221+    mutable std::optional<uint256> m_output_hash;

sipa commented at 9:57 pm on January 19, 2022:

Perhaps it is cleaner to not make this mutable, but instead make the places where ScriptExecutionData is used non-const? That’d make it also clear that it is not safe for concurrent modification.

JeremyRubin commented at 10:15 pm on January 19, 2022:

i think that seems reasonable, but it is a little bit of a tradeoff because you really ought not to be modifying the fields after creation except in this case, and non-consting it would make that unclear.

i’d also (ideally) make the m_output_hash retrieved through a getter function rather than inline logic, but I didn’t want to make this PR more complex of an interface change.

maybe in a followup PR we could do some refactors to make it gotten through a Getter and rename the class to MutableScriptExecutionData? Or break out the Mutable and Immutable part as two separate caches? Also an option to just always pre-cache this, but that violates ‘dont pay for what you dont use’

sipa commented at 10:26 pm on January 19, 2022:

It’s a simple struct with some state data. As long as there is no benefit to actually having anything immutable, I don’t think there is much of a problem with just making it non-const everywhere. m_validation_weight_left is also changed at runtime.

DrahtBot added the label Consensus on Jan 19, 2022

Optimize CHECKSIGADD Script Validation cfa575266b

JeremyRubin force-pushed on Jan 19, 2022

DrahtBot commented at 7:56 am on January 20, 2022: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#22793 (Simplify BaseSignatureChecker virtual functions and GenericTransactionSignatureChecker constructors by achow101)
#21702 (Implement BIP-119 Validation (CheckTemplateVerify) by JeremyRubin)

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.

MarcoFalke added the label Refactoring on Jan 20, 2022

jamesob commented at 3:05 pm on January 20, 2022: member

Benchmarks are showing results consistent with a 0.5% speedup:

bench name	command
ibd.local.range.500000.550000	`bitcoind -dbcache=10000 -debug=coindb -debug=bench -listen=0 -connect=0 -addnode=127.0.0.1:8888 -prune=9999999 -printtoconsole=0 -assumevalid=0`

#24105 vs. $mergebase (absolute)

bench name	x	#24105	$mergebase
ibd.local.range.500000.550000.total_secs	2	6004.5920 (± 11.7900)	6035.6871 (± 1.0297)
ibd.local.range.500000.550000.peak_rss_KiB	2	7234538.0000 (± 3322.0000)	7236830.0000 (± 250.0000)
ibd.local.range.500000.550000.cpu_kernel_secs	2	357.3100 (± 3.3900)	359.2450 (± 0.8750)
ibd.local.range.500000.550000.cpu_user_secs	2	36706.6300 (± 8.2500)	36801.1350 (± 10.6050)

#24105 vs. $mergebase (relative)

bench name	x	#24105	$mergebase
ibd.local.range.500000.550000.total_secs	2	1	1.005
ibd.local.range.500000.550000.peak_rss_KiB	2	1	1.000
ibd.local.range.500000.550000.cpu_kernel_secs	2	1	1.005
ibd.local.range.500000.550000.cpu_user_secs	2	1	1.003

jonatack commented at 4:39 pm on January 20, 2022: member

ACK cfa575266bc0198574a82e8e386040e969b05dea

sipa commented at 5:07 pm on January 20, 2022: member

utACK cfa575266bc0198574a82e8e386040e969b05dea

MarcoFalke commented at 5:24 pm on January 20, 2022: member

ibd.local.range.500000.550000

wat?

How can this result in a speedup in syncing a part of the chain that has no taproot inputs at all? This code is almost dead during IBD, so shouldn’t at all influence IBD time.

MarcoFalke commented at 6:15 pm on January 20, 2022: member

If someone wants to write a “real” benchmark there is already src/bench/verify_script.cpp which can serve as a template.

JeremyRubin commented at 7:03 pm on January 20, 2022: contributor

@MarcoFalke i don’t think that’s a useful template since what is needed is a taproot transaction to test this.

I agree that the @jamesob result is suspect for the reason you mentioned.

MarcoFalke commented at 7:09 pm on January 20, 2022: member

Jup, with template I meant that all you need to do is create the taproot transaction. Obviously the benchmark doesn’t yet bench taproot, since the bench was written before taproot.

jamesob commented at 7:34 pm on January 20, 2022: member

ibd.local.range.500000.550000

wat?

How can this result in a speedup in syncing a part of the chain that has no taproot inputs at all? This code is almost dead during IBD, so shouldn’t at all influence IBD time.

Yeah I just blindly ran

0bitcoinperf bench-pr --num-blocks 50_000 \
1  --run-id checksigadd-optimize \
2  --bitcoind-args='-dbcache=10000 -assumevalid=0' \
3  --run-count 2 24105

which anyone is capable of doing (provided they’re willing to navigate the somewhat labyrinthine bitcoinperf setup process).

I had only cursorily skimmed the change when doing this; the standard deviation of the timing on this branch’s IBD is ~0.2%, so there’s a decent chance the result is just noise. But it’s not like I cooked the benchmark or anything.

sipa commented at 8:21 pm on January 20, 2022: member

Sometimes even seemingly unrelated code changes can affect performance (e.g. by ordering the functions slightly differently in memory, resulting in different CPU instruction caching or alignment) in small but statistically significant ways.

MarcoFalke commented at 1:06 pm on January 22, 2022: member

review ACK cfa575266bc0198574a82e8e386040e969b05dea

JeremyRubin commented at 5:50 pm on January 22, 2022: contributor

ready to merge?

theStack approved

theStack commented at 10:19 pm on January 22, 2022: member

Code-review ACK cfa575266bc0198574a82e8e386040e969b05dea

nit: could adapt the PR description before merge, the “because of mutable field” part doesn’t apply anymore

JeremyRubin commented at 0:21 am on January 24, 2022: contributor

nit addressed

MarcoFalke commented at 11:35 am on January 24, 2022: member

Conceptually the same optimization works also for bip 143 hashing, so I am wondering if it is worth it to keep the 143/341 symmetry. Though, this will likely make a larger/uglier diff.

JeremyRubin commented at 7:17 pm on January 24, 2022: contributor

I think this is good to go as is.

The optimization can be added for BIP-143 later, I can draft a follow up PR for that.

In any case, it would be separate commits because we want to preserve bisecting.

MarcoFalke merged this on Jan 25, 2022

MarcoFalke closed this on Jan 25, 2022

sidhujag referenced this in commit 6dee1741b9 on Jan 28, 2022

DrahtBot locked this on Jan 25, 2023

Optimize CHECKSIGADD Script Validation #24105

Conflicts

#24105 vs. $mergebase (absolute)

#24105 vs. $mergebase (relative)