65.9K
CodeProject 正在变化。 阅读更多。
Home

我们将 std::shared_mutex 加速 10 倍

AlexeyAB
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

5.00/5 (77投票s)

2017年4月24日

CPOL

43分钟阅读

viewsIcon

109444

downloadIcon

1224

x86_64 CPU 上的原子操作和 C++11 内存屏障及汇编指令

三篇相关文章

  1. 我们让任何对象都线程安全
  2. 我们让 std::shared_mutex 快 10 倍
  3. 线程安全的 std::map，速度堪比无锁 map

引言

锁基数据结构的高性能

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

接下来，我们将展示如何将 contfree_safe_ptr<std::map> 的性能提升到与功能类似的复杂且优化的无锁数据结构相媲美的水平，例如：libCDS 库（并发数据结构库）中的 SkipListMap 和 BronsonAVLTreeMap：https://github.com/khizmax/libcds。

而且，我们可以为任何最初非线程安全的 T 类提供这种多线程性能，将其用作 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() 函数的线程都会给普通共享变量 int a; 加 1。在一般情况下，这样的代码不是线程安全的，因为对普通变量的复合操作（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

两个线程都给初始值为 = 0 的同一个全局变量加了 +1，但最终变量 a = 1 - 这种问题称为数据竞争。

有三种方法可以避免此类问题：

  1. 使用带原子变量的原子指令——但有一个缺点，原子函数数量非常少——因此，很难用这类函数实现复杂的逻辑：https://cppreference.cn/w/cpp/atomic/atomic
  2. 为每个新容器开发自己的复杂无锁算法。
  3. 使用锁（std::mutex、std::shared_timed_mutex、spinlock…）——它们允许一次只有一个线程进入锁定的代码，因此数据竞争问题不会出现，我们可以使用任意复杂的逻辑，通过使用任何普通的非线程安全对象。

对于 std::atomic<int> a：如果最初 a=0; 并且有 2 个线程执行操作 a+=1;，那么结果将始终是 a=2;

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 标准：https://cppreference.cn/w/cpp/atomic/atomic

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

以下是意义相同的三个正确代码片段：

  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

有五个主要区别：

  1. 优化：对于 std::atomic<T> a;，可能发生两种对于 volatile 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; 不影响常规变量（非原子/非易失性）的顺序，但所有易失性变量的调用始终保持严格的相互顺序，即，编译器无法更改任何两个易失性操作的执行顺序，但此顺序可能被 CPU/PCI-express/其他存储此易失性变量的缓冲区所在的设备物理更改。
  3. 溢出：为 std::atomic<T> a; 操作指定的 std::memory_order_release、std::memory_order_acq_rel、std::memory_order_seq_cst 内存屏障会触发所有常规变量在原子操作执行前溢出（从 CPU 寄存器写入主内存）。也就是说，这些屏障会将 CPU 寄存器中的常规变量上传到主内存/缓存，除非编译器可以 100% 保证该局部变量不能在其他线程中使用。
  4. 原子性/对齐：对于 std::atomic<T> a;，其他线程会看到操作已完全执行或未执行。对于整数类型 T，这是通过编译器对内存中原子变量的位置进行对齐来实现的——至少，变量位于单个缓存行中，以便 CPU 的一个操作可以更改或加载该变量。相反，编译器不保证易失性变量的对齐。易失性变量通常用于访问设备内存（或在其他情况），因此设备驱动程序的 API 返回指向易失性变量的指针，并且该 API 会在必要时确保对齐。
  5. RMW 操作（读-修改-写）的原子性：对于 std::atomic<T> a;，操作（++、--、+=、-=、*=、/=、CAS、exchange）是原子执行的，即，如果两个线程执行操作 ++a;，那么 a 变量将始终增加 2。这是通过锁定缓存行（x86_64）或在支持 LL/SC 的 CPU（ARM、PowerPC）上为 RMW 操作期间标记缓存行来实现的。易失性变量不保证复合 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, a[rip] 而不是两个操作。
  2. 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] 的缓存行设置“eXclusive”状态。只有在那之后，值 5 才从 Store-Buffer 实际写入到 b[rip] 的此缓存行中。有关 x86_64 MOESI / MESIF 上的缓存一致性协议的更多详细信息，其变化对所有核心可见，请参阅此链接。

为了避免花费所有这些时间 - 在将“5”放入 Store-Buffer 后立即，而不等待实际的缓存条目，我们可以开始执行以下指令：读取内存或寄存器操作。这就是 x86_64 CPU 的执行方式。

