Improve peformance of CTransaction::HasWitness (28107 follow-up)

dergoegge commented at 11:03 am on November 1, 2023: member

This addresses #28107 (review) from #28107.

DrahtBot commented at 11:03 am on November 1, 2023: contributor

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	theStack, stickies-v, TheCharlatan, achow101
Concept ACK	glozow

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

fanquake requested review from ajtowns on Nov 1, 2023

fanquake requested review from glozow on Nov 1, 2023

in src/primitives/transaction.cpp:87 in fed7b91855 outdated

83+    for (size_t i = 0; i < vin.size(); i++) {
84+        if (!vin[i].scriptWitness.IsNull()) {
85+            has_witness = true;
86+            break;
87+        }
88+    }

stickies-v commented at 11:51 am on November 1, 2023:

nit: I’d at least use a range based loop

0    bool has_witness{false};
1    for (const auto input : vin) {
2        if (!input.scriptWitness.IsNull()) {
3            has_witness = true;
4            break;
5        }
6    }

but probably okay to refactor to use algorithm?

0    bool has_witness = std::any_of(vin.begin(), vin.end(), [](const auto& input) {
1        return !input.scriptWitness.IsNull();
2    });

dergoegge commented at 11:56 am on November 1, 2023: member

Can someone please re-run the “CI / macOS 13 native” job, failure seems unrelated.

in src/primitives/transaction.cpp:89 in fed7b91855 outdated

