From 0761024b349048ebf79dbfe71caab11826833464 Mon Sep 17 00:00:00 2001 From: jeffro256 Date: Mon, 3 Nov 2025 17:05:57 -0600 Subject: tx_memory_pool: speedup get_complement() for large requests Changes complexity from M*N to (2*N+M)*log2(M). The FCMP++ stressnet recently hit mempool sizes of ~55k txs. If the requesting node's mempool is populated, this results in an average of (55000*55000)/2 (about 1.5 billion) comparisons for the responding node. Under this commit, this would be reduced to (55000+55000)*log2(55000) comparisons (about 2.6 million), a 99.83% reduction. --- src/cryptonote_core/tx_pool.cpp | 13 ++++++++++--- 1 file changed, 10 insertions(+), 3 deletions(-) (limited to 'src/cryptonote_core/tx_pool.cpp') diff --git a/src/cryptonote_core/tx_pool.cpp b/src/cryptonote_core/tx_pool.cpp index 40c004da4..3bc508037 100644 --- a/src/cryptonote_core/tx_pool.cpp +++ b/src/cryptonote_core/tx_pool.cpp @@ -668,17 +668,24 @@ namespace cryptonote return true; } //--------------------------------------------------------------------------------- - bool tx_memory_pool::get_complement(const std::vector &hashes, std::vector &txes) const + bool tx_memory_pool::get_complement(std::vector hashes, std::vector &txes) const { CRITICAL_REGION_LOCAL(m_transactions_lock); CRITICAL_REGION_LOCAL1(m_blockchain); + // Sort so we can do binary search later + std::sort(hashes.begin(), hashes.end()); + m_blockchain.for_all_txpool_txes([this, &hashes, &txes](const crypto::hash &txid, const txpool_tx_meta_t &meta, const cryptonote::blobdata_ref*) { const auto tx_relay_method = meta.get_relay_method(); if (tx_relay_method != relay_method::block && tx_relay_method != relay_method::fluff) return true; - const auto i = std::find(hashes.begin(), hashes.end(), txid); - if (i == hashes.end()) + + // Do binary search for our pool TXID in given list, skip to next if already present + const auto hash_it = std::lower_bound(hashes.cbegin(), hashes.cend(), txid); + if (hash_it != hashes.cend() && *hash_it == txid) + return true; + { cryptonote::blobdata bd; try -- cgit v1.2.3