Утечка памяти в Google sparse_hash_map

На этой неделе я пытался обнаружить необычное поведение памяти: когда я запускаю свой код с одним потоком, у меня появляется определенный объем памяти, но если я запускаю его с несколькими потоками, объем памяти увеличивается без видимой причины.

Я знаю, что из-за недетерминированной природы многопоточной программы могут происходить странные вещи, поэтому для ее устранения лучше использовать некий детерминированный подход. Однако даже в такой очень детерминированной ситуации мне не удалось понять, почему объем памяти увеличивается.

Вот самая маленькая программа, которую мне удалось написать, которая воспроизводит проблему:

#include <chrono>
#include <iomanip>
#include <iostream>
#include <openssl/sha.h>
#include <sparsehash/sparse_hash_map>
#include <thread>

struct mystruct
{
uint64_t values[16];
inline bool operator==(const mystruct &other) const {
return !memcmp(values, other.values, sizeof(values));
}
inline bool operator!=(const mystruct &other) const {
return !(*this == other);
}
};

namespace std {
template<>
class hash<mystruct> {
public:
inline size_t operator()(const mystruct &s) const
{
return s.values[0];
}
};
}

google::sparse_hash_map<mystruct, uint64_t, std::hash<mystruct>> 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 < N / THREADS; j++) {
SHA256((unsigned char*)&data, 8, buf);
memcpy(&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 < 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 < 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<std::chrono::milliseconds>(end - begin).count();
double speed = 1000.0*(double)total_keys / (double)elapsed_ms ;

std::cout << std::fixed << "Processed " << total_keys << " items in " << elapsed_ms << " ms (" << std::setprecision(0) << speed << " keys/s)"  << ", next key is " << next << std::endl;
}

for (uint64_t i = 0; i < THREADS; i++) {
t[i].join();
}
}

Идея программы очень проста:

• Вставьте известная и заданная последовательность 1 миллион ключей в хеш-таблицу с циклом
• Посмотрите, как программа выводит каждые 100 мс на консоль, сколько клавиш она вставила до сих пор, и какая следующая клавиша будет вставлена
• Подождите, пока ОС не убьет программу

Итак, цель состоит в том, чтобы убедиться, что для предопределенной последовательности вставок потребление памяти одинаково независимо от того, сколько потоков помещает данные в хеш-таблицу, количество вставленных ключей примерно одинаково (я не против, если есть несколько различий ключей, например, из-за того, что ОС решила убить приложение). Ну, разница может быть огромной.

insert_data Функция использует простой цикл вращения, чтобы гарантировать последовательность вставки, то есть числа 0, 128, 256 и т. д. (использование блокировки / мьютекса не делает различий).

Я запустил программу в следующей среде:

• Виртуальная машина Debian 8.3 Linux с 4 ГБ оперативной памяти
• Нет подкачки памяти с своп -а
• GCC 4.9.2 с -O3 флаг

и это результаты, когда приведенный выше код работает с другим числом ПОТОКИ переменная:

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

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

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

Как видите, все три теста идентифицировали конкретный ключ 1717986944 как ключ, который запускает изменение размера хеш-таблицы, и все они происходят при одном и том же вставленном ключе n.13421773, и это подтверждает, что вставки всегда происходят строго в одном и том же порядке, независимо от количества запущенных потоков.

Тем не менее НИТИ = 1 вставлено на 3556052 больше ключей (соответствует 434 МБ), чем НИТИ = 2, и вставил на 6602521 больше ключей (соответствует 805МБ), чем НИТИ = 4.

Может кто-нибудь объяснить мне, почему у меня такое странное потребление памяти даже в таких детерминированных условиях? Есть ли что-то, что я действительно скучаю?