我们使 std:shared_mutex 快 10 倍

在本文中，我们将详细介绍原子操作和 C++11 内存屏障以及它在 x86_64 CPU 上生成的汇编指令。接下来，我们将展示如何将 contfree_safe_ptr<std::map> 的工作加速到在功能方面类似于 std::map<> 的复杂和优化的无锁数据结构的级别，例如示例：来自 libCDS 库（并发数据结构库）的 SkipListMap 和 BronsonAVLTreeMap：https://github.com/khizmax/libcds。我们可以为任何最初用作 contfree_safe_ptr<T> 的非线程安全 T 类获得这样的多线程性能——它是 safe_ptr<T, contention_free_shared_mutex> 类，其中 contention_free_shared_mutex 是自己优化的共享互斥锁。即，我们将展示如何实现您自己的高性能无争用共享互斥锁，这在阅读上几乎不冲突。我们实现了我们自己的活动锁——自旋锁和递归自旋锁——来锁定更新操作中的行。我们将创建 RAII 阻塞指针以避免多重锁定的成本。以下是性能测试的结果。作为“只是为了好玩”的奖励，我们将演示我们自己的简化分区类型 partitioned_map 类的实现方式，该类针对多线程进行了更加优化，由几个 std::map 组成，类似于 RDBMS 中的分区表，当最初知道每个部分的边界时。如果我们更改一组线程中的相同数据，即，如果我们在多个线程中同时运行 thread_func() 函数：那么每个调用 thread_func() 函数的线程都将普通共享变量 int a 加 1；在一般情况下，这样的代码不会是线程安全的，因为与普通变量的复合操作（RMW - 读取-修改-写入）由许多小操作组成，另一个线程可以在这些小操作之间更改数据。操作 a = a+1;至少包含三个小操作：

对于非原子int a，如果初始a=0； 2个线程执行操作a=a+1；那么结果应该是a=2；但是可能会发生以下情况（逐步）： int a = 0; // register1 = ?, register2 = ?, a = 0Thread 1: register1 = a; // register1 = 0, register2 = ?, a = 0Thread 2: register2 = a // register1 = 0, register2 = 0, a = 0Thread 1: register1++; // register1 = 1, register2 = 0, a = 0线程 2: register2++; // register1 = 1, register2 = 1, a = 0Thread 1: a = register1; // register1 = 1, register2 = 1, a = 1Thread 2: a = register2; // register1 = 1, register2 = 1, a = 1 两个线程对同一个初始值=0的全局变量加+1，但最终变量a=1——这样的问题叫做Data-Races。使用带有原子变量的原子指令——但有一个缺点，原子函数的数量非常少——因此，借助此类函数很难实现复杂的逻辑：http://en.cppreference.com/w /cpp/atomic/atomic 使用锁（std::mutex、std::shared_timed_mutex、spinlock…）——它们允许1个线程一个接一个地进入锁定的代码，因此不会出现数据竞争的问题，我们可以通过使用任何普通的非线程安全对象来使用任意复杂的逻辑。对于 std::atomic<int> a: 如果最初 a=0; 2个线程执行操作a+=1；那么结果总是 a=2; std::atomic < int > a = 0; // register1 = ?, register2 = ?, a = 0Thread 1: register1 = a; // register1 = 0, register2 = ?, a = 0Thread 1: register1++; // register1 = 1, register2 = 0, a = 0线程 1: a = register1; // register1 = 1, register2 = 0, a = 1Thread 2: register2 = a; // register1 = 1, register2 = 1, a = 1Thread 2: register2++; // register1 = 1, register2 = 2, a = 1Thread 2: a = register2; // 寄存器 1 = 1，寄存器 2 = 2，a = 2

在支持 LL/SC 的处理器上，例如在 ARM 上，会发生其他步骤，但具有相同的正确结果：a = 2。顺序一致性 std::memory_order_seq_cst 是默认内存屏障（最严格和可靠，但也是相对于其他人最慢）。优化：对于 std::atomic<T> a;两种优化是可能的，这对于 volatile T a 是不可能的；融合优化：a = 10；一 = 20;可以用a = 20的编译器代替；用常数优化替代：a = 1；本地 = 一个;可以用编译器代替 a = 1;本地 = 1;重新排序： std::atomic<T>a;操作可以根据使用的内存屏障 std::memory_order _... 限制对普通变量的操作和其他原子变量的操作的重新排序。 相反， volatile T a;不影响常规变量的顺序（非原子/非易失性），但对所有易失性变量的调用始终保持严格的相互顺序，即任何两个易失性操作的执行顺序都不能被编译器改变，但不是由 CPU。溢出：std::memory_order_release、std::memory_order_acq_rel、std::memory_order_seq_cst 内存屏障，为 std::atomic<T> a 指定；操作，在执行原子操作之前启动所有常规变量的溢出。也就是说，这些屏障将CPU寄存器中的常规变量上传到主存/缓存中，除非编译器可以100%保证这个局部变量不能在其他线程中使用。原子性/对齐：对于 std::atomic<T> a;其他线程看到操作已完全执行或根本未执行。对于 Integral 类型 T，这是通过编译器在内存中对齐原子变量位置来实现的 - 至少，该变量位于单个缓存行中，以便 CPU 的一次操作可以更改或加载该变量。相反，编译器不保证 volatile 变量的对齐。易失性变量通常用于访问设备的内存（或在其他情况下），因此设备驱动程序的 API 会返回一个指向易失性变量的指针，如果需要，此 API 可确保对齐。

