GrabDuck

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

:

Суть в том, что с каждым входом (цепочкой синонимов хэш-функции) связывают свой 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 медленней доступа к кэшу).

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