Следующий шаблон является обычным для многих программ, которые хотят сообщить пользователю, сколько раз они выполняли различные действия:
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
гонкой данных?
doit
иreport_stats
в основном правильная - она асимптотична для правильного ответа. Гонка данных сdoit
между потоками имеет катастрофические последствия, в конце концов давая неверный ответ. - person Mark Lakata   schedule 12.04.2014doit
иreport_stats
. Что касается бедствия, это зависит от того, как используется счет! Количество вызовов JVM должно быть только приблизительным; Хогвилд! может быть доказано, что можно исправить несколько неверные промежуточные результаты; и конечного пользователя в исходном примере может интересовать только приблизительное количество вызовов функции. - person tmyklebu   schedule 12.04.2014doit
, и потоками, вызывающимиreport_stats
. Однако, по сути, он опирается на ассоциативную операцию объединения счетчиков потоков; как-то напрягает, что решение чистой проблемы параллелизма должно полагаться на нетривиальные свойства выполняемых операций. - person tmyklebu   schedule 12.04.2014doit
иreport_stats
- это только запись и чтение. Обе эти операции являются атомарными для целочисленной (размером с регистр) арифметики в любой известной мне архитектуре, поэтому вам не нужно использовать блокировку, чтобы сделать их атомарными.report_stats
сообщит либо последнее значение, либо более старое значение, но оно никогда не будет лгать и давать совершенно неправильное значение. У вас должен быть способ синхронизации конвейеров и памяти после завершения всех потоков, но это операция O (1), поэтому меня не беспокоит, насколько это дорого. - person Mark Lakata   schedule 14.04.2014doit
иreport_stats
разрушает абсолютно все по стандарту. Я работаю здесь с моделью памяти C++, а не с какой-то конкретной машиной. (В частности, C++ прямо заявляет, что любая гонка данных вообще, даже междуdoit
иreport_stats
, приводит к неопределенному поведению.) - person tmyklebu   schedule 14.04.2014