“Тонкая блокировка” в хэш-таблицах

В чем суть "тонкой блокировки" в хэш-таблицах и как её реализовать?

Ответ

Суть в том, что с каждым входом (цепочкой синонимов хэш-функции) связывают свой mutex.
Реализация на Си тривиальна:
struct hash_entry { pthread_mutex_t mutex; struct hash_item *list; // если, например, используете односвязный список };
При создании таблицы
struct hash_entry table[HASH_SIZE];
устанавливаете table[i].list в NULL и вызываете pthread_mutex_init(&table[i].mutex, 0); (если нет особых требований к атрибутам мьютекса).

Update
После комментария от @VladD решил добавить немного рассуждений на тему параллельной работы с хэш-таблицей.
В принципе для действий, затрагивающих всю таблицу, можно добавить rwlock (см., например, man pthread_rwlock_init и др. man для pthread_rwlock...). Тогда функции, требующие "тонкой блокировки" будут вызывать
pthread_rwlock_t tablock; ... pthread_rwlock_rdlock(&tablock); // совместная блокировка таблицы int i = hash_func(key, keylen) % HASH_SIZE; pthread_mutex_lock(&table[i].mutex); // блокировка цепочки // действия с цепочкой синонимов ... pthread_mutex_unlock(&table[i].mutex); pthread_rwlock_unlock(&tablock);
а функции, которые затрагивают всю таблицу
pthread_rwlock_wrlock(&tablock); // монопольная блокировка таблицы // действия с таблицей ... pthread_rwlock_unlock(&tablock);
т.е. получаем схему писатель-читатели с вложенной монопольной блокировкой цепочек коллизий.
Однако, на мой взгляд, в большинстве случаев подобные схемы (и вообще "тонкая блокировка") не оправдывают возлагаемых на них надежд из-за накладных расходов на блокировку.
Реально, если не удается вообще уйти (а к этому всегда надо стремиться (KISS-принцип)) от многопоточной работы с таблицей, выгодней просто блокировать ее всю, независимо от вида операций, поскольку обычно цепочки синонимов короткие и большинство операций с элементами таблицы весьма быстрые.
Еще одним доводом в пользу такого подхода может быть тривиальная экономия памяти (размер объекта pthread_mutex_t 40 байт на 64-bit X_86), которая (как это ни странно, на первый взгляд) часто приводит к ускорению программы (поскольку доступ к памяти может быть раз в 100 медленней доступа к кэшу).
Если возникают сомнения по поводу времени работы самой хэш-функции от ключа (например, известно, что ключи на самом деле весьма длинные и используется какая-то изощренная схема хэширования), то ее вычисление можно проводить до блокировки таблицы (а вот вычисление самого индекса, конечно же, уже получив блокировку).