Гарантирует ли C ++ безопасный доступ к смежным элементам массива из двух потоков

Question

Что касается стандарта C ++ (я полагаю, что C ++ 11 и более поздние версии, так как ранее потоки не рассматривались), безопасно ли выполнять одновременную запись в различных , возможно смежных, элементовмассив?

Например:

#include <iostream>
#include <thread>

int array[10];

void func(int i) {
   array[i] = 42;
}

int main() 
{
   for(int i = 0; i < 10; ++i) {
      // spawn func(i) on a separate thread
      // (e.g. with std::async, let me skip the details)
   }
   // join

   for(int i = 0; i < 10; ++i) {
      std::cout << array[i] << std::endl; // prints 42?
   }

   return 0;
}

В этом случае гарантируется ли языком, что записи различных элементов массива не вызывают условия гонки?И гарантировано ли это для любого типа, или есть какие-то требования для того, чтобы это было безопасно?

Answer 1

Да.

С https://en.cppreference.com/w/cpp/language/memory_model:

Когда оценка выражения записывается в область памяти , а другая оценка читает или изменяет ту же памятьместо, выражения, как говорят, конфликтуют.Программа с двумя противоречивыми оценками имеет гонку данных, если только [...]

Тогда:

A ячейка памяти равна

• объект скалярного типа (арифметический тип, тип указателя, тип перечисления или std :: nullptr_t)
• или наибольшая непрерывная последовательность битовых полей ненулевой длины

Итак, если элементы массива хранятся в разных местах памяти, у вас нет противоречивых оценок.

И массив равен:

Объявление в форме T a[N];, объявляет a как объект массива, который состоит из N смежно расположенных объектов типа T.

Поскольку два разных объекта не могут иметь один и тот же адрес, они и их составляющие не могут иметь одну и ту же область памяти.Что гарантирует удовлетворение более ранних требований.

Более того, объекты могут состоять из нескольких ячеек памяти, поэтому вы даже можете иметь два потока, работающих с разными элементами одного и того же объекта!

Обратите вниманиечтобы ваш пример был верным, join также должен быть написан правильно, но он не связан со смежными элементами массива, а скорее работает с одним и тем же, так что я думаю, что это выходит за рамки вопроса.

---

Личная заметка: кстати.Если бы это не было гарантировано, это серьезно ограничило бы, если бы не показало бесполезные параллельные вычисления в стандартной библиотеке.

Answer 2

Гонки данных происходят только в одной и той же ячейке памяти, то есть гонка данных может происходить только по двум значениям x и y, только если &x == &y.

[intro.races]/ 2

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

[intro.races] / 21

Выполнение программы содержит гонку данных, если она содержит два потенциально одновременных конфликтующих действия [...]

Остальная часть чего здесь не применима.Так что нет, в вашем массиве нет гонки данных.

Answer 3

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

Для большинства программ доступ к памяти является основным узким местом.Критические к производительности разделы кода должны быть написаны осторожно, чтобы избежать чрезмерных ошибок в кеше.Кеш имеет несколько уровней, и каждый уровень быстрее предыдущего.Однако, когда данные не находятся в кэше, или когда данные могли быть изменены другим процессором, их необходимо повторно загрузить в кэш.

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

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

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

Answer 4

Да, но «ОК» не означает, что это разумно.

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

Вот один пример: ложный обмен ТАК вопрос / ответ