khizmax Mar 4 2015 at 09:00

Lock-free структуры данных. Concurrent maps: rehash, no rebuild

6 min

19K

Programming*C++*Algorithms*Concurrent computing*

+34

Comments 8

d3m1gd Mar 5 2015 at 00:07

А почему нужно обращать биты в ключах для сортировки? Как-то не очень очевиден этот момент, можно поподробнее?

khizmax Mar 5 2015 at 11:54

Список в целом у нас должен быть как-то отсортирован, иначе непонятно, как вставлять новый элемент (это относится только к конкурентным map'ам). Обычно в hash map сортируют по хешам и ключам (если хеши равны) или просто по ключам в списке коллизий. В split-ordered list сортировка по хешам или ключам не подходит, см. рисунки (для наглядности я полагаю, что хеш равен ключу), ведь нам надо обеспечить, чтобы список не надо было перестраивать при рехешинге. Если обратить хеш-значения, список становится отсортированным и при расщеплении bucket'а отсортированность сохраняется, — то, что надо. Это просто прием, трюк. Наконец, если хеши равны — сортируем по ключам, то есть критерий сортировки комбинированный.

leventov Mar 5 2015 at 16:35

Список в целом у нас должен быть как-то отсортирован, иначе непонятно, как вставлять новый элемент (это относится только к конкурентным map'ам).

Можно просто при вставке идти по списку в поисках ключа, если дошли до конца списка, присоединяем последнюю запить КАСом нулевой ссылки в предыдущей последней записи. Если уже не null, идем дальше.

То есть, отсортированность необязательна?

khizmax Mar 5 2015 at 17:01

А вот этот вопрос — обязательна ли отсортированность — для меня до сих пор остается открытым.
Во всех работах про hash map рассматриваются только отсортированные списки, — почему?
У меня есть пока два аргумента «за» отсортированность:

если её не будет, то вставка будет происходить всегда в конец списка, и мы получим толкотню CAS'ов на конце, — то есть ту же самую ситуацию, что и в lock-free очередях/стеках, которые из-за этого плохо масштабируются. С другой стороны, вероятность contention для hash map весьма низка, если у нас «хорошо разбрасывающая» хеш-функция и заполненность hash map достаточно низка; к тому же основная операция в hash map — поиск
Поиск в отсортированном списке в среднем будет в два раза быстрее. Контраргумент: списки в hash map очень короткие, так что эти «два раза» вряд ли будут заметны

Убийственного аргумента «за» отсортированность я пока что не придумал.

leventov Mar 5 2015 at 04:40

Может, вместо обращения хеш-значения использовать более изощренную операцию сравнения, чем < (меньше)? Типа

(1 << MSB(h1 ^ h2)) & h2

khizmax Mar 5 2015 at 12:04

Имеется в виду:

struct less {
    bool operator()( size_t h1, size_t h2) const
    {
         return ((1 << MSB(h1 ^ h2)) & h2 ) != 0;
    }
};

Так?
Я не вижу, как эта формула обеспечит нам ненужность перестройки списка при рехешинге, см предыдущий комментарий. Не могли бы пояснить?

leventov Mar 5 2015 at 16:32

Да, только least significant bit, я перепутал, думал на ваших схемах значения в bit endian приведены, привык так читать.

Использовать такую формулу для сравнения хешей при определении места вставки хеша в список — тоже самое, что полностью обернуть значение и сравнивать их встроенным «меньше», разве нет?

khizmax Mar 5 2015 at 17:48

Мне кажется, что для обычных, необращенных хешей — most significant bit, и от endianness это не зависит:
tmp1 := MSB( h1 ^ h2 ) — дает номер старшего бита, в котором h1 и h2 различаются.
tmp2 := 1 << tmp1 — дает число с этим единственным битом = 1. Надеюсь, endianness не влияет на сдвиги.
tmp3 := tmp2 & h2 — тестируем, у кого выставлен этот бит. Если у h2, то tmp3 != 0, то есть h2 > h1 и less() возвратит true. Если не у h2 (значит, у h1), то tmp3 == 0 и less() возвратит false.
Вроде бы все правильно. Одно «но» — случай h1 == h2: MSB тогда не определена, и предикат less должен выглядеть так:

return h1 != h2 && ((1 << MSB(h1 ^ h2)) & h2 ) != 0;

Для обращенных хешей (shah) MSB превращается в LSB. То есть мы можем, не обращая порядок бит, сравнивать хеши.
Остается вопрос — будет ли это быстрее, чем вычисление shah. По виду выражений — должно быть побыстрее, но учитывая, что shah мы храним, чтобы его не вычислять постоянно, — не факт, что быстрее.
Идея интересная, надо проверить…

Show the best of all time