replace std::list with std::vector on some hot paths

also use reserve where appropriate

4 files changed, 62 insertions, 59 deletions

diff --git a/src/cryptonote_protocol/block_queue.cpp b/src/cryptonote_protocol/block_queue.cpp
index 9ae33d540..c39d67ceb 100644
--- a/src/cryptonote_protocol/block_queue.cpp
+++ b/src/cryptonote_protocol/block_queue.cpp
@@ -50,10 +50,10 @@ namespace std {
 namespace cryptonote
 {
 
-void block_queue::add_blocks(uint64_t height, std::list<cryptonote::block_complete_entry> bcel, const boost::uuids::uuid &connection_id, float rate, size_t size)
+void block_queue::add_blocks(uint64_t height, std::vector<cryptonote::block_complete_entry> bcel, const boost::uuids::uuid &connection_id, float rate, size_t size)
 {
   boost::unique_lock<boost::recursive_mutex> lock(mutex);
-  std::list<crypto::hash> hashes;
+  std::vector<crypto::hash> hashes;
   bool has_hashes = remove_span(height, &hashes);
   blocks.insert(span(height, std::move(bcel), connection_id, rate, size));
   if (has_hashes)
@@ -97,7 +97,7 @@ void block_queue::flush_stale_spans(const std::set<boost::uuids::uuid> &live_con
   }
 }
 
-bool block_queue::remove_span(uint64_t start_block_height, std::list<crypto::hash> *hashes)
+bool block_queue::remove_span(uint64_t start_block_height, std::vector<crypto::hash> *hashes)
 {
   boost::unique_lock<boost::recursive_mutex> lock(mutex);
   for (block_map::iterator i = blocks.begin(); i != blocks.end(); ++i)
@@ -172,7 +172,7 @@ bool block_queue::requested(const crypto::hash &hash) const
   return false;
 }
 
-std::pair<uint64_t, uint64_t> block_queue::reserve_span(uint64_t first_block_height, uint64_t last_block_height, uint64_t max_blocks, const boost::uuids::uuid &connection_id, const std::list<crypto::hash> &block_hashes, boost::posix_time::ptime time)
+std::pair<uint64_t, uint64_t> block_queue::reserve_span(uint64_t first_block_height, uint64_t last_block_height, uint64_t max_blocks, const boost::uuids::uuid &connection_id, const std::vector<crypto::hash> &block_hashes, boost::posix_time::ptime time)
 {
   boost::unique_lock<boost::recursive_mutex> lock(mutex);
 
@@ -183,14 +183,14 @@ std::pair<uint64_t, uint64_t> block_queue::reserve_span(uint64_t first_block_hei
   }
 
   uint64_t span_start_height = last_block_height - block_hashes.size() + 1;
-  std::list<crypto::hash>::const_iterator i = block_hashes.begin();
+  std::vector<crypto::hash>::const_iterator i = block_hashes.begin();
   while (i != block_hashes.end() && requested(*i))
   {
     ++i;
     ++span_start_height;
   }
   uint64_t span_length = 0;
-  std::list<crypto::hash> hashes;
+  std::vector<crypto::hash> hashes;
   while (i != block_hashes.end() && span_length < max_blocks)
   {
     hashes.push_back(*i);
@@ -230,7 +230,7 @@ std::pair<uint64_t, uint64_t> block_queue::get_start_gap_span() const
   return std::make_pair(current_height + 1, first_span_height - current_height - 1);
 }
 
-std::pair<uint64_t, uint64_t> block_queue::get_next_span_if_scheduled(std::list<crypto::hash> &hashes, boost::uuids::uuid &connection_id, boost::posix_time::ptime &time) const
+std::pair<uint64_t, uint64_t> block_queue::get_next_span_if_scheduled(std::vector<crypto::hash> &hashes, boost::uuids::uuid &connection_id, boost::posix_time::ptime &time) const
 {
   boost::unique_lock<boost::recursive_mutex> lock(mutex);
   if (blocks.empty())
@@ -248,7 +248,7 @@ std::pair<uint64_t, uint64_t> block_queue::get_next_span_if_scheduled(std::list<
   return std::make_pair(i->start_block_height, i->nblocks);
 }
 
-void block_queue::set_span_hashes(uint64_t start_height, const boost::uuids::uuid &connection_id, std::list<crypto::hash> hashes)
+void block_queue::set_span_hashes(uint64_t start_height, const boost::uuids::uuid &connection_id, std::vector<crypto::hash> hashes)
 {
   boost::unique_lock<boost::recursive_mutex> lock(mutex);
   for (block_map::iterator i = blocks.begin(); i != blocks.end(); ++i)
@@ -264,7 +264,7 @@ void block_queue::set_span_hashes(uint64_t start_height, const boost::uuids::uui
   }
 }
 
-bool block_queue::get_next_span(uint64_t &height, std::list<cryptonote::block_complete_entry> &bcel, boost::uuids::uuid &connection_id, bool filled) const
+bool block_queue::get_next_span(uint64_t &height, std::vector<cryptonote::block_complete_entry> &bcel, boost::uuids::uuid &connection_id, bool filled) const
 {
   boost::unique_lock<boost::recursive_mutex> lock(mutex);
   if (blocks.empty())
diff --git a/src/cryptonote_protocol/block_queue.h b/src/cryptonote_protocol/block_queue.h
index 69ddaa435..9059e89ac 100644
--- a/src/cryptonote_protocol/block_queue.h
+++ b/src/cryptonote_protocol/block_queue.h
@@ -31,7 +31,7 @@
 #pragma once
 
 #include <string>
-#include <list>
+#include <vector>
 #include <set>
 #include <boost/thread/recursive_mutex.hpp>
 #include <boost/uuid/uuid.hpp>
@@ -49,15 +49,15 @@ namespace cryptonote
     struct span
     {
       uint64_t start_block_height;
-      std::list<crypto::hash> hashes;
-      std::list<cryptonote::block_complete_entry> blocks;
+      std::vector<crypto::hash> hashes;
+      std::vector<cryptonote::block_complete_entry> blocks;
       boost::uuids::uuid connection_id;
       uint64_t nblocks;
       float rate;
       size_t size;
       boost::posix_time::ptime time;
 
-      span(uint64_t start_block_height, std::list<cryptonote::block_complete_entry> blocks, const boost::uuids::uuid &connection_id, float rate, size_t size):
+      span(uint64_t start_block_height, std::vector<cryptonote::block_complete_entry> blocks, const boost::uuids::uuid &connection_id, float rate, size_t size):
         start_block_height(start_block_height), blocks(std::move(blocks)), connection_id(connection_id), nblocks(this->blocks.size()), rate(rate), size(size), time() {}
       span(uint64_t start_block_height, uint64_t nblocks, const boost::uuids::uuid &connection_id, boost::posix_time::ptime time):
         start_block_height(start_block_height), connection_id(connection_id), nblocks(nblocks), rate(0.0f), size(0), time(time) {}
@@ -67,21 +67,21 @@ namespace cryptonote
     typedef std::set<span> block_map;
 
   public:
-    void add_blocks(uint64_t height, std::list<cryptonote::block_complete_entry> bcel, const boost::uuids::uuid &connection_id, float rate, size_t size);
+    void add_blocks(uint64_t height, std::vector<cryptonote::block_complete_entry> bcel, const boost::uuids::uuid &connection_id, float rate, size_t size);
     void add_blocks(uint64_t height, uint64_t nblocks, const boost::uuids::uuid &connection_id, boost::posix_time::ptime time = boost::date_time::min_date_time);
     void flush_spans(const boost::uuids::uuid &connection_id, bool all = false);
     void flush_stale_spans(const std::set<boost::uuids::uuid> &live_connections);
-    bool remove_span(uint64_t start_block_height, std::list<crypto::hash> *hashes = NULL);
+    bool remove_span(uint64_t start_block_height, std::vector<crypto::hash> *hashes = NULL);
     void remove_spans(const boost::uuids::uuid &connection_id, uint64_t start_block_height);
     uint64_t get_max_block_height() const;
     void print() const;
     std::string get_overview() const;
-    std::pair<uint64_t, uint64_t> reserve_span(uint64_t first_block_height, uint64_t last_block_height, uint64_t max_blocks, const boost::uuids::uuid &connection_id, const std::list<crypto::hash> &block_hashes, boost::posix_time::ptime time = boost::posix_time::microsec_clock::universal_time());
+    std::pair<uint64_t, uint64_t> reserve_span(uint64_t first_block_height, uint64_t last_block_height, uint64_t max_blocks, const boost::uuids::uuid &connection_id, const std::vector<crypto::hash> &block_hashes, boost::posix_time::ptime time = boost::posix_time::microsec_clock::universal_time());
     bool is_blockchain_placeholder(const span &span) const;
     std::pair<uint64_t, uint64_t> get_start_gap_span() const;
-    std::pair<uint64_t, uint64_t> get_next_span_if_scheduled(std::list<crypto::hash> &hashes, boost::uuids::uuid &connection_id, boost::posix_time::ptime &time) const;
-    void set_span_hashes(uint64_t start_height, const boost::uuids::uuid &connection_id, std::list<crypto::hash> hashes);
-    bool get_next_span(uint64_t &height, std::list<cryptonote::block_complete_entry> &bcel, boost::uuids::uuid &connection_id, bool filled = true) const;
+    std::pair<uint64_t, uint64_t> get_next_span_if_scheduled(std::vector<crypto::hash> &hashes, boost::uuids::uuid &connection_id, boost::posix_time::ptime &time) const;
+    void set_span_hashes(uint64_t start_height, const boost::uuids::uuid &connection_id, std::vector<crypto::hash> hashes);
+    bool get_next_span(uint64_t &height, std::vector<cryptonote::block_complete_entry> &bcel, boost::uuids::uuid &connection_id, bool filled = true) const;
     bool has_next_span(const boost::uuids::uuid &connection_id, bool &filled) const;
     size_t get_data_size() const;
     size_t get_num_filled_spans_prefix() const;
diff --git a/src/cryptonote_protocol/cryptonote_protocol_defs.h b/src/cryptonote_protocol/cryptonote_protocol_defs.h
index cf0043287..db159f0f4 100644
--- a/src/cryptonote_protocol/cryptonote_protocol_defs.h
+++ b/src/cryptonote_protocol/cryptonote_protocol_defs.h
@@ -109,7 +109,7 @@ namespace cryptonote
   struct block_complete_entry
   {
     blobdata block;
-    std::list<blobdata> txs;
+    std::vector<blobdata> txs;
     BEGIN_KV_SERIALIZE_MAP()
       KV_SERIALIZE(block)
       KV_SERIALIZE(txs)
@@ -145,7 +145,7 @@ namespace cryptonote
 
     struct request
     {
-      std::list<blobdata>   txs;
+      std::vector<blobdata>   txs;
 
       BEGIN_KV_SERIALIZE_MAP()
         KV_SERIALIZE(txs)
@@ -161,8 +161,8 @@ namespace cryptonote
 
     struct request
     {
-      std::list<crypto::hash>    txs;
-      std::list<crypto::hash>    blocks;
+      std::vector<crypto::hash>    txs;
+      std::vector<crypto::hash>    blocks;
 
       BEGIN_KV_SERIALIZE_MAP()
         KV_SERIALIZE_CONTAINER_POD_AS_BLOB(txs)
@@ -177,9 +177,9 @@ namespace cryptonote
 
     struct request
     {
-      std::list<blobdata>              txs;
-      std::list<block_complete_entry>  blocks;
-      std::list<crypto::hash>               missed_ids;
+      std::vector<blobdata>              txs;
+      std::vector<block_complete_entry>  blocks;
+      std::vector<crypto::hash>          missed_ids;
       uint64_t                         current_blockchain_height;
 
       BEGIN_KV_SERIALIZE_MAP()
@@ -230,7 +230,7 @@ namespace cryptonote
       uint64_t start_height;
       uint64_t total_height;
       uint64_t cumulative_difficulty;
-      std::list<crypto::hash> m_block_ids;
+      std::vector<crypto::hash> m_block_ids;
 
       BEGIN_KV_SERIALIZE_MAP()
         KV_SERIALIZE(start_height)
diff --git a/src/cryptonote_protocol/cryptonote_protocol_handler.inl b/src/cryptonote_protocol/cryptonote_protocol_handler.inl
index 2e1df8078..b4786b903 100644
--- a/src/cryptonote_protocol/cryptonote_protocol_handler.inl
+++ b/src/cryptonote_protocol/cryptonote_protocol_handler.inl
@@ -351,7 +351,7 @@ namespace cryptonote
       return 1;
     }
     m_core.pause_mine();
-    std::list<block_complete_entry> blocks;
+    std::vector<block_complete_entry> blocks;
     blocks.push_back(arg.b);
     m_core.prepare_handle_incoming_blocks(blocks);
     for(auto tx_blob_it = arg.b.txs.begin(); tx_blob_it!=arg.b.txs.end();tx_blob_it++)
@@ -438,7 +438,7 @@ namespace cryptonote
         }
       }      
       
-      std::list<blobdata> have_tx;
+      std::vector<blobdata> have_tx;
       
       // Instead of requesting missing transactions by hash like BTC, 
       // we do it by index (thanks to a suggestion from moneromooo) because
@@ -578,8 +578,8 @@ namespace cryptonote
         else
         {
           std::vector<crypto::hash> tx_ids;
-          std::list<transaction> txes;
-          std::list<crypto::hash> missing;
+          std::vector<transaction> txes;
+          std::vector<crypto::hash> missing;
           tx_ids.push_back(tx_hash);
           if (m_core.get_transactions(tx_ids, txes, missing) && missing.empty())
           {
@@ -626,7 +626,7 @@ namespace cryptonote
         b.block = arg.b.block;
         b.txs = have_tx;
 
-        std::list<block_complete_entry> blocks;
+        std::vector<block_complete_entry> blocks;
         blocks.push_back(b);
         m_core.prepare_handle_incoming_blocks(blocks);
           
@@ -687,8 +687,8 @@ namespace cryptonote
   {
     MLOG_P2P_MESSAGE("Received NOTIFY_REQUEST_FLUFFY_MISSING_TX (" << arg.missing_tx_indices.size() << " txes), block hash " << arg.block_hash);
     
-    std::list<std::pair<cryptonote::blobdata, block>> local_blocks;
-    std::list<cryptonote::blobdata> local_txs;
+    std::vector<std::pair<cryptonote::blobdata, block>> local_blocks;
+    std::vector<cryptonote::blobdata> local_txs;
 
     block b;
     if (!m_core.get_block_by_hash(arg.block_hash, b))
@@ -725,8 +725,8 @@ namespace cryptonote
       }
     }    
 
-    std::list<cryptonote::transaction> txs;
-    std::list<crypto::hash> missed;
+    std::vector<cryptonote::transaction> txs;
+    std::vector<crypto::hash> missed;
     if (!m_core.get_transactions(txids, txs, missed))
     {
       LOG_ERROR_CCONTEXT("Failed to handle request NOTIFY_REQUEST_FLUFFY_MISSING_TX, "
@@ -774,10 +774,12 @@ namespace cryptonote
       return 1;
     }
 
-    for(auto tx_blob_it = arg.txs.begin(); tx_blob_it!=arg.txs.end();)
+    std::vector<cryptonote::blobdata> newtxs;
+    newtxs.reserve(arg.txs.size());
+    for (size_t i = 0; i < arg.txs.size(); ++i)
     {
       cryptonote::tx_verification_context tvc = AUTO_VAL_INIT(tvc);
-      m_core.handle_incoming_tx(*tx_blob_it, tvc, false, true, false);
+      m_core.handle_incoming_tx(arg.txs[i], tvc, false, true, false);
       if(tvc.m_verifivation_failed)
       {
         LOG_PRINT_CCONTEXT_L1("Tx verification failed, dropping connection");
@@ -785,10 +787,9 @@ namespace cryptonote
         return 1;
       }
       if(tvc.m_should_be_relayed)
-        ++tx_blob_it;
-      else
-        arg.txs.erase(tx_blob_it++);
+        newtxs.push_back(std::move(arg.txs[i]));
     }
+    arg.txs = std::move(newtxs);
 
     if(arg.txs.size())
     {
@@ -996,7 +997,7 @@ skip:
         {
           const uint64_t previous_height = m_core.get_current_blockchain_height();
           uint64_t start_height;
-          std::list<cryptonote::block_complete_entry> blocks;
+          std::vector<cryptonote::block_complete_entry> blocks;
           boost::uuids::uuid span_connection_id;
           if (!m_block_queue.get_next_span(start_height, blocks, span_connection_id))
           {
@@ -1070,7 +1071,7 @@ skip:
               LOG_ERROR_CCONTEXT("Internal error: tvc.size() != block_entry.txs.size()");
               return 1;
             }
-            std::list<blobdata>::const_iterator it = block_entry.txs.begin();
+            std::vector<blobdata>::const_iterator it = block_entry.txs.begin();
             for (size_t i = 0; i < tvc.size(); ++i, ++it)
             {
               if(tvc[i].m_verifivation_failed)
@@ -1248,7 +1249,7 @@ skip:
   template<class t_core>
   bool t_cryptonote_protocol_handler<t_core>::should_download_next_span(cryptonote_connection_context& context) const
   {
-    std::list<crypto::hash> hashes;
+    std::vector<crypto::hash> hashes;
     boost::uuids::uuid span_connection_id;
     boost::posix_time::ptime request_time;
     std::pair<uint64_t, uint64_t> span;
@@ -1267,7 +1268,7 @@ skip:
       // we might be in a weird case where there is a filled next span,
       // but it starts higher than the current height
       uint64_t height;
-      std::list<cryptonote::block_complete_entry> bcel;
+      std::vector<cryptonote::block_complete_entry> bcel;
       if (!m_block_queue.get_next_span(height, bcel, span_connection_id, true))
         return false;
       if (height > m_core.get_current_blockchain_height())
@@ -1415,7 +1416,7 @@ skip:
       {
         if (span.second == 0)
         {
-          std::list<crypto::hash> hashes;
+          std::vector<crypto::hash> hashes;
           boost::uuids::uuid span_connection_id;
           boost::posix_time::ptime time;
           span = m_block_queue.get_next_span_if_scheduled(hashes, span_connection_id, time);
@@ -1441,14 +1442,18 @@ skip:
           goto skip;
         }
         // take out blocks we already have
-        while (!context.m_needed_objects.empty() && m_core.have_block(context.m_needed_objects.front()))
+        size_t skip = 0;
+        while (skip < context.m_needed_objects.size() && m_core.have_block(context.m_needed_objects[skip]))
         {
           // if we're popping the last hash, record it so we can ask again from that hash,
           // this prevents never being able to progress on peers we get old hash lists from
-          if (context.m_needed_objects.size() == 1)
-            context.m_last_known_hash = context.m_needed_objects.front();
-          context.m_needed_objects.pop_front();
+          if (skip + 1 == context.m_needed_objects.size())
+            context.m_last_known_hash = context.m_needed_objects[skip];
+          ++skip;
         }
+        if (skip > 0)
+          context.m_needed_objects = std::vector<crypto::hash>(context.m_needed_objects.begin() + skip, context.m_needed_objects.end());
+
         const uint64_t first_block_height = context.m_last_response_height - context.m_needed_objects.size() + 1;
         span = m_block_queue.reserve_span(first_block_height, context.m_last_response_height, count_limit, context.m_connection_id, context.m_needed_objects);
         MDEBUG(context << " span from " << first_block_height << ": " << span.first << "/" << span.second);
@@ -1456,7 +1461,7 @@ skip:
       if (span.second == 0 && !force_next_span)
       {
         MDEBUG(context << " still no span reserved, we may be in the corner case of next span scheduled and everything else scheduled/filled");
-        std::list<crypto::hash> hashes;
+        std::vector<crypto::hash> hashes;
         boost::uuids::uuid span_connection_id;
         boost::posix_time::ptime time;
         span = m_block_queue.get_next_span_if_scheduled(hashes, span_connection_id, time);
@@ -1487,23 +1492,21 @@ skip:
             MERROR("ERROR: skip " << skip << ", m_needed_objects " << context.m_needed_objects.size() << ", first_context_block_height" << first_context_block_height);
             return false;
           }
-          while (skip--)
-            context.m_needed_objects.pop_front();
+          if (skip > 0)
+            context.m_needed_objects = std::vector<crypto::hash>(context.m_needed_objects.begin() + skip, context.m_needed_objects.end());
           if (context.m_needed_objects.size() < span.second)
           {
             MERROR("ERROR: span " << span.first << "/" << span.second << ", m_needed_objects " << context.m_needed_objects.size());
             return false;
           }
 
-          auto it = context.m_needed_objects.begin();
           for (size_t n = 0; n < span.second; ++n)
           {
-            req.blocks.push_back(*it);
+            req.blocks.push_back(context.m_needed_objects[n]);
             ++count;
-            context.m_requested_objects.insert(*it);
-            auto j = it++;
-            context.m_needed_objects.erase(j);
+            context.m_requested_objects.insert(context.m_needed_objects[n]);
           }
+          context.m_needed_objects = std::vector<crypto::hash>(context.m_needed_objects.begin() + span.second, context.m_needed_objects.end());
         }
 
         context.m_last_request_time = boost::posix_time::microsec_clock::universal_time();
@@ -1664,7 +1667,7 @@ skip:
   {
     NOTIFY_NEW_FLUFFY_BLOCK::request fluffy_arg = AUTO_VAL_INIT(fluffy_arg);
     fluffy_arg.current_blockchain_height = arg.current_blockchain_height;    
-    std::list<blobdata> fluffy_txs;
+    std::vector<blobdata> fluffy_txs;
     fluffy_arg.b = arg.b;
     fluffy_arg.b.txs = fluffy_txs;