Merge bitcoin/bitcoin#28385: [refactor] rewrite DisconnectedBlockTransactions to not use boost

4313c77400eb8eaa8586db39a7e29a861772ea80 make DisconnectedBlockTransactions responsible for its own memory management (glozow)
cf5f1faa037e9a40a5029cc7dd4ee61454b62466 MOVEONLY: DisconnectedBlockTransactions to its own file (glozow)
2765d6f3434c101fe2d46e9313e540aa680fbd77 rewrite DisconnectedBlockTransactions as a list + map (glozow)
79ce9f0aa46de8ff742be83fd6f68eab40e073ec add std::list to memusage (glozow)
59a35a7398f5bcb3e3805d1e4f363e4c2fb336b3 [bench] DisconnectedBlockTransactions (glozow)
925bb723ca71aa76380b769d8926c7c2ad9bbb7b [refactor] batch-add transactions to DisconnectedBlockTransactions (glozow)

Pull request description:

  Motivation
  - I think it's preferable to use stdlib data structures instead of depending on boost if we can achieve the same thing.
  - Also see #28335 for further context/motivation. This PR simplifies that one.

  Things done in this PR:
  - Add a bench for `DisconnectedBlockTransactions` where we reorg and the new chain has {100%, 90%, 10%} of the same transactions. AFAIU in practice, it's usually close to 100%.
  - Rewrite `DisconnectedBlockTransactions` as a `std::list` + `unordered_map` instead of a boost multi index container.
    - On my machine, the bench suggests the performance is very similar.
  - Move `DisconnectedBlockTransactions` from txmempool.h to its own kernel/disconnected_transactions.h. This struct isn't used by txmempool and doesn't have much to do with txmempool. My guess is that it's been living there for convenience since the boost includes are there.

ACKs for top commit:
  ismaelsadeeq:
    Tested ACK 4313c77400eb8eaa8586db39a7e29a861772ea80
  stickies-v:
    ACK 4313c77400eb8eaa8586db39a7e29a861772ea80
  TheCharlatan:
    ACK 4313c77400eb8eaa8586db39a7e29a861772ea80

Tree-SHA512: 273c80866bf3acd39b2a039dc082b7719d2d82e0940e1eb6c402f1c0992e997256722b85c7e310c9811238a770cfbdeb122ea4babbc23835d17128f214a1ef9e

1 files changed, 130 insertions, 0 deletions

