Атомный, масштабируемый, монотонный счетчик с границей

Question

У меня есть критический путь кода, в котором потоки используют атомное приращение целого числа, чтобы подсчитать количество событий, которые произошли во всем мире. Это достаточно быстро, но по-прежнему требует, чтобы линия кеша, содержащая целое число, отскакивала между ядрами. В системе NUMA это создает много трафика MESI.

Псевдо код горячего погладить является то, что все нити этого:

const int CHECK_VALUE = 42; 

int counterNew = counter++; 
if (counterNew == CHECK_VALUE) { 
    Do Final work 
} 

Счетчик монотонно возрастает и значение оно должно достигать заранее известно.

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

Можно ли сделать лучше, чем использование атомного приращения, чтобы отслеживать значение counter, если я знаю, что он монотонен и конечное значение известно?

Answer 1

Вы можете сделать это с помощью атомной операции CAS (сравните смену ans). На архитектуре i386 это инструкция CMPXCHG. При необходимости вы можете использовать небольшую функцию сборки, внедрять CAS на своей платформе или задать мне о внедрении Intel. Ваш код должен быть следующим:

int local_cnt; 
// Atomic increment counter 
do { 
    local_cnt = counter; 
} while(cas(&counter, local_cnt, local_cnt + 1) != local_cnt); 

// check old counter value 
if(local_cnt == CHECK_VALUE) { 
    // do something 
} 

Answer 2

без синхронизации, то возможно, что счетчик будет оставаться застрял в 0. На самом деле это не будет иметь, что состояние гонки почти так часто, так что счетчик будет примерно точно. Я думаю, вы можете доказать, что в последовательности счетчиков не будет пропущено никакого значения: нельзя изменить счетчик на 2, если он не был ранее 1, что относится ко всем значениям, которые может иметь счетчик. Таким образом, глобальный счетчик, использующий ++ вместо атомного приращения, будет работать, если будет нормально пропустить несколько событий. Однако, даже несинхронизированный, это все равно вызовет некоторые проблемы с памятью, которые вы хотите избежать (пересинхронизация строк кэша по процессорам).

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

Другой способ, которым вы могли бы это сделать, - обрезать внутренний счетчик в данных потока, а когда он достиг 10, ударьте глобальный счетчик. Это сократило бы # глобальных приращений на 10.

Другим способом было бы вырезать внутренний счетчик в потоке. Выполняйте синхронизацию всякий раз, когда отдельный поток достиг cEvents/threadcount.

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

Существует множество способов делать подобные вещи с помощью личных счетчиков. Все зависит от требуемой точности.