Гарантируется ли хеширование без блокировки без std :: atomics поточно-ориентированным в C ++ 11?

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

struct Data
{
uint64_t key;
uint64_t value;
};

struct HashEntry
{
uint64_t key_xor_value;
uint64_t value;
};

void insert_data(Data const& e, HashEntry* h, std::size_t tableOffset)
{
h[tableOffset].key_xor_value = e.key ^ e.value;
h[tableOffset].value = e.value;
}

bool data_is_present(Data const& e, HashEntry const* h, std::size_t tableOffset)
{
auto const tmp_key_xor_value = h[tableOFfset].key_xor_value;
auto const tmp_value = h[tableOffset].value;

return e.key == (tmp_key_xor_value ^ tmp_value);
}

Идея в том, что HashEntry Структура хранит XOR-ed комбинацию двух 64-битных слов Data структура. Если два потока чередуют чтение / запись в два 64-битных слова HashEntry структура, идея состоит в том, что это может быть обнаружено потоком чтения, снова делая XOR и сравнивая с оригиналом key, Таким образом, может произойти потеря эффективности из-за поврежденных хеш-записей, но при этом гарантированная корректность будет в случае, если декодированный извлеченный ключ соответствует оригиналу.

В статье упоминается, что она основана на следующем предположении:

В оставшейся части этого обсуждения предположим, что 64-битная память
операции чтения / записи являются атомарными, то есть все 64-битное значение
читать / писать в один цикл.

Мои вопросы: приведенный выше код без явного использования std::atomic<uint64_t> гарантированно поточно-ориентированный в C ++ 11? Или могут быть повреждены отдельные 64-битные слова при одновременном чтении / записи? Даже на 64-битных платформах? И чем это отличается от старого C ++ 98 Standard?

Цитаты из стандарта будет высоко ценится.

ОБНОВИТЬ: на основе этой удивительной статьи Ханс Бём о «доброкачественных» данных гонках, простой способ получить укушенный компилятор — отменить оба XOR из insert_data() а также data_is_present() всегда возвращаться trueнапример, если он находит фрагмент локального кода, такой как

insert_data(e, h, t);
if (data_is_present(e, h, t)) // optimized to true as if in single-threaded code
read_and_process(e, h, t); // data race if other thread has written

2

Решение

Спецификация C ++ 11 в значительной степени определяет любую попытку одного потока прочитать или записать область памяти, в которую другой поток записывает как неопределенное поведение (отсутствует использование атомик или мьютексов для предотвращения чтения / записи из одного потока, в то время как другой поток пишу).

Отдельные компиляторы могут сделать это безопасным, но спецификация C ++ 11 не обеспечивает само покрытие. Одновременное чтение никогда не является проблемой; он пишет в одном потоке, а читает / пишет в другом.

И чем это отличается от старого C ++ 98 Standard?

Стандарт C ++ 98/03 не предусматривает любой покрытие в отношении потоков. Что касается модели памяти C ++ 98/03, потоки это не то, что может случиться.

7

Другие решения

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

2

Код полностью сломан. Компилятор обладает значительной свободой для изменения порядка команд, если его анализ показывает, что общий эффект идентичен. В insert_data например, нет гарантии, что key_xor_value будет обновлено до valueвыполняется ли обновление во временных регистрах перед записью обратно в кэш, не говоря уже о том, когда эти обновления кеша — независимо от их «порядка» в языке машинного кода и конвейере выполнения команд ЦП — будут сброшены из ядра или ядер обновления ». (если контекстно-переключенная середина функции) закрытые кэши, чтобы стать видимыми для других потоков. Компилятор может даже выполнять обновления поэтапно, используя 32-битные регистры, в зависимости от ЦП, будь то компиляция 32-битной или 64-битной, опции компиляции и т. Д.

Атомарные операции, как правило, требуют чего-то вроде инструкций стиля CAS (Compare and Swap), или volatile и инструкции по барьеру памяти, которые синхронизируют данные между кешами ядер и обеспечивают некоторое упорядочение.

1
По вопросам рекламы [email protected]