diff --git a/src/bench/disconnected_transactions.cpp b/src/bench/disconnected_transactions.cpp
new file mode 100644
index 0000000000..d6f1590950
--- /dev/null
+++ b/src/bench/disconnected_transactions.cpp
@@ -0,0 +1,130 @@
+// Copyright (c) 2023 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <bench/bench.h>
+#include <kernel/disconnected_transactions.h>
+#include <primitives/block.h>
+#include <test/util/random.h>
+#include <test/util/setup_common.h>
+
+constexpr size_t BLOCK_VTX_COUNT{4000};
+constexpr size_t BLOCK_VTX_COUNT_10PERCENT{400};
+
+using BlockTxns = decltype(CBlock::vtx);
+
+/** Reorg where 1 block is disconnected and 2 blocks are connected. */
+struct ReorgTxns {
+    /** Disconnected block. */
+    BlockTxns disconnected_txns;
+    /** First connected block. */
+    BlockTxns connected_txns_1;
+    /** Second connected block, new chain tip. Has no overlap with disconnected_txns. */
+    BlockTxns connected_txns_2;
+    /** Transactions shared between disconnected_txns and connected_txns_1. */
+    size_t num_shared;
+};
+
+static BlockTxns CreateRandomTransactions(size_t num_txns)
+{
+    // Ensure every transaction has a different txid by having each one spend the previous one.
+    static uint256 prevout_hash{uint256::ZERO};
+
+    BlockTxns txns;
+    txns.reserve(num_txns);
+    // Simplest spk for every tx
+    CScript spk = CScript() << OP_TRUE;
+    for (uint32_t i = 0; i < num_txns; ++i) {
+        CMutableTransaction tx;
+        tx.vin.emplace_back(CTxIn{COutPoint{prevout_hash, 0}});
+        tx.vout.emplace_back(CTxOut{CENT, spk});
+        auto ptx{MakeTransactionRef(tx)};
+        txns.emplace_back(ptx);
+        prevout_hash = ptx->GetHash();
+    }
+    return txns;
+}
+
+/** Creates blocks for a Reorg, each with BLOCK_VTX_COUNT transactions. Between the disconnected
+ * block and the first connected block, there will be num_not_shared transactions that are
+ * different, and all other transactions the exact same. The second connected block has all unique
+ * transactions. This is to simulate a reorg in which all but num_not_shared transactions are
+ * confirmed in the new chain. */
+static ReorgTxns CreateBlocks(size_t num_not_shared)
+{
+    auto num_shared{BLOCK_VTX_COUNT - num_not_shared};
+    const auto shared_txns{CreateRandomTransactions(/*num_txns=*/num_shared)};
+
+    // Create different sets of transactions...
+    auto disconnected_block_txns{CreateRandomTransactions(/*num_txns=*/num_not_shared)};
+    std::copy(shared_txns.begin(), shared_txns.end(), std::back_inserter(disconnected_block_txns));
+
+    auto connected_block_txns{CreateRandomTransactions(/*num_txns=*/num_not_shared)};
+    std::copy(shared_txns.begin(), shared_txns.end(), std::back_inserter(connected_block_txns));
+
+    assert(disconnected_block_txns.size() == BLOCK_VTX_COUNT);
+    assert(connected_block_txns.size() == BLOCK_VTX_COUNT);
+
+    return ReorgTxns{/*disconnected_txns=*/disconnected_block_txns,
+                     /*connected_txns_1=*/connected_block_txns,
+                     /*connected_txns_2=*/CreateRandomTransactions(BLOCK_VTX_COUNT),
+                     /*num_shared=*/num_shared};
+}
+
+static void Reorg(const ReorgTxns& reorg)
+{
+    DisconnectedBlockTransactions disconnectpool{MAX_DISCONNECTED_TX_POOL_SIZE * 1000};
+    // Disconnect block
+    const auto evicted = disconnectpool.AddTransactionsFromBlock(reorg.disconnected_txns);
+    assert(evicted.empty());
+
+    // Connect first block
+    disconnectpool.removeForBlock(reorg.connected_txns_1);
+    // Connect new tip
+    disconnectpool.removeForBlock(reorg.connected_txns_2);
+
+    // Sanity Check
+    assert(disconnectpool.size() == BLOCK_VTX_COUNT - reorg.num_shared);
+
+    disconnectpool.clear();
+}
+
+/** Add transactions from DisconnectedBlockTransactions, remove all but one (the disconnected
+ * block's coinbase transaction) of them, and then pop from the front until empty. This is a reorg
+ * in which all of the non-coinbase transactions in the disconnected chain also exist in the new
+ * chain. */
+static void AddAndRemoveDisconnectedBlockTransactionsAll(benchmark::Bench& bench)
+{
+    const auto chains{CreateBlocks(/*num_not_shared=*/1)};
+    assert(chains.num_shared == BLOCK_VTX_COUNT - 1);
+
+    bench.minEpochIterations(10).run([&]() NO_THREAD_SAFETY_ANALYSIS {
+        Reorg(chains);
+    });
+}
+
+/** Add transactions from DisconnectedBlockTransactions, remove 90% of them, and then pop from the front until empty. */
+static void AddAndRemoveDisconnectedBlockTransactions90(benchmark::Bench& bench)
+{
+    const auto chains{CreateBlocks(/*num_not_shared=*/BLOCK_VTX_COUNT_10PERCENT)};
+    assert(chains.num_shared == BLOCK_VTX_COUNT - BLOCK_VTX_COUNT_10PERCENT);
+
+    bench.minEpochIterations(10).run([&]() NO_THREAD_SAFETY_ANALYSIS {
+        Reorg(chains);
+    });
+}
+
+/** Add transactions from DisconnectedBlockTransactions, remove 10% of them, and then pop from the front until empty. */
+static void AddAndRemoveDisconnectedBlockTransactions10(benchmark::Bench& bench)
+{
+    const auto chains{CreateBlocks(/*num_not_shared=*/BLOCK_VTX_COUNT - BLOCK_VTX_COUNT_10PERCENT)};
+    assert(chains.num_shared == BLOCK_VTX_COUNT_10PERCENT);
+
+    bench.minEpochIterations(10).run([&]() NO_THREAD_SAFETY_ANALYSIS {
+        Reorg(chains);
+    });
+}
+
+BENCHMARK(AddAndRemoveDisconnectedBlockTransactionsAll, benchmark::PriorityLevel::HIGH);
+BENCHMARK(AddAndRemoveDisconnectedBlockTransactions90, benchmark::PriorityLevel::HIGH);
+BENCHMARK(AddAndRemoveDisconnectedBlockTransactions10, benchmark::PriorityLevel::HIGH);