当内存排序放宽时,C++ 延迟会增加
C++ latency increases when memory ordering is relaxed
我正在 Windows 7 64 位 VS2013(x64 发布版本)试验内存排序。我想使用最快的同步来共享对容器的访问。我选择了原子比较和交换。
我的程序产生了两个线程。作者推送到向量,reader 检测到这一点。
最初我没有指定任何内存顺序,所以我假设它使用 memory_order_seq_cst
?
对于 memory_order_seq_cst
,每个操作的延迟为 340-380 个周期。
为了尝试提高性能,我让存储使用 memory_order_release
,加载使用 memory_order_acquire
。
但是,每个操作的延迟增加到大约 1,940 个周期。
我是不是误会了什么?完整代码如下。
使用默认 memory_order_seq_cst
:
#include <iostream>
#include <atomic>
#include <thread>
#include <vector>
std::atomic<bool> _lock{ false };
std::vector<uint64_t> _vec;
std::atomic<uint64_t> _total{ 0 };
std::atomic<uint64_t> _counter{ 0 };
static const uint64_t LIMIT = 1000000;
void writer()
{
while (_counter < LIMIT)
{
bool expected{ false };
bool val = true;
if (_lock.compare_exchange_weak(expected, val))
{
_vec.push_back(__rdtsc());
_lock = false;
}
}
}
void reader()
{
while (_counter < LIMIT)
{
bool expected{ false };
bool val = true;
if (_lock.compare_exchange_weak(expected, val))
{
if (_vec.empty() == false)
{
const uint64_t latency = __rdtsc() - _vec[0];
_total += (latency);
++_counter;
_vec.clear();
}
_lock = false;
}
}
}
int main()
{
std::thread t1(writer);
std::thread t2(reader);
t2.detach();
t1.join();
std::cout << _total / _counter << " cycles per op" << std::endl;
}
使用 memory_order_acquire
和 memory_order_release
:
void writer()
{
while (_counter < LIMIT)
{
bool expected{ false };
bool val = true;
if (_lock.compare_exchange_weak(expected, val, std::memory_order_acquire))
{
_vec.push_back(__rdtsc());
_lock.store(false, std::memory_order_release);
}
}
}
void reader()
{
while (_counter < LIMIT)
{
bool expected{ false };
bool val = true;
if (_lock.compare_exchange_weak(expected, val, std::memory_order_acquire))
{
if (_vec.empty() == false)
{
const uint64_t latency = __rdtsc() - _vec[0];
_total += (latency);
++_counter;
_vec.clear();
}
_lock.store(false, std::memory_order_release);
}
}
}
你没有任何保护措施来防止线程在释放锁后立即再次获取锁,只是发现 _vec.empty()
是 not false,或者存储另一个TSC 值,覆盖 reader 从未见过的值。 我怀疑您的更改让 reader 浪费更多时间来阻止编写器(反之亦然),从而导致实际吞吐量减少。
TL:DR: 真正的问题是你的锁定缺乏公平性(对于刚刚解锁的线程来说太容易成为赢得比赛的线程再次锁定它),以及你使用它的方式锁。 (你必须先拿下它,然后才能确定是否有任何有用的事情要做,迫使另一个线程重试,并导致核心之间缓存行的额外传输。)
让一个线程重新获取锁而另一个线程没有轮到总是无用并且浪费工作,不像许多实际情况需要更多重复来填充或清空队列。这是一个糟糕的生产者-消费者算法(队列太小(大小 1),and/or reader 在读取 vec[0]
后丢弃所有向量元素),以及最糟糕的锁定方案。
_lock.store(false, seq_cst);
编译为 xchg
而不是普通的 mov
存储。
它必须等待存储缓冲区耗尽并且速度很慢1(例如,在 Skylake 上,微编码为 8 微码,每 23 个周期的吞吐量对于许多重复的 back-to-返回操作,在 L1d 缓存中已经很热的无争用情况下。您没有指定任何关于您拥有的硬件)。
_lock.store(false, std::memory_order_release);
只是编译成一个普通的 mov
存储,没有额外的屏障指令。因此 _counter
的重新加载可以与其并行发生(尽管分支预测 + 推测执行使这不是问题)。更重要的是,下一次 CAS 尝试拿锁实际上可以更快地尝试。
当多个内核在高速缓存行上进行访问时,存在硬件仲裁来访问它,大概是通过一些公平启发式算法,但我不知道细节是否已知。
脚注 1:在最近的一些 CPU 中,xchg
不如 mov
+mfence
慢,尤其是 Skylake 派生的 CPUs。这是在 x86 上实现 seq_cst 纯存储的最佳方式。但它比普通的 mov
.
慢
你可以通过让你的锁力交替写入器来完全解决/ reader
Writer 等待 false
,然后在完成后存储 true
。 Reader 则相反。因此,如果其他线程没有轮到,作者永远无法重新进入临界区。 (当你 "wait for a value" 以只读方式加载时,而不是 CAS。x86 上的 CAS 需要缓存行的独占所有权,防止其他线程读取。只有一个 reader 和一个作者,你不需要任何原子 RMW 就可以工作。)
如果您有多个 reader 和多个编写器,您可以有一个 4 状态同步变量,其中一个编写器尝试将其从 0 转换为 1,然后在完成后存储 2。 Reader尝试从 2 到 3 CAS,完成后存储 0。
SPSC(单一生产者单一消费者)案例很简单:
enum lockstates { LK_WRITER=0, LK_READER=1, LK_EXIT=2 };
std::atomic<lockstates> shared_lock;
uint64_t shared_queue; // single entry
uint64_t global_total{ 0 }, global_counter{ 0 };
static const uint64_t LIMIT = 1000000;
void writer()
{
while(1) {
enum lockstates lk;
while ((lk = shared_lock.load(std::memory_order_acquire)) != LK_WRITER) {
if (lk == LK_EXIT)
return;
else
SPIN; // _mm_pause() or empty
}
//_vec.push_back(__rdtsc());
shared_queue = __rdtsc();
shared_lock.store(LK_READER, ORDER); // seq_cst or release
}
}
void reader()
{
uint64_t total=0, counter=0;
while(1) {
enum lockstates lk;
while ((lk = shared_lock.load(std::memory_order_acquire)) != LK_READER) {
SPIN; // _mm_pause() or empty
}
const uint64_t latency = __rdtsc() - shared_queue; // _vec[0];
//_vec.clear();
total += latency;
++counter;
if (counter < LIMIT) {
shared_lock.store(LK_WRITER, ORDER);
}else{
break; // must avoid storing a LK_WRITER right before LK_EXIT, otherwise writer races and can overwrite with LK_READER
}
}
global_total = total;
global_counter = counter;
shared_lock.store(LK_EXIT, ORDER);
}
Full version on Godbolt。在我的 i7-6700k Skylake 台式机上(2 核 Turbo = 4200MHz,TSC = 4008MHz),使用 clang++ 9.0.1 -O3
编译。正如预期的那样,数据非常嘈杂;我做了一堆 运行s 并手动选择了一个低点和高点,忽略了一些可能由于热身效应而导致的实际异常高点。
在单独的物理内核上:
-DSPIN='_mm_pause()' -DORDER=std::memory_order_release
:~180 到~210 个周期/op,基本上为零 machine_clears.memory_ordering
(比如 19
总共超过 1000000 ops,这要归功于 pause
在自旋中等待循环。)
-DSPIN='_mm_pause()' -DORDER=std::memory_order_seq_cst
:~195 到~215 个参考周期/操作,相同的近零机器清除。
-DSPIN='' -DORDER=std::memory_order_release
: ~195 到 ~225 ref c/op, 9 到 10 M/sec 机器清除没有 pause
.
-DSPIN='' -DORDER=std::memory_order_seq_cst
:变化更大,速度更慢,~250 到~315 c/op,8 到 10 M/sec 机器清除没有 pause
这些时间比我系统上 seq_cst
"fast" 的原始时间快 3 倍 。使用 std::vector<>
而不是标量可能占其中的约 4 个周期;我认为当我更换它时会有轻微的影响。不过,也许只是随机噪音。 200 / 4.008GHz 大约是 50ns 内核间延迟,这听起来适合四核 "client" 芯片。
从最佳版本(mo_release,在 pause
上旋转以避免机器清除):
$ clang++ -Wall -g -DSPIN='_mm_pause()' -DORDER=std::memory_order_release -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r4 ./a.out
195 ref cycles per op. total ticks: 195973463 / 1000000 ops
189 ref cycles per op. total ticks: 189439761 / 1000000 ops
193 ref cycles per op. total ticks: 193271479 / 1000000 ops
198 ref cycles per op. total ticks: 198413469 / 1000000 ops
Performance counter stats for './a.out' (4 runs):
199.83 msec task-clock:u # 1.985 CPUs utilized ( +- 1.23% )
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
128 page-faults # 0.643 K/sec ( +- 0.39% )
825,876,682 cycles:u # 4.133 GHz ( +- 1.26% )
10,680,088 branches:u # 53.445 M/sec ( +- 0.66% )
44,754,875 instructions:u # 0.05 insn per cycle ( +- 0.54% )
106,208,704 uops_issued.any:u # 531.491 M/sec ( +- 1.07% )
78,593,440 uops_executed.thread:u # 393.298 M/sec ( +- 0.60% )
19 machine_clears.memory_ordering # 0.094 K/sec ( +- 3.36% )
0.10067 +- 0.00123 seconds time elapsed ( +- 1.22% )
从最差的版本开始(mo_seq_cst,没有pause
):自旋等待循环旋转得更快,所以分支和微指令issued/executed要高得多,但实际有用的吞吐量有点差。
$ clang++ -Wall -g -DSPIN='' -DORDER=std::memory_order_seq_cst -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r4 ./a.out
280 ref cycles per op. total ticks: 280529403 / 1000000 ops
215 ref cycles per op. total ticks: 215763699 / 1000000 ops
282 ref cycles per op. total ticks: 282170615 / 1000000 ops
174 ref cycles per op. total ticks: 174261685 / 1000000 ops
Performance counter stats for './a.out' (4 runs):
207.82 msec task-clock:u # 1.985 CPUs utilized ( +- 4.42% )
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
130 page-faults # 0.623 K/sec ( +- 0.67% )
857,989,286 cycles:u # 4.129 GHz ( +- 4.57% )
236,364,970 branches:u # 1137.362 M/sec ( +- 2.50% )
630,960,629 instructions:u # 0.74 insn per cycle ( +- 2.75% )
812,986,840 uops_issued.any:u # 3912.003 M/sec ( +- 5.98% )
637,070,771 uops_executed.thread:u # 3065.514 M/sec ( +- 4.51% )
1,565,106 machine_clears.memory_ordering # 7.531 M/sec ( +- 20.07% )
0.10468 +- 0.00459 seconds time elapsed ( +- 4.38% )
将 reader 和 writer 都固定到一个物理内核的逻辑内核上,可以加快 lot: 在我的系统,核心 3 和 7 是兄弟,所以 Linux taskset -c 3,7 ./a.out
阻止内核将它们调度到其他任何地方:每个操作 33 到 39 个引用周期,或者 80 到 82 没有 pause
.
(,)
$ clang++ -Wall -g -DSPIN='_mm_pause()' -DORDER=std::memory_order_release -O3 inter-thread.cpp -pthread &&
taskset -c 3,7 perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r4 ./a.out
39 ref cycles per op. total ticks: 39085983 / 1000000 ops
37 ref cycles per op. total ticks: 37279590 / 1000000 ops
36 ref cycles per op. total ticks: 36663809 / 1000000 ops
33 ref cycles per op. total ticks: 33546524 / 1000000 ops
Performance counter stats for './a.out' (4 runs):
89.10 msec task-clock:u # 1.942 CPUs utilized ( +- 1.77% )
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
128 page-faults # 0.001 M/sec ( +- 0.45% )
365,711,339 cycles:u # 4.104 GHz ( +- 1.66% )
7,658,957 branches:u # 85.958 M/sec ( +- 0.67% )
34,693,352 instructions:u # 0.09 insn per cycle ( +- 0.53% )
84,261,390 uops_issued.any:u # 945.680 M/sec ( +- 0.45% )
71,114,444 uops_executed.thread:u # 798.130 M/sec ( +- 0.16% )
16 machine_clears.memory_ordering # 0.182 K/sec ( +- 1.54% )
0.04589 +- 0.00138 seconds time elapsed ( +- 3.01% )
在共享同一物理内核的逻辑内核上。最好的情况是延迟比内核之间低 5 倍,同样是暂停 + mo_release。但实际基准只完成了 40% 的时间,而不是 20%
-DSPIN='_mm_pause()' -DORDER=std::memory_order_release
:~33 到~39 个参考周期/op,接近零 machine_clears.memory_ordering
-DSPIN='_mm_pause()' -DORDER=std::memory_order_seq_cst
:~111 到~113 个引用周期/op,总共 19 个机器清除。出乎意料的最差!
-DSPIN='' -DORDER=std::memory_order_release
:~81 到~84 ref cycles/op,~12.5 M 机器清除/秒
-DSPIN='' -DORDER=std::memory_order_seq_cst
: ~94 到 ~96 c/op, 5 M/sec 机器清除没有 pause
.
所有这些测试都与 clang++
一起使用 xchg
用于 seq_cst 商店。 g++
使用 mov
+mfence
在 pause
的情况下速度较慢,在没有 pause
的情况下速度更快并且机器清除更少。 (对于超线程情况。)通常与 pause
的独立核心情况非常相似,但在没有 pause
的情况下,seq_cst 的独立核心情况更快。 (同样,特别是在 Skylake 上,针对这一测试。)
原版更多调查:
还值得检查性能计数器 machine_clears.memory_ordering
().
我确实检查了我的 Skylake i7-6700k,每秒 machine_clears.memory_ordering
的速率没有显着差异(快速 seq_cst 和慢速大约 5M / 秒发布),在 4.2GHz。
"cycles per op" 结果与 seq_cst 版本(400 到 422)惊人地一致。我的 CPU 的 TSC 参考频率是 4008MHz,最大睿频时的实际核心频率是 4200MHz。如果你有 340-380 周期,我假设你的 CPU 的最大涡轮相对于它的参考频率比我的更高。 And/or 不同的微架构。
但我发现 mo_release
版本的结果各不相同:在 Arch GNU/Linux 上使用 GCC9.3.0 -O3
:5790 个运行,另一个是2269。使用 clang9.0.1 -O3
73346 和 7333 两个 运行s,是的,确实是 10 倍)。这是一个惊喜。当清空/推送向量时,这两个版本都没有对 free/allocate 内存进行系统调用,而且我没有看到从 clang 版本中清除很多内存排序机器。使用您的原始 LIMIT,两个 运行s with clang 显示每个操作有 1394 和 22101 个周期。
使用 clang++,甚至 seq_cst 时间的变化也比 GCC 多一些,并且更高,例如 630 到 700。(g++ 使用 mov
+mfence
for seq_cst 纯商店,clang++ 使用 xchg
就像 MSVC 一样)。
其他具有 mo_release
的性能计数器显示出类似的指令、分支和每秒 uops 的速率,所以我认为这表明代码只是花费更多时间在错误的线程上旋转它的轮子关键部分和另一个卡住重试。
两个perf 运行s,第一个是mo_release,第二个是mo_seq_cst.
$ clang++ -DORDER=std::memory_order_release -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r1 ./a.out
27989 cycles per op
Performance counter stats for './a.out':
16,350.66 msec task-clock:u # 2.000 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
231 page-faults # 0.014 K/sec
67,412,606,699 cycles:u # 4.123 GHz
697,024,141 branches:u # 42.630 M/sec
3,090,238,185 instructions:u # 0.05 insn per cycle
35,317,247,745 uops_issued.any:u # 2159.989 M/sec
17,580,390,316 uops_executed.thread:u # 1075.210 M/sec
125,365,500 machine_clears.memory_ordering # 7.667 M/sec
8.176141807 seconds time elapsed
16.342571000 seconds user
0.000000000 seconds sys
$ clang++ -DORDER=std::memory_order_seq_cst -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r1 ./a.out
779 cycles per op
Performance counter stats for './a.out':
875.59 msec task-clock:u # 1.996 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
137 page-faults # 0.156 K/sec
3,619,660,607 cycles:u # 4.134 GHz
28,100,896 branches:u # 32.094 M/sec
114,893,965 instructions:u # 0.03 insn per cycle
1,956,774,777 uops_issued.any:u # 2234.806 M/sec
1,030,510,882 uops_executed.thread:u # 1176.932 M/sec
8,869,793 machine_clears.memory_ordering # 10.130 M/sec
0.438589812 seconds time elapsed
0.875432000 seconds user
0.000000000 seconds sys
我用内存顺序修改了你的代码作为 CPP 宏,所以你可以用 -DORDER=std::memory_order_release
编译以获得慢速版本。
acquire
与 seq_cst
在这里无关紧要;它在 x86 上针对负载和原子 RMW 编译为相同的 asm。只有纯商店需要 seq_cst.
的特殊 asm
您还遗漏了 stdint.h
和 intrin.h
(MSVC) / x86intrin.h
(其他所有内容)。固定版本为 on Godbolt with clang and MSVC。早些时候,我将 LIMIT 提高了 10 倍,以确保 CPU 频率有时间在大部分时间区域上升到最大涡轮增压,但恢复了该更改,因此测试 mo_release
只需要几秒钟, 不是分钟。
设置 LIMIT 以检查特定的总 TSC 周期可能有助于它在更一致的时间退出。这仍然不包括作者被锁定的时间,但总的来说应该 运行 花费极长时间的可能性较小。
如果您只是想测量线程间延迟,您还会遇到很多非常复杂的事情。
()
你有两个线程都读取作者每次更新的 _total
,而不是在完成后只存储一个标志。所以作者有潜在的内存排序机器从读取另一个线程写入的变量中清除。
您在 reader 中也有一个 _counter
的原子 RMW 增量,即使该变量是 reader 私有的。它可以是您在 reader.join()
之后读取的普通非原子全局变量,或者更好的是它可以是您仅在循环后存储到全局变量的局部变量。 (一个普通的非原子全局变量可能最终会在每次迭代时存储到内存中,而不是保存在寄存器中,因为发布存储。而且由于这是一个小程序,所有全局变量可能彼此相邻,并且可能在同一缓存行中。)
std::vector
也是不必要的。 __rdtsc()
不会为零,除非它绕过 64 位计数器 1,因此您可以只使用 0
作为标量 uint64_t
表示为空。或者,如果你修复了你的锁定,那么 reader 在没有轮到作者的情况下无法重新进入关键部分,你可以删除该检查。
脚注 2:对于 ~4GHz TSC 参考频率,即 2^64 / 10^9 秒,足够接近 2^32 秒 ~= 136 年环绕 TSC。注意TSC参考频率是不是当前核心时钟频率;对于给定的 CPU,它固定为某个值。通常接近额定 "sticker" 频率,而不是最大涡轮频率。
此外,以 _
开头的名称在 ISO C++ 中保留在全局范围内。不要将它们用于您自己的变量。 (通常不在任何地方。如果你真的想要,你可以使用尾随下划线。)
我正在 Windows 7 64 位 VS2013(x64 发布版本)试验内存排序。我想使用最快的同步来共享对容器的访问。我选择了原子比较和交换。
我的程序产生了两个线程。作者推送到向量,reader 检测到这一点。
最初我没有指定任何内存顺序,所以我假设它使用 memory_order_seq_cst
?
对于 memory_order_seq_cst
,每个操作的延迟为 340-380 个周期。
为了尝试提高性能,我让存储使用 memory_order_release
,加载使用 memory_order_acquire
。
但是,每个操作的延迟增加到大约 1,940 个周期。
我是不是误会了什么?完整代码如下。
使用默认 memory_order_seq_cst
:
#include <iostream>
#include <atomic>
#include <thread>
#include <vector>
std::atomic<bool> _lock{ false };
std::vector<uint64_t> _vec;
std::atomic<uint64_t> _total{ 0 };
std::atomic<uint64_t> _counter{ 0 };
static const uint64_t LIMIT = 1000000;
void writer()
{
while (_counter < LIMIT)
{
bool expected{ false };
bool val = true;
if (_lock.compare_exchange_weak(expected, val))
{
_vec.push_back(__rdtsc());
_lock = false;
}
}
}
void reader()
{
while (_counter < LIMIT)
{
bool expected{ false };
bool val = true;
if (_lock.compare_exchange_weak(expected, val))
{
if (_vec.empty() == false)
{
const uint64_t latency = __rdtsc() - _vec[0];
_total += (latency);
++_counter;
_vec.clear();
}
_lock = false;
}
}
}
int main()
{
std::thread t1(writer);
std::thread t2(reader);
t2.detach();
t1.join();
std::cout << _total / _counter << " cycles per op" << std::endl;
}
使用 memory_order_acquire
和 memory_order_release
:
void writer()
{
while (_counter < LIMIT)
{
bool expected{ false };
bool val = true;
if (_lock.compare_exchange_weak(expected, val, std::memory_order_acquire))
{
_vec.push_back(__rdtsc());
_lock.store(false, std::memory_order_release);
}
}
}
void reader()
{
while (_counter < LIMIT)
{
bool expected{ false };
bool val = true;
if (_lock.compare_exchange_weak(expected, val, std::memory_order_acquire))
{
if (_vec.empty() == false)
{
const uint64_t latency = __rdtsc() - _vec[0];
_total += (latency);
++_counter;
_vec.clear();
}
_lock.store(false, std::memory_order_release);
}
}
}
你没有任何保护措施来防止线程在释放锁后立即再次获取锁,只是发现 _vec.empty()
是 not false,或者存储另一个TSC 值,覆盖 reader 从未见过的值。 我怀疑您的更改让 reader 浪费更多时间来阻止编写器(反之亦然),从而导致实际吞吐量减少。
TL:DR: 真正的问题是你的锁定缺乏公平性(对于刚刚解锁的线程来说太容易成为赢得比赛的线程再次锁定它),以及你使用它的方式锁。 (你必须先拿下它,然后才能确定是否有任何有用的事情要做,迫使另一个线程重试,并导致核心之间缓存行的额外传输。)
让一个线程重新获取锁而另一个线程没有轮到总是无用并且浪费工作,不像许多实际情况需要更多重复来填充或清空队列。这是一个糟糕的生产者-消费者算法(队列太小(大小 1),and/or reader 在读取 vec[0]
后丢弃所有向量元素),以及最糟糕的锁定方案。
_lock.store(false, seq_cst);
编译为 xchg
而不是普通的 mov
存储。
它必须等待存储缓冲区耗尽并且速度很慢1(例如,在 Skylake 上,微编码为 8 微码,每 23 个周期的吞吐量对于许多重复的 back-to-返回操作,在 L1d 缓存中已经很热的无争用情况下。您没有指定任何关于您拥有的硬件)。
_lock.store(false, std::memory_order_release);
只是编译成一个普通的 mov
存储,没有额外的屏障指令。因此 _counter
的重新加载可以与其并行发生(尽管分支预测 + 推测执行使这不是问题)。更重要的是,下一次 CAS 尝试拿锁实际上可以更快地尝试。
当多个内核在高速缓存行上进行访问时,存在硬件仲裁来访问它,大概是通过一些公平启发式算法,但我不知道细节是否已知。
脚注 1:在最近的一些 CPU 中,xchg
不如 mov
+mfence
慢,尤其是 Skylake 派生的 CPUs。这是在 x86 上实现 seq_cst 纯存储的最佳方式。但它比普通的 mov
.
你可以通过让你的锁力交替写入器来完全解决/ reader
Writer 等待 false
,然后在完成后存储 true
。 Reader 则相反。因此,如果其他线程没有轮到,作者永远无法重新进入临界区。 (当你 "wait for a value" 以只读方式加载时,而不是 CAS。x86 上的 CAS 需要缓存行的独占所有权,防止其他线程读取。只有一个 reader 和一个作者,你不需要任何原子 RMW 就可以工作。)
如果您有多个 reader 和多个编写器,您可以有一个 4 状态同步变量,其中一个编写器尝试将其从 0 转换为 1,然后在完成后存储 2。 Reader尝试从 2 到 3 CAS,完成后存储 0。
SPSC(单一生产者单一消费者)案例很简单:
enum lockstates { LK_WRITER=0, LK_READER=1, LK_EXIT=2 };
std::atomic<lockstates> shared_lock;
uint64_t shared_queue; // single entry
uint64_t global_total{ 0 }, global_counter{ 0 };
static const uint64_t LIMIT = 1000000;
void writer()
{
while(1) {
enum lockstates lk;
while ((lk = shared_lock.load(std::memory_order_acquire)) != LK_WRITER) {
if (lk == LK_EXIT)
return;
else
SPIN; // _mm_pause() or empty
}
//_vec.push_back(__rdtsc());
shared_queue = __rdtsc();
shared_lock.store(LK_READER, ORDER); // seq_cst or release
}
}
void reader()
{
uint64_t total=0, counter=0;
while(1) {
enum lockstates lk;
while ((lk = shared_lock.load(std::memory_order_acquire)) != LK_READER) {
SPIN; // _mm_pause() or empty
}
const uint64_t latency = __rdtsc() - shared_queue; // _vec[0];
//_vec.clear();
total += latency;
++counter;
if (counter < LIMIT) {
shared_lock.store(LK_WRITER, ORDER);
}else{
break; // must avoid storing a LK_WRITER right before LK_EXIT, otherwise writer races and can overwrite with LK_READER
}
}
global_total = total;
global_counter = counter;
shared_lock.store(LK_EXIT, ORDER);
}
Full version on Godbolt。在我的 i7-6700k Skylake 台式机上(2 核 Turbo = 4200MHz,TSC = 4008MHz),使用 clang++ 9.0.1 -O3
编译。正如预期的那样,数据非常嘈杂;我做了一堆 运行s 并手动选择了一个低点和高点,忽略了一些可能由于热身效应而导致的实际异常高点。
在单独的物理内核上:
-DSPIN='_mm_pause()' -DORDER=std::memory_order_release
:~180 到~210 个周期/op,基本上为零machine_clears.memory_ordering
(比如19
总共超过 1000000 ops,这要归功于pause
在自旋中等待循环。)-DSPIN='_mm_pause()' -DORDER=std::memory_order_seq_cst
:~195 到~215 个参考周期/操作,相同的近零机器清除。-DSPIN='' -DORDER=std::memory_order_release
: ~195 到 ~225 ref c/op, 9 到 10 M/sec 机器清除没有pause
.-DSPIN='' -DORDER=std::memory_order_seq_cst
:变化更大,速度更慢,~250 到~315 c/op,8 到 10 M/sec 机器清除没有pause
这些时间比我系统上 seq_cst
"fast" 的原始时间快 3 倍 。使用 std::vector<>
而不是标量可能占其中的约 4 个周期;我认为当我更换它时会有轻微的影响。不过,也许只是随机噪音。 200 / 4.008GHz 大约是 50ns 内核间延迟,这听起来适合四核 "client" 芯片。
从最佳版本(mo_release,在 pause
上旋转以避免机器清除):
$ clang++ -Wall -g -DSPIN='_mm_pause()' -DORDER=std::memory_order_release -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r4 ./a.out
195 ref cycles per op. total ticks: 195973463 / 1000000 ops
189 ref cycles per op. total ticks: 189439761 / 1000000 ops
193 ref cycles per op. total ticks: 193271479 / 1000000 ops
198 ref cycles per op. total ticks: 198413469 / 1000000 ops
Performance counter stats for './a.out' (4 runs):
199.83 msec task-clock:u # 1.985 CPUs utilized ( +- 1.23% )
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
128 page-faults # 0.643 K/sec ( +- 0.39% )
825,876,682 cycles:u # 4.133 GHz ( +- 1.26% )
10,680,088 branches:u # 53.445 M/sec ( +- 0.66% )
44,754,875 instructions:u # 0.05 insn per cycle ( +- 0.54% )
106,208,704 uops_issued.any:u # 531.491 M/sec ( +- 1.07% )
78,593,440 uops_executed.thread:u # 393.298 M/sec ( +- 0.60% )
19 machine_clears.memory_ordering # 0.094 K/sec ( +- 3.36% )
0.10067 +- 0.00123 seconds time elapsed ( +- 1.22% )
从最差的版本开始(mo_seq_cst,没有pause
):自旋等待循环旋转得更快,所以分支和微指令issued/executed要高得多,但实际有用的吞吐量有点差。
$ clang++ -Wall -g -DSPIN='' -DORDER=std::memory_order_seq_cst -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r4 ./a.out
280 ref cycles per op. total ticks: 280529403 / 1000000 ops
215 ref cycles per op. total ticks: 215763699 / 1000000 ops
282 ref cycles per op. total ticks: 282170615 / 1000000 ops
174 ref cycles per op. total ticks: 174261685 / 1000000 ops
Performance counter stats for './a.out' (4 runs):
207.82 msec task-clock:u # 1.985 CPUs utilized ( +- 4.42% )
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
130 page-faults # 0.623 K/sec ( +- 0.67% )
857,989,286 cycles:u # 4.129 GHz ( +- 4.57% )
236,364,970 branches:u # 1137.362 M/sec ( +- 2.50% )
630,960,629 instructions:u # 0.74 insn per cycle ( +- 2.75% )
812,986,840 uops_issued.any:u # 3912.003 M/sec ( +- 5.98% )
637,070,771 uops_executed.thread:u # 3065.514 M/sec ( +- 4.51% )
1,565,106 machine_clears.memory_ordering # 7.531 M/sec ( +- 20.07% )
0.10468 +- 0.00459 seconds time elapsed ( +- 4.38% )
将 reader 和 writer 都固定到一个物理内核的逻辑内核上,可以加快 lot: 在我的系统,核心 3 和 7 是兄弟,所以 Linux taskset -c 3,7 ./a.out
阻止内核将它们调度到其他任何地方:每个操作 33 到 39 个引用周期,或者 80 到 82 没有 pause
.
(
$ clang++ -Wall -g -DSPIN='_mm_pause()' -DORDER=std::memory_order_release -O3 inter-thread.cpp -pthread &&
taskset -c 3,7 perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r4 ./a.out
39 ref cycles per op. total ticks: 39085983 / 1000000 ops
37 ref cycles per op. total ticks: 37279590 / 1000000 ops
36 ref cycles per op. total ticks: 36663809 / 1000000 ops
33 ref cycles per op. total ticks: 33546524 / 1000000 ops
Performance counter stats for './a.out' (4 runs):
89.10 msec task-clock:u # 1.942 CPUs utilized ( +- 1.77% )
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
128 page-faults # 0.001 M/sec ( +- 0.45% )
365,711,339 cycles:u # 4.104 GHz ( +- 1.66% )
7,658,957 branches:u # 85.958 M/sec ( +- 0.67% )
34,693,352 instructions:u # 0.09 insn per cycle ( +- 0.53% )
84,261,390 uops_issued.any:u # 945.680 M/sec ( +- 0.45% )
71,114,444 uops_executed.thread:u # 798.130 M/sec ( +- 0.16% )
16 machine_clears.memory_ordering # 0.182 K/sec ( +- 1.54% )
0.04589 +- 0.00138 seconds time elapsed ( +- 3.01% )
在共享同一物理内核的逻辑内核上。最好的情况是延迟比内核之间低 5 倍,同样是暂停 + mo_release。但实际基准只完成了 40% 的时间,而不是 20%
-DSPIN='_mm_pause()' -DORDER=std::memory_order_release
:~33 到~39 个参考周期/op,接近零machine_clears.memory_ordering
-DSPIN='_mm_pause()' -DORDER=std::memory_order_seq_cst
:~111 到~113 个引用周期/op,总共 19 个机器清除。出乎意料的最差!-DSPIN='' -DORDER=std::memory_order_release
:~81 到~84 ref cycles/op,~12.5 M 机器清除/秒-DSPIN='' -DORDER=std::memory_order_seq_cst
: ~94 到 ~96 c/op, 5 M/sec 机器清除没有pause
.
所有这些测试都与 clang++
一起使用 xchg
用于 seq_cst 商店。 g++
使用 mov
+mfence
在 pause
的情况下速度较慢,在没有 pause
的情况下速度更快并且机器清除更少。 (对于超线程情况。)通常与 pause
的独立核心情况非常相似,但在没有 pause
的情况下,seq_cst 的独立核心情况更快。 (同样,特别是在 Skylake 上,针对这一测试。)
原版更多调查:
还值得检查性能计数器 machine_clears.memory_ordering
(
我确实检查了我的 Skylake i7-6700k,每秒 machine_clears.memory_ordering
的速率没有显着差异(快速 seq_cst 和慢速大约 5M / 秒发布),在 4.2GHz。
"cycles per op" 结果与 seq_cst 版本(400 到 422)惊人地一致。我的 CPU 的 TSC 参考频率是 4008MHz,最大睿频时的实际核心频率是 4200MHz。如果你有 340-380 周期,我假设你的 CPU 的最大涡轮相对于它的参考频率比我的更高。 And/or 不同的微架构。
但我发现 mo_release
版本的结果各不相同:在 Arch GNU/Linux 上使用 GCC9.3.0 -O3
:5790 个运行,另一个是2269。使用 clang9.0.1 -O3
73346 和 7333 两个 运行s,是的,确实是 10 倍)。这是一个惊喜。当清空/推送向量时,这两个版本都没有对 free/allocate 内存进行系统调用,而且我没有看到从 clang 版本中清除很多内存排序机器。使用您的原始 LIMIT,两个 运行s with clang 显示每个操作有 1394 和 22101 个周期。
使用 clang++,甚至 seq_cst 时间的变化也比 GCC 多一些,并且更高,例如 630 到 700。(g++ 使用 mov
+mfence
for seq_cst 纯商店,clang++ 使用 xchg
就像 MSVC 一样)。
其他具有 mo_release
的性能计数器显示出类似的指令、分支和每秒 uops 的速率,所以我认为这表明代码只是花费更多时间在错误的线程上旋转它的轮子关键部分和另一个卡住重试。
两个perf 运行s,第一个是mo_release,第二个是mo_seq_cst.
$ clang++ -DORDER=std::memory_order_release -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r1 ./a.out
27989 cycles per op
Performance counter stats for './a.out':
16,350.66 msec task-clock:u # 2.000 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
231 page-faults # 0.014 K/sec
67,412,606,699 cycles:u # 4.123 GHz
697,024,141 branches:u # 42.630 M/sec
3,090,238,185 instructions:u # 0.05 insn per cycle
35,317,247,745 uops_issued.any:u # 2159.989 M/sec
17,580,390,316 uops_executed.thread:u # 1075.210 M/sec
125,365,500 machine_clears.memory_ordering # 7.667 M/sec
8.176141807 seconds time elapsed
16.342571000 seconds user
0.000000000 seconds sys
$ clang++ -DORDER=std::memory_order_seq_cst -O3 inter-thread.cpp -pthread &&
perf stat --all-user -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles:u,branches:u,instructions:u,uops_issued.any:u,uops_executed.thread:u,machine_clears.memory_ordering -r1 ./a.out
779 cycles per op
Performance counter stats for './a.out':
875.59 msec task-clock:u # 1.996 CPUs utilized
0 context-switches # 0.000 K/sec
0 cpu-migrations # 0.000 K/sec
137 page-faults # 0.156 K/sec
3,619,660,607 cycles:u # 4.134 GHz
28,100,896 branches:u # 32.094 M/sec
114,893,965 instructions:u # 0.03 insn per cycle
1,956,774,777 uops_issued.any:u # 2234.806 M/sec
1,030,510,882 uops_executed.thread:u # 1176.932 M/sec
8,869,793 machine_clears.memory_ordering # 10.130 M/sec
0.438589812 seconds time elapsed
0.875432000 seconds user
0.000000000 seconds sys
我用内存顺序修改了你的代码作为 CPP 宏,所以你可以用 -DORDER=std::memory_order_release
编译以获得慢速版本。
acquire
与 seq_cst
在这里无关紧要;它在 x86 上针对负载和原子 RMW 编译为相同的 asm。只有纯商店需要 seq_cst.
您还遗漏了 stdint.h
和 intrin.h
(MSVC) / x86intrin.h
(其他所有内容)。固定版本为 on Godbolt with clang and MSVC。早些时候,我将 LIMIT 提高了 10 倍,以确保 CPU 频率有时间在大部分时间区域上升到最大涡轮增压,但恢复了该更改,因此测试 mo_release
只需要几秒钟, 不是分钟。
设置 LIMIT 以检查特定的总 TSC 周期可能有助于它在更一致的时间退出。这仍然不包括作者被锁定的时间,但总的来说应该 运行 花费极长时间的可能性较小。
如果您只是想测量线程间延迟,您还会遇到很多非常复杂的事情。
(
你有两个线程都读取作者每次更新的 _total
,而不是在完成后只存储一个标志。所以作者有潜在的内存排序机器从读取另一个线程写入的变量中清除。
您在 reader 中也有一个 _counter
的原子 RMW 增量,即使该变量是 reader 私有的。它可以是您在 reader.join()
之后读取的普通非原子全局变量,或者更好的是它可以是您仅在循环后存储到全局变量的局部变量。 (一个普通的非原子全局变量可能最终会在每次迭代时存储到内存中,而不是保存在寄存器中,因为发布存储。而且由于这是一个小程序,所有全局变量可能彼此相邻,并且可能在同一缓存行中。)
std::vector
也是不必要的。 __rdtsc()
不会为零,除非它绕过 64 位计数器 1,因此您可以只使用 0
作为标量 uint64_t
表示为空。或者,如果你修复了你的锁定,那么 reader 在没有轮到作者的情况下无法重新进入关键部分,你可以删除该检查。
脚注 2:对于 ~4GHz TSC 参考频率,即 2^64 / 10^9 秒,足够接近 2^32 秒 ~= 136 年环绕 TSC。注意TSC参考频率是不是当前核心时钟频率;对于给定的 CPU,它固定为某个值。通常接近额定 "sticker" 频率,而不是最大涡轮频率。
此外,以 _
开头的名称在 ISO C++ 中保留在全局范围内。不要将它们用于您自己的变量。 (通常不在任何地方。如果你真的想要,你可以使用尾随下划线。)