Skip to content

Commit 7624823

Browse files
furszyfurszy
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. Coming from btc@9805f4af7ecb6becf8a146bd845fb131ffa625c9
1 parent 191c62e commit 7624823

File tree

6 files changed

+95
-43
lines changed

6 files changed

+95
-43
lines changed

‎CMakeLists.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -193,6 +193,7 @@ set(SERVER_SOURCES
193193
./src/checkpoints.cpp
194194
./src/httprpc.cpp
195195
./src/httpserver.cpp
196+
./src/indirectmap.h
196197
./src/init.cpp
197198
./src/interfaces/handler.cpp
198199
./src/interfaces/wallet.cpp

‎src/Makefile.am‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -189,6 +189,7 @@ BITCOIN_CORE_H = \
189189
hash.h \
190190
httprpc.h \
191191
httpserver.h \
192+
indirectmap.h \
192193
init.h \
193194
interfaces/handler.h \
194195
interfaces/wallet.h \

‎src/indirectmap.h‎

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

‎src/memusage.h‎

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

8+
#include "indirectmap.h"
89
#include "prevector.h"
910

1011
#include <stdlib.h>
@@ -185,6 +186,20 @@ static inline size_t DynamicUsage(const std::shared_ptr<X>& p)
185186
return p ? MallocUsage(sizeof(X)) + MallocUsage(sizeof(stl_shared_counter)) : 0;
186187
}
187188

189+
// indirectmap has underlying map with pointer as key
190+
191+
template<typename X, typename Y>
192+
static inline size_t DynamicUsage(const indirectmap<X, Y>& m)
193+
{
194+
return MallocUsage(sizeof(stl_tree_node<std::pair<const X*, Y> >)) * m.size();
195+
}
196+
197+
template<typename X, typename Y>
198+
static inline size_t IncrementalDynamicUsage(const indirectmap<X, Y>& m)
199+
{
200+
return MallocUsage(sizeof(stl_tree_node<std::pair<const X*, Y> >));
201+
}
202+
188203
// Boost data structures
189204

190205
template<typename X>

‎src/txmempool.cpp‎

