Стоимость атомных счетчиков и шпиндельных блоков на x86 (_64)

Введение

Недавно я столкнулся с некоторыми проблемами синхронизации, которые привели меня к spinlocks и атомным счетчикам. Затем я искал немного больше, как они работают, и нашел std:: memory_order и барьеры памяти (mfence, lfence и sfence).

Итак, кажется, что я использую приобретать/выпускать для спин-локов и расслабленной для счетчиков.

Некоторая ссылка

x86 MFENCE - Забор памяти
x86 LOCK - Сигнал подтверждения LOCK #

Вопрос

Что такое машинный код (отредактируйте: см. ниже) для этих трех операций (lock = test_and_set, unlock = clear, increment = operator ++= fetch_add) со значением по умолчанию (seq_cst) и с приобретением/выпуском/расслаблением (в этом порядке для этих трех операций). Какая разница (какие барьеры памяти где) и стоимость (сколько циклов процессора)?

Цель

Мне просто интересно, насколько плохо мой старый код (не указывая порядок памяти = seq_cst), и если я должен создать некоторый class atomic_counter, полученный из std::atomic, но используя расслабленное упорядочение памяти ( а также хорошую спин-блокировку с приобретением/выпуском вместо мьютексов в некоторых местах... или использовать что-то из ускорительной библиотеки - я до сих пор избегал повышения).

Мои знания

До сих пор я понимаю, что spinlocks защищает больше, чем он сам (но также и общий ресурс/память), поэтому должно быть что-то, что делает некоторый вид памяти согласованным для нескольких потоков/ядер (это будут те, которые приобретают/выпускают и заборы памяти). Атомный счетчик просто живет для себя и нуждается только в этом атомарном приращении (никакой другой памяти не задействован, и я действительно не забочусь о значении, когда я его читаю, он информативен и может быть несколько циклов старый, без проблем). Существует префикс LOCK, и некоторые инструкции, такие как xchg, неявно имеют его. Здесь мои знания заканчиваются, я не знаю, как работают кеш и шины, и что стоит (но я знаю, что современные процессоры могут изменять порядок инструкций, выполнять их параллельно и использовать кеш памяти и некоторую синхронизацию). Спасибо за объяснение.

PS: У меня есть старый 32-битный компьютер, теперь можно видеть только lock addl и простой xchg, ничего другого - все версии выглядят одинаково (кроме разблокировки), memory_order не имеет никакого значения для моего старый компьютер (кроме разблокировки, релиз использует move вместо xchg). Это будет верно для 64-битного ПК? (изменить: см. ниже) Должен ли я заботиться о порядке памяти? (ответ: нет, не много, релиз на разблокировке сохраняет несколько циклов, все).

Код:

#include <atomic>
using namespace std;

atomic_flag spinlock;
atomic<int> counter;

void inc1() {
    counter++;
}
void inc2() {
    counter.fetch_add(1, memory_order_relaxed);
}
void lock1() {
    while(spinlock.test_and_set()) ;
}
void lock2() {
    while(spinlock.test_and_set(memory_order_acquire)) ;
}
void unlock1() {
    spinlock.clear();
}
void unlock2() {
    spinlock.clear(memory_order_release);
}

int main() {
    inc1();
    inc2();
    lock1();
    unlock1();
    lock2();
    unlock2();
}

g++ -std = С++ 11 -O1 -S ( 32-разрядный Cygwin, сокращенный вывод)

__Z4inc1v:
__Z4inc2v:
    lock addl   $1, _counter    ; both seq_cst and relaxed
    ret
__Z5lock1v:
__Z5lock2v:
    movl    $1, %edx
L5:
    movl    %edx, %eax
    xchgb   _spinlock, %al      ; both seq_cst and acquire
    testb   %al, %al
    jne L5
    rep ret
__Z7unlock1v:
    movl    $0, %eax
    xchgb   _spinlock, %al      ; seq_cst
    ret
__Z7unlock2v:
    movb    $0, _spinlock       ; release
    ret

ОБНОВЛЕНИЕ для x86_64bit: (см. `mfence` в `unlock1`)

_Z4inc1v:
_Z4inc2v:
    lock addl   $1, counter(%rip)   ; both seq_cst and relaxed
    ret
_Z5lock1v:
_Z5lock2v:
    movl    $1, %edx