Intel® 64 和 IA-32 架构软件开发人员手册卷 3（3A、3B、3C & 3D）：系统编程指南。

引用

8.2.3.4 加载可能与不同位置的先前存储重排序

Intel-64 内存排序模型允许将加载与不同位置的先前存储重排序。但是，加载不会与相同位置的存储重排序。

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

以下是常规变量、易失性变量和原子变量写入内存的可能重排序示例。

这段使用常规变量的代码可能会被编译器或 CPU 重排序，因为在一个线程内其含义不会改变。但在多个线程的上下文中，这种重排序可能会影响程序的逻辑。

如果两个变量是易失性的，那么可能发生以下重排序。编译器在编译时不能重排序易失性变量上的操作，但编译器允许 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 最大限度地优化代码。而被禁止的重排序方向允许我们保持代码的正确性。https://cppreference.cn/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 屏障，因为标准中对其使用可行性存在疑问——标准引文。

引用

§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) 或其相应的运算符：https://cppreference.cn/w/cpp/atomic/atomic

其余四种内存屏障可用于任何操作，但以下除外：“acquire”不用于 store()，“release”不用于 load()。

根据所选的内存屏障，编译器和 CPU 不得在不同方向上将可执行代码移到屏障的相对位置。

现在让我们看看箭头表示什么，什么可以互换，什么不可以互换

为了使两个指令可以互换，必须同时允许两个指令的屏障进行这种互换。因为“其他任何代码”是指没有屏障的常规非原子变量，所以它们允许任何顺序更改。以 Relaxed-Release-Relaxed 为例，正如你所见，相同内存屏障的重排序可能性取决于它们的出现顺序。

让我们通过实现最简单的“spin-lock”类型锁的示例来考虑这些内存屏障的含义以及它们给我们带来的好处，这种锁需要最常见的 Acquire-Release 重排序语义。Spin-lock 是一种使用方式与 std::mutex 相似的锁。

首先，我们在程序主体中直接实现自旋锁概念。然后，我们实现了一个单独的自旋锁类。要实现锁（mutex、spinlock…），应该使用 Acquire-Release 语义，C++11 标准 § 1.10.1 (3)。

引用

§ 1.10.1 (3)

…例如，获取互斥量的调用将在构成互斥量的位置上执行**获取**操作。相应地，释放同一互斥量的调用将在这些相同的位置上执行**释放**操作。非正式地，在 A 上执行释放操作会强制之前在其他内存位置上发生的副作用对稍后在 A 上执行消耗或获取操作的其他线程可见。

Acquire-Release 语义的主要要点是：线程 2 在执行 flag.load(std::memory_order_acquire) 操作后，应该能看到线程 1 在执行 flag.store(0, std::memory_order_release) 操作之前对任何变量/结构/类（甚至非原子变量）所做的所有更改。

锁（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); 之前执行。这种重排序是可以接受的，并且不会产生数据竞争，因为所有访问多个线程共享数据的所有代码始终包含在“acquire”和“release”这两个屏障之间。而在外部，是只处理线程本地数据的代码，其执行顺序无关紧要。线程本地依赖项始终以类似于单线程执行的方式存储。这就是为什么 int new_shared_value = shared_value; 不能在 shared_value += 25; 之前执行的原因。

编译器在 std::memory_order 中具体做了什么

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

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

  • **左侧**。在 Acquire-Release 的情况下，一切都正确执行。
  • **右侧**。在 **Relaxed**-Release 的情况下，锁保护的关键部分的代码可能会被编译器或 CPU 移到外部。然后，在锁定之前，就会出现数据竞争问题——许多线程将开始同时处理非原子操作的数据。

请注意，通常不可能仅通过原子操作来实现与一般数据相关的全部逻辑，因为原子操作的数量非常少且速度相当慢。因此，执行以下操作更简单、更快：通过一个原子操作设置“closed”标志，处理所有非原子操作（与线程共享数据相关），然后设置“open”标志。

我们将在此过程中按时间顺序进行示意性展示：

例如，两个线程开始执行 add_to_shared() 函数：

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

在本章开头，我们提供了 2 个示例：

  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

