Гонки данных, UB и счетчики в C++11

Следующий шаблон является обычным для многих программ, которые хотят сообщить пользователю, сколько раз они выполняли различные действия:

int num_times_done_it; // global

void doit() {
  ++num_times_done_it;
  // do something
}

void report_stats() {
  printf("called doit %i times\n", num_times_done_it);
  // and probably some other stuff too
}

К сожалению, если несколько потоков могут вызывать doit без какой-либо синхронизации, одновременное чтение-изменение-запись в num_times_done_it может быть гонкой данных, и, следовательно, поведение всей программы будет неопределенным. Кроме того, если report_stats может вызываться одновременно с doit при отсутствии какой-либо синхронизации, происходит еще одна гонка данных между потоком, изменяющим num_times_done_it, и потоком, сообщающим его значение.

Часто программист просто хочет получить в основном правильный подсчет количества вызовов doit с минимальными издержками.

(Если вы считаете этот пример тривиальным, Hogwild! набирает значительную скорость. Преимущество перед стохастическим градиентным спуском без гонки данных, использующим, по сути, этот трюк.Кроме того, я считаю, что JVM Hotspot выполняет именно такой незащищенный многопоточный доступ к общему счетчику для подсчета вызовов методов --- хотя это ясно, поскольку он генерирует ассемблерный код вместо C++11.)

Очевидные нерешения:

  • Atomics, с любым порядком памяти, о котором я знаю, здесь терпит неудачу «как можно меньше накладных расходов» (атомарное приращение может быть значительно дороже, чем обычное приращение), в то же время передавая «в основном правильно» (будучи точно правильным).
  • Я не верю, что добавление volatile в микс делает гонки данных приемлемыми, поэтому замена объявления num_times_done_it на volatile int num_times_done_it ничего не исправит.
  • Есть неудобное решение — иметь отдельный счетчик для каждого потока и суммировать их все в report_stats, но это не решает проблему гонки данных между doit и report_stats. Кроме того, это беспорядочно, предполагается, что обновления являются ассоциативными, и на самом деле не соответствует использованию Hogwild!

Можно ли реализовать счетчики вызовов с четко определенной семантикой в ​​нетривиальной многопоточной программе на C++11 без какой-либо формы синхронизации?

EDIT: кажется, что мы можем сделать это косвенным образом, используя memory_order_relaxed:

atomic<int> num_times_done_it;
void doit() {
  num_times_done_it.store(1 + num_times_done_it.load(memory_order_relaxed),
                          memory_order_relaxed);
  // as before
}

Однако gcc 4.8.2 генерирует этот код на x86_64 (с -O3):

   0:   8b 05 00 00 00 00       mov    0x0(%rip),%eax
   6:   83 c0 01                add    $0x1,%eax
   9:   89 05 00 00 00 00       mov    %eax,0x0(%rip)

и clang 3.4 генерирует этот код на x86_64 (опять же с -O3):

   0:   8b 05 00 00 00 00       mov    0x0(%rip),%eax
   6:   ff c0                   inc    %eax
   8:   89 05 00 00 00 00       mov    %eax,0x0(%rip)

Насколько я понимаю x86-TSO, обе эти последовательности кода, за исключением прерываний и забавных флагов защиты страниц, полностью эквивалентны памяти с одной инструкцией inc и памяти с одной инструкцией add, сгенерированной прямым кодом. Является ли такое использование memory_order_relaxed гонкой данных?