.L5:
    movl    %edx, %eax
    xchgb   spinlock(%rip), %al     ; both seq_cst and acquire
    testb   %al, %al
    jne .L5
    ret
_Z7unlock1v:
    movb    $0, spinlock(%rip)
    mfence                          ; seq_cst
    ret
_Z7unlock2v:
    movb    $0, spinlock(%rip)      ; release
    ret

Ответы

Ответ 1

x86 имеет в основном сильную модель памяти, все обычные магазины/нагрузки имеют раздельно/приобретают семантику неявно. Исключением являются только операции хранения невременного хранилища SSE, которые требуют, чтобы sfence заказывался, как обычно. Все инструкции read-modify-write (RMW) с префиксом LOCK подразумевают полный барьер памяти, т.е. Seq_cst.

Таким образом, на x86 имеем

test_and_set можно закодировать с помощью lock bts (для бит-мерных операций), lock cmpxchg или lock xchg (или просто xchg, что подразумевает LOCK). Другие реализации спин-блокировки могут использовать инструкции, такие как lock inc (или dec), если они нуждаются, например. справедливости. Невозможно реализовать try_lock с выпуском/приобретением забора (по крайней мере, вам понадобится автономный барьер памяти mfence).
clear закодирован с lock and (по-бит) или lock xchg, однако более эффективные реализации будут использовать обычную запись (mov) вместо заблокированной инструкции.
fetch_add закодирован с помощью lock add.

Удаление префикса LOCK не гарантирует атомарности для операций RMW, поэтому такие операции не могут быть интерпретированы строго как имеющие memory_order_relaxed в представлении С++. Однако на практике вам может потребоваться доступ к атомной переменной через более быструю неатомную операцию, когда она безопасна (в конструкторе, под блокировкой).

В нашем опыте на самом деле не имеет значения, какая именно атомная операция RMW выполняется, они принимают почти одинаковое количество циклов для выполнения (и mfence - около x0.5 операции блокировки). Вы можете оценить производительность алгоритмов синхронизации, подсчитав количество атомных операций (и mfences) и количество каналов памяти (промахи в кэше).

Ответ 2

Ваши x86 и x86_64 действительно очень "хорошо себя ведут". В частности, они не переупорядочивают операции записи (и любые спекулятивные записи отбрасываются, когда они находятся в очереди записи процессора/ядра), и они не переупорядочивают операции чтения. Тем не менее, они начнут операции чтения как можно раньше, а это значит, что чтение и запись могут быть переупорядочены. (Чтение чего-либо, сидящего в очереди записи, считывает значение в очереди, поэтому чтение/запись того же местоположения не переупорядочено.) Итак:

Операции
read-modify-write требуют LOCK, что делает их неявным образом memory_order_seq_cst.

Итак, для этих операций вы ничего не получаете, ослабляя порядок памяти (на x86/x86_64). Общий совет - "держать его простым" и придерживаться memory_order_seq_cst, который, к счастью, не стоит ничего лишнего для x86 и x86_64.

Для чего-либо более нового, чем Pentium, если процессор/ядро уже имеет "исключительный" доступ к затронутой памяти, LOCK не влияет на другие cpus/core и может быть относительно простой операцией.
memory_order_acquire/_release не требуют mfence или любые другие служебные данные.

Итак, для атомной нагрузки/хранения, если получение/освобождение является достаточным, то для x86/x86_64 эти операции "не облагаются налогом".
memory_order_seq_cst требует mfence...

..., который стоит понять.

(NB: мы здесь говорим о том, что делает процессор с инструкциями, сгенерированными компилятором. Переупорядочение операций компилятором очень похоже на проблему, но не рассматривается здесь.)

An mfence останавливает процессор/ядро, пока все ожидающие записи не будут удалены из очереди на запись. В частности, любые операции чтения, которые следуют за mfence, не будут запускаться, пока очередь записи не будет пустой. Рассмотрим два потока:

  initial state: wa = wb = 0

  thread 'A'                    thread 'B'
    wa = 1 ;  (mov [wa] ← 1)      wb = 1 ;   (mov [wb] ← 1)
    a  = wb ; (mov ebx ← [wb])    b  = wa ;  (mov ebx ← [wa])

