Описывается lock-free hash-table с открытой адресацией. Ключ и значение хранятся как единое целое в 128-битной ячейке над которой делается 128-битный CAS(2word-CAS в статье). Поддерживают 3 операции: insert, update, insertOrUpdate. Удаление через update на del_key. Update и insertOrUpdate принимают на вход функцию, которую необходимо применить к значению. Поддерживается аппроксимативный size через threadLocal счетчики удачных вставок/удалений и один глобальный счетчик, который и является размером таблицы. Описано две стратегии переноса элементов: использование пользовательских потоков и использование дополнительного threadPool. Описаны подходы для работы со сложными ключами: через указатель на сложный ключ и(или) значение, либо через хранение подписи(signature) сложного ключа и(или) значения в младших битах указателя. Также достаточно общими словами написано, что можно использовать транзакционную память на последовательных участах без особой конкретики.
1 Comment
Vitalii Karavaev