ConcurrentHashMap для C++

f03n1x
f03n1x

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

Понятно, что можно взять обычную хеш таблицу и прикрыть ее от race condition при помощи mutex'a, но это приведет к тому, что у нас не будет возможности параллельно обращаться к данным внутри хеш таблицы. Более подробно про это можно почитать тут.

Я написал STL совместимую реализацию и разместил ее на github.

Данная имплементация дублирует интерфейс стандартного типа unordered_map и позволяет писать многопоточный код так же легко и удобно, как если бы он таким не был.

#include "concurrent_hash_map.hpp"
#include <string>

concurrent_unordered_map<std::string, int> m;
m.insert(std::make_pair("abc", 123));
assert(m["abc"] == 123);

 

11
рейтинг
6 комментариев
Сергей Прейс
Может стоит сделать у коллекций дополнительный параметр в шаблоне - concurency_policy примерно как execution_policy для алгоритмов сделали.
Сергей Прейс
f03n1x
Сергей, это очень клевая идея, но она несколько большего масштаба, чем просто одна структура данных :). На самом деле это еще связано с интерфейсом этих объектов. Для того, чтобы сделать так как вы хотите необходимо, чтобы у обычных, многопоточных и lock-free коллекций был одинаковый интерфейс. Не факт, что такое в принципе возможно сделать.
f03n1x
yndx-antoshkka
Сергей Прейс, дополнительный параметр в шаблоне добавить нельзя: это поменяет ABI а значит такая идея в комитете C++ не пройдёт.
yndx-antoshkka
Сергей Прейс
f03n1x, ну в общем да, согласен. Ради одной коллекции не стоит наводить общность. Просто кажется, что иметь две разных реализации одной концепции под разными именами немного странно. Кажется, что более правильно сделать что-то с существующей концепцией.
Сергей Прейс
Сергей Прейс
yndx-antoshkka, порядка 70 шаблонов в получили новый параметр в C++17 (execution_policy). Но наверное я понимаю о чем вы: для функций это получилось сделать из-за перегрузки (overloading) а для классов такого механизма не существует. В принципе unordered_map в этом случае остаётся концептуально прежним, меняется только реализация, так что нет необходимости добавлять параметр в шаблон - можно добавить конструкторы с новым параметром concurency_policy, который будет влиять на внутреннюю реализацию, но не на ABI.
Сергей Прейс
konyuchenko.nikita
Я бы скорей предпочел видеть что-то на вроде такого:
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator< std::pair<const Key, T> >
> class unordered_map
: public generic_unordered_map<
Key,
T,
Hash,
KeyEqual,
Allocator,
std::concurrent_policy::none>;

template<
class Key,
class T,
class Hash,
class KeyEqual,
class Allocation,
class ConcurrentPolicy
> class generic_unordered_map;

Concurrent Policies:
none
lock_free - several implementations for platforms (ARM needs different implementation than x86)
mutex_based
etc.

При этом в unordered_map дополнительный шаблонный параметр не попадает (хотя ABI все равно меняется)
konyuchenko.nikita
Другие идеи
Группа создана, чтобы собирать предложения к стандарту C++, организовывать их внутренние обсуждения, помогать готовить их для отправки в комитет и защищать на общих собраниях в рабочей группе по С++ Международной организации по стандартизации (ISO).