源码搜藏网

介绍

基于锁的数据结构的高性能

在本文中，我们将详细介绍原子操作和C ++ 11内存屏障及其在x86_64 CPU上生成的汇编程序指令。

接下来，我们将展示如何加速contfree_safe_ptr<std::map>复杂和优化的无锁数据结构的工作，这些结构std::map<>与其功能类似，例如：SkipListMap 和BronsonAVLTreeMap libCDS库（并发数据结构库）：https://github.com/khizmax/libcds

我们可以为你最初使用的非线程安全的T-class获得这样的多线程性能contfree_safe_ptr<T> - 它是   safe_ptr<T, contention_free_shared_mutex>  类，它contention_free_shared_mutex  是自己优化的共享互斥锁。

也就是说，我们将展示如何实现您自己的高性能无争用共享互斥锁，它几乎不会与读数冲突。我们实现了自己的主动锁 - 自旋锁和递归 - 自旋锁 - 来锁定更新操作中的行。我们将创建RAII阻塞指针以避免多次锁定的成本。以下是性能测试的结果。

而作为“只是为了好玩”的奖励，我们将演示实现我们自己的简化分区类型partitioned_map的方法，它甚至针对多线程进行了更优化，包括几个std :: map，类似于RDBMS的分区表，当最初知道每个部分的边界时。

背景

原子操作的基础知识

让我们考虑多线程，原子性和内存障碍的基础知识。

如果我们从一组线程中更改相同的数据，即如果我们在多个线程中同时运行thread_func（）函数：

int a;
void thread_func() { a = a + 1; } 	// wrong: data-race

然后每个调用thread_func（）函数的线程将1添加到普通共享变量int a; 在一般情况下，这样的代码将不是线程安全的，因为具有普通变量的复合操作（RMW-读取 - 修改 - 写入）由许多小操作组成，在这些操作之间另一个线程可以更改数据。操作a = a + 1; 由至少三个迷你操作组成：

1. 将变量“a”的值加载到CPU寄存器中
2. 将1添加到寄存器中的值
3. 将寄存器的值写回变量“a”

对于非原子 int a，如果最初a = 0; 和2个线程执行操作a = a + 1; 那么结果应该是a = 2; 但以下情况可能会发生（一步一步）：

int a = 0; 				        // register1 = ?, register2 = ?, a = 0
Thread 1: register1 = a; 		// register1 = 0, register2 = ?, a = 0
Thread 2: register2 = a 		// register1 = 0, register2 = 0, a = 0
Thread 1: register1++;  		// register1 = 1, register2 = 0, a = 0
Thread 2: register2++;  		// register1 = 1, register2 = 1, a = 0
Thread 1: a = register1; 		// register1 = 1, register2 = 1, a = 1
Thread 2: a = register2; 		// register1 = 1, register2 = 1, a = 1

两个线程将+1添加到同一个全局变量，初始值= 0，但最后，变量a = 1- 这样的问题称为Data-Races。

有3种方法可以帮助避免这样的问题：

1. 将原子指令与原子变量一起使用 - 但是有一个缺点，原子函数的数量非常少 - 因此，借助这些函数很难实现复杂的逻辑：http：//en.cppreference.com/w / CPP /原子/原子
2. 为每个新容器开发自己的复杂无锁算法。
3. 要使用锁（std :: mutex，std :: shared_timed_mutex，spinlock ...） - 它们一个接一个地接受锁定的代码，因此不会出现数据争用的问题，我们可以使用任意复杂的逻辑使用任何普通的非线程安全对象。

对于：如果最初a = 0; 和2个线程执行操作a + = 1; 那么结果总是a = 2;std::atomic<int> a

std::atomic<int> a;
void thread_func() { a += 1; } 	// correct: no data-race

以下内容始终发生在x86_64 CPU上（逐步）：

std::atomic<int> a = 0;         // register1 = ?, register2 = ?, a = 0

Thread 1: register1 = a; 		// register1 = 0, register2 = ?, a = 0
Thread 1: register1++;  		// register1 = 1, register2 = 0, a = 0
Thread 1: a = register1; 		// register1 = 1, register2 = 0, a = 1

Thread 2: register2 = a; 		// register1 = 1, register2 = 1, a = 1
Thread 2: register2++;  		// register1 = 1, register2 = 2, a = 1
Thread 2: a = register2; 		// register1 = 1, register2 = 2, a = 2

在具有LL / SC支持的处理器上，例如在ARM上，会发生其他步骤，但具有相同的正确结果：a = 2。

原子变量被引入标准C ++ 11：http：//en.cppreference.com/w/cpp/atomic/atomic

std::atomic<> 模板类成员函数总是原子的。

以下是正确代码的3个片段，其含义相同：

1.示例：

std::atomic< int > a;
a = 20;
a += 50;

2.它与例1完全相同：

std::atomic< int > a;
a.store( 20 );
a.fetch_add( 50 );

3.它与例1相同：

std::atomic< int > a;
a.store( 20, std::memory_order_seq_cst );
a.fetch_add( 50, std::memory_order_seq_cst );

这意味着对于std :: atomic：

• load()并且store() 等于operator=和operator T
• fetch_add() 并且  fetch_sub()等于operator+=和operator-=
• 顺序一致性std::memory_order_seq_cst 是默认的内存屏障（最严格和可靠，但对于其他人来说也是最慢的）。

让我们注意C ++ 11中std :: atomic和volatile之间的区别：http：//www.drdobbs.com/parallel/volatile-vs-volatile/212701484

有5个主要差异：

1. 优化：对于std :: atomic <T> a; 两种优化是可能的，这对于易失性T a是不可能的;

• 融合的优化：a = 10; a = 20; 可以用a = 20的编译器替换;
• 通过常数优化替换：a = 1; local = a; 可以用编译器替换a = 1; local = 1 ;;

2.  重新排序： std :: atomic <T> a; 操作可以限制自身的重新排序，以便使用普通变量进行操作，并根据所使用的内存屏障std :: memory_order _ ...来操作其他原子变量。相反，volatile T a; 不会影响常规变量（非原子/非易失性）的顺序，但对所有volatile变量的调用始终保持严格的相互顺序，即编译器不能更改任何两个volatile操作的执行顺序，但不是由CPU。

3. 溢流式：的std :: memory_order_release，性病:: memory_order_acq_rel，性病:: memory_order_seq_cst内存屏障，其为标准::原子<T>指定; 操作，在执行原子操作之前启动所有常规变量的溢出。也就是说，这些障碍将常规变量从CPU寄存器上传到主存储器/缓存中，除非编译器可以100％保证该局部变量不能在其他线程中使用。