Lines changed: 18 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -142,11 +142,11 @@ void CTxMemPool::UpdateTransactionsFromBlock(const std::vector<uint256> &vHashes
142142
if (it == mapTx.end()) {
143143
continue;
144144
}
145-
std::map<COutPoint, CInPoint>::iterator iter = mapNextTx.lower_bound(COutPoint(hash, 0));
145+
auto iter = mapNextTx.lower_bound(COutPoint(hash, 0));
146146
// First calculate the children, and update setMemPoolChildren to
147147
// include them, and update their setMemPoolParents to include this tx.
148-
for (; iter != mapNextTx.end() && iter->first.hash == hash; ++iter) {
149-
const uint256 &childHash = iter->second.ptx->GetHash();
148+
for (; iter != mapNextTx.end() && iter->first->hash == hash; ++iter) {
149+
const uint256 &childHash = iter->second->GetHash();
150150
txiter childIter = mapTx.find(childHash);
151151
assert(childIter != mapTx.end());
152152
// We can skip updating entries we've encountered before or that
@@ -404,7 +404,7 @@ bool CTxMemPool::addUnchecked(const uint256& hash, const CTxMemPoolEntry &entry,
404404
std::set<uint256> setParentTransactions;
405405
if(!tx.HasZerocoinSpendInputs()) {
406406
for (unsigned int i = 0; i < tx.vin.size(); i++) {
407-
mapNextTx[tx.vin[i].prevout] = CInPoint(&tx, i);
407+
mapNextTx.insert(std::make_pair(&tx.vin[i].prevout, newit->GetSharedTx()));
408408
setParentTransactions.insert(tx.vin[i].prevout.hash);
409409
}
410410
}
@@ -504,10 +504,10 @@ void CTxMemPool::removeRecursive(const CTransaction& origTx, std::list<CTransact
504504
// happen during chain re-orgs if origTx isn't re-accepted into
505505
// the mempool for any reason.
506506
for (unsigned int i = 0; i < origTx.vout.size(); i++) {
507-
std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
507+
auto it = mapNextTx.find(COutPoint(origTx.GetHash(), i));
508508
if (it == mapNextTx.end())
509509
continue;
510-
txiter nextit = mapTx.find(it->second.ptx->GetHash());
510+
txiter nextit = mapTx.find(it->second->GetHash());
511511
assert(nextit != mapTx.end());
512512
txToRemove.insert(nextit);
513513
}
@@ -584,9 +584,9 @@ void CTxMemPool::removeConflicts(const CTransaction& tx, std::list<CTransactionR
584584
std::list<CTransaction> result;
585585
LOCK(cs);
586586
for (const CTxIn& txin : tx.vin) {
587-
std::map<COutPoint, CInPoint>::iterator it = mapNextTx.find(txin.prevout);
587+
auto it = mapNextTx.find(txin.prevout);
588588
if (it != mapNextTx.end()) {
589-
const CTransaction& txConflict = *it->second.ptx;
589+
const CTransaction& txConflict = *it->second;
590590
if (txConflict != tx) {
591591
removeRecursive(txConflict, removed);
592592
}
@@ -704,10 +704,10 @@ void CTxMemPool::check(const CCoinsViewCache* pcoins) const
704704
}
705705
// Check whether its inputs are marked in mapNextTx.
706706
if(!fHasZerocoinSpends) {
707-
std::map<COutPoint, CInPoint>::const_iterator it3 = mapNextTx.find(txin.prevout);
707+
auto it3 = mapNextTx.find(txin.prevout);
708708
assert(it3 != mapNextTx.end());
709-
assert(it3->second.ptx == &tx);
710-
assert(it3->second.n == i);
709+
assert(it3->first == &txin.prevout);
710+
assert(*it3->second == tx);
711711
} else {
712712
fDependsWait=false;
713713
}
@@ -746,10 +746,10 @@ void CTxMemPool::check(const CCoinsViewCache* pcoins) const
746746
// Check children against mapNextTx
747747
if (!fHasZerocoinSpends) {
748748
CTxMemPool::setEntries setChildrenCheck;
749-
std::map<COutPoint, CInPoint>::const_iterator iter = mapNextTx.lower_bound(COutPoint(tx.GetHash(), 0));
749+
auto iter = mapNextTx.lower_bound(COutPoint(it->GetTx().GetHash(), 0));
750750
int64_t childSizes = 0;
751-
for (; iter != mapNextTx.end() && iter->first.hash == tx.GetHash(); ++iter) {
752-
txiter childit = mapTx.find(iter->second.ptx->GetHash());
751+
for (; iter != mapNextTx.end() && iter->first->hash == tx.GetHash(); ++iter) {
752+
txiter childit = mapTx.find(iter->second->GetHash());
753753
assert(childit != mapTx.end()); // mapNextTx points to in-mempool transactions
754754
if (setChildrenCheck.insert(childit).second) {
755755
childSizes += childit->GetTxSize();
@@ -787,14 +787,12 @@ void CTxMemPool::check(const CCoinsViewCache* pcoins) const
787787
stepsSinceLastRemove = 0;
788788
}
789789
}
790-
for (std::map<COutPoint, CInPoint>::const_iterator it = mapNextTx.begin(); it != mapNextTx.end(); it++) {
791-
const uint256& hash = it->second.ptx->GetHash();
790+
for (auto it = mapNextTx.cbegin(); it != mapNextTx.cend(); it++) {
791+
const uint256& hash = it->second->GetHash();
792792
indexed_transaction_set::const_iterator it2 = mapTx.find(hash);
793-
const CTransaction& tx = it2->GetTx();
793+
const CTransactionRef& tx = it2->GetSharedTx();
794794
assert(it2 != mapTx.end());
795-
assert(&tx == it->second.ptx);
796-
assert(tx.vin.size() > it->second.n);
797-
assert(it->first == it->second.ptx->vin[it->second.n].prevout);
795+
assert(tx == it->second);
798796
}
799797

800798
// Consistency check for sapling nullifiers

‎src/txmempool.h‎

Lines changed: 2 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@
1313

1414
#include "amount.h"
1515
#include "coins.h"
16+
#include "indirectmap.h"
1617
#include "policy/feerate.h"
1718
#include "primitives/transaction.h"
1819
#include "sync.h"
@@ -285,28 +286,6 @@ struct ancestor_score {};
285286

286287
class CBlockPolicyEstimator;
287288

288-
/** An inpoint - a combination of a transaction and an index n into its vin */
289-
class CInPoint
290-
{
291-
public:
292-
const CTransaction* ptx;
293-
uint32_t n;
294-
295-
CInPoint() { SetNull(); }
296-
CInPoint(const CTransaction* ptxIn, uint32_t nIn)
297-
{
298-
ptx = ptxIn;
299-
n = nIn;
300-
}
301-
void SetNull()
302-
{
303-
ptx = NULL;
304-
n = (uint32_t)-1;
305-
}
306-
bool IsNull() const { return (ptx == NULL && n == (uint32_t)-1); }
307-
size_t DynamicMemoryUsage() const { return 0; }
308-
};
309-
310289
/**
311290
* CTxMemPool stores valid-according-to-the-current-best-chain
312291
* transactions that may be included in the next block.
@@ -498,7 +477,7 @@ class CTxMemPool
498477
void UpdateChild(txiter entry, txiter child, bool add);
499478

500479
public:
501-
std::map<COutPoint, CInPoint> mapNextTx;
480+
indirectmap<COutPoint, CTransactionRef> mapNextTx;
502481
std::map<uint256, std::pair<double, CAmount> > mapDeltas;
503482

504483
/** Create a new CTxMemPool.

0 commit comments

Comments
 (0)