Skip to content

Commit 9805f4a

Browse files
kazcwkazcw
committed
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.
1 parent 03cf6e8 commit 9805f4a

File tree

6 files changed

+96
-41
lines changed

6 files changed

+96
-41
lines changed

‎src/Makefile.am‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -94,6 +94,7 @@ BITCOIN_CORE_H = \
9494
core_memusage.h \
9595
httprpc.h \
9696
httpserver.h \
97+
indirectmap.h \
9798
init.h \
9899
key.h \
99100
keystore.h \

‎src/indirectmap.h‎

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
#ifndef BITCOIN_INDIRECTMAP_H
2+
#define BITCOIN_INDIRECTMAP_H
3+
4+
template <class T>
5+
struct DereferencingComparator { bool operator()(const T a, const T b) const { return *a < *b; } };
6+
7+
/* Map whose keys are pointers, but are compared by their dereferenced values.
8+
*
9+
* Differs from a plain std::map<const K*, T, DereferencingComparator<K*> > in
10+
* that methods that take a key for comparison take a K rather than taking a K*
11+
* (taking a K* would be confusing, since it's the value rather than the address
12+
* of the object for comparison that matters due to the dereferencing comparator).
13+
*
14+
* Objects pointed to by keys must not be modified in any way that changes the
15+
* result of DereferencingComparator.
16+
*/
17+
template <class K, class T>
18+
class indirectmap {
19+
private:
20+
typedef std::map<const K*, T, DereferencingComparator<const K*> > base;
21+
base m;
22+
public:
23+
typedef typename base::iterator iterator;
24+
typedef typename base::const_iterator const_iterator;
25+
typedef typename base::size_type size_type;
26+
typedef typename base::value_type value_type;
27+
28+
// passthrough (pointer interface)
29+
std::pair<iterator, bool> insert(const value_type& value) { return m.insert(value); }
30+
31+
// pass address (value interface)
32+
iterator find(const K& key) { return m.find(&key); }
33+
const_iterator find(const K& key) const { return m.find(&key); }
34+
iterator lower_bound(const K& key) { return m.lower_bound(&key); }
35+
const_iterator lower_bound(const K& key) const { return m.lower_bound(&key); }
36+
size_type erase(const K& key) { return m.erase(&key); }
37+
size_type count(const K& key) const { return m.count(&key); }
38+
39+
// passthrough
40+
bool empty() const { return m.empty(); }
41+
size_type size() const { return m.size(); }
42+
size_type max_size() const { return m.max_size(); }
43+
void clear() { m.clear(); }
44+
iterator begin() { return m.begin(); }
45+
iterator end() { return m.end(); }
46+
const_iterator begin() const { return m.begin(); }
47+
const_iterator end() const { return m.end(); }
48+
const_iterator cbegin() const { return m.cbegin(); }
49+
const_iterator cend() const { return m.cend(); }
50+
};
51+
52+
#endif // BITCOIN_INDIRECTMAP_H