Оставаясь на своих устройствах, x86/x86_64 может производить любой из (a = 1, b = 1), (a = 0, b = 1), (a = 1, b = 0) и (a = 0, b = 0). Последнее недействительно, если вы ожидаете memory_order_seq_cst - поскольку вы не можете получить это путем чередования операций. Причина, по которой это может произойти, заключается в том, что записи wa и wb помещаются в очередь в соответствующей очереди процессора/ядра, а чтение wa и wb может быть запланировано и может быть завершено до записи. Для достижения памяти_order_seq_cst вам понадобится mfence:

  thread 'A'                    thread 'B'
    wa = 1 ;  (mov [wa] ← 1)      wb = 1 ;   (mov [wb] ← 1)
        mfence ;                      mfence
    a  = wb ; (mov ebx ← [wb])    b  = wa ;  (mov ebx ← [wa])

Поскольку между потоками нет синхронизации, результатом может быть что угодно, кроме (a = 0, b = 0). Интересно, что mfence предназначен для самого потока, поскольку он предотвращает операцию чтения, начинающуюся до завершения записи. Единственное, что беспокоит другие темы, это порядок, в котором происходит запись, а x86/x86_64 не переупорядочивает их в любом случае.

Итак, чтобы реализовать memory_order_seq_cst atomic_load() и atomic_store(), необходимо вставить mfence после одного или нескольких хранилищ и до загрузки. Если эти операции реализованы как функции библиотеки, общим соглашением является добавление mfence во все магазины, оставив нагрузку "голым". (Логика заключается в том, что нагрузки более распространены, чем магазины, и кажется, что лучше добавить накладные расходы в хранилище.)

Для спин-замков, по крайней мере, ваш вопрос, похоже, сводится к тому, что операция с разблокировкой требует mfence, или нет, и какая разница.

C11 atomic_flag_clear(), неявно, memory_order_seq_cst, для которого требуется mfence. C11 atomic_flag_test_and_set() является не только операцией чтения-изменения-записи, но также подразумевается memory_order_seq_cst - и LOCK делает это.

C11 не предлагает прямую блокировку в библиотеке threads.h. Но вы можете использовать atomic_flag - хотя для вашей x86/x86_64 у вас есть проблема с инструкцией PAUSE. Вопрос в том, нужна ли вам память_order_seq_cst для этого, в частности для разблокировки? Я думаю, что ответ отрицательный, и что трюк должен сделать: atomic_flag_test_and_set_explicit(xxx, memory_order_acquire) и atomic_flag_clear(xxx, memory_order_release).

FWIW, glibc pthread_spin_unlock() не имеет mfence. Также не работает gcc __sync_lock_release() (который явно является операцией "release" ). Но gcc _atomic_clear() выровнена с C11 atomic_flag_clear() и принимает параметр порядка памяти.

Чем отличается mfence от разблокировки? Понятно, что это очень разрушительно для трубопровода, и поскольку это не обязательно, не нужно многого выработать точный масштаб его воздействия, который будет зависеть от обстоятельств.

Ответ 3

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

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

Очень простой и немой spinlock для x86 выглядит так (мое ядро использует это):

typedef volatile uint32_t _SPINLOCK __attribute__ ((aligned(16)));
static inline void _SPIN_LOCK(_SPINLOCK* lock) {
__asm (
       "cli\n"
       "lock bts %0, 0\n"
       "jnc 1f\n"
       "0:\n"
       "pause\n"
       "test %0, 1\n"
       "je 0b\n"
       "lock bts %0, 0\n"
       "jc 0b\n"
       "1:\n"
       :
       : "m"(lock)
       :
       );
}

Логика проста

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

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

Примечание 2. Spinlock не судит по циклам, разумная реализация должна быть довольно быстрой, для мгновенной реализации выше вы должны захватить блокировку при первой попытке в хорошо спроектированном использовании, если нет, исправить алгоритм или разделить блокировку для предотвращения/сокращения блокировки.

Примечание 3. Вы должны также рассмотреть другие вещи, такие как справедливость.

Ответ 4

и стоимость (сколько циклов процессора)?

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

Например, если атомный op прямо после memcpy(), который выталкивает несколько строк кэша в основную память, задержка может быть в 100 наносекунд. Один и тот же атомный op, но после серии арифметических команд только для регистров может занимать всего несколько тактов.