RMW 操作的原子性（读-修改-写）：对于 std::atomic<T> a;操作 ( ++, --, += , -= , *=, /=, CAS, exchange) 以原子方式执行，即如果两个线程执行操作 ++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。 GCC 7.0 编译器重新排序：它交换写入内存 b = 5；并从内存上传到寄存器 int tmp_c = c ;。这允许你尽早请求“c”值，而在 CPU 等待这个长操作的同时，CPU 管道允许执行操作 b = 5；因为这两个操作不相互依赖。

它结合从内存上传到寄存器 int tmp_a = a;和加法运算 - tmp_c = tmp_c + tmp_a;结果，我们有一个操作 add eax, a[rip] 而不是两个操作。 x86_64 CPU重新排序：CPU可以将实际写入内存的mov b[rip], 5和从内存读取进行交换，结合加法操作——add eax, a[rip]。在通过 mov b[rip], 5 指令开始写入内存时，会发生以下情况：首先，将 5 的值和 b[rip] 的地址放入 Store-buffer 队列，包含地址的缓存行预计所有 CPU 内核中的 b[rip] 都将失效并等待它们的响应，然后 CPU-Core-0 为包含 b[rip] 的缓存行设置“排他”状态。只有在此之后，才会将 Store-buffer 中的 5 值实际写入 b[rip] 处的该缓存行。有关 x86_64 MOESI / MESIF 上的缓存一致性协议的更多详细信息，所有内核立即可见的更改，请参阅此链接。为了不一直等待——在“5”放入Store-Buffer之后，无需等待实际的缓存条目，我们可以开始执行以下指令：从内存中读取或寄存器操作。这就是 x86_64 CPU 的功能：英特尔® 64 位和 IA-32 架构软件开发人员手册第 3 卷（3A、3B、3C 和 3D）：系统编程指南。 Intel-64 内存排序模型允许使用较早的存储将加载重新排序到不同的位置。但是，加载不会与存储重新排序到同一位置。 x86_64 系列的 CPU 具有强大的内存模型。具有弱内存模型的 CPU，例如 PowerPC 和 ARM v7/v8，可以执行更多的重新排序。

以下是可能对普通变量、易失性变量和原子变量的内存中的条目进行重新排序的示例。这段带有普通变量的代码可以由编译器或 CPU 重新排序，因为它的含义在一个线程内不会改变。但是在一组线程中，这种重新排序会影响程序的逻辑。如果两个变量是 volatile，则可以进行以下重新排序。编译器不能在编译时对 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 memory_order_consume。立即，我们注意到我们实际上不会使用 memory_order_consume 屏障，因为在标准中，对其使用的实用性存在怀疑 - 来自标准的引用。 (1.3) — memory_order_consume：加载操作对受影响的内存位置执行消耗操作。 [注意：首选memory_order_acquire，它比memory_order_consume提供更强的保证。实现发现提供比 memory_order_acquire 更好的性能是不可行的。规范修订正在考虑中。 — 尾注] memory_order_acq_rel。另外，我们注意到memory_order_acq_rel屏障只用于RMW（Read-Modify-Write）的原子复合操作，例如：compare_exchange_weak()/_strong(), exchange(), fetch_(add, sub, and, or, xor ) 或其对应的操作符：http://en.cppreference.com/w/cpp/atomic/atomic 其余四个内存屏障可用于任何操作，除了以下操作：“acquire”不用于 store() ，并且“释放”不用于 load()。