4.  原子性/对齐：对于std :: atomic <T> a; 其他线程看到该操作已完全执行或根本未执行。对于Integral-types T，这可以通过编译器对内存中的原子变量位置进行对齐来实现 - 至少，变量位于单个高速缓存行中，以便可以通过CPU的一个操作来更改或加载变量。相反，编译器不保证volatile变量的对齐。易失性变量通常用于访问设备的内存（或在其他情况下），因此设备驱动程序的API返回指向volatile变量的指针，并且此API在必要时确保对齐。

5. RMW操作的原子性（读 - 修改 - 写）：对于std :: atomic <T> a; 操作（++， - ，+ =， - =，* =，/ =，CAS，交换）以原子方式执行，即如果两个线程执行操作++ a; 然后，a变量将始终增加2.这可以通过锁定缓存行（x86_64）或在RMW操作期间在支持LL / SC（ARM，PowerPC）的CPU上标记缓存行来实现。易失性变量不能确保复合RMW操作的原子性。

变量std :: atomic和volatile有一个通用规则：每个读或写操作总是调用内存/缓存，即值永远不会缓存在CPU寄存器中。

我们还注意到，对于普通变量和对象（非原子/非易失性），可以对编译器或CPU完成的任何相互独立指令的优化和任何重新排序。

回想一下，用std :: memory_order_release，std :: memory_order_acq_rel和std :: memory_order_seq_cst内存屏障写入内存的操作可以保证所有非原子/非易失性变量的溢出（从寄存器写入内存），现在在CPU注册中，立即：https：//en.wikipedia.org/wiki/Register_allocation#Spilling

更改指令执行的顺序

编译器和处理器更改指令的顺序以优化程序并提高其性能。

以下是GCC编译器和CPU x86_64完成的优化示例：https：//godbolt.org/g/n91hpt

全尺寸图片：https：//hsto.org/files/3d2/18b/c7b/3d218bc7b3584f82820f92077096d7a0.jpg

优化如图所示：

1. GCC 7.0 编译器重新排序：

• 它将写入交换到存储器b = 5; 并从内存上传到寄存器int tmp_c = c ;. 这允许您尽可能早地询问“c”值，并且当CPU等待这个长时间操作时，CPU管道允许执行操作b = 5; 因为这两个操作不相互依赖。
• 它将从内存上传到寄存器int tmp_a = a; 和加法运算 - tmp_c = tmp_c + tmp_a; 在结果中，我们有一个操作添加eax，一个[rip]而不是两个操作。

2. x86_64 CPU重新排序：

CPU可以将实际写入交换到存储器mov b [rip]，并从存储器读取，并与加法操作相结合 - 添加eax，[rip]。

通过mov b [rip]，5指令启动写入存储器时，会发生以下情况：首先，将值5和b [rip]的地址放在存储缓冲区队列中，缓存行包含地址所有CPU内核中的b [rip]预计将被无效并且正在等待它们的响应，然后CPU-Core-0为包含b [rip]的高速缓存行设置“eXclusive”状态。只有在那之后，从存储缓冲区实际写入值5才会在b [rip]中执行到该缓存行。有关x86_64 MOESI / MESIF上的缓存一致性协议的更多详细信息，其中所有内核的更改立即可见，请参阅：https：//en.wikipedia.org/wiki/MESIF_protocol 。

为了不等待所有这些时间 - 在“5”被放入Store-Buffer之后，不等待实际的高速缓存条目，我们就可以开始执行以下指令：从内存或寄存器操作中读取。这就是x86_64 CPU的表现 -

英特尔®64和IA-32架构软件开发人员手册第3卷（3A，3B，3C和3D）：系统编程指南：https：//www-ssl.intel.com/content/dam/www/public/us/en /documents/manuals/64-ia-32-architectures-software-developer-system-programming-manual-325384.pdf

引用：

8.2.3.4载荷可以与较早的商店重新排序到不同的地点

Intel-64内存订购模型允许将负载与较早的存储重新排序到不同的位置。但是，加载不会与商店重新排序到同一位置。

x86_64系列的CPU具有强大的内存模型。具有弱内存模型的CPU（例如，PowerPC和ARM v7 / v8）可以执行更多的重新排序。

以下是在普通变量，volatile变量和原子变量的内存中可能重新排序条目的示例。

具有普通变量的代码可以由编译器或CPU重新排序，因为它的含义在一个线程内不会改变。但是在一组线程中，这种重新排序会影响程序的逻辑。

如果2个变量是易失性的，则可以进行以下重新排序。编译器无法在编译时对volatile变量的操作重新排序，但编译器允许CPU在运行时执行此重新排序。

为了防止所有或仅一些重新排序，有原子操作（回想一下原子操作使用最严格的内存屏障 - std::memory_order_seq_cst默认情况下）。

另一个线程可以完全按照修改的顺序查看内存中变量的变化。

如果我们没有为原子操作指定内存屏障，那么默认使用最严格的屏障std :: memory_order_seq_cst，并且不能使用此类操作重新排序原子或非原子操作（但是我们会考虑例外情况）后来）。

在上面的例子中，我们首先写入普通变量a和b，然后 - 写入原子变量a_at和b_at，并且这个顺序不能改变。此外，写入内存b_at不能比写入内存a_at更早发生。但是写入变量a和b可以相对于彼此重新排序。

当我们说“可以重新排序”时，这意味着它们可以，但不一定。这取决于编译器在编译期间如何决定优化C ++代码，或者CPU如何决定在运行时执行此操作。

下面我们将考虑更弱的内存屏障，允许在允许的方向上重新排序指令。这允许编译器和CPU更好地优化代码并提高性能。

重新排序内存操作的障碍

C ++ 11标准内存模型为我们提供了6种类型的内存屏障，这些内存屏障对应于用于推测性执行的现代CPU的功能。通过使用它们，我们并不完全禁止更改订单，但我们仅在必要的方向上禁止它。这允许编译器和CPU尽可能地优化代码。重新排序的禁止方向允许我们保持代码的正确性。http://en.cppreference.com/w/cpp/atomic/memory_order

enum memory_order {
    memory_order_relaxed,
    memory_order_consume,
    memory_order_acquire,
    memory_order_release,
    memory_order_acq_rel,
    memory_order_seq_cst
};

memory_order_consume。我们立即注意到，我们实际上不会使用memory_order_consume障碍，因为在标准中对其使用的实用性存在疑问 - 来自标准的引用：http：//www.open-std.org/jtc1/sc22/wg21 /docs/papers/2016/n4606.pdf

引用：

§29.3                                                                         

