Условие гонки с записью того же значения в C ++?

Question

Есть ли проблема с наличием состояния гонки в вашем коде, когда операция записывает одно постоянное значение? Например, если есть параллельный цикл, который заполняет массив seen для каждого значения в другом массиве arr (при условии отсутствия проблем с индексами за пределами границ). критическим разделом может быть следующий код:

//parallel body with index i
int val = arr[i];
seen[val] = true;

Поскольку записывается только значение true, делает ли это необходимость в мьютексе ненужной и, возможно, вредной для производительности? Даже если потоки нападают друг на друга, они просто заполняют адрес одним и тем же значением, правильно?

Answer 1

Модель памяти C ++ не дает вам свободного прохода для записи одного и того же значения.

Если два потока пишут в неатомарный объект без синхронизации, это просто условие гонки.А состояние гонки означает, что ваша программа выполняет неопределенное поведение.А неопределенное поведение, возникающее в любом месте выполнения вашей программы, означает, что поведение вашей программы, как до, так и после точки неопределенного поведения, никак не ограничено стандартом C ++.

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

Одна вещь, которую вы должны понять, это то, что C ++ не является языком макросов ассемблера.Это не должно производить наивного ассемблера, которого вы себе представляете.Вместо этого C ++ пытается упростить для вашего компилятора создание ассемблера, а это совсем другое.

Компиляторы могут и действительно определить, «если X случится, мы получим неопределенное поведение; поэтому я буду оптимизировать вокруг факта»что X не происходит "при генерации кода.В этом случае здесь, компилятор может доказать , что программа с определенным поведением может когда-либо иметь один и тот же val в двух разных несинхронизированных потоках.

Все это может произойти задолго до того, как какая-либо сборка будетГенерируемый.

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

---

Так что этоUB в C ++.И когда у вас есть UB, вы должны проверять ассемблерный код, созданный вашей программой, везде, где может видеть компилятор, который касается этого.Если вы используете LTO, это означает, что во всей вашей программе, по крайней мере, везде, где вызывается или взаимодействует с вашим кодом, который выполняет UB, на неясное расстояние.

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

Answer 2

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

То есть, если seen определено как bool seen[N];, тогда seen имеет длину N байтов, и каждый элемент находится непосредственно рядом со своим соседом.Если один поток изменяет элемент 0, а другой поток изменяет элемент 2, оба эти изменения происходят в одном и том же 64-битном машинном слове.Если эти два изменения вносятся одновременно разными ядрами (или даже на разных процессорах системы с несколькими процессорами), они будут пытаться разрешить конфликт как целое 64-разрядное машинное слово (или больше в некоторых случаях).Результатом этого будет то, что один из записанных true будет возвращен к своему предыдущему состоянию (вероятно, false) обновлением победившего потока на соседний элемент.

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