根据选择的内存屏障，对于编译器和 CPU，禁止将可执行代码相对于屏障向不同方向移动。现在让我们看看箭头指定了什么，什么可以互换，什么不能互换： 对于要互换的两条指令，两条指令的屏障必须允许这样的互换。因为“其他任何代码”是指没有任何障碍的普通非原子变量，因此它们允许任何顺序更改。以Relaxed-Release-Relaxed 为例，如您所见，更改相同内存屏障顺序的可能性取决于它们出现的顺序。让我们考虑一下，这些内存屏障是什么意思，它们给我们带来了什么好处，通过最简单的“自旋锁”类型锁的实现示例，它需要最常见的获取-释放重新排序语义。自旋锁是一种在使用方式上类似于 std::mutex 的锁。首先，我们直接在我们的程序体中实现了自旋锁的概念。然后，我们实现了一个单独的自旋锁类。要实现锁（互斥锁、自旋锁...），您应该使用获取-释放语义，C++11 标准 § 1.10.1 (3)。 … 例如，获取互斥锁的调用将对包含互斥锁的位置执行获取操作。相应地，释放相同互斥锁的调用将在相同位置执行释放操作。非正式地，对 A 执行释放操作会强制其他内存位置上的先前副作用对稍后对 A 执行消耗或获取操作的其他线程可见。 Acquire-Release 语义的要点是： Thread-2 after执行 flag.load(std::memory_order_acquire) 操作应该会看到 Thread-1 在执行 flag.store(0, std: :memory_order_release) 操作。

锁（互斥锁、自旋锁……）的基本目的是创建只能由一个线程同时执行的一部分代码。这样的代码区称为临界区。在其中，您可以使用任何普通代码，包括那些没有 std::atomic<> 的代码。内存屏障阻止编译器优化程序，从而使临界区的操作不会超出其限制。首先捕获锁的线程执行代码的这个锁，其余线程在循环中等待。当第一个线程释放锁时，CPU 决定下一个等待的线程将捕获它，等等。示例 1 更可取。因此，对于它，我们将示意性地展示使用内存屏障的意图——纯蓝色表示原子操作：屏障的目的很简单——编译器优化器不允许将指令从临界区移到外部：任何其他独立指令执行顺序的改变可以由编译器（编译时）或 CPU（运行时）执行，以优化性能。例如，这行 int new_shared_value = shared_value;可以在 lock_flag.clear(std::memory_order_release); 之前执行。这种重新排序是可以接受的，并且不会造成数据竞争，因为访问多个线程共有的数据的整个代码总是包含在两个屏障中——“获取”和“释放”。而在外面，有一段代码只对线程本地数据起作用，它的执行顺序无关紧要。线程本地依赖总是以类似于单线程执行的方式存储。这就是为什么， int new_shared_value = shared_value;不能在 shared_value + = 25 之前执行；

1, 6：编译器为加载操作生成汇编指令acquire-barrier，为存储操作生成释放屏障，如果这些屏障对于给定的CPU架构是必要的 2：编译器取消先前在CPU中的变量缓存registers 以便重新加载被另一个线程改变的这些变量的值——在 load(acquire) 操作之后 5：编译器将所有变量的值从 CPU 寄存器保存到内存中，以便它们可以被其他线程看到其他线程，即，它执行溢出（链接） - 直到存储（释放）3、4：编译器阻止优化器更改禁止方向上的指令顺序 - 由红色箭头指示 现在让我们看看会发生什么，如果我们使用 Relaxed-Release 语义而不是 Acquire-Release：在右边。在relaxed-Release的情况下，临界区中受锁保护的部分代码可以被编译器或CPU移到外面。然后，数据竞争就会出现问题——在锁定之前，许多线程将开始与数据同时工作，这些数据不是由原子操作处理的。请注意，通常不可能仅借助原子操作来实现与一般数据相关的所有逻辑，因为它们很少，而且速度相当慢。因此，执行以下操作更简单快捷：通过一个原子操作设置标志“关闭”，执行与线程共有的数据相关的所有非原子操作，以及设置标志“打开”。

线程 1 来得早一点，通过一条原子指令 test_and_set() 一次执行 2 个操作：它执行检查，如果 lock_flag == false，则将“真”值设置为它（即锁定自旋-lock) 并返回“false”。因此，while(lock_flag.test_and_set());表达式立即结束，临界区的代码开始执行。此时，线程 2 也开始执行这条原子指令 test_and_set()：它执行检查，如果 lock_flag == false，则设置“true”值。否则，它不会改变任何东西并返回当前的“真”值。因此，while(lock_flag.test_and_set());表达式将被执行，直到，while(lock_flag);线程1执行加法操作shared_value += 25；然后通过原子操作（即解锁自旋锁）设置 lock_flag=false 值。最后，线程2在等待条件lock_flag == false后，赋值lock_flag = true，返回“false”，完成循环。然后执行shared_value + = 25的加法；并分配 lock_flag = false （解锁自旋锁）。让我们看看 x86_64 的汇编代码如何，whi ......