更多详情，请参阅：https://cppreference.cn/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。主要区别（Clang 和 MSVC）与 GCC 在使用顺序一致性语义的存储操作时，即：a.store（val, memory_order_seq_cst）；- 在这种情况下，Clang 和 MSVC 生成 [LOCK] XCHG reg, [addr] 指令，该指令以与 MFENCE 屏障相同的方式清除 CPU Store-Buffer。而 GCC 在这种情况下使用两条指令 MOV [addr], reg 和 MFENCE。
  • RMW (CAS, ADD…) 总是 seq_cst。由于 x86_64 上的所有原子 RMW（读取-修改-写入）指令都带有 LOCK 前缀，该前缀会清除 Store-Buffer，因此在汇编代码级别，它们都对应于顺序一致性语义。任何 memory_order 的 RMW 都会生成相同的代码，包括 memory_order_acq_rel。
  • LOAD(acquire), STORE(release)。正如您所见，在 x86_64 上，前 4 个内存屏障（relaxed、consume、acquire、release）生成相同的汇编代码——也就是说，x86_64 架构自动提供 acquire-release 语义。此外，它由 MESIF（Intel）/ MOESI（AMD）缓存一致性协议提供。这仅对普通编译器工具分配的内存是 true 的，这些内存默认标记为 Write Back（但对于标记为 Un-cacheable 或 Write Combined 的内存则不适用，这些内存用于与设备映射内存区域交互 - 在其中仅自动提供 Acquire-语义）。

正如我们所知，相关的操作永远不能被重排序，例如：（Read-X, Write-X）或（Write-X, Read-X）。

  1. Herb Sutter 关于 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 中生成四种代码选项：http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
    引用
    1. load: MOV（从内存）store: MOV（到内存），MFENCE
    2. load: MOV（从内存）store: LOCK XCHG（到内存）
    3. load: MFENCE + MOV（从内存）store: MOV（到内存）
    4. load: LOCK XADD（0，从内存）store: MOV（到内存）

内存屏障与 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)

Clang 3.8 (x86_64)

此外，我们将在表中简要展示不同内存屏障对 CAS（Compare-and-swap）指令重排序的影响：https://cppreference.cn/w/cpp/atomic/atomic/compare_exchange

内存访问操作重排序示例

现在我们将展示四个连续操作：LOAD、STORE、LOAD、STORE 的更复杂的重排序示例。

  • 蓝色矩形表示原子操作。
  • 浅蓝色矩形内的深蓝色矩形（示例 3 和 4 中）是复合原子读取-修改-写入 (RMW) 指令的部分，该指令由多个操作组成。
  • 白色矩形是常规非原子操作。

我们将提供四个示例。每个示例都将演示常规变量操作围绕原子变量操作的可能重排序。但只有在示例 1 和 3 中，原子操作之间也可能发生一些重排序。

第一种情况有趣之处在于，多个临界区可以合并为一个。

编译器在编译时无法进行这种重排序，但编译器允许 CPU 在运行时进行此重排序。因此，在不同线程中以不同序列运行的临界区的合并不会导致死锁，因为初始指令序列对处理器可见。
因此，处理器会尝试提前进入第二个临界区，但如果无法做到，它将继续完成第一个临界区。

第三种情况有趣之处在于，两个复合原子指令的部分可以重排序。

STORE A ⇔ LOAD B

  • 这在 PowerPC 架构上是可能的，其中复合操作由 3 个独立的 ASM 指令组成（lwarx、addi、stwcx），并且它们的原子性通过 LL / SC 技术实现（wiki 链接）；有关汇编代码，请参阅：godbolt.org/g/j8uw7n 编译器在编译时无法进行这种重排序，但编译器允许 CPU 在运行时进行此重排序。

第二种情况有趣之处在于 std::memory_order_seq_cst 是最强的屏障，并且似乎禁止在其周围重排序任何原子或非原子操作。但 seq_cst-barriers 除了 acquire/release 之外，只有一个额外的属性——只有当两个原子操作都有 seq_cst-barrier 时，STORE-A（seq_cst）；LOAD-B（seq_cst）；的顺序才不能重排序。这是 C++ 标准中的两个引述：

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**，它与“happens before”顺序以及所有受影响位置的修改顺序一致，使得每个加载原子对象 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/docs/papers/2016/n4606.pdf

引用

§ 29.3 (8)

[ 注意：**memory_order_seq_cst 仅保证没有数据竞争且只使用 memory_order_seq_cst 操作的程序的顺序一致性。除非格外小心，否则使用任何较弱的顺序都会使此保证无效**。特别是，memory_order_seq_cst 栅栏仅对栅栏本身保证总顺序。通常，栅栏不能用于恢复具有较弱顺序规范的原子操作的顺序一致性。— 结束注释 ]

