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.

6 files changed, 18 insertions, 8 deletions

diff --git a/src/crypto/hash.h b/src/crypto/hash.h
index 8ea626314..274907076 100644
--- a/src/crypto/hash.h
+++ b/src/crypto/hash.h
@@ -101,6 +101,9 @@ namespace crypto {
 
   constexpr static crypto::hash null_hash = {};
   constexpr static crypto::hash8 null_hash8 = {};
+
+  inline bool operator<(const hash &lhs, const hash &rhs) noexcept { return memcmp(&lhs, &rhs, sizeof(hash)) < 0; }
+  inline bool operator>(const hash &lhs, const hash &rhs) noexcept { return rhs < lhs; }
 }
 
 CRYPTO_MAKE_HASHABLE(hash)
diff --git a/src/cryptonote_core/cryptonote_core.cpp b/src/cryptonote_core/cryptonote_core.cpp
index d30bc72a7..e9932ca39 100644
--- a/src/cryptonote_core/cryptonote_core.cpp
+++ b/src/cryptonote_core/cryptonote_core.cpp
@@ -1843,9 +1843,9 @@ namespace cryptonote
     m_blockchain_storage.flush_invalid_blocks();
   }
   //-----------------------------------------------------------------------------------------------
-  bool core::get_txpool_complement(const std::vector<crypto::hash> &hashes, std::vector<cryptonote::blobdata> &txes)
+  bool core::get_txpool_complement(std::vector<crypto::hash> hashes, std::vector<cryptonote::blobdata> &txes)
   {
-    return m_mempool.get_complement(hashes, txes);
+    return m_mempool.get_complement(std::move(hashes), txes);
   }
   //-----------------------------------------------------------------------------------------------
   bool core::update_blockchain_pruning()
diff --git a/src/cryptonote_core/cryptonote_core.h b/src/cryptonote_core/cryptonote_core.h
index ab9a0ee12..f1339dbb9 100644
--- a/src/cryptonote_core/cryptonote_core.h
+++ b/src/cryptonote_core/cryptonote_core.h
@@ -898,7 +898,7 @@ namespace cryptonote
       *
       * @return true iff success, false otherwise
       */
-     bool get_txpool_complement(const std::vector<crypto::hash> &hashes, std::vector<cryptonote::blobdata> &txes);
+     bool get_txpool_complement(std::vector<crypto::hash> hashes, std::vector<cryptonote::blobdata> &txes);
 
      /**
       * @brief validates some simple properties of a transaction
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<crypto::hash> &hashes, std::vector<cryptonote::blobdata> &txes) const
+  bool tx_memory_pool::get_complement(std::vector<crypto::hash> hashes, std::vector<cryptonote::blobdata> &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
diff --git a/src/cryptonote_core/tx_pool.h b/src/cryptonote_core/tx_pool.h
index df79aea1d..ed75a3dfc 100644
--- a/src/cryptonote_core/tx_pool.h
+++ b/src/cryptonote_core/tx_pool.h
@@ -489,7 +489,7 @@ namespace cryptonote
     /**
      * @brief get transactions not in the passed set
      */
-    bool get_complement(const std::vector<crypto::hash> &hashes, std::vector<cryptonote::blobdata> &txes) const;
+    bool get_complement(std::vector<crypto::hash> hashes, std::vector<cryptonote::blobdata> &txes) const;
 
     /**
      * @brief get info necessary for update of pool-related info in a wallet, preferably incremental
diff --git a/src/cryptonote_protocol/cryptonote_protocol_handler.inl b/src/cryptonote_protocol/cryptonote_protocol_handler.inl
index fb195b390..6a3fd2532 100644
--- a/src/cryptonote_protocol/cryptonote_protocol_handler.inl
+++ b/src/cryptonote_protocol/cryptonote_protocol_handler.inl
@@ -855,7 +855,7 @@ namespace cryptonote
     std::vector<cryptonote::blobdata> local_txs;
 
     std::vector<cryptonote::blobdata> txes;
-    if (!m_core.get_txpool_complement(arg.hashes, txes))
+    if (!m_core.get_txpool_complement(std::move(arg.hashes), txes))
     {
       LOG_ERROR_CCONTEXT("failed to get txpool complement");
       return 1;