person tmyklebu    schedule 11.04.2014    source источник
comment
Если вам не нужно, чтобы решение было правильным, его, конечно, можно оптимизировать так, чтобы оно было сколь угодно быстрым (с уменьшением вероятности получения полезных результатов). Быстро, правильно, легко; Выбери два.   -  person BenPope    schedule 11.04.2014
comment
@BenPope: Это забавная фраза, но здесь она не особенно актуальна. Я спрашиваю, как справиться с тем, что на момент написания полностью теоретической проблемы. Ни один известный мне компилятор не сгенерирует неприемлемый код для шаблона в моем посте. Однако в будущем это может измениться...   -  person tmyklebu    schedule 11.04.2014
comment
Я не уверен, что понимаю, как неудобно иметь отдельные счетчики для каждого потока. Гонка данных с отдельными счетчиками между doit и report_stats в основном правильная - она ​​асимптотична для правильного ответа. Гонка данных с doit между потоками имеет катастрофические последствия, в конце концов давая неверный ответ.   -  person Mark Lakata    schedule 12.04.2014
comment
@MarkLakata: Да. Как я уже сказал, это полностью теоретическая проблема; Я никогда не видел, чтобы текущий компилятор взорвал это. Однако стандарт C++ говорит, что любая гонка данных представляет собой неопределенное поведение, даже между doit и report_stats. Что касается бедствия, это зависит от того, как используется счет! Количество вызовов JVM должно быть только приблизительным; Хогвилд! может быть доказано, что можно исправить несколько неверные промежуточные результаты; и конечного пользователя в исходном примере может интересовать только приблизительное количество вызовов функции.   -  person tmyklebu    schedule 12.04.2014
comment
@MarkLakata: Отвечая на ваш прямой вопрос, я нахожу это неловким в нескольких отношениях. Во-первых, это космический взрыв (возможно, тривиальный для одного счетчика, но менее тривиальный, если по какой-то причине у нас их много). Во-вторых, вам по-прежнему нужно обновлять их атомарно, чтобы избежать гонки между потоками, вызывающими doit, и потоками, вызывающими report_stats. Однако, по сути, он опирается на ассоциативную операцию объединения счетчиков потоков; как-то напрягает, что решение чистой проблемы параллелизма должно полагаться на нетривиальные свойства выполняемых операций.   -  person tmyklebu    schedule 12.04.2014
comment
@tmyklebu - состояние гонки между doit и report_stats - это только запись и чтение. Обе эти операции являются атомарными для целочисленной (размером с регистр) арифметики в любой известной мне архитектуре, поэтому вам не нужно использовать блокировку, чтобы сделать их атомарными. report_stats сообщит либо последнее значение, либо более старое значение, но оно никогда не будет лгать и давать совершенно неправильное значение. У вас должен быть способ синхронизации конвейеров и памяти после завершения всех потоков, но это операция O (1), поэтому меня не беспокоит, насколько это дорого.   -  person Mark Lakata    schedule 14.04.2014
comment
@MarkLakata: модель памяти C ++ слабее, чем любая известная мне модель машинной памяти (кроме Itanium); гонка данных между doit и report_stats разрушает абсолютно все по стандарту. Я работаю здесь с моделью памяти C++, а не с какой-то конкретной машиной. (В частности, C++ прямо заявляет, что любая гонка данных вообще, даже между doit и report_stats, приводит к неопределенному поведению.)   -  person tmyklebu    schedule 14.04.2014


Ответы (2)


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

И, в зависимости от компилятора и платформы, атомарность не так уж и дорога (см. доклад Херба Саттера об атомном оружии http://channel9.msdn.com/Shows/Going+Deep/Cpp-and-Beyond-2012-Herb-Sutter-atomic-Weapons-1-of-2), но в вашем случае это создаст проблемы с тайниками, так что это не рекомендуется.

person Tobias Langner    schedule 11.04.2014
comment
это не решение № 3, заявленное OP - person Bryan Chen; 11.04.2014
comment
Вот в чем дело; вы не можете суммировать их, пока не синхронизируетесь с чем-то без той же гонки данных. - person tmyklebu; 11.04.2014

Кажется, что трюк memory_order_relaxed — правильный способ сделать это.

Это Сообщение в блоге Дмитрия Вьюкова из Intel начинается с точного ответа на мой вопрос и продолжается перечислением memory_order_relaxed store и load в качестве подходящей альтернативы.

Я все еще не уверен, действительно ли это нормально; в частности, N3710 заставляет меня сомневаться что я вообще когда-либо понимал memory_order_relaxed.

person tmyklebu    schedule 12.04.2014