Можно ли адаптировать этот 32-битный алгоритм хеш-таблицы без блокировки для 64-битных ключей? - PullRequest
Новая
       11

Можно ли адаптировать этот 32-битный алгоритм хеш-таблицы без блокировки для 64-битных ключей?

0 голосов
/ 30 мая 2018

Проблема и контекст

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

enter image description here

Вот код: 

void ArrayOfItems::SetItem(uint32_t key, uint32_t value)
{
    for (uint32_t idx = 0;; idx++)
    {
        uint32_t prevKey = mint_compare_exchange_strong_32_relaxed(&m_entries[idx].key, 0, key);
        if ((prevKey == 0) || (prevKey == key))
        {
            mint_store_32_relaxed(&m_entries[idx].value, value);
            return;
        }
    }
}

Для конкретной проблемы мне нужно вставить в таблицу случайные пары ключ-вал.Поэтому мне нужны как минимум 64-битные ключи, потому что с 32-битными существует вероятность столкновения 50% после 65536 вставок, что слишком мало.К сожалению, у меня нет 64-битного cmpxchg в качестве примитива.

Вопрос

Можно ли обобщить приведенную выше хеш-таблицу на 64-битные ключи, используятолько 32-битный cmpxchg?

1 Ответ

0 голосов
/ 31 мая 2018

Я не уверен из вопроса, хотите ли вы по-прежнему сохранять характеристику без блокировки или просто хотите запустить и запустить 64-битное хранилище ключей / значений.(?)

Существует 64-битный MurmurHash3, размещенный здесь @kol: хэширует небольшое число в случайное 64-битное целое число

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

--------------- Редактировать: ---------------
Автор имеет по крайней мере два видео в своей хэш-таблице, оба с 2007 года:

Дополнительные разделы в языках программирования: хеш-таблица без блокировки https://www.youtube.com/watch?v=HJ-719EGIts

Хеш-таблица быстрого ожидания без ожидания
https://youtu.be/WYXgtXWejRM

Он связывает поток своей программы с конечным автоматом.Не принимая во внимание проблему увеличения таблицы, существует четыре состояния, в которых может находиться местоположение, прежде чем к нему будет применена потенциальная мутация.Ключ / Значение = [ноль / ноль], [X / ноль], [X / X], [ноль / X].

Чтение состояния при подготовке к мутации не гарантирует при параллельности, что состояние остается неизменным во время применения мутации.

При 32-битных операциях мы имеем следующую логику:
- Если ключ чтения = требуемый ключ, значение может быть записано в местоположение.
- Если ключ чтения = ноль,и значение = не ноль, тогда другой поток изменяет местоположение.
- если ключ чтения = ноль, а значение = ноль, то местоположение может быть записано через успешный ключ CAS.

Если вы хотите использовать 32-битные атомарные операции для хранения 64-битных данных без блокировки, тогда диаграмма состояний увеличивается в размерах с большим количеством состояний отказа, например:
- вы можете прочитать наполовину созданныйKey.
- Обновление CAS одной половины записи значения может быть растоптано другим потоком, в случае неудачи на втором CAS.
- Создание CAS одной половины записи ключа может быть растоптано другим потоком,сбой на втором CAS.
- 32-битное представление инициализатора массива 'nil' должно быть исключено как половина 64-битного ключа или значение

Процесс увеличения размера таблицы добавляет некоторыебольше государств, чтобы рассмотреть, также.

...