85+            has_witness = true;
86+            break;
87+        }
88+    }
89+
90+    if (!has_witness) {

stickies-v commented at 11:56 am on November 1, 2023:

Could simplify return statement too so the whole fn just becomes:

0Wtxid CTransaction::ComputeWitnessHash() const
1{
2    bool has_witness = std::any_of(vin.begin(), vin.end(), [](const auto& input) {
3        return !input.scriptWitness.IsNull();
4    });
5
6    return Wtxid::FromUint256(has_witness ? (CHashWriter{0} << *this).GetHash() : hash.ToUint256());
7}

fanquake commented at 11:58 am on November 1, 2023: member

failure seems unrelated.

Are you sure?

 0 Traceback (most recent call last):
 1  File "/Users/runner/work/bitcoin/bitcoin/ci/scratch/build/bitcoin-x86_64-apple-darwin/test/functional/test_framework/test_framework.py", line 132, in main
 2    self.run_test()
 3  File "/Users/runner/work/bitcoin/bitcoin/ci/scratch/build/bitcoin-x86_64-apple-darwin/test/functional/rpc_createmultisig.py", line 65, in run_test
 4    self.do_multisig()
 5  File "/Users/runner/work/bitcoin/bitcoin/ci/scratch/build/bitcoin-x86_64-apple-darwin/test/functional/rpc_createmultisig.py", line 241, in do_multisig
 6    tx = node0.sendrawtransaction(rawtx3["hex"], 0)
 7         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 8  File "/Users/runner/work/bitcoin/bitcoin/ci/scratch/build/bitcoin-x86_64-apple-darwin/test/functional/test_framework/coverage.py", line 50, in __call__
 9    return_val = self.auth_service_proxy_instance.__call__(*args, **kwargs)
10                 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
11  File "/Users/runner/work/bitcoin/bitcoin/ci/scratch/build/bitcoin-x86_64-apple-darwin/test/functional/test_framework/authproxy.py", line 129, in __call__
12    raise JSONRPCException(response['error'], status)
13test_framework.authproxy.JSONRPCException: mandatory-script-verify-flag-failed (Witness program was passed an empty witness) (-26)

dergoegge commented at 12:01 pm on November 1, 2023: member

Are you sure?

Yes, it passes locally.

fanquake commented at 12:04 pm on November 1, 2023: member

Want to document it as an intermittent failure?

stickies-v commented at 12:07 pm on November 1, 2023: contributor

Approach ACK

I had similar thoughts while reviewing 28107 but figured the computation was still fast enough. Given that ComputeWitnessHash is only called once during initialization (and is private) and HasWitness is called frequently, this approach is strictly better.

fanquake commented at 1:20 pm on November 1, 2023: member

The rpc_createmultisig.py test is now failing in two other CI jobs and MSAN is unhappy:

 0==19201==WARNING: MemorySanitizer: use-of-uninitialized-value
 1    [#0](/bitcoin-bitcoin/0/) 0x563f069e85d0 in bcmp /msan/llvm-project/compiler-rt/lib/msan/../sanitizer_common/sanitizer_common_interceptors.inc:856:10
 2    [#1](/bitcoin-bitcoin/1/) 0x563f0956bff5 in base_blob<256u>::Compare(base_blob<256u> const&) const src/./uint256.h:54:66
 3    [#2](/bitcoin-bitcoin/2/) 0x563f0956bff5 in operator!=(base_blob<256u> const&, base_blob<256u> const&) src/./uint256.h:57:89
 4    [#3](/bitcoin-bitcoin/3/) 0x563f0956bff5 in CTransaction::HasWitness() const src/./primitives/transaction.h:370:33
 5    [#4](/bitcoin-bitcoin/4/) 0x563f0956bff5 in void SerializeTransaction<CHashWriter, CTransaction>(CTransaction const&, CHashWriter&) src/./primitives/transaction.h:265:16
 6    [#5](/bitcoin-bitcoin/5/) 0x563f09569863 in void CTransaction::Serialize<CHashWriter>(CHashWriter&) const src/./primitives/transaction.h:326:9
 7    [#6](/bitcoin-bitcoin/6/) 0x563f09569863 in void Serialize<CHashWriter, CTransaction>(CHashWriter&, CTransaction const&) src/./serialize.h:776:7
 8    [#7](/bitcoin-bitcoin/7/) 0x563f09569863 in CHashWriter& CHashWriter::operator<<<CTransaction>(CTransaction const&) src/./hash.h:161:9
 9    [#8](/bitcoin-bitcoin/8/) 0x563f09569863 in CTransaction::ComputeWitnessHash() const src/primitives/transaction.cpp:93:47
10    [#9](/bitcoin-bitcoin/9/) 0x563f09569f47 in CTransaction::CTransaction(CMutableTransaction&&) src/primitives/transaction.cpp:97:190
11    [#10](/bitcoin-bitcoin/10/) 0x563f06eb3f68 in std::__1::__shared_ptr_emplace<CTransaction const, std::__1::allocator<CTransaction const>>::__shared_ptr_emplace[abi:v170002]<CMutableTransaction>(std::__1::allocator<CTransaction const>, CMutableTransaction&&) /msan/cxx_build/include/c++/v1/__memory/shared_ptr.h:302:37
12    [#11](/bitcoin-bitcoin/11/) 0x563f06eb3f68 in std::__1::shared_ptr<CTransaction const> std::__1::allocate_shared[abi:v170002]<CTransaction const, std::__1::allocator<CTransaction const>, CMutableTransaction, void>(std::__1::allocator<CTransaction const> const&, CMutableTransaction&&) /msan/cxx_build/include/c++/v1/__memory/shared_ptr.h:1022:55
13    [#12](/bitcoin-bitcoin/12/) 0x563f09071b26 in std::__1::shared_ptr<CTransaction const> std::__1::make_shared[abi:v170002]<CTransaction const, CMutableTransaction, void>(CMutableTransaction&&) /msan/cxx_build/include/c++/v1/__memory/shared_ptr.h:1031:12
14    [#13](/bitcoin-bitcoin/13/) 0x563f09071b26 in std::__1::shared_ptr<CTransaction const> MakeTransactionRef<CMutableTransaction>(CMutableTransaction&&) src/./primitives/transaction.h:418:93
15    [#14](/bitcoin-bitcoin/14/) 0x563f09071b26 in ChainstateManager::UpdateUncommittedBlockStructures(CBlock&, CBlockIndex const*) const src/validation.cpp:3706:24
16    [#15](/bitcoin-bitcoin/15/) 0x563f09073e46 in ChainstateManager::GenerateCoinbaseCommitment(CBlock&, CBlockIndex const*) const src/validation.cpp:3733:5
17    [#16](/bitcoin-bitcoin/16/) 0x563f08bb9dd6 in node::BlockAssembler::CreateNewBlock(CScript const&) src/node/miner.cpp:160:69
18    [#17](/bitcoin-bitcoin/17/) 0x563f0822b2a5 in TestChain100Setup::CreateBlock(std::__1::vector<CMutableTransaction, std::__1::allocator<CMutableTransaction>> const&, CScript const&, Chainstate&) src/test/util/setup_common.cpp:310:56

glozow commented at 1:34 pm on November 1, 2023: member

Concept ACK

in src/primitives/transaction.h:370 in fed7b91855 outdated

371-            if (!vin[i].scriptWitness.IsNull()) {
372-                return true;
373-            }
374-        }
375-        return false;
376+        return hash.ToUint256() != m_witness_hash.ToUint256();

maflcko commented at 1:42 pm on November 1, 2023:

what about leaving this function as-is and making the two members std::optional instead, then add an early-return one-line happy-path for the case when both are not nullopt?

ajtowns commented at 1:55 pm on November 1, 2023:

Making them optional would add 16 bytes to every CTransaction struct, I think? This approach would also prevent them from being marked const in CTransaction. If having m_witness_hash be non-const was okay, you could default it to uint256::ZERO and set m_witness_hash = ComputeWitnessHash() in the constructor. I don’t think that’s ideal though.

DrahtBot added the label CI failed on Nov 1, 2023

ajtowns commented at 1:57 pm on November 1, 2023: contributor

0 [#3](/bitcoin-bitcoin/3/) 0x563f0956bff5 in CTransaction::HasWitness() const src/./primitives/transaction.h:370:33
1 [#4](/bitcoin-bitcoin/4/) 0x563f0956bff5 in void SerializeTransaction<CHashWriter, CTransaction>(CTransaction const&, CHashWriter&) src/./primitives/transaction.h:265:16

If it’s not obvious, the bug is that m_witness_hash is initialised by serializing the transaction with its witness, but in that case, Serialize calls HasWitness() to work out which format to use, which with this change relies on access to m_witness_hash which is not yet initialised.

dergoegge force-pushed on Nov 1, 2023

dergoegge commented at 2:17 pm on November 1, 2023: member

Added a std::optional<bool> to CTransaction as a cache for HasWitness.

stickies-v commented at 2:40 pm on November 1, 2023: contributor

I’m not a fan of the std::optional<bool> cache approach, it’s an error-prone API imo (even if it’s private and small). I think it makes more sense to just calculate the boolean at initialization and follow the same pattern as for hash and m_witness_hash? It has to be calculated for every instance anyway.

~As e.g. in https://github.com/stickies-v/bitcoin/commit/2e69a6597c1a07b319e9cba4601474fbe0761f71~

Edit: using default initializers makes everything a bit more concise: https://github.com/stickies-v/bitcoin/commit/eb316f9c4d13bd1482ac5d0e69fc74b33aef8189 (diff)

dergoegge force-pushed on Nov 1, 2023

dergoegge commented at 3:11 pm on November 1, 2023: member

Thanks @stickies-v went with your suggestion as my previous idea was buggy again🔥

[primitives] Precompute result of CTransaction::HasWitness af1d2ff883

dergoegge force-pushed on Nov 1, 2023

in src/primitives/transaction.h:313 in af1d2ff883

309@@ -310,12 +310,15 @@ class CTransaction
310 
311 private:
312     /** Memory only. */
313+    const bool m_has_witness;

ajtowns commented at 3:25 pm on November 1, 2023:

Not really a fan of adding 8 bytes to every CTransaction, though I guess it’s not horrible?

Another approach would be to separate out the raw data and compute-logic into one class, and the optimised version with the w/txid cached into a separate class. That looks like: https://github.com/ajtowns/bitcoin/commit/89e3c808927984309a002b2cab1c0a622f5c15f8

dergoegge commented at 2:40 pm on November 3, 2023:

Personally, I don’t think the extra bytes matter that much, so I would lean towards leaving this as is.

stickies-v commented at 11:28 am on November 13, 2023:

nit: Using default initializer makes more sense here I think:

 0diff --git a/src/primitives/transaction.cpp b/src/primitives/transaction.cpp
 1index 77a363f7b6..a20cf25f53 100644
 2--- a/src/primitives/transaction.cpp
 3+++ b/src/primitives/transaction.cpp
 4@@ -93,8 +93,10 @@ Wtxid CTransaction::ComputeWitnessHash() const
 5     return Wtxid::FromUint256((CHashWriter{0} << *this).GetHash());
 6 }
 7 
 8-CTransaction::CTransaction(const CMutableTransaction& tx) : vin(tx.vin), vout(tx.vout), nVersion(tx.nVersion), nLockTime(tx.nLockTime), m_has_witness{ComputeHasWitness()}, hash{ComputeHash()}, m_witness_hash{ComputeWitnessHash()} {}
 9-CTransaction::CTransaction(CMutableTransaction&& tx) : vin(std::move(tx.vin)), vout(std::move(tx.vout)), nVersion(tx.nVersion), nLockTime(tx.nLockTime), m_has_witness{ComputeHasWitness()}, hash{ComputeHash()}, m_witness_hash{ComputeWitnessHash()} {}
10+CTransaction::CTransaction(const CMutableTransaction& tx)
11+    : vin(tx.vin), vout(tx.vout), nVersion(tx.nVersion), nLockTime(tx.nLockTime) {}
12+CTransaction::CTransaction(CMutableTransaction&& tx)
13+    : vin(std::move(tx.vin)), vout(std::move(tx.vout)), nVersion(tx.nVersion), nLockTime(tx.nLockTime) {}
14 
15 CAmount CTransaction::GetValueOut() const
16 {
17diff --git a/src/primitives/transaction.h b/src/primitives/transaction.h
18index 594168bbcc..facbd8c769 100644
19--- a/src/primitives/transaction.h
20+++ b/src/primitives/transaction.h
21@@ -310,9 +310,9 @@ public:
22 
23 private:
24     /** Memory only. */
25-    const bool m_has_witness;
26-    const Txid hash;
27-    const Wtxid m_witness_hash;
28+    const bool m_has_witness{ComputeHasWitness()};
29+    const Txid hash{ComputeHash()};
30+    const Wtxid m_witness_hash{ComputeWitnessHash()};
31 
32     Txid ComputeHash() const;
33     Wtxid ComputeWitnessHash() const;

ajtowns commented at 10:54 am on November 15, 2023:

Really, we’re already wasting 16 bytes due to vin and vout supporting capacity() != size() despite both being const and never needing to be resized.

DrahtBot removed the label CI failed on Nov 1, 2023

glozow added the label Refactoring on Nov 2, 2023

theStack commented at 3:33 pm on November 6, 2023: contributor

Concept ACK

theStack commented at 10:37 pm on November 12, 2023: contributor

The code looks correct.

I’m still unsure on how to assess whether the extra memory needed is okay or not, other than “gut feeling”. I would have expected that the increased size of CTransaction (on my system, it’s 128 bytes on the PR vs. 120 bytes on master, a growth of ~6.66%) has a tiny impact on the mempool usage accounting as well, but it seems that it doesn’t, as RecursiveDynamicUsage only cares about a tx’s inputs and outputs fields: https://github.com/bitcoin/bitcoin/blob/8243762700bc6e7876ae5d4fc000500858b99f66/src/core_memusage.h#L32-L41

(A bit off-topic to this PR, but is it really intended to only do dynamic accounting? Just because something doesn’t grow dynamically doesn’t mean it’s completely free, the static parts still have to reside somewhere in memory.)

sipa commented at 11:04 pm on November 12, 2023: member

@theStack The dynamic memory isn’t the only thing that matters, but it’s the only thing you don’t already account for at another level.

If you have a single transaction, and want its memory usage, use sizeof(transaction) + DynamicMemoryUsage(transaction). It’d be convenient to have the transaction sizeof added to that memory usage. However, things would go wrong if you use a collection then.

Say you have a vector of transactions, and want its memory usage. You’d use sizeof(vector) + dynamic memory of the vector (which consists of the memory allocated by the vector, plus the memory allocated by all of the transactions in it). However, the transactions themselves are in the vector’s allocated memory. If they’d be counted alongside their own allocated memory, they’d be counted twice here (and incorrectly, because the overhead of memory allocation only applies once to the entire array, not individually).

theStack commented at 11:47 pm on November 12, 2023: contributor

@sipa: Thanks for clarifying, that makes sense and I see now why it would be a bad idea to add the static part directly in the DynamicMemoryUsage functions. For the specific case of mempool usage accounting, one could add sizeof(CTransaction) at the call-site though? E.g.

 0diff --git a/src/kernel/mempool_entry.h b/src/kernel/mempool_entry.h
 1index 1f175a5ccf..95362fe2d9 100644
 2--- a/src/kernel/mempool_entry.h
 3+++ b/src/kernel/mempool_entry.h
 4@@ -108,7 +108,7 @@ public:
 5         : tx{tx},
 6           nFee{fee},
 7           nTxWeight{GetTransactionWeight(*tx)},
 8-          nUsageSize{RecursiveDynamicUsage(tx)},
 9+          nUsageSize{sizeof(*tx) + RecursiveDynamicUsage(tx)},
10           nTime{time},
11           entry_sequence{entry_sequence},
12           entryHeight{entry_height},

(Not saying it’s really worth it to fiddle around in this area, and I personally wouldn’t feel comfortable to open a PR. I was just very surprised that one could – in theory – bloat up CTransaction and it still goes unnoticed for the mempool usage accounting.)

sipa commented at 1:30 am on November 13, 2023: member

@theStack (deleted my previous comment, I had missed a lot).

RecursiveDynamicUsage for CTransactionRef (which is a std::shared_ptr<CTransaction>) should already account for both the memory allocated in the shared pointer as well as the memory allocated by the transaction. See src/core_memusage.h:

0template<typename X>
1static inline size_t RecursiveDynamicUsage(const std::shared_ptr<X>& p) {
2    return p ? memusage::DynamicUsage(p) + RecursiveDynamicUsage(*p) : 0;
3}

where memusage::DynamicUsage(p) invokes this function from src/memusage.h:

0template<typename X>
1static inline size_t DynamicUsage(const std::shared_ptr<X>& p)
2{
3    // A shared_ptr can either use a single continuous memory block for both
4    // the counter and the storage (when using std::make_shared), or separate.
5    // We can't observe the difference, however, so assume the worst.
6    return p ? MallocUsage(sizeof(X)) + MallocUsage(sizeof(stl_shared_counter)) : 0;
7}

Is it possible that you just don’t see the added field cause changes because either it’s fitting in earlier padding space, or because the rounding up effect of malloc() hides the difference?

theStack commented at 3:02 am on November 13, 2023: contributor

@sipa: Ah, very interesting, have to admit I completely overlooked RecursiveDynamicUsage(const std::shared_ptr<X>& p).

Is it possible that you just don’t see the added field cause changes because either it’s fitting in earlier padding space, or because the rounding up effect of malloc() hides the difference?

Yes, it was the latter. The added field did lead to a size increase of CTransaction (from 120 to 128 bytes), but MallocUsage indeed yields the same value for both of these sizes on a 64-bit machine (namely ((120+31)»4)«4 = ((128+31)»4)«4 = 144). So that’s the reason why I did see the same mempool usage accounting results both on master and the PR on my machine (and wrongly concluded from that that the size of CTransaction is not accounted for). To be sure, I intentionally bloated CTransaction up much more with an const uint8_t dummy[100] = {}; entry and verified that the mempool usage was higher indeed. So, the accounting seems to work as expected and my worries were unjustified.

If anyone wants to run these experiments: what I did was to start bitcoind with an existing mempool.dat in datadir both on master and the PR branch with -nolisten -noconnect (to avoid clogging the mempool with new txs), wait until the mempool loaded, ran bitcoin-cli getmempoolinfo and compared the "usage" result field value (other fields like "size", "bytes" and "total_fee" should always be equal for the same mempool.dat).

ACK af1d2ff88344e1545ac8d9ad09f8e37e264da712

(still based on a gut feeling, but garnished with some napkin math: the mempool on my node is close to it’s maximum of 300MB and has about ~100k entries now; MallocUsage increases in 16-bytes steps on 64-bit machines, so that would in the worst case lead to ~1,6MB more usage, where now “only” ~99.5k entries would fit; I think that’s fine).

DrahtBot requested review from stickies-v on Nov 13, 2023

DrahtBot requested review from glozow on Nov 13, 2023

stickies-v approved

stickies-v commented at 11:49 am on November 13, 2023: contributor

ACK af1d2ff88344e1545ac8d9ad09f8e37e264da712

I think the PR and commit description would benefit from describing that this is not a strict improvement, as we slightly increase memory usage (which I think is an acceptable trade-off).

DrahtBot requested review from stickies-v on Nov 13, 2023

DrahtBot removed review request from stickies-v on Nov 14, 2023

dergoegge commented at 10:43 am on November 21, 2023: member

I think this is rfm. Could a maintainer take a look?

TheCharlatan approved

TheCharlatan commented at 8:18 pm on November 22, 2023: contributor

ACK af1d2ff88344e1545ac8d9ad09f8e37e264da712

Nit: Maybe add a HasWitness check somewhere in the transaction_tests?

mzumsande commented at 8:40 pm on November 22, 2023: contributor

Since it comes with a memory cost, I wonder if the the performance gain we get for it can be measured. Does this speed up any benchmarks / IBD?

dergoegge commented at 10:00 am on November 23, 2023: member

Since it comes with a memory cost, I wonder if the the performance gain we get for it can be measured. Does this speed up any benchmarks / IBD?

It’s less of a gain and more just trying to revert the performance regression I introduced in #28017. I guess you are asking if it is a noticeable regression. I would think both the performance regression and the new memory cost from here are negligible and I can certainly also live with what is in master now.

mzumsande commented at 4:59 pm on November 24, 2023: contributor

I guess you are asking if it is a noticeable regression. I would think both the performance regression and the new memory cost from here are negligible and I can certainly also live with what is in master now.

I think this should be easily benched just with a --reindex-chainstate? I could try that next week if no one else wants to. I just think that if it’s possible within reasonable efforts, this kind of decisions should be made based on empirical data rather than guessing what the performance / memory impacts may be.

dergoegge commented at 5:45 pm on November 24, 2023: member

this kind of decisions should be made based on empirical data rather than guessing what the performance / memory impacts may be.

This makes it sound like this is all up in the air when the trade-off for this PR is well known. All this does is revert to the performance we had pre-#28107 while adding an extra 8 bytes to every CTransaction instance.

The runtime complexity of HasWitness is now O(tx.vin.size()) while it used to be O(1). That could be considered good enough reasoning for this PR even if a IBD/reindex benchmark doesn’t show a noticeable difference. The 4 concept acks and 3 full acks seem to agree on that.

In any case the memory usage of CTransaction could be optimized in a follow-up, even beyond reverting the overhead from this PR (https://github.com/bitcoin/bitcoin/pull/28766#discussion_r1394031188).

Feel free to do the benchmark, but I’m not sure if the result matters much at this point, since we have already spend sufficient review time on this PR.

dergoegge commented at 8:49 pm on November 24, 2023: member

All this does is revert to the performance we had pre-https://github.com/bitcoin/bitcoin/issues/28107 while adding an extra > 8 bytes to every CTransaction instance.

The runtime complexity of HasWitness is now O(tx.vin.size()) while it used to be O(1).

Whoops, this isn’t really true. HasWitness was unchanged by #28107, the only change in this regard was https://github.com/bitcoin/bitcoin/pull/28107/commits/cdb14d79e809bf7d1612b21b554a9fcfb2ab1c91.

This PR improves the performance for all call sites of HasWitness not just the ones in https://github.com/bitcoin/bitcoin/pull/28107/commits/cdb14d79e809bf7d1612b21b554a9fcfb2ab1c91.

achow101 commented at 1:44 pm on November 28, 2023: member

ACK af1d2ff88344e1545ac8d9ad09f8e37e264da712

achow101 merged this on Nov 28, 2023

achow101 closed this on Nov 28, 2023

Improve peformance of CTransaction::HasWitness (28107 follow-up) #28766

Code Coverage

Reviews