‎src/main.cpp‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1049,9 +1049,10 @@ bool AcceptToMemoryPoolWorker(CTxMemPool& pool, CValidationState& state, const C
10491049
LOCK(pool.cs); // protect pool.mapNextTx
10501050
BOOST_FOREACH(const CTxIn &txin, tx.vin)
10511051
{
1052-
if (pool.mapNextTx.count(txin.prevout))
1052+
auto itConflicting = pool.mapNextTx.find(txin.prevout);
1053+
if (itConflicting != pool.mapNextTx.end())
10531054
{
1054-
const CTransaction *ptxConflicting = pool.mapNextTx[txin.prevout].ptx;
1055+
const CTransaction *ptxConflicting = itConflicting->second;
10551056
if (!setConflicts.count(ptxConflicting->GetHash()))
10561057
{
10571058
// Allow opt-out of transaction replacement by setting

‎src/memusage.h‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,8 @@
55
#ifndef BITCOIN_MEMUSAGE_H
66
#define BITCOIN_MEMUSAGE_H
77

8+
#include "indirectmap.h"
9+
810
#include <stdlib.h>
911

1012
#include <map>
@@ -106,6 +108,20 @@ static inline size_t IncrementalDynamicUsage(const std::map<X, Y, Z>& m)
106108
return MallocUsage(sizeof(stl_tree_node<std::pair<const X, Y> >));
107109
}
108110

111+
// indirectmap has underlying map with pointer as key
112+
113+
template<typename X, typename Y>
114+
static inline size_t DynamicUsage(const indirectmap<X, Y>& m)
115+
{
116+
return MallocUsage(sizeof(stl_tree_node<std::pair<const X*, Y> >)) * m.size();
117+
}
118+
119+
template<typename X, typename Y>
120+
static inline size_t IncrementalDynamicUsage(const indirectmap<X, Y>& m)
121+
{
122+
return MallocUsage(sizeof(stl_tree_node<std::pair<const X*, Y> >));
123+
}
124+
109125
// Boost data structures
110126

111127
template<typename X>

‎src/txmempool.cpp‎

Lines changed: 22 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -147,11 +147,11 @@ void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashes
147147
if (it == mapTx.end()) {
148148
continue;
149149
}
150-
std::map<COutPoint, CInPoint>::iterator iter = mapNextTx.lower_bound(COutPoint(hash, 0));
150+
auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
151151
// First calculate the children, and update setMemPoolChildren to
152152
// include them, and update their setMemPoolParents to include this tx.
153-
for (; iter != mapNextTx.end() && iter->first.hash == hash; ++iter) {
154-
const uint256 &childHash = iter->second.ptx->GetHash();
153+
for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
154+
const uint256 &childHash = iter->second->GetHash();
155155
txiter childIter = mapTx.find(childHash);
156156
assert(childIter != mapTx.end());
157157
// We can skip updating entries we've encountered before or that
@@ -365,11 +365,11 @@ void CTxMemPool::pruneSpent(const uint256 &hashTx, CCoins &coins)
365365
{
366366
LOCK(cs);
367367

368-
std::map<COutPoint, CInPoint>::iterator it = mapNextTx.lower_bound(COutPoint(hashTx, 0));
368+
auto it = mapNextTx.lower_bound(COutPoint(hashTx, 0));
369369

370370
// iterate over all COutPoints in mapNextTx whose hash equals the provided hashTx
371-
while (it != mapNextTx.end() && it->first.hash == hashTx) {
372-
coins.Spend(it->first.n); // and remove those outputs from coins
371+
while (it != mapNextTx.end() && it->first->hash == hashTx) {
372+
coins.Spend(it->first->n); // and remove those outputs from coins
373373
it++;
374374
}
375375
}
@@ -414,7 +414,7 @@ bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry,
414414
const CTransaction& tx = newit->GetTx();
415415
std::set<uint256> setParentTransactions;
416416
for (unsigned int i = 0; i < tx.vin.size(); i++) {
417-
mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
417+
mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, &tx));
418418
setParentTransactions.insert(tx.vin[i].prevout.hash);
419419
}
420420
// Don't bother worrying about child transactions of this one.
@@ -500,10 +500,10 @@ void CTxMemPool::removeRecursive(const CTransaction &origTx, std::list<CTransact
500500
// happen during chain re-orgs if origTx isn't re-accepted into
501501
// the mempool for any reason.
502502
for (unsigned int i = 0; i < origTx.vout.size(); i++) {
503-
std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
503+
auto it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
504504
if (it == mapNextTx.end())
505505
continue;
506-
txiter nextit = mapTx.find(it->second.ptx->GetHash());
506+
txiter nextit = mapTx.find(it->second->GetHash());
507507
assert(nextit != mapTx.end());
508508
txToRemove.insert(nextit);
509509
}
@@ -561,9 +561,9 @@ void CTxMemPool::removeConflicts(const CTransaction &tx, std::list<CTransaction>
561561
list<CTransaction> result;
562562
LOCK(cs);
563563
BOOST_FOREACH(const CTxIn &txin, tx.vin) {
564-
std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(txin.prevout);
564+
auto it = mapNextTx.find(txin.prevout);
565565
if (it != mapNextTx.end()) {
566-
const CTransaction &txConflict = *it->second.ptx;
566+
const CTransaction &txConflict = *it->second;
567567
if (txConflict != tx)
568568
{
569569
removeRecursive(txConflict, removed);
@@ -671,10 +671,10 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
671671
assert(coins && coins->IsAvailable(txin.prevout.n));
672672
}
673673
// Check whether its inputs are marked in mapNextTx.
674-
std::map<COutPoint, CInPoint>::const_iterator it3 = mapNextTx.find(txin.prevout);
674+
auto it3 = mapNextTx.find(txin.prevout);
675675
assert(it3 != mapNextTx.end());
676-
assert(it3->second.ptx == &tx);
677-
assert(it3->second.n == i);
676+
assert(it3->first == &txin.prevout);
677+
assert(it3->second == &tx);
678678
i++;
679679
}
680680
assert(setParentCheck == GetMemPoolParents(it));
@@ -701,10 +701,10 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
701701

702702
// Check children against mapNextTx
703703
CTxMemPool::setEntries setChildrenCheck;
704-
std::map<COutPoint, CInPoint>::const_iterator iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
704+
auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
705705
int64_t childSizes = 0;
706-
for (; iter != mapNextTx.end() && iter->first.hash == it->GetTx().GetHash(); ++iter) {
707-
txiter childit = mapTx.find(iter->second.ptx->GetHash());
706+
for (; iter != mapNextTx.end() && iter->first->hash == it->GetTx().GetHash(); ++iter) {
707+
txiter childit = mapTx.find(iter->second->GetHash());
708708
assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
709709
if (setChildrenCheck.insert(childit).second) {
710710
childSizes += childit->GetTxSize();
@@ -738,14 +738,12 @@ void CTxMemPool::check(const CCoinsViewCache *pcoins) const
738738
stepsSinceLastRemove = 0;
739739
}
740740
}
741-
for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) {
742-
uint256 hash = it->second.ptx->GetHash();
741+
for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
742+
uint256 hash = it->second->GetHash();
743743
indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
744744
const CTransaction& tx = it2->GetTx();
745745
assert(it2 != mapTx.end());
746-
assert(&tx == it->second.ptx);
747-
assert(tx.vin.size() > it->second.n);
748-
assert(it->first == it->second.ptx->vin[it->second.n].prevout);
746+
assert(&tx == it->second);
749747
}
750748

751749
assert(totalTxSize == checkTotal);
@@ -1044,8 +1042,8 @@ void CTxMemPool::TrimToSize(size_t sizelimit, std::vector<uint256>* pvNoSpendsRe
10441042
BOOST_FOREACH(const CTxIn& txin, tx.vin) {
10451043
if (exists(txin.prevout.hash))
10461044
continue;
1047-
std::map<COutPoint, CInPoint>::iterator it = mapNextTx.lower_bound(COutPoint(txin.prevout.hash, 0));
1048-
if (it == mapNextTx.end() || it->first.hash != txin.prevout.hash)
1045+
auto it = mapNextTx.lower_bound(COutPoint(txin.prevout.hash, 0));
1046+
if (it == mapNextTx.end() || it->first->hash != txin.prevout.hash)
10491047
pvNoSpendsRemaining->push_back(txin.prevout.hash);
10501048
}
10511049
}

‎src/txmempool.h‎

Lines changed: 2 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -11,6 +11,7 @@
1111

1212
#include "amount.h"
1313
#include "coins.h"
14+
#include "indirectmap.h"
1415
#include "primitives/transaction.h"
1516
#include "sync.h"
1617

@@ -305,20 +306,6 @@ struct ancestor_score {};
305306

306307
class CBlockPolicyEstimator;
307308

308-
/** An inpoint - a combination of a transaction and an index n into its vin */
309-
class CInPoint
310-
{
311-
public:
312-
const CTransaction* ptx;
313-
uint32_t n;
314-
315-
CInPoint() { SetNull(); }
316-
CInPoint(const CTransaction* ptxIn, uint32_t nIn) { ptx = ptxIn; n = nIn; }
317-
void SetNull() { ptx = NULL; n = (uint32_t) -1; }
318-
bool IsNull() const { return (ptx == NULL && n == (uint32_t) -1); }
319-
size_t DynamicMemoryUsage() const { return 0; }
320-
};
321-
322309
/**
323310
* CTxMemPool stores valid-according-to-the-current-best-chain
324311
* transactions that may be included in the next block.
@@ -477,7 +464,7 @@ class CTxMemPool
477464
void UpdateChild(txiter entry, txiter child, bool add);
478465

479466
public:
480-
std::map<COutPoint, CInPoint> mapNextTx;
467+
indirectmap<COutPoint, const CTransaction*> mapNextTx;
481468
std::map<uint256, std::pair<double, CAmount> > mapDeltas;
482469

483470
/** Create a new CTxMemPool.

0 commit comments

Comments
 (0)