Мелкозернистые замки на С ++ карте карт

Question

У меня есть приложение на C ++ 17, в котором несколько потоков одновременно записывают данные на карту карт:

// global shared variable across threads
std::map<int, std::map<int, int>> the_map;

// many threads inserting different values for varying i and j
auto val = somewhat_expensive_f()
the_map[i][j] = val;

Для этого приложения существуют десятки тысяч уникальных (i, j) пар ина карте порядка 2000 в the_map после завершения. Я экспериментирую с несколькими потоками, выполняющими дорогостоящие вычисления, которые вставляются в эту карту карт. Прямо сейчас я использую std::map, который не допускает одновременных вставок.

Я обернул вставки std::lock_guard<std::mutex> в качестве первого разреза, и, конечно, это действительно замедлило приложение и затруднило работупараллелизм. Мой инстинкт заключается в том, что я могу использовать некоторую параллельную карту карт или детальную блокировку.

Для второго подхода мой инстинкт состоит в том, чтобы сделать какой-то массив блокировок, которые индексируются с использованием хеша (i, j) кортежа. Например, lock_guard<mutex>(array_of_locks[hash((i<<32)|j) % array_sz]) может разрешить совместное использование нескольких блокировок для тысяч дополнительных карт.

Вопрос 1: Я на правильном пути? Есть ли какие-либо отзывы об этом подходе?

Вопрос 2: При таком подходе у меня возникает проблема с ложным разделением смежных мьютексов в массиве. Я мог бы заполнить их, чтобы заполнить всю строку кэша. Есть ли лучшие подходы?

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

Answer 1

Разделение вашей карты на несколько карт, каждая из которых может быть заблокирована независимо, является хорошим и практичным подходом. Ключом к эффективному выполнению этой задачи является помнить, что, хотя на вашей карте может быть 10 тысяч записей, у вас, вероятно, не так много потоков или столько ядер.

Если на вашей машине, скажем,8 ядер, а затем хеширование ваших ключей в 64 разных сегментах, каждое со своей собственной картой и мьютексом, обеспечит маловероятную конкуренцию и не приведет к значительному замедлению работы приложения.

Не более 8 ядер могут пытатьсявставьте в одно и то же время, и даже если они будут делать это постоянно, они будут блокироваться только в 12% случаев. Тем не менее, в ваших темах, вероятно, будет много других дел, поэтому реальные разногласия будут намного меньше.

Как указывает @Eric, магические слова Google для этого - "чередование блокировок".

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

Одна вещь, о которой вы можете беспокоиться, это конфликт в используемом распределителе памятивыделить узлы карты. В конце концов, все они из одной кучи.