replace mapNextTx with slimmer setSpends

kazcw commented at 9:21 pm on May 3, 2016: contributor

mapNextTx entries comprise about 15% of application memory usage once the mempool warms up; most of this space is taken by the key type, which contains a uint256. The same uint256 is accessible from the map’s value type.

setSpends represents the information as a set of CSpendRefs. A CSpendRef is, logically, a reference to a COutPoint; the COutPoint may be either “free” (as in the case of setSpends.find(COutPoint(…))), or in an element of the vin of a CTransaction (as in all the values inserted into setSpend). If the COutPoint is associated with a spending CTransaction, the CSpendRef is also capable of providing access to the corresponding transaction.

[This object bimodality is necessary because lookup on a set requires constructing an object of the set’s key type, an inconvenience corrected in C++14.]

Saves about 10% of total memory usage (an entry in mapNextTx is 48 bytes; an entry in setSpends in 16 bytes). Since the mempool is DynamicUsage-regulated, this will translate to a larger mempool in the same amount of space.

(Supersedes #7991, which addressed the same issue less efficiently)

MarcoFalke added the label Refactoring on May 4, 2016

MarcoFalke added the label Resource usage on May 4, 2016

MarcoFalke added the label Mempool on May 4, 2016

sdaftuar commented at 5:37 pm on May 5, 2016: member

Code review ACK, will test.

dcousens commented at 2:51 am on May 6, 2016: contributor

[This object bimodality is necessary because lookup on a set requires constructing an object of the set’s key type, an inconvenience corrected in C++14.]

I thought we were only at C++11? Or are you suggesting this is something else that would be corrected by moving to C++14?

kazcw commented at 3:36 am on May 6, 2016: contributor

I’m just blaming C++<=11 for my tagged union. When we eventually switch to C++14 there’s a much cleaner solution that doesn’t require putting two things that should be different types in the same class.

in src/txmempool.h: in 26427666fd outdated

344+    constexpr CSpendRef(const COutPoint& outpoint) noexcept : spent(&outpoint), n(0), haveSpender(false) {}
345+    const COutPoint& GetOutPoint() const noexcept {
346+        return haveSpender ? GetInPoint().GetOutPoint() : *spent;
347+    }
348+    constexpr CInPoint GetInPoint() const noexcept {
349+        return haveSpender ? CInPoint{ spender, n } : throw std::logic_error("!haveSpender in CSpendRef::GetInPoint()");

dcousens commented at 4:05 am on May 6, 2016:

noexcept, then a throw

Did I misunderstand the meaning of this qualifier?

kazcw commented at 5:31 am on May 6, 2016:

noexcept guarantees std::terminate occurs if an exception escapes the function; it’s a hard assert that’s allowed inside a constexpr.

dcousens commented at 5:36 am on May 6, 2016:

TIL, thanks @kazcw

sdaftuar commented at 6:41 pm on May 6, 2016: member

ACK. Nice improvement!

dcousens commented at 2:25 am on May 7, 2016: contributor

utACK 2642766

sipa commented at 7:33 pm on May 9, 2016: member

Concept ACK

kazcw commented at 10:32 pm on May 9, 2016: contributor

I just realized that no users of mapNextTx need to know which CTxIn of a transaction spends a particular prevout. This makes a map-based approach possible with the same memory usage as this set implementation. I’m going to replace this with the map implementation because it’s definitely cleaner that way (doesn’t require the CSpendRef trick, and a map better reflects the function of the data structure).

kazcw force-pushed on May 9, 2016

in src/indirectmap.h: in 507437a0f0 outdated

23+    typedef typename base::iterator iterator;
24+    typedef typename base::const_iterator const_iterator;
25+    typedef typename base::size_type size_type;
26+
27+    // passthrough (pointer interface)
28+    T& operator[](const K* key) { return m[key]; }

TheBlueMatt commented at 7:29 pm on May 15, 2016:

Feel like this might lead to errors at some point? I’d kinda prefer if you only do this for insert().

sipa commented at 9:15 pm on May 16, 2016:

I guess it’s the correct thing to do if you want to mimic the std::map interface as good as possible, but operator[] automatically constructing elements is annoying…

TheBlueMatt commented at 7:50 pm on May 15, 2016: member

ACK 507437a0f067dd696c1fe9698f4ad60a3801ce3f +/- removing [] and forcing insertion through insert(). It’d also be nice to get a test for indirectmap, or at least the following, if you’re feeling lazy:

 0diff --git a/src/txmempool.cpp b/src/txmempool.cpp
 1index 2f867c8..42c3da4 100644
 2--- a/src/txmempool.cpp
 3+++ b/src/txmempool.cpp
 4@@ -673,6 +673,7 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
 5             // Check whether its inputs are marked in mapNextTx.
 6             auto it3 = mapNextTx.find(txin.prevout);
 7             assert(it3 != mapNextTx.end());
 8+            assert(it3->first == &txin.prevout);
 9             assert(it3->second == &tx);
10             i++;
11         }

kazcw commented at 9:38 pm on May 16, 2016: contributor

The find-and-maybe-insert operator does seem especially squirrelly in this case. Added a squashme with insert(...) instead; added the assertion.

sipa commented at 10:34 pm on May 16, 2016: member

utACK f379416127f0832ba4aa73c1af874df79b58124c

TheBlueMatt commented at 5:05 am on May 17, 2016: member

Seems you forgot to add the assertion?

kazcw commented at 5:22 am on May 17, 2016: contributor

Oops, I hadn’t saved the changes to the file yet

kazcw force-pushed on May 17, 2016

TheBlueMatt commented at 5:26 pm on May 17, 2016: member

re-ACK 64949c7f9c7d47df170fa3814bb5aa89235c8e74

sipa commented at 3:25 pm on June 2, 2016: member

Can you squash?

mapNextTx: use pointer as key, simplify value

Saves about 10% of application memory usage once the mempool warms up. Since the
mempool is DynamicUsage-regulated, this will translate to a larger mempool in
the same amount of space.

Map value type: eliminate the vin index; no users of the map need to know which
input of the transaction is spending the prevout.

Map key type: replace the COutPoint with a pointer to a COutPoint. A COutPoint
is 36 bytes, but each COutPoint is accessible from the same map entry's value.
A trivial DereferencingComparator functor allows indirect map keys, but the
resulting syntax is misleading: `map.find(&outpoint)`. Implement an indirectmap
that acts as a wrapper to a map that uses a DereferencingComparator, supporting
a syntax that accurately reflect the container's semantics: inserts and
iterators use pointers since they store pointers and need them to remain
constant and dereferenceable, but lookup functions take const references.

9805f4af7e

kazcw force-pushed on Jun 2, 2016

kazcw commented at 7:34 pm on June 2, 2016: contributor

Squashed all my commits from 64949c7 -> 9805f4a

sipa commented at 11:18 pm on June 2, 2016: member

utACK 9805f4af7ecb6becf8a146bd845fb131ffa625c9, but well-tested by the CTxMemPool::check function.

sipa merged this on Jun 2, 2016

sipa closed this on Jun 2, 2016

sipa referenced this in commit a82f03393a on Jun 2, 2016

codablock referenced this in commit 0768578a9a on Sep 16, 2017

codablock referenced this in commit 804e383689 on Sep 19, 2017

codablock referenced this in commit fb88e9b607 on Dec 22, 2017

andvgal referenced this in commit 7896756e81 on Jan 6, 2019

wqking referenced this in commit 3a7c81307e on Dec 13, 2019

furszy referenced this in commit 1f010c0969 on Jan 23, 2021

MarcoFalke locked this on Sep 8, 2021

replace mapNextTx with slimmer setSpends #7997