Рассмотрим следующую попытку создания хэш-таблицы без блокировки для многопоточных алгоритмов поиска (вдохновленный этим бумага)
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
Спецификация C ++ 11 в значительной степени определяет любую попытку одного потока прочитать или записать область памяти, в которую другой поток записывает как неопределенное поведение (отсутствует использование атомик или мьютексов для предотвращения чтения / записи из одного потока, в то время как другой поток пишу).
Отдельные компиляторы могут сделать это безопасным, но спецификация C ++ 11 не обеспечивает само покрытие. Одновременное чтение никогда не является проблемой; он пишет в одном потоке, а читает / пишет в другом.
И чем это отличается от старого C ++ 98 Standard?
Стандарт C ++ 98/03 не предусматривает любой покрытие в отношении потоков. Что касается модели памяти C ++ 98/03, потоки это не то, что может случиться.
Я не думаю, что это зависит так сильно от компилятора, как от процессора (его набора команд), который вы используете. Я не думаю, что предположение будет очень переносимым.
Код полностью сломан. Компилятор обладает значительной свободой для изменения порядка команд, если его анализ показывает, что общий эффект идентичен. В insert_data
например, нет гарантии, что key_xor_value
будет обновлено до value
выполняется ли обновление во временных регистрах перед записью обратно в кэш, не говоря уже о том, когда эти обновления кеша — независимо от их «порядка» в языке машинного кода и конвейере выполнения команд ЦП — будут сброшены из ядра или ядер обновления ». (если контекстно-переключенная середина функции) закрытые кэши, чтобы стать видимыми для других потоков. Компилятор может даже выполнять обновления поэтапно, используя 32-битные регистры, в зависимости от ЦП, будь то компиляция 32-битной или 64-битной, опции компиляции и т. Д.
Атомарные операции, как правило, требуют чего-то вроде инструкций стиля CAS (Compare and Swap), или volatile
и инструкции по барьеру памяти, которые синхронизируют данные между кешами ядер и обеспечивают некоторое упорядочение.