（1.3） - memory_order_consume：加载操作对受影响的内存位置执行使用操作。[注意：首选memory_order_acquire，它提供比memory_order_consume更强的保证。实现发现，提供比memory_order_acquire更好的性能是不可行的。正在考虑规范修订。 - 结束说明]

memory_order_acq_rel。此外，我们注意到，memory_order_acq_rel屏障仅用于RMW的原子化合物操作（读-修改-写），如：compare_exchange_weak()/ _strong()，exchange()，fetch_(add, sub, and, or, xor)或它们相应的操作符：http://en.cppreference.com/w/cpp/atomic/原子

其余4个内存屏障可用于任何操作，但以下情况除外：“acquire”不用于store（），“release”不用于load（）。

根据所选的内存屏障，对于编译器和CPU，禁止在不同方向上相对于屏障移动可执行代码。

现在让我们看一下箭头指定的内容以及可以互换的内容和不可互换的内容：

对于要互换的2条指令，两条指令的障碍必须允许这种互换。因为“其他任何代码”意味着没有任何障碍的普通非原子变量，所以它们允许任何订单更改。通过Relaxed-Release-Relaxed的例子，正如您所看到的，改变相同记忆障碍顺序的可能性取决于它们的外观顺序。

让我们考虑一下，这些内存障碍意味着什么以及它们给我们带来了什么好处，通过实现最简单的“自旋锁”类型锁的例子，它需要最常见的Acquire-Release重新排序语义。Spin-lock是一种锁，就其使用方式而言类似于std :: mutex。

首先，我们在程序正文中实现了自旋锁概念。然后我们实现了一个单独的自旋锁类。要实现锁（互斥锁，自旋锁......），你应该使用Acquire-Release语义，C ++ 11标准§1.10.1（3）：http：//www.open-std.org/jtc1/sc22/wg21 /docs/papers/2016/n4606.pdf

引用：

§1.10.1（3）

...例如，获取互斥锁的呼叫将对包含互斥锁的位置执行获取操作。相应地，释放相同互斥锁的调用将在这些相同位置执行释放操作。非正式地，对A执行释放操作会强制对其他存储器位置的先​​前副作用变得对其他线程可见，这些线程稍后在A上执行消耗或获取操作。

Acquire-Release语义的要点是：执行flag.load（std :: memory_order_acquire）操作后的Thread-2应该看到已经创建的任何变量/结构/类（甚至不是原子的）的所有更改在执行flag.store（0，std :: memory_order_release）操作之前，由Thread-1执行。

锁（mutex，spinlock ...）的基本目的是创建一部分代码，只能由一个线程同时执行。这样的代码区域称为临界区域。在其中，您可以使用任何普通代码，包括那些没有std :: atomic <>的代码。

内存障碍阻止编译器优化程序，以便关键部分的操作不会超出其限制。

首先捕获锁的线程执行代码锁定，其余线程在循环中等待。当第一个线程释放锁时，CPU决定下一个等待线程将捕获它，等等。

这是两个相同的例子：

1.使用std::atomic_flag：[19] http://coliru.stacked-crooked.com/a/1ec9a0c2b10ce864

2.通过使用std::atomic<int>：[20] http://coliru.stacked-crooked.com/a/03c019596b65199a

实施例-1是更优选的。因此，对于它，我们将示意性地显示使用内存屏障的意图 - 实心蓝色显示原子操作：

[19] http://coliru.stacked-crooked.com/a/1ec9a0c2b10ce864

障碍的目的非常简单 - 不允许编译器优化器将指令从关键部分移动到外部：

• 在memory_order_ acquire之后没有指令可以在它之前执行。
• 在memory_order_ release之前没有指令可以在它之后执行。

可以由编译器（编译时）或CPU（运行时）执行独立指令执行顺序的任何其他更改，以优化性能。

例如，该行int new_shared_value = shared_value;可以在之前执行lock_flag.clear(std::memory_order_release);。这样的重新排序是可以接受的，并且不会创建数据争用，因为访问多个线程共有的数据的整个代码总是包含在两个障碍中 - “获取”和“释放”。在外部，有一个代码只适用于线程本地数据，并且它的执行顺序无关紧要。线程本地依赖项始终以类似于单线程执行的方式存储。这就是为什么int new_shared_value = shared_value;之前无法执行的原因shared_value + = 25;

编译器在std :: memory_order中到底做了什么：

• 1,6：如果给定的CPU架构需要这些障碍，编译器会为加载操作和存储操作的释放障碍生成汇编程序指令acquire-barrier
• 2：编译器取消先前在CPU寄存器中缓存的变量，以便重新加载由另一个线程更改的这些变量的值 - 在加载（获取）操作之后
• 5：编译器将所有变量的值从CPU寄存器保存到内存中，以便其他线程可以看到它们，即它执行溢出（链接） - 直到存储（释放）
• 3,4：编译器阻止优化器改变禁止方向的指令顺序 - 用红色箭头表示

现在让我们看看会发生什么，如果我们使用Relaxed - Release语义而不是Acquire-Release：

• 在左边。在Acquire-Release的情况下，一切都正确执行。
• 在右边。在Relaxed -Release的情况下，由锁定保护的关键部分内的部分代码可以由编译器或CPU移出。然后，Data Races会出现问题 - 在锁定之前，许多线程将开始与数据同时工作，这些数据不会被原子操作处理。

请注意，通常只有在原子操作的帮助下才能实现与一般数据相关的所有逻辑，因为它们很少而且速度很慢。因此，执行以下操作更简单，更快捷：通过一个原子操作设置标志“关闭”，执行与线程共有的数据相关的所有非原子操作，并设置标志“打开”。

我们将及时示意地展示这个过程：

例如，两个线程开始执行add_to_shared（）函数。

1. Thread-1提前一点，并通过一个原子指令test_and_set（）一次执行2个操作：它执行检查，如果lock_flag == false，则它为其设置“true”值（即，锁定旋转-lock）并返回“false”。因此，while（lock_flag.test_and_set（））; 表达式立即结束，并且临界区的代码开始执行。
2. 此时，thread-2也开始执行这个原子指令test_and_set（）：它执行检查，如果lock_flag == false，则设置“true”值。否则，它不会更改任何内容并返回当前的“true”值。因此，while（lock_flag.test_and_set（））; 表达式将执行，while（lock_flag）;
3. Thread-1执行加法操作shared_value + = 25; 然后通过原子操作设置lock_flag = false值（即解锁自旋锁）。
4. 最后，thread-2在完成等待条件lock_flag == false后，指定lock_flag = true，返回“false”并完成循环。然后它执行shared_value + = 25的添加; 并指定lock_flag = false（解锁自旋锁）。