non-seq_cst 原子操作（原子和非原子）围绕 seq_cst- 原子操作允许的重排序方向与 acquire/release 的方向相同。

  • a.load(memory_order_seq_cst) – 允许与其他非 seq_cst 原子操作相同的重排序，就像 a.load(memory_order_acquire) 一样。
  • b.store(memory_order_seq_cst) – 允许与其他非 seq_cst 原子操作相同的重排序，就像 a.store(memory_order_release) 一样。

可以实现更严格的顺序，但不保证。

在 seq_cst 的情况下，以及在 acquire 和 release 的情况下，STORE (seq_cst) 之前的任何内容都不能在其之后执行，而 LOAD (seq_cst) 之后的任何内容都不能在其之前执行。

但在反方向，重排序是可能的，C++ 代码和 x86_64 及 PowerPC 汇编代码的示例。

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

以下是围绕 memory_order_seq_cst 操作允许的顺序更改：

  • 在 x86_64 上，在 CPU 层面，允许 Store-Load 重排序。也就是说，以下序列可以重排序：STORE-C(release); LOAD-B(seq_cst); ⇒ LOAD-B(seq_cst); STORE-C(release);，因为在 x86_64 架构中，MFENCE 仅在 STORE(seq_cst) 之后添加，而对于 LOAD(seq_cst)，汇编指令与 LOAD(release) 和 LOAD(relaxed) 相同：https://godbolt.org/g/BsLqas
  • 在 PowerPC 上，在 CPU 层面，允许 Store-Load、Store-Store 重排序等。也就是说，以下序列可以重排序：STORE-A(seq_cst); STORE-C(relaxed); LOAD-C(relaxed); ⇒ LOAD-C(relaxed); STORE-C(relaxed); STORE-A(seq_cst);，因为在 PowerPC 架构上，对于 seq_cst-barrier，sync (hwsync) 仅在 STORE(seq_cst) 和 LOAD(seq_cst) 之前添加。因此，STORE(seq_cst) 和 LOAD(seq_cst) 之间的所有指令都可以在 STORE(seq_cst) 之前执行：https://godbolt.org/g/dm7tWd

有关更多详细信息，请参阅以下具有 seq_cst 和 relaxed 语义的三个变量的示例。

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

为什么会发生这种顺序变化？因为 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

线程间数据交换还有另一个特征，它在四线程或更多线程的交互时显现。如果至少以下操作之一未使用最严格的屏障 memory_order_seq_cst，则不同线程可以看到相同更改的顺序不同。例如：

  1. 如果线程 1 先更改了某个值
  2. 然后线程 2 第二个更改了某个值
  3. 那么线程 3 可能首先看到线程 2 所做的更改，之后才看到线程 1 所做的更改。
  4. 而线程 4 则相反，可能首先看到线程 1 所做的更改，之后才看到线程 2 所做的更改。

这可能是由于缓存一致性协议的硬件特性和 CPU 中核心的位置拓扑。在这种情况下，两个核心可以看到彼此所做的更改，然后才看到其他核心所做的更改。为了使所有线程都能以相同的顺序看到更改，即它们具有单个总顺序（C++ 11 § 29.3 (3)），所有操作（LOAD、STORE、RMW）都必须使用内存屏障 memory_order_seq_cst：https://cppreference.cn/w/cpp/atomic/memory_order

在以下示例中，程序永远不会因 assert(z.load()! = 0) 错误而终止；因为所有操作都使用最严格的内存屏障 - memory_order_seq_cst：http://coliru.stacked-crooked.com/a/52726a5ad01f6529

在线编译器中的此代码位于链接处：https://cppreference.cn/w/cpp/atomic/memory_order

在图中，我们将通过 4 个线程的示例展示 Acquire-Release 语义和 Sequential 语义可能发生的顺序更改：

  1. Acquire-Release
    • 可以按允许的方向更改常规变量的顺序。
    • 可以更改具有 Acquire-Release 语义的原子变量的顺序。
  2. Sequential
    • 可以按允许的方向更改常规变量的顺序。
    • **不可能**更改具有 Sequential 语义的原子变量的顺序。

主动自旋锁和递归自旋锁

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

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

操作系统提供的同步对象数量可能有限。表中的行数可能高达数百万甚至数十亿，许多操作系统不允许创建如此多的互斥量。而自旋锁的数量可以是任意的，只要 RAM 允许。这就是为什么它们可以用于锁定每一行。

