我在Windows 7 64位VS2013(x64发行版)上尝试内存排序。我想使用最快的同步共享对容器的访问。我选择了原子比较和交换。
我的程序产生两个线程。作者将一个推入 vector ,然后读者将其检测到。
最初我没有指定任何内存顺序,所以我假设它使用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()
不为假,或者存储另一个TSC值,从而覆盖了读者从未见过的值。 我怀疑您的更改使读者浪费了更多时间来阻止作者(反之亦然),从而导致实际吞吐量降低。
TL:DR:真正的问题是锁定上缺乏公平性(对于刚刚解锁的线程来说,要想再次赢得锁定就太容易了,这太容易了),以及您使用该锁定的方式。 (在确定是否有任何有用的事情,迫使另一个线程重试以及导致内核之间的高速缓存行额外传输之前,必须先采取这一措施。)
让线程重新获取锁而没有其他线程转弯总是无用和浪费的工作,这与许多实际情况不同,在这种情况下,需要更多重复来填充或清空队列。这是一种糟糕的生产者-消费者算法(队列太小(大小1),和/或阅读器在读取vec[0]
之后会丢弃所有 vector 元素),并且是最糟糕的锁定方案。_lock.store(false, seq_cst);
编译为xchg
,而不是普通的mov
存储。
它必须等待存储缓冲区耗尽,并且速度很慢(例如,在Skylake上,微码编码为8 uops,对于许多重复的背对背操作,吞吐量为每23个循环1个,在无争用情况下)在L1d缓存中已经很热。您没有指定有关所拥有硬件的任何信息。_lock.store(false, std::memory_order_release);
确实可以编译为简单的mov
存储,而无需额外的屏障指令。因此,_counter
的重新加载可以与其并行发生(尽管分支预测+投机执行使这不是问题)。更重要的是,下一次CAS尝试进行锁定实际上可以更快地尝试。
当有多个内核锤击高速缓存行时,可以通过硬件仲裁来访问高速缓存行,这大概是通过一些公平启发法进行的,但是我不知道细节是否已知。
脚注1:在最近的某些CPU(尤其是Skylake派生的CPU)上,xchg
的速度不及mov
+ mfence
的速度。这是在x86上实现seq_cst纯存储的最佳方法。但这比普通的mov
慢。
您可以通过交替使用作家/读者的锁定力来完全解决
Writer等待false
,然后在完成后存储true
。读者则相反。因此,在没有其他线程转弯的情况下,作者永远无法重新输入关键部分。 (当您“等待一个值”时,对它进行只读加载而不是对CAS进行加载。x86上的CAS需要高速缓存行的独占所有权,以防止其他线程读取。只有一个读取器和一个写入器,您才能不需要任何原子RMW即可工作。)
如果您有多个读取器和多个写入器,则可以有一个4状态同步变量,其中写入器尝试将其从0到1进行CAS,然后在完成时存储2。读者尝试从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
编译。正如预期的那样,数据非常嘈杂。我进行了一堆跑步,并手动选择了一个低点和高点,而忽略了可能是由于热身效应导致的一些实际异常高点。在单独的物理核心上:
-DSPIN='_mm_pause()' -DORDER=std::memory_order_release
:〜180至〜210个周期/ op,基本上为零,machine_clears.memory_ordering
(如s19
总计超过1000000 ops,这要归功于spin-wait循环中的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
“快速”快约3倍。使用std::vector<>
代替标量可能会占大约4个周期;我认为当我更换它时会产生轻微的影响。不过,也许只是随机噪音。 200 / 4.008GHz大约是50ns的内核间延迟,这对于四核“客户端”芯片来说似乎是正确的。从最佳版本开始(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
):spin-wait循环旋转得更快,因此发出/执行的分支和uops更高,但是实际有用的吞吐量却稍差一些。$ 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% )
将读取器和写入器固定到一个物理核心的逻辑核心上可以大大提高:在我的系统上,核心3和7是同级的,因此Linux
taskset -c 3,7 ./a.out
阻止了内核将它们调度到其他任何地方:每个操作33到39个引用周期,或者80到82(不带pause
)。(What will be used for data exchange between threads are executing on one Core with HT?,)
$ 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引用周期/操作,总共19次机器清除。令人惊讶的是最糟糕的! -DSPIN='' -DORDER=std::memory_order_release
:〜81至〜84个引用周期/操作,〜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,这是一项测试。)原始版本的更多调查:
还值得检查perf计数器中的
machine_clears.memory_ordering
(Why flush the pipeline for Memory Order Violation caused by other logical processors?)。我确实检查了我的Skylake i7-6700k,在4.2GHz时,每秒
machine_clears.memory_ordering
的速率(快速seq_cst和缓慢释放的速率约为5M /秒)没有显着差异。对于seq_cst版本(400到422),“每个操作的周期数”结果令人惊讶地一致。我的CPU的TSC引用频率为4008MHz,最大睿频时的实际核心频率为4200MHz。如果您获得340-380周期,我认为您的CPU的最大加速比其最大引用频率要高。和/或其他微体系结构。
但是我发现
mo_release
版本的结果大相径庭:在Arch GNU / Linux上使用GCC9.3.0 -O3
:一次运行5790,另一次运行2269。使用clang9.0.1 -O3
73346和7333进行两次运行,是的,实际上是10倍。真是令人惊讶当清空/推送 vector 时,这两个版本都没有进行系统调用来释放/分配内存,而且我看不到从clang版本中清除很多内存排序器。使用您的原始LIMIT时,用c运行两次显示每个操作1394和22101个周期。使用clang++,甚至seq_cst的时间变化也要比使用GCC的时间有所变化,并且变化更大,例如630到700。(g++对seq_cst纯存储使用
mov
+ mfence
,clang++像MSVC一样使用xchg
)。其他带有
mo_release
的性能计数器显示的指令,分支和每秒微指令的速率相似,因此我认为这表明该代码只是在关键部分花了更多的时间用错误的线程旋转轮子,而其他卡住了重试。运行两个性能,第一个是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
在这里无关紧要;对于负载和原子RMW,它可以在x86上编译为相同的asm。仅纯存储需要seq_cst的特殊asm。另外,您还忽略了
stdint.h
和intrin.h
(MSVC)/ x86intrin.h
(其他所有内容)。固定版本为on Godbolt with clang and MSVC。早些时候,我将LIMIT提高了10倍,以确保CPU频率有时间在大多数时间区域内提高到最大涡轮速度,但是恢复了该更改,因此测试mo_release
只需几秒钟,而不是几分钟。设置LIMIT以检查某个总TSC周期可能有助于在更一致的时间内退出。那仍然不算写者被锁定的时间,但是总的来说,运行它所花费的时间要少得多。
如果您只是想测量线程间的延迟,您还会遇到很多非常复杂的事情。
(How does the communication between CPU happen?)
您有两个线程都读取writer每次更新的
_total
,而不仅仅是在完成后仅存储标志。因此,编写者有可能从读取另一个线程写入的变量中清除内存排序机。在阅读器中,您也具有
_counter
的原子RMW增量,即使该变量是阅读器专用的。它可能是在reader.join()
之后读取的普通非原子全局变量,甚至更好的是它是局部变量,您仅在循环后将其存储到全局变量中。 (由于发行版存储的原因,一个普通的非原子全局变量可能仍会在每次迭代时最终存储到内存中,而不是保存在寄存器中。由于这是一个很小的程序,因此所有全局变量可能彼此相邻,并且可能在同一缓存行中。)std::vector
也是不必要的。除非环绕64位counter1,否则__rdtsc()
不会为零,因此您可以仅将0
用作标量uint64_t
中的哨兵值,以表示为空。或者,如果您修复了锁定问题,以使读者在没有作者转弯的情况下无法重新进入关键部分,则可以删除该支票。脚注2:对于〜4GHz TSC引用频率,即2 ^ 64/10 ^ 9秒,足够接近2 ^ 32秒〜= 136年,可以环绕TSC。注意,TSC引用频率不是当前内核时钟频率;对于给定的CPU,它固定为某个值。通常接近额定“贴纸”频率,而不是最大涡轮增压。
同样,在ISO C++中,在全局范围内保留带有前置
_
的名称。不要将它们用于您自己的变量。 (通常不在任何地方。如果您确实需要,可以使用下划线代替。)
关于c++ - 放松内存排序时,C++延迟会增加,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61649951/