在本章开头，我们举了两个例子：

1. 通过使用std :: atomic_flag和test_and_set（）：[21] http://coliru.stacked-crooked.com/a/1ec9a0c2b10ce864
2. 通过使用std :: atomic <int>和compare_exchange_weak（）：[22] http://coliru.stacked-crooked.com/a/03c019596b65199a

有关更多详细信息，请参阅：http：//en.cppreference.com/w/cpp/atomic/atomic

让我们看看由GCC编译器生成的x86_64的汇编程序代码与这两个示例有何不同：

为方便使用，它可以组合成一个类：

class spinlock_t {
    std::atomic_flag lock_flag;
public:
    spinlock_t() { lock_flag.clear(); }

    bool try_lock() { return !lock_flag.test_and_set(std::memory_order_acquire); }
    void lock() { for (size_t i = 0; !try_lock(); ++i) if (i % 100 == 0) std::this_thread::yield(); }
    void unlock() { lock_flag.clear(std::memory_order_release); }
};

使用示例spinlock_t：[23] http://coliru.stacked-crooked.com/a/92b8b9a89115f080

下表将帮助您了解应使用哪个障碍以及将编译到哪个障碍：

全尺寸图片：https：//hsto.org/files/4f8/7b4/1b6/4f87b41b64a54549afca679af1028f84.jpg

只有在汇编程序x86_64中编写代码时，编译器才能交换汇编程序指令以进行优化时，您必须知道以下信息：

• seq_cst。GCC的主要区别（Clang和MSVC）是当您对顺序一致性语义使用存储操作时，即：a.store（val，memory_order_seq_cst）; - 在这种情况下，Clang和MSVC生成[LOCK] XCHG reg，[addr]指令，它以与MFENCE屏障相同的方式清除CPU存储缓冲区。在这种情况下，GCC使用两个指令MOV [addr]，reg和MFENCE。  
• RMW（CAS，ADD ...）总是seq_cst。由于x86_64上的所有原子RMW（读取 - 修改 - 写入）指令都具有LOCK前缀（清除存储缓冲区），因此它们都对应于汇编程序代码级别的顺序一致性语义。RMW的任何memory_order都会生成相同的代码，包括memory_order_acq_rel。                                                                                                                                         
• LOAD（获得），STORE（发布）。如您所见，在x86_64上，前4个内存屏障（宽松，消费，获取，发布）生成相同的汇编代码 - 即x86_64架构自动提供获取释放语义。此外，它由MESIF（英特尔）/ MOESI（AMD）缓存一致性协议提供。这仅适用于通常编译工具分配的内存，默认情况下标记为回写（但对于标记为Un-cacheable或Write Combined的内存不适用，用于处理来自Mapped Memory Area的内存）设备 - 仅获取 - 语义自动提供在其中）。

我们知道，依赖操作不能在任何地方重新排序，例如：（Read-X，Write-X）或（Write-X，Read-X）

1.来自Herb Sutter for x86_64的演讲：https ://onedrive.live.com/view.aspx ? resid = 4E86B0CF20EF15AD！24884 & app = WordPdf & authkey =! AMtj_EflYn2507c

在x86_64中，以下任何一项都无法重新排序：

引用：

• Read-X - Read-Y
• Read-X - Write-Y
• Write-X - Write-Y

2.在x86_64中，可以重新排序以下任何一项：Write-X < - > Read-Y。为了防止它，使用std :: memory_order_seq_cst屏障，它可以在x86_64中生成4个代码选项，具体取决于编译器：http：//www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings  html的

引用：

1. load：MOV（来自内存）存储：MOV（到内存），MFENCE
2. load：MOV（来自内存）store：LOCK XCHG（to memory）
3. load：MFENCE + MOV（来自内存）存储：MOV（到内存）
4. load：LOCK XADD（0，from memory）store：MOV（to memory）

内存屏障与体系结构CPU指令（x86_64，PowerPC，ARMv7，ARMv8，AArch64，Itanium）之间的对应关系汇总表：http：//www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings 。 HTML

您可以通过单击以下链接查看不同编译器的实际汇编代码。您还可以选择其他架构：ARM，ARM64，AVR，PowerPC。

GCC 6.1（x86_64）：

• load()/ store()：https://godbolt.org/g/xq9ulH
• RMW（fetch_add）：https：//godbolt.org/g/dp1zZ0
• CAS（compare_exchange_weak()/ compare_exchange_strong()）：https：//godbolt.org/g/OMuXmz
• std::atomic_flag::test_and_set()：https：//godbolt.org/g/7ksl0J

Clang 3.8（x86_64）：

• load()/ store()：https://godbolt.org/g/gfpeZW
• RMW -  fetch_add：https：//godbolt.org/g/afoIQW
• CAS -  compare_exchange_weak()/ compare_exchange_strong()：https://godbolt.org/g/kYXzK6
• std::atomic_flag::test_and_set()：https：//godbolt.org/g/RD5fJG

此外，我们将在表格中简要说明各种内存屏障对CAS（比较和交换）的顺序有何影响 - 说明：http：//en.cppreference.com/w/cpp/atomic/原子/ compare_exchange

重新排序内存访问操作的示例

现在我们将展示从4个连续操作重新排序的更复杂的例子：LOAD，STORE，LOAD，STORE。

•蓝色矩形指定原子操作

•浅蓝色内部的深蓝色矩​​形（在示例3和4中）是复合原子读 - 修改 - 写（RMW）指令的一部分，由多个操作组成

•白色矩形是常见的非原子操作

我们将给出4个例子。每个示例都将演示使用原子变量围绕操作的普通变量对操作进行重新排序。但仅在示例1和3中，一些原子操作之间的重新排序也是可能的。

1 ^日的情况下是有趣，几个关键部分可融合成一体。

编译器无法在编译时执行此类重新排序，但编译器允许CPU在运行时执行此重新排序。因此，在不同线程中以不同顺序运行的关键部分的融合不会导致死锁，因为处理器可以看到初始指令序列。
因此，处理器将尝试提前进入第二个关键部分，但如果不能，则将继续完成第一个关键部分。

3 ^次的情况下是有趣，两种化合物的原子指令的部分可以被重新排序：

存储⇔加载B

• 这可以通过PowerPC架构实现，其中复合操作由3个独立的ASM指令（lwarx，addi，stwcx）组成，其原子性通过LL / SC技术（wiki-link）实现; 对于汇编程序代码，请参阅：  godbolt.org/g/j8uw7n  编译器无法在编译时执行此类重新排序，但编译器允许CPU在运行时执行此重新排序。