事实上，spinlock 会为每行增加 1 字节，或使用递归自旋锁（1 字节用于标志 + 8 字节用于递归计数器 + 8 字节用于 thread_id 线程号）时增加 17 字节。

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

嵌套锁示例

让我们看看 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++ 标准中：https://cppreference.cn/w/cpp/thread

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

shared_mutex 是一种 mutex，它允许许多线程同时读取相同数据，前提是当时没有线程正在更改这些数据。Shared_mutex 的诞生并非一蹴而就。关于其与普通 std::mutex 相比的性能一直存在争议。

shared_mutex 的经典实现，其中包含读者数量计数器，仅在许多读者长时间持有锁时才显示出速度优势——即，当他们长时间阅读时。对于短暂的读取，shared_mutex 仅会减慢程序速度并使代码复杂化。

但所有 shared_mutex 实现的短暂读取速度都很慢吗？

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

让我们尝试解决这个问题。

有一种类型的算法被归类为写竞争自由——当没有单个内存单元可以被一个以上的线程写入时。在更一般的情况下，没有单个缓存行可以被一个以上的线程写入。为了使我们的共享互斥量在存在读取器的情况下被分类为写竞争自由，读取器不应相互干扰——也就是说，每个读取器都应将其读取的标志写入自己的单元，并在读取结束时从同一单元中移除标志——无需 RMW 操作。

写竞争自由是最具生产力的保证，比等待自由或无锁更具生产力。

每个单元可能位于单独的缓存行以排除伪共享，也可能单元紧密排列——一个缓存行中 16 个单元——性能损失将取决于 CPU 和线程数量。

在设置标志之前，读取器会检查是否有写入器——即，是否有独占锁。而且，由于共享互斥量的使用场景通常写入器很少，因此所有使用的核心都可以将其值副本保留在其缓存-L1 的共享状态（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() 时，将调用写入器的独占锁。线程很少创建，操作系统创建它们所花费的时间如此之长，以至于在新线程注册到我们对象上的时间可以忽略不计。

我们将确保没有明显的错误——通过示例，我们将展示一切正常工作，然后我们将示意性地展示我们方法的正确性。

以下是一个快速共享锁示例，其中读取器不相互干扰：[30] http://coliru.stacked-crooked.com/a/b78467b7a3885e5b

  1. 在共享锁期间，不允许进行对象更改。两行递归共享锁这一行说明了这一点：assert(readonly_safe_map_string->at("apple") == readonly_safe_map_string->at("potato")); - 两行的值应始终相等，因为我们在 std::lock_guard 的一个独占锁下更改 std::map 中的 2 行。
  2. 在读取时，我们确实调用了 lock_shared() 函数。让我们将循环减少到两次迭代，删除修改数据的行，只保留 main() 函数中 std::map 的前两次插入。现在我们在 lock_shared() 函数中添加 S 字母输出，在 lock() 函数中添加 X 字母输出。我们看到首先出现两个 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 的算法：

  • T1-读 & T2-读：读者线程使用 lock_shared() 锁定互斥量——这些线程不会相互干扰，因为它们在每个线程单独的内存单元中写入锁的状态。此时，不允许写入器线程进行独占锁定（want_x_lock == false）。除非线程数大于专用单元数。在这种情况下，即使是读者线程也会通过 CAS 函数进行独占锁定：want_x_lock = true。
  • T1-写 & T2-写：写入器线程竞争同一个标志（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）并从头重复此算法。

写入器线程设置标志（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 个线程可以创建，使用我们的锁进行读取并休眠 500 毫秒；在此期间，在 100 毫秒时，包含我们的锁 contention_free_shared_mutex 的 contfree_safe_ptr 对象可以被移除；然后这 20 个线程才能醒来并终止。在它们终止时，在远程锁对象中注销没有发生错误。

作为小补充，我们将支持 MSVS2013，以便拥有旧编译器的用户也能看到示例。我们添加了简化的线程注册支持，但不支持线程注销。

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

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

算法和所选屏障的正确工作

上面我们进行了测试，显示没有明显的错误。但为了证明其有效性，有必要创建可能的操作顺序和变量状态变化的示意图。

独占 lock()/unlock() 与 recursive_spinlock_t 的情况几乎相同。因此，我们不会详细考虑它。

读者线程对 lock_shared() 的竞争和写入器线程对 lock() 的竞争已在上面详细讨论过。

