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

Question

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

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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