Стоимость атомных счетчиков и спинлок на x86 (_64)
Предисловие
Недавно я столкнулся с некоторыми проблемами синхронизации, которые привели меня к Взаимные блокировки а также атомные счетчики. Потом я искал немного больше, как эти работы и нашел станд :: memory_order и барьеры памяти (mfence, lfence а также sfence).
Так что теперь, кажется, я должен использовать приобретение / выпуск для спинлоков и расслабленный для счетчиков.
Некоторая ссылка
x86 MFENCE — Ограждение памяти
x86 LOCK — Assert LOCK # Сигнал
Вопрос
Что такое машинный код (редактировать: см. ниже) для этих трех операций (блокировка = test_and_set, разблокировать = Чисто, приращение = оператор ++ знак равно fetch_add) по умолчанию (seq_cst) порядок памяти и с приобретением / выпуском / расслаблением (в таком порядке для этих трех операций). В чем разница (какие барьеры памяти где) и стоимость (сколько циклов процессора)?
Цель
Мне просто интересно, насколько плох мой старый код (без указания порядка памяти = используется seq_cst) на самом деле, и если я должен создать некоторые class atomic_counter происходит от std::atomic но используя упорядоченный порядок памяти (а также хорошая спин-блокировка с acqu / release вместо мьютексов в некоторых местах … или использовать что-то из библиотеки boost — я пока избегал boost).
Мои знания
До сих пор я понимаю, что спин-блокировки защищают больше, чем себя (но некоторый общий ресурс / память также), поэтому должно быть что-то, что делает некоторое представление памяти связным для нескольких потоков / ядер (это будут те ограждения на приобретение / выпуск и память). Атомный счетчик просто живет для себя и нуждается только в том атомном приращении (никакая другая память не задействована, и я не особо беспокоюсь о значении, когда читаю его, оно информативно и может иметь несколько циклов, не проблема). Существует некоторая LOCK префикс и некоторые инструкции, такие как xchg неявно иметь это. На этом мои знания заканчиваются, я не знаю, как на самом деле работают кеш и шины и что стоит за ними (но я знаю, что современные процессоры могут переупорядочивать инструкции, выполнять их параллельно и использовать кэш-память и некоторую синхронизацию). Спасибо за объяснение.
P.S .: У меня сейчас старый 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 = c ++ 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
Решение
х86 имеет в основном сильная модель памяти, все обычные хранилища / загрузки имеют неявную семантику выпуска / приобретения. Исключение составляют только временные операции хранения SSE, которые требуют sfence быть заказанным как обычно. Все инструкции чтения-изменения-записи (RMW) с LOCK префикс подразумевает полный барьер памяти, то есть seq_cst.
Таким образом, на x86 мы имеем
test_and_setможет быть закодирован сlock bts(для побитовых операций),lock cmpxchg, или жеlock xchg(или простоxchgчто подразумеваетlock). Другие реализации спин-блокировки могут использовать такие инструкции, какlock inc(или декабрь), если им нужно, например, справедливости. Невозможно реализоватьtry_lockс ограждением освобождения / приобретения (по крайней мере, вам понадобится автономный барьер памятиmfenceтем не мение).clearзакодировано сlock and(для побитового) илиlock xchg, хотя, более эффективные реализации будут использовать обычную запись (mov) вместо заблокированной инструкции.fetch_addзакодировано сlock add.
Удаление lock префикс не гарантирует атомарности для операций RMW, поэтому такие операции нельзя интерпретировать строго как memory_order_relaxed в представлении C ++. Однако на практике вы можете захотеть получить доступ к атомарной переменной с помощью более быстрой неатомарной операции, когда она безопасна (в конструкторе, под блокировкой).
По нашему опыту, на самом деле не имеет значения, какая именно атомарная операция RMW выполняется, они выполняют почти одинаковое количество циклов (а mfence составляет около х0,5 от операции блокировки). Вы можете оценить производительность алгоритмов синхронизации, посчитав количество атомарных операций (и mfences) и количество косвенных обращений к памяти (пропуски кэша).
Другие решения
Рекомендую: x86-TSO: модель строгого и полезного программиста для мультипроцессоров x86.
Ваши x86 и x86_64 действительно «хорошо себя ведут». В частности, они делают не переупорядочить операции записи (и любые спекулятивные записи отбрасываются, когда они находятся в очереди записи процессора / ядра), и они делают не переупорядочить операции чтения. Тем не менее, они начнут операции чтения как можно раньше, что означает, что чтение и запись Можно быть переупорядочен. (Чтение чего-либо, находящегося в очереди записи, читает значение в очереди, поэтому чтение / запись то же место являются не переоформлен.) Итак:
-
операции чтения-изменения-записи требуют
LOCKs, что делает их, неявно, memory_order_seq_cst.Поэтому для этих операций вы ничего не получите, ослабив порядок в памяти (на x86 / x86_64). Общий совет — «будь проще» и придерживайся memory_order_seq_cst, что, к счастью, ничего не стоит для x86 и x86_64.
Для чего-то более нового, чем Pentium, если процессор / ядро уже имеет «эксклюзивный» доступ к затронутой памяти,
LOCKне влияет на другие процессоры / ядра и может быть относительно простой операцией. -
memory_order_acquire / _Release не требует
mfenceили любые другие накладные расходы.Таким образом, для атомарной загрузки / хранения, если приобретения / выпуска достаточно, то для x86 / x86_64 эти операции не облагаются налогом.
-
memory_order_seq_cst действительно требует
mfence…
…что стоит понять.
(NB: мы здесь говорим о том, что процессор делает с инструкциями, сгенерированными компилятором. Переупорядочение операций компилятора — очень похожая проблема, но здесь она не рассматривается.)
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) а также (а = 0, б = 0). Последний недействительным если вы ожидаете memory_order_seq_cst — поскольку вы не можете получить это путем чередования операций. Причина этого может заключаться в том, что записи wa а также wb ставятся в очередь в очереди соответствующего процессора / ядра, и читает wa а также wb оба могут быть запланированы, и оба могут завершиться, прежде чем писать. Достигать memory_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])
Поскольку между потоками нет синхронизации, результатом может быть что угодно Кроме (а = 0, б = 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 проблема обучения, чтобы иметь дело с. Вопрос в том, необходимость memory_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() (что явно является операцией «освобождения»). Но GCC _atomic_clear() выровнен с C11 atomic_flag_clear()и принимает параметр порядка памяти.
Какая разница mfence сделать чтобы разблокировать? Понятно, что это очень разрушительно для трубопровода, и, поскольку в этом нет необходимости, мало что можно извлечь из точного масштаба его воздействия, которое будет зависеть от обстоятельств.
spinlock не использует mfence, mfence только обеспечивает сериализацию / сброс данных текущего ядра. Сам забор никоим образом не относится к атомной эксплуатации.
Для спин-блокировки вам нужно какое-то атомарное действие для обмена данными с местом в памяти. Существует много разных реализаций, нацеленных на разные требования: например, работает ли оно на ядре или в пространстве пользователя? это справедливая блокировка?
Очень простой и тупой спинлок для 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. Вам также следует учитывать и другие вещи, такие как справедливость.
ре
и стоимость (сколько циклов процессора)?
По крайней мере, на x86 инструкции, выполняющие синхронизацию памяти (атомарные операции, ограждения), имеют очень переменную задержку цикла ЦП. Они ждут, чтобы буферы хранилища процессора были сброшены в память, и это резко меняется в зависимости от содержимого буфера хранилища.
Например, если атомная операция идет сразу после memcpy() что выталкивает несколько строк кэша в основную память, задержка может быть в сотнях наносекунд. Тот же атомарный оператор, но после ряда арифметических инструкций только для регистра, может занять всего несколько тактов.