现在的主要任务是表明 lock_shared() 在所有情况下都至少使用 Acquire 语义；并且 unlock_shared() 在所有情况下都至少使用 Release 语义。但这并不是重复递归锁定/解锁的先决条件。

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

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. 然后执行紫色操作。

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

由于执行了 2 个条件，假定已考虑了多线程的所有必要副作用。

  1. 决定进入锁的时刻始终具有至少“acquire”级别的语义。
    • 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 就足够了，因为这不是实际进入锁——我们已经在锁中了。但这不会带来太多速度提升，并且可能会使理解复杂化。

Using the Code

如何使用

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

要在 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

不同锁类型的比例（共享锁和独占锁）的锁性能：

  • % 独占锁 = （写入操作的百分比）
  • % 共享锁 = 100 - （写入操作的百分比）

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

性能（值越大越好）

MOps - 每秒百万操作

  • 对于 0% 的修改——我们的共享互斥量（作为“contfree_safe_ptr<map>”的一部分）性能为 34.60 Mops，这比标准的 std::shared_mutex（作为“safe_ptr<map, std::shared_mutex>”的一部分）快 **14 倍**，后者仅显示 2.44 Mops。
  • 对于 15% 的修改——我们的共享互斥量（作为“contfree_safe_ptr<map>”的一部分）性能为 5.16 Mops，这比标准的 std::shared_mutex（作为“safe_ptr<map, std::shared_mutex>”的一部分）快 **7 倍**，后者仅显示 0.74 Mops。

我们的锁“contention-free shared-mutex”适用于任何数量的线程：前 36 个线程作为无竞争锁，后续线程作为独占锁。从图表中可以看出——即使是独占锁“std::mutex”在 15% 的修改下也比“std::shared_mutex”快。

无竞争锁的 36 个线程数由模板参数指定，可以更改。

现在我们将显示不同锁类型比例（共享锁和独占锁）的中值延迟。

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

开始命令行：

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

中值延迟（值越低越好），微秒。

因此，我们创建了一个共享锁，其中读者在锁定和解锁期间不相互干扰，这与 std::shared_timed_mutex 和 boost::shared_mutex 不同。但是，我们为每个线程有以下额外分配：锁数组中的 64 字节 + 24 字节由 unregister_t 结构占用用于注销 + 指向该结构的元素来自 hash_map。总计，每个线程约 100 字节。

一个更严重的问题是可扩展性。例如，如果您有 8 个 CPU（Intel® Xeon® Processor E7-8890 v4），每个 CPU 有 24 个核心（每个有 48 个超线程），那么总共是 384 个逻辑核心。每个写入器线程必须读取 24576 字节（来自每个 384 个核心的 64 字节）才能写入。但它们可以并行读取。这当然比等待一个缓存行像普通 std::shared_timed_mutex 和 boost::shared_mutex（对于任何类型的唯一/共享锁）那样稳定地从 384 个线程中的每个线程转移到另一个线程要好。但 1000 个核心及以上的并行化通常通过不同的方法实现，而不是通过调用原子操作来处理每个消息。上面讨论的所有选项——原子操作、主动锁、无锁数据结构——对于单个消息的低延迟（0.5-10 微秒）都是必需的。

为了获得高每秒操作数（即，为了获得高系统整体性能和数十万个逻辑核心的可扩展性），它们使用大规模并行方法，“隐藏延迟”和“批处理”——批处理当消息被排序（对于 map）或分组（对于 hash_map）并与已有的排序或分组数组融合 50-500 微秒时。结果，每个操作的延迟增加十倍到百倍，但这种延迟发生在大量线程同时发生。结果，“细粒度时间多线程”实现了隐藏延迟。

假设：每个消息的延迟增加一百倍，但处理的消息数量增加一万倍。这在每单位时间内效率提高百倍。开发 GPU 时使用此类原理。也许，在接下来的文章中，我们将更详细地讨论这个问题。

关注点

结论：我们开发了自己的“共享互斥锁”，它不需要像标准的 std::shared_mutex 那样，让读线程之间相互同步。我们严格证明了我们“shared-mutex”工作正确性。此外，我们还详细研究了原子操作、内存屏障以及允许的重排序方向，以最大限度地优化性能。接下来，我们将看看与标准的 std::shared_mutex 相比，我们能够提高多线程程序的性能多少。

历史

  • 2017年4月24日 - 初始版本
  • 2017年5月1日 - 添加了GitHub链接
© . All rights reserved.