diff options
author | Wladimir J. van der Laan <laanwj@gmail.com> | 2018-01-15 15:36:25 +0100 |
---|---|---|
committer | Wladimir J. van der Laan <laanwj@gmail.com> | 2018-01-15 15:36:35 +0100 |
commit | 44080a90a29292df96e92f22242785c5040000a1 (patch) | |
tree | 696d8675a32395ac11c97a9cc66c24cbc81633a2 /src | |
parent | 4db16ec82793beb941a7db2750e774246d7fbc21 (diff) | |
parent | 0a22a52918ad5af6d105b4f5ae9dd6c52199f0e8 (diff) | |
download | bitcoin-44080a90a29292df96e92f22242785c5040000a1.tar.xz |
Merge #12118: Sort mempool by min(feerate, ancestor_feerate)
0a22a52 Use mempool's ancestor sort in transaction selection (Suhas Daftuar)
7abfa53 Add test for new ancestor feerate sort behavior (Suhas Daftuar)
9a51319 Sort mempool by min(feerate, ancestor_feerate) (Suhas Daftuar)
6773f92 Refactor CompareTxMemPoolEntryByDescendantScore (Suhas Daftuar)
Pull request description:
This more closely approximates the desirability of a given transaction for
mining, and should result in less re-sorting when transactions get removed from
the mempool after being mined.
I measured this as approximately a 5% speedup in removeForBlock.
Tree-SHA512: ffa36b567c5dfe3e8908c545a459b6a5ec0de26e7dc81b1050dd235cac9046564b4409a3f8c5ba97bd8b30526e8fec8f78480a912e317979467f32305c3dd37b
Diffstat (limited to 'src')
-rw-r--r-- | src/miner.cpp | 2 | ||||
-rw-r--r-- | src/miner.h | 23 | ||||
-rw-r--r-- | src/test/mempool_tests.cpp | 17 | ||||
-rw-r--r-- | src/txmempool.h | 66 |
4 files changed, 71 insertions, 37 deletions
diff --git a/src/miner.cpp b/src/miner.cpp index 4e63ab4df0..dda52790c6 100644 --- a/src/miner.cpp +++ b/src/miner.cpp @@ -352,7 +352,7 @@ void BlockAssembler::addPackageTxs(int &nPackagesSelected, int &nDescendantsUpda // Try to compare the mapTx entry to the mapModifiedTx entry iter = mempool.mapTx.project<0>(mi); if (modit != mapModifiedTx.get<ancestor_score>().end() && - CompareModifiedEntry()(*modit, CTxMemPoolModifiedEntry(iter))) { + CompareTxMemPoolEntryByAncestorFee()(*modit, CTxMemPoolModifiedEntry(iter))) { // The best entry in mapModifiedTx has higher score // than the one from mapTx. // Switch which transaction (package) to consider diff --git a/src/miner.h b/src/miner.h index 698b4a4788..9c086332d4 100644 --- a/src/miner.h +++ b/src/miner.h @@ -41,6 +41,12 @@ struct CTxMemPoolModifiedEntry { nSigOpCostWithAncestors = entry->GetSigOpCostWithAncestors(); } + int64_t GetModifiedFee() const { return iter->GetModifiedFee(); } + uint64_t GetSizeWithAncestors() const { return nSizeWithAncestors; } + CAmount GetModFeesWithAncestors() const { return nModFeesWithAncestors; } + size_t GetTxSize() const { return iter->GetTxSize(); } + const CTransaction& GetTx() const { return iter->GetTx(); } + CTxMemPool::txiter iter; uint64_t nSizeWithAncestors; CAmount nModFeesWithAncestors; @@ -67,21 +73,6 @@ struct modifiedentry_iter { } }; -// This matches the calculation in CompareTxMemPoolEntryByAncestorFee, -// except operating on CTxMemPoolModifiedEntry. -// TODO: refactor to avoid duplication of this logic. -struct CompareModifiedEntry { - bool operator()(const CTxMemPoolModifiedEntry &a, const CTxMemPoolModifiedEntry &b) const - { - double f1 = (double)a.nModFeesWithAncestors * b.nSizeWithAncestors; - double f2 = (double)b.nModFeesWithAncestors * a.nSizeWithAncestors; - if (f1 == f2) { - return CTxMemPool::CompareIteratorByHash()(a.iter, b.iter); - } - return f1 > f2; - } -}; - // A comparator that sorts transactions based on number of ancestors. // This is sufficient to sort an ancestor package in an order that is valid // to appear in a block. @@ -106,7 +97,7 @@ typedef boost::multi_index_container< // Reuse same tag from CTxMemPool's similar index boost::multi_index::tag<ancestor_score>, boost::multi_index::identity<CTxMemPoolModifiedEntry>, - CompareModifiedEntry + CompareTxMemPoolEntryByAncestorFee > > > indexed_modified_transaction_set; diff --git a/src/test/mempool_tests.cpp b/src/test/mempool_tests.cpp index e5afeddf26..1766c6a093 100644 --- a/src/test/mempool_tests.cpp +++ b/src/test/mempool_tests.cpp @@ -398,6 +398,23 @@ BOOST_AUTO_TEST_CASE(MempoolAncestorIndexingTest) sortedOrder.erase(sortedOrder.end()-2); sortedOrder.insert(sortedOrder.begin(), tx7.GetHash().ToString()); CheckSort<ancestor_score>(pool, sortedOrder); + + // High-fee parent, low-fee child + // tx7 -> tx8 + CMutableTransaction tx8 = CMutableTransaction(); + tx8.vin.resize(1); + tx8.vin[0].prevout = COutPoint(tx7.GetHash(), 0); + tx8.vin[0].scriptSig = CScript() << OP_11; + tx8.vout.resize(1); + tx8.vout[0].scriptPubKey = CScript() << OP_11 << OP_EQUAL; + tx8.vout[0].nValue = 10*COIN; + + // Check that we sort by min(feerate, ancestor_feerate): + // set the fee so that the ancestor feerate is above tx1/5, + // but the transaction's own feerate is lower + pool.addUnchecked(tx8.GetHash(), entry.Fee(5000LL).FromTx(tx8)); + sortedOrder.insert(sortedOrder.end()-1, tx8.GetHash().ToString()); + CheckSort<ancestor_score>(pool, sortedOrder); } diff --git a/src/txmempool.h b/src/txmempool.h index ad0249c9a2..d6f8e7094b 100644 --- a/src/txmempool.h +++ b/src/txmempool.h @@ -206,18 +206,14 @@ class CompareTxMemPoolEntryByDescendantScore public: bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const { - bool fUseADescendants = UseDescendantScore(a); - bool fUseBDescendants = UseDescendantScore(b); + double a_mod_fee, a_size, b_mod_fee, b_size; - double aModFee = fUseADescendants ? a.GetModFeesWithDescendants() : a.GetModifiedFee(); - double aSize = fUseADescendants ? a.GetSizeWithDescendants() : a.GetTxSize(); - - double bModFee = fUseBDescendants ? b.GetModFeesWithDescendants() : b.GetModifiedFee(); - double bSize = fUseBDescendants ? b.GetSizeWithDescendants() : b.GetTxSize(); + GetModFeeAndSize(a, a_mod_fee, a_size); + GetModFeeAndSize(b, b_mod_fee, b_size); // Avoid division by rewriting (a/b > c/d) as (a*d > c*b). - double f1 = aModFee * bSize; - double f2 = aSize * bModFee; + double f1 = a_mod_fee * b_size; + double f2 = a_size * b_mod_fee; if (f1 == f2) { return a.GetTime() >= b.GetTime(); @@ -225,12 +221,21 @@ public: return f1 < f2; } - // Calculate which score to use for an entry (avoiding division). - bool UseDescendantScore(const CTxMemPoolEntry &a) const + // Return the fee/size we're using for sorting this entry. + void GetModFeeAndSize(const CTxMemPoolEntry &a, double &mod_fee, double &size) const { + // Compare feerate with descendants to feerate of the transaction, and + // return the fee/size for the max. double f1 = (double)a.GetModifiedFee() * a.GetSizeWithDescendants(); double f2 = (double)a.GetModFeesWithDescendants() * a.GetTxSize(); - return f2 > f1; + + if (f2 > f1) { + mod_fee = a.GetModFeesWithDescendants(); + size = a.GetSizeWithDescendants(); + } else { + mod_fee = a.GetModifiedFee(); + size = a.GetTxSize(); + } } }; @@ -261,27 +266,48 @@ public: } }; +/** \class CompareTxMemPoolEntryByAncestorScore + * + * Sort an entry by min(score/size of entry's tx, score/size with all ancestors). + */ class CompareTxMemPoolEntryByAncestorFee { public: - bool operator()(const CTxMemPoolEntry& a, const CTxMemPoolEntry& b) const + template<typename T> + bool operator()(const T& a, const T& b) const { - double aFees = a.GetModFeesWithAncestors(); - double aSize = a.GetSizeWithAncestors(); + double a_mod_fee, a_size, b_mod_fee, b_size; - double bFees = b.GetModFeesWithAncestors(); - double bSize = b.GetSizeWithAncestors(); + GetModFeeAndSize(a, a_mod_fee, a_size); + GetModFeeAndSize(b, b_mod_fee, b_size); // Avoid division by rewriting (a/b > c/d) as (a*d > c*b). - double f1 = aFees * bSize; - double f2 = aSize * bFees; + double f1 = a_mod_fee * b_size; + double f2 = a_size * b_mod_fee; if (f1 == f2) { return a.GetTx().GetHash() < b.GetTx().GetHash(); } - return f1 > f2; } + + // Return the fee/size we're using for sorting this entry. + template <typename T> + void GetModFeeAndSize(const T &a, double &mod_fee, double &size) const + { + // Compare feerate with ancestors to feerate of the transaction, and + // return the fee/size for the min. + double f1 = (double)a.GetModifiedFee() * a.GetSizeWithAncestors(); + double f2 = (double)a.GetModFeesWithAncestors() * a.GetTxSize(); + + if (f1 > f2) { + mod_fee = a.GetModFeesWithAncestors(); + size = a.GetSizeWithAncestors(); + } else { + mod_fee = a.GetModifiedFee(); + size = a.GetTxSize(); + } + } }; // Multi_index tag names |