2 ^次的情况下是有趣，性病:: memory_order_seq_cst是最强的障碍，似乎禁止原子或非原子操作的任何重新排序自己周围。但是seq_cst-barriers与获取/释放相比只有一个额外的属性 - 只有两个原子操作都有seq_cst-barrier，然后操作序列STORE-A（seq_cst）; LOAD-B（seq_cst）; 不能重新订购。以下是C ++标准中的2个引号：

1.仅对于使用障碍memory_order_seq_cst的操作保留严格的相互执行顺序，标准C ++ 11§29.3（3）：http：//www.open-std.org/jtc1/sc22/wg21/docs/papers/ 2016 / n4606.pdf

引用：

§29.3（3）

有须在所有memory_order_seq_cst操作的单个总s阶，与顺序和修改订单所有受影响的位置，使得从一个原子物体M加载一个值的每个memory_order_seq_cst动作B遵循以下值中的一个的“之前发生”一致：...

2.如果原子操作具有与memory_order_seq_cst不同的障碍，则可以在允许的方向上使用memory_order_seq_cst操作对其进行重新排序，标准C ++ 11§29.3（8）：http：//www.open-std.org/jtc1/ SC22 / WG21 /文档/文件/ 2016 / n4606.pdf

引用：

§29.3（8）

[注意：memory_order_seq_cst仅针对没有数据争用且仅使用memory_order_seq_cst操作的程序确保顺序一致性。除非使用极度谨慎，否则使用较弱的订购将使此保证无效。特别是，memory_order_seq_cst围栏仅确保围栏本身的总订单。通常，Fences不能用于恢复具有较弱排序规范的原子操作的顺序一致性。 - 结束说明]

允许在seq_cst -atomic操作周围重新排序非seq_cst原子操作（原子和非原子）的方向与获取/释放相同：

• a.load(memory_order_seq_cst)- 允许与a.load(memory_order_acquire)其他非seq_cst原子操作                                                                                                               相同的重新排序
• b.store(memory_order_seq_cst)- 允许与a.store(memory_order_release)其他非seq_cst原子操作相同的重新排序

更严格的订单是可能的，但不能保证。

在seq_cst以及获取和释放的情况下，STORE（seq_cst）之后不能执行任何操作，并且在LOAD（seq_cst）之后不能执行任何操作。

但是在相反的方向上，可以重新排序，例如C ++代码和在Assembler x86_64和PowerPC上生成的代码。

现在，我们将显示编译器允许CPU使用的指令顺序的更改，例如，GCC for x86_64和PowerPC。

可以执行以下顺序更改memory_order_seq_cst操作：

• 在x86_64上，在CPU级别，允许存储 - 加载重新排序。也就是说，可以重新排序以下序列：                                                                                                                                     STORE-C(release); LOAD-B(seq_cst);   ⇒    ，如在x86_64架构中，仅在STORE（seq_cst）之后添加MFENCE，但对于LOAD（seq_cst），汇编指令对于LOAD（释放）和LOAD（放宽）是相同的）：https：//godbolt.org/g/BsLqasLOAD-B(seq_cst); STORE-C(release);         
• 在PowerPC上，在CPU级别，允许存储加载，存储 - 存储重新排序等。也就是说，可以重新排序以下序列：                                                                                                  ⇒                                                 ，如在PowerPC架构上，对于seq_cst-barrier，同步（hwsync）仅在STORE（seq_cst）之前和LOAD（seq_cst）之前添加。因此，STORE（seq_cst）和LOAD（seq_cst）之间的所有指令都可以在STORE（seq_cst）之前执行：https：//godbolt.org/g/dm7tWd STORE-A(seq_cst); STORE-C(relaxed); LOAD-C(relaxed);LOAD-C(relaxed); STORE-C(relaxed); STORE-A(seq_cst);

有关更多详细信息，请参阅以下示例，其中包含3个具有语义的变量：seq_cst和relaxed。

C ++编译器允许重新排序

• PowerPC的C ++到ASM：https：  //godbolt.org/g/mEM8T8
• C ++到ASM for x86_64：https：//godbolt.org/g/Tft2vw

为什么订单的这种变化可能？因为C ++编译器生成汇编代码，允许您对x86_64和PowerPC CPU进行重新排序：

引用：

在指令之间没有汇编程序屏障的情况下，不同CPU允许重新排序

“内存障碍：软件黑客的硬件视图”Paul E. McKenney 2010年6月7日：http：//www.rdrop.com/users/paulmck/scalability/paper/whymb.2010.06.07c.pdf

线程之间还有一个数据交换功能，它表现在4个线程或更多线程的交互上。如果以下操作中的至少一个不使用最严格的屏障memory_order_seq_cst，则不同的线程可以以不同的顺序看到相同的更改。例如：

1. 如果thread-1首先改变了某个值
2. 并且线程2改变了一些值
3. 然后，thread-3可以首先看到thread-2所做的更改，然后才会看到thread-1所做的更改
4. 相反，thread-4可以先看到thread-1所做的更改，然后才会看到thread-2所做的更改。

这是可能的，因为高速缓存一致性协议的硬件特征和CPU中核心的位置拓扑。在这种情况下，在看到其他核心所做的更改之前，有两个核心可以看到彼此所做的更改。为了使所有线程能够以相同的顺序看到变化，即它们将具有单个总顺序（C ++11§29.3（3）），所有操作（LOAD，STORE，RMW）都必须与内存屏障memory_order_seq_cst：http：//en.cppreference.com/w/cpp/atomic/memory_order

在以下示例中，程序永远不会以assert（z.load（）！= 0）错误结束; 由于所有操作都使用最严格的内存屏障 - memory_order_seq_cst：http：//coliru.stacked-crooked.com/a/52726a5ad01f6529

此链接采用在线编译器中的代码：http：  //en.cppreference.com/w/cpp/atomic/memory_order

在图中，我们将通过4个线程的示例显示Acquire-Release语义和Sequential语义可能的顺序变化：

1. 获取 - 发布：

• 可以在允许的方向上更改普通变量的顺序
• 可以使用Acquire-Release语义更改原子变量的顺序

2. 顺序：

• 可以在允许的方向上更改普通变量的顺序
• 这是不可能改变原子变量的连续语义顺序

主动自旋锁和递归自旋锁

我们将通过实现自己的主动锁的示例来展示如何将内存屏障应用于原子操作：自旋锁和递归 - 自旋锁。

此外，我们将需要这些锁来锁定表中的单独行（行锁）而不是锁定整个表（表锁）。这将增加并行度并提高性能，因为不同的线程可以并行处理不同的行，而不会锁定整个表。

