title: Memory leak in Google sparse_hash_map
body: <p>This week I've been trying to spot an unusual memory behavior: when I run my code with one single thread I have a specific memory footprint, but if I run it with multiple threads then the memory footprint increases a lot with no apparent reason. </p>
  
  <p>I know strange things can happen due to the indeterministic nature of a multithreaded program, so some deterministic approach is better used to debug this. However, even in a such very deterministic situation I failed to see why the memory footprint increases. </p>
  
  <p>Here's the smallest program I've been able to write that reproduce the problem:</p>
  
  <h1>test.cpp</h1>
  
  <pre><code>#include &lt;chrono&gt;
  #include &lt;iomanip&gt;
  #include &lt;iostream&gt;
  #include &lt;openssl/sha.h&gt;
  #include &lt;sparsehash/sparse_hash_map&gt;
  #include &lt;thread&gt;
  
  struct mystruct
  {
      uint64_t values[16];
      inline bool operator==(const mystruct &amp;other) const {
          return !memcmp(values, other.values, sizeof(values));
      }
      inline bool operator!=(const mystruct &amp;other) const { 
          return !(*this == other); 
      }
  };
  
  namespace std {
      template&lt;&gt;
      class hash&lt;mystruct&gt; {
      public:
          inline size_t operator()(const mystruct &amp;s) const 
          {
              return s.values[0];
          }
      };
  }
  
  google::sparse_hash_map&lt;mystruct, uint64_t, std::hash&lt;mystruct&gt;&gt; h;
  
  const uint64_t N = 1ull * 1024ull * 1024ull * 1024ull;
  const int step = 128;
  volatile uint64_t next = 0;
  uint64_t total_keys = 0;
  const uint64_t THREADS = 1;
  
  void insert_data(uint64_t data) {
      unsigned char buf[256];
      mystruct b;
      for (uint64_t j = 0; j &lt; N / THREADS; j++) {
          SHA256((unsigned char*)&amp;data, 8, buf);
          memcpy(&amp;b, buf, sizeof(mystruct));
  
          while (next != data)
              ;
  
          h[b] = 1;
          total_keys++;
          next += step;
          data += THREADS * step;
      }
  }
  
  int main() {
      std::thread t[THREADS];
  
      for (uint64_t i = 0; i &lt; THREADS; i++) {
          t[i] = std::thread(insert_data, i * step);
      }   
  
      std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
      while (total_keys &lt; N) {
          std::this_thread::sleep_for(std::chrono::milliseconds(100));
  
          std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
          uint64_t elapsed_ms = std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(end - begin).count();
          double speed = 1000.0*(double)total_keys / (double)elapsed_ms ;
  
          std::cout &lt;&lt; std::fixed &lt;&lt; "Processed " &lt;&lt; total_keys &lt;&lt; " items in " &lt;&lt; elapsed_ms &lt;&lt; " ms (" &lt;&lt; std::setprecision(0) &lt;&lt; speed &lt;&lt; " keys/s)"  &lt;&lt; ", next key is " &lt;&lt; next &lt;&lt; std::endl;
      }
  
      for (uint64_t i = 0; i &lt; THREADS; i++) {
          t[i].join();
      }
  }
  </code></pre>
  
  <p>The idea of the program is dead simple:</p>
  
  <ul>
  <li>Insert a <strong>known and predetermined sequence</strong> of 1 gazillion keys into the hashtable with a loop</li>
  <li>Watch the program dumping every 100ms on the console how many keys it inserted so far, and what's the next key that is going to be inserted</li>
  <li>Wait until the OS kills the program</li>
  </ul>
  
  <p>So, the goal is to verify that for a predefined sequence of inserts the memory consumption is the same <em>regardless of how many threads push the data into the hashtable</em>, that is the number of inserted keys is roughly the same (I don't mind if there's a few keys of differences, eg due to OS deciding to kill the application). Well the difference can be huge. </p>
  
  <p>The <code>insert_data</code> function uses a simple spin loop to guarantee the insertion sequence, that is the numbers 0, 128, 256, and so on... (using a lock/mutex makes no differences). </p>
  
  <p>I ran the program in the following environment:</p>
  
  <ul>
  <li>A Debian 8.3 Linux VM with 4GB of RAM</li>
  <li>No swap memory with <em>swapoff -a</em></li>
  <li>GCC 4.9.2 with <code>-O3</code> flag</li>
  </ul>
  
  <p>and these are the results when the above code runs with different number of the <strong>THREADS</strong> variable:</p>
  
  <h1>THREADS = 1</h1>
  
  <pre><code>Processed 54241 items in 100 ms (542410 keys/s), next key is 6942848
  Processed 104857 items in 200 ms (524285 keys/s), next key is 13421696
  ...
  Processed 13410458 items in 35698 ms (375664 keys/s), next key is 1716538624
  Processed 13421773 items in 35799 ms (374920 keys/s), next key is 1717986944
  ...
  ... 6 seconds of data because hashtable is being resized...
  ...
  Processed 13421773 items in 41245 ms (325416 keys/s), next key is 1717986944
  Processed 13438143 items in 41345 ms (325025 keys/s), next key is 1720082432
  ...
  Processed 23580346 items in 65567 ms (359637 keys/s), next key is 3018284416
  Killed
  </code></pre>
  
  <h1>THREADS = 2</h1>
  
  <pre><code>Processed 69922 items in 101 ms (692297 keys/s), next key is 8950016
  Processed 121766 items in 202 ms (602802 keys/s), next key is 15586048
  ...
  Processed 13409271 items in 37098 ms (361455 keys/s), next key is 1716386688
  Processed 13421773 items in 37198 ms (360820 keys/s), next key is 1717986944
  ...
  ... 6 seconds of data because hashtable is being resized...
  ...
  Processed 13421773 items in 43204 ms (310660 keys/s), next key is 1717986944
  Processed 13443021 items in 43304 ms (310434 keys/s), next key is 1720706688
  ...
  Processed 20024294 items in 64129 ms (312250 keys/s), next key is 2563110656
  Killed
  </code></pre>
  
  <h1>THREADS = 4</h1>
  
  <pre><code>Processed 31 items in 100 ms (310 keys/s), next key is 3968
  Processed 33882 items in 200 ms (169410 keys/s), next key is 4336896
  ...
  Processed 13399262 items in 48949 ms (273739 keys/s), next key is 1715105536
  Processed 13421773 items in 49049 ms (273640 keys/s), next key is 1717986944
  ...
  ... 5 seconds of data because hashtable is being resized...
  ...
  Processed 13421773 items in 54091 ms (248133 keys/s), next key is 1717986944
  Processed 13421773 items in 54201 ms (247630 keys/s), next key is 1717986944
  Killed
  </code></pre>
  
  <p>As you can see, all three tests identified the particular key <code>1717986944</code> as the key that triggers the hashtable resize, and all of them happen at the same inserted key n.<code>13421773</code>, and this confirms that the inserts always happen strictly in the same order regardless of the number of running threads.</p>
  
  <p>However, the <strong>THREADS=1</strong> inserted 3556052 more keys (corresponding to 434MB) than <strong>THREADS=2</strong>, and inserted 6602521 more keys (corresponding to 805MB) than <strong>THREADS=4</strong>. </p>
  
  <p>Can anyone explain me why I have a such weird memory consumption even in such deterministic conditions? Is there something that I'm actually missing?</p>