Связанный список записей хэш-таблицы - блокировки Mutex для безопасной работы с потоками - PullRequest
Новая
       10

Связанный список записей хэш-таблицы - блокировки Mutex для безопасной работы с потоками

0 голосов
/ 19 февраля 2012

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

Ответы [ 2 ]

0 голосов
/ 21 февраля 2012

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

0 голосов
/ 19 февраля 2012

Здесь многое зависит от деталей вашей хеш-таблицы.Моя немедленная реакция заключается в том, чтобы вообще избежать мьютекса / критической секции, по крайней мере, если вы можете.

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

struct LL_item { 
    LL_item *next;
    std::string key;
    whatever_type value;
};

Чтобы вставить элемент этого типа в связанный список, вы делаете что-то вроде: 

LL_item *item = new LL_item;

// set key and value here
item->next = &item;
InterlockedExchangePointer(&item->next, &bucket->head);

До InterlockedExchangePointer,bucket->head содержит адрес первого элемента в списке.Мы инициализируем наш новый элемент своим собственным адресом в указателе next.Затем мы (атомарно) обмениваем следующий указатель в нашем новом элементе с указателем на указатель на (предыдущий) первый узел в списке.После обмена следующий указатель нового узла содержит адрес ранее первого элемента в списке, а указатель на начало списка содержит адрес нашего нового узла.

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

...