可以限制操作系统提供的同步对象的数量。表中的行数可以等于数百万或数十亿，许多操作系统不允许您创建这么多的互斥锁。并且，就RAM而言，自旋锁的数量可以是任意数量。这就是为什么它们可以用于锁定每一行。

实际上，自旋锁每行+1字节，或者在使用递归自旋锁时为+17字节（标志为1字节，递归计数器为8字节，thread_id线程数为8字节）。

• 我们已经给出了一个实现和使用自旋锁的例子：[24] http://coliru.stacked-crooked.com/a/92b8b9a89115f080
• 现在我们将给出一个实现和使用recursive_spinlock的例子：[25] http://coliru.stacked-crooked.com/a/eae6b7da971810a3

recursive_spinlock和普通自旋锁之间的主要区别在于recursive_spinlock可以被同一个线程重复锁定，即它支持递归嵌套锁。同样，std :: recursive_mutex与std :: mutex不同。

嵌套锁的示例：

• spinlock_t - 发生永久死锁 - 不撤回结果：[26] http://coliru.stacked-crooked.com/a/d3b93315270fd367
• recursive_spinlock_t - 正常工作 - 撤回结果shared_value = 50：[27] http://coliru.stacked-crooked.com/a/875ad2754a007037

让我们看看recursive_spinlock_t是如何工作的。

如果您尝试在MSVC 2013编译器中运行此代码，由于std :: this_thread :: get_id（）函数，您将获得非常强烈的减速：https：//connect.microsoft.com/VisualStudio/feedback/details/ 1558211

我们将修改recursive_spinlock_t类，以便将线程id缓存在变量__declspec（thread）中 - 这是C ++ 11标准的thread_local模拟。此示例将在MSVC 2013中显示出良好的性能：[28] http://coliru.stacked-crooked.com/a/3090a9778d02f6ea

这是旧版MSVC 2013的补丁，所以我们不会考虑这个解决方案的美妙之处。

据信，在大多数情况下，互斥锁的递归锁定是一个设计错误，但在我们的例子中，这可能是一个缓慢但有效的代码。其次，所有都可能是错误的，并且使用嵌套的递归锁定，recursive_spinlock_t将工作得更慢，并且spinlock_t将永远挂起 - 这更好，这取决于你。

在使用我们的线程安全指针safe_ptr <T>的情况下，两个示例都非常合乎逻辑，但第二个示例仅适用于recursive_spinlock：

• safe_int_spin_recursive->second++;     //可以使用：spinlock＆recursive_spinlock
• safe_int_spin_recursive->second = safe_int_spin->second + 1;    //只有recursive_spinlock

实现自己的高性能共享互斥体

众所周知，新的互斥体逐渐出现在新的C ++标准中：http：//en.cppreference.com/w/cpp/thread

• C ++ 11：mutex，timed_mutex，recursive_mutex，recursive_timed_mutex
• C ++ 14：shared_timed_mutex
• C ++ 17：shared_mutex

shared_mutex是一个互斥体，允许许多线程同时读取相同的数据，如果那时没有线程可以更改这些数据。Shared_mutex未在一天内创建。与通常的std :: mutex相比，它的性能存在争议。

shared_mutex的经典实现与读者数量的计数显示了速度的优势，只有当许多读者长时间持有锁定时 - 即他们已经阅读了很长时间。对于短读取，shared_mutex只会降低程序速度并使代码复杂化。

但是所有shared_mutex实现在短读取中都是如此之慢？

std :: shared_mutex和boost :: shared_mutex运行缓慢的主要原因是读者的原子计数器。每个读取器线程在锁定期间递增计数器并在解锁时递减计数器。结果，线程不断地在核心之间驱动一个高速缓存线（即，驱动其独占状态（E））。根据这种实现的逻辑，每个读者线程计算当前读者的数量，但这对读者线程来说绝对不重要，因为只有没有一个作者才重要。并且，由于增量和减量是RMW操作，它们总是生成存储缓冲区清理（MFENCE x86_64），并且在x86_64级别，asm实际上对应于顺序一致性的最慢语义。

我们试着解决这个问题。

存在一种被分类为无写无争用的算法 - 当没有单个存储器单元可以写入多个线程时。在更一般的情况下，没有一个高速缓存行可以写入多个线程。为了使我们的共享互斥体只在读者在场的情况下被归类为无写入无争用，读者必须互相干扰 - 即每个读者都应该将一个标志（由它读取）写入其中。拥有单元格并在读取结束时删除同一单元格中的标志 - 无需RMW操作。

写无争用是最有效的保证，比无等待或无锁更有效。

每个单元可能位于单独的高速缓存行中以排除错误共享，并且单元可能紧密排列 - 在一个高速缓存行中16 - 性能损失将取决于CPU和线程数。

在设置标志之前，阅读器会检查是否有编写器 - 即是否存在独占锁。并且由于在编写器很少的情况下使用共享互斥锁，因此所有使用的内核都可以在其共享状态（S）的缓存中具有该值的副本，其中它们将接收编写器的值。标志3个周期，直到它改变。

对于所有作者来说，通常都有相同的标志want_x_lock - 这意味着目前有一个作家。编写器线程使用RMW操作设置和删除它。

lock（）：while(!want_x_lock.compare_exchange_weak(flag, true, std::memory_order_acquire))

unlock（）：want_x_lock.store(false, std::memory_order_release);

但是为了使读者不互相干扰，他们应该在不同的存储单元中写入有关其共享锁的信息。我们将为这些锁分配一个数组，我们将使用默认模板参数20设置它的大小。在第一次调用时，lock_shared（）线程将自动注册，占用此数组中的某个位置。如果线程数大于数组的大小，则在调用lock_shared（）时，其余线程将调用writer的独占锁。很少创建线程，操作系统创建它们所花费的时间太长，以至于在我们的对象中注册新线程的时间可以忽略不计。

我们将确保没有明显的错误 - 通过示例，我们将证明一切正常，之后我们将示意性地演示我们的方法的正确性。

以下是这种快速共享锁的示例，其中读者不会相互干扰：[30] http://coliru.stacked-crooked.com/a/b78467b7a3885e5b

1. 在共享锁期间，不能更改对象。这一行的两个递归共享锁显示了这一点：assert（readonly_safe_map_string-> at（“apple”）== readonly_safe_map_string-> at（“potato”））; - 两行的值应该总是相等，因为我们在一个eXclusive-lock std :: lock_guard下更改了std :: map中的2行
2. 在阅读过程中，我们真的调用了lock_shared（）函数。让我们将循环减少到两次迭代，删除修改数据的行，并在main（）函数中只保留std :: map中的前两个插入。现在我们将S字母的输出添加到lock_shared（）函数，将X字母的输出添加到lock（）函数。我们看到首先有两个X插入，然后才会看到S - 实际上，当读取const对象时，我们调用shared_lock（）：[31] http://coliru.stacked-crooked.com/a/ 515ba092a46135ae
3. 在更改期间，我们确实调用了lock（）函数。现在我们将注释掉读数，只留下更改数组的操作。现在只显示X个字母：[32] http://coliru.stacked-crooked.com/a/882eb908b22c98d6

主要任务是确保同时只能存在两种状态中的一种：

1. 任意数量的线程成功执行了lock_shared（）。所有尝试执行lock（）的线程都应该更改为待机模式。
2. 其中一个线程成功执行了lock（）。所有其他尝试执行lock_shared（）或lock（）的线程应该更改为待机模式。

示意性地，兼容状态表如下所示。

让我们考虑我们的contention_free_shared_mutex的算法，用于2个线程一次尝试执行操作的情况：

• T1读取和T2读取：读取器线程使用lock_shared（）锁定互斥锁 - 这些线程不会相互干扰，因为它们会为每个线程分别写入存储器单元中的锁定状态。此时不应该有写入线程的独占锁定（want_x_lock == false）。除非线程数大于专用单元的数量。在这种情况下，即使读取器线程也只使用CAS函数锁定：want_x_lock = true。
• T1-write和T2-write：写入线程相互竞争同一个标志（want_x_lock），并尝试使用原子CAS函数将其设置为“true”：want_x_lock.compare_exchange_weak（）; 在这里，一切都很简单，就像我们上面讨论的通常的recursive_spinlock_t一样。
• T1读取和T2写入：读取器线程T1将锁定标志写入其单元，并且仅在此之后检查是否设置了标志（want_x_lock）。如果设置为（true），则取消其锁定，然后等待状态（want_x_lock == false）并从头开始重复此算法。

写入线程T2设置标志（want_x_lock = true），然后等待直到所有读取器线程从其单元格中移除锁定标志。

写入者线程的优先级高于读者。如果他们同时设置了他们的锁定标志，那么读者线程通过以下操作检查是否存在写入线程（want_x_lock == true）。如果有写入线程，则读取器取消其锁定。编写器线程看到读者没有锁定并成功完成锁定功能。由于顺序一致性（std :: memory_order_seq_cst）的语义，满足了这些锁的全局顺序。

下面，示意性地示出了两个线程（读取器和写入器）的交互。

全尺寸：https：  //hsto.org/files/422/036/ffc/422036ffce8e4c7e9b464c8a293fd410.jpg

在这两种功能 lock_shared()和lock()，对于标记操作1和2中使用的std::memory_order_seq_cst-即该操作须为全部线程的单个总次序。

在cont-free shared-mutex中自动注销线程

当一个线程首次访问我们的锁时，它就会被注册。当此线程终止或锁定被删除时，应取消注册。

但现在让我们看看如果20个线程与我们的互斥锁一起工作然后这些线程终止并尝试注册新的20个线程会发生什么，只要锁的数组是20：[33] http://coliru.stacked-crooked.com/ A / f1ac55beedd31966

正如您所看到的，前20个线程已成功注册，但以下20个线程无法注册（register_thread = -1）并且必须使用编写器的独占锁，尽管之前的20个线程已经消失且不再使用锁。

为了解决这个问题，我们在删除线程时添加线程注册的自动取消。如果线程已经使用了很多这样的锁，那么在线程终止时，应该在所有这样的锁中取消注册。并且，如果在删除线程时存在已经删除的锁，则由于尝试取消不存在的锁中的注册而不会发生错误。

示例：[34] http://coliru.stacked-crooked.com/a/4172a6160ca33a0f

如您所见，首先注册了20个线程。删除它们并创建了20个新线程后，它们也可以注册 - 在相同的数字下register_thread = 0 - 19（参见示例输出）。

现在我们将展示即使线程已经使用锁定，然后锁定被删除，然后在线程终止时，由于尝试取消不存在的锁定对象中的注册，将不会出现错误：[ 35] http://coliru.stacked-crooked.com/A/d2e5a4ba1cd787da

我们设置定时器，以便创建20个线程，使用我们的锁执行读取并在500ms处入睡; 那时，在100ms内，可以删除包含我们内部的锁contention_free_shared_mutex的contfree_safe_ptr对象; 并且只有在那20个线程可以唤醒并终止之后。终止后，由于远程锁定对象中的注销而没有错误。

作为一个小小的补充，我们将支持MSVS2013，以便旧编译器的所有者也可以看到这个例子。我们添加了对注册线程的简化支持，但没有注销线程的可能性。

最终结果将作为一个例子显示，其中考虑了上述所有想法。

示例：[36] http://coliru.stacked-crooked.com/a/0a1007765f13aa0d

算法的正确运行和选定的障碍

上面我们进行了没有明显错误的测试。但是为了证明工作能力，有必要创建一个可能的操作顺序和变量可能状态变化的方案。

独占锁（）/ unlock（）几乎与recursive_spinlock_t一样简单。所以，我们不会详细考虑它。

上面详细讨论了lock_shared（）的读者线程竞争和lock（）的编写者线程竞争。

现在主要的任务是表明lock_shared（）在所有情况下至少使用Acquire-semantic; 并且unlock_shared（）在所有情况下至少使用Release-semantic。但这不是重复递归锁定/解锁的先决条件。

现在让我们看看这些障碍是如何在我们的代码中实现的。

lock_shared()示意性地显示了障碍。红色交叉箭头表示禁止更改订单的方向：

unlock_shared()示意性显示的障碍：

全尺寸：https：//hsto.org/files/065/9ce/bd7/0659cebd72424256b6254c57d35c7d07.jpg

带有标记条件转换的全尺寸：https：//hsto.org/files/fa7/4d2/2b7/fa74d22b7cda4bf4b1015ee263cad9ee.jpg

我们还显示了相同函数lock_shared（）的框图：

全尺寸图片：

https://hsto.org/files/c3a/abd/4e7/c3aabd4e7cfa4e9db55b2843467d878f.jpg

在椭圆形块中，指示了严格的操作序列：

1. 执行第一个红色操作
2. 然后，执行紫色操作

绿色表示可以按任何顺序执行的更改，因为这些更改不会锁定我们的“共享互斥锁”，但只会增加递归嵌套计数 - 这些更改仅对本地使用很重要。也就是说，这些操作并不是锁的实际入口。

由于执行了2个条件，因此假设考虑了多线程的所有必要的副作用：

1.决定输入锁定的时刻总是至少具有“获取”级别的语义：

• want_x_lock.load(std::memory_order_seq_cst)
• want_x_lock.compare_exchange_weak(flag, true, std::memory_order_seq_cst)

2.首先，我们总是锁定（1红色），然后我们检查（2紫色），我们是否可以进入锁定。

此外，通过将这些操作及其序列与算法的逻辑进行简单比较，可以验证算法的正确性。

从多线程执行逻辑的角度来看，我们的锁“contention_free_shared_mutex”的所有其他功能都更加明显。

此外，在递归锁中，原子操作不需要具有std :: memory_order_acquire障碍（如图中所示），有足够的设置std :: memory_order_relaxed，因为这不是锁的实际入口 - 我们已经在锁定。但这并没有增加太多的速度，并且可能使理解复杂化。

使用代码

如何使用

如何contention_free_shared_mutex<>在C ++中使用高度优化的shared_mutex 的示例。

下载此代码用于Linux（GCC 6.3.0）和Windows（MSVS 2015/13）：  contfree_shared_mutex.zip - 8.4 KB

要在Linux上使用编译器Clang ++ 3.8.0进行编译，您应该更改Makefile。

隐藏   收缩    复制代码

#include < iostream >
#include < thread >
#include < vector >

#include "safe_ptr.h"

template < typename T >
void func(T &s_m, int &a, int &b)
{
	for (size_t i = 0; i < 100000; ++i)
	{
		// x-lock for modification
		{
			s_m.lock();
			a++; 
			b++;
			s_m.unlock();
		}

		// s-lock for reading
		{
			s_m.lock_shared();
			assert(a == b);		// will never happen
			s_m.unlock_shared();
		}
	}
}

int main() {

	int a = 0;
	int b = 0;
	sf::contention_free_shared_mutex< > s_m;
	
	// 19 threads
	std::vector< std::thread > vec_thread(20);
	for (auto &i : vec_thread) i = std::move(std::thread([&]() { func(s_m, a, b); }));
	for (auto &i : vec_thread) i.join();
	
	std::cout << "a = " << a << ", b = " << b << std::endl;
	getchar();

	return 0;
}

此代码在在线编译器中：http：//coliru.stacked-crooked.com/a/11c191b06aeb5fb6

如您所见，我们sf::contention_free_shared_mutex<>的使用方式与标准相同  std::shared_mutex。

基准：std :: shared_mutex VS contention_free_shared_mutex

以下是针对单个服务器CPU Intel Xeon E5-2660 v3 2.6 GHz测试16个线程的示例。首先，我们对蓝色和紫色线感兴趣：

• safe_ptr<std::map, std::shared_mutex> 
• contfree_safe_ptr<std::map>

您可以下载此Linux（GCC 6.3.0）和Windows（MSVS 2015）基准：bench_contfree.zip - 8.5 KB

要在Linux上使用编译器Clang ++ 3.8.0进行编译，您应该更改Makefile。

启动命令行：

numactl --localalloc --cpunodebind = 0 ./benchmark 16

针对不同比例的锁类型的各种锁的性能：共享锁和独占锁：

• ％exclusive locks =（写入操作的百分比）
• ％shared locks = 100 - （写入操作的百分比）

（在std :: mutex的情况下 - 总是使用独占锁）

表现（越大越好）

MOps - 每秒百万次操作

• 对于0％的修改 - 我们的共享互斥体（作为«contfree_safe_ptr <map>»的一部分）显示性能34.60 Mops，比标准std :: shared_mutex 快14倍（作为«safe_ptr <map，std :: shared_mutex的一部分） >»）只显示2.44 Mops。                                                                                               
• 对于15％的修改 - 我们的共享互斥体（作为«contfree_safe_ptr <map>»的一部分）显示性能5.16 Mops，比标准std :: shared_mutex 快7倍（作为«safe_ptr <map，std :: shared_mutex的一部分） >»）仅显示0.74 Mops。

我们的锁«无争用共享互斥锁»适用于任意数量的线程：前36个线程为无争用，下一个线程为独占锁。从图中可以看出 - 即使是排它锁«std :: mutex»也比«std :: shared_mutex»更快地完成了15％的修改。

无争用锁的线程数36由模板参数指定，并且可以改变。

现在我们将显示不同比例的锁类型的中位延迟：共享锁和排它锁。

在测试代​​码main.cpp中，您应该设置： const bool measure_latency = true;

启动命令行：

numactl --localalloc --cpunodebind = 0 ./benchmark 16

中位延迟（越低越好），微秒

因此，我们创建了一个共享锁，其中读取器在锁定和解锁期间不会相互干扰，这与std :: shared_timed_mutex和boost :: shared_mutex不同。但是我们为每个线程提供了以下附加分配：lock数组中的64个字节+ 24个字节被unregister_t结构占用，用于注销+从hash_map指向此结构的元素。总的来说，每个线程约为100个字节。

更严重的问题是缩放功能。例如，如果您有8个CPU（英特尔®至强®处理器E7-8890 v4），每个CPU有24个内核（每个48个超线程线程），则总共有384个逻辑内核。在写入之前，每个写入器线程必须读取24576个字节（384个核心中的每个64个字节）。但他们可以通过并行阅读。它肯定比等待一个高速缓存行始终从每个384个线程到每个线程更好，就像普通的std :: shared_timed_mutex和boost :: shared_mutex（对于任何类型的唯一/共享锁）一样。但是通过不同的方法实现并行1000个核心和更多核心，而不是通过调用原子操作来处理每个消息。上面讨论的所有选项 - 原子操作，主动锁定，无锁数据结构 - 对于小延迟（0。

对于每秒操作数量的高指标（例如，一般的高系统性能和数万个逻辑核心的可扩展性），它们使用大规模并行方法，“隐藏延迟”和“批处理” - 批处理当消息被排序（用于映射）或分组（用于hash_map）并与已经可用的已排序或分组的数组融合50-500 usec时。因此，每个操作都有一百倍的延迟，但这种延迟一次发生在大量线程中。结果，由于使用“细粒度时间多线程”而发生隐藏延迟。

我们假设：每条消息都有100倍的延迟，但正在处理的消息数量是10,000倍。这个时间单位的效率提高了百倍。在GPU上进行开发时使用这些原则。或许，在以下文章中，我们将更详细地讨论这个问题。

兴趣点

结论：我们已经开发了自己的“共享互斥体”，它不需要读取器线程彼此同步，如标准std :: shared_mutex中所示。我们已经严格证明了我们“共享互斥体”工作的正确性。此外，我们还研究了原子操作，内存屏障和允许的重新排序方向，以便最详细地优化性能。接下来，与标准的std :: shared_mutex相比，我们将看到我们能够提高多线程程序的性能。