点赞再看,已成习惯。

本文出自论文《Can Seqlocks Get Along With Programming Language Memory Models?》,由老马啸西风翻译整理。

这篇论文李大狗在 StampedLock 的算法笔记中提及,好奇心驱使着我将论文找出来,拜读一下。

序言

在某些情况下,Seqlock是一种重要的同步机制,它表示对常规读写器锁的重大改进。

它们避免了在读取器关键部分期间更新同步变量的需要,从而通过避免在锁对象本身上丢失缓存一致性而提高了性能。

不幸的是,他们依靠关键区域内的投机性赛车负荷。 这使它们成为强调语言无竞争编程的编程语言级内存模型的有趣问题案例。

我们分析了C ++ 11内存模型中的多种实现方案,并简要介绍了Java中的相应问题。

在此过程中,我们观察到可能有“读-修改-写”操作的使用,即读-修改-写操作原子地写回原始值,而不修改它,仅是为了存储模型的结果, 并且对于编译器优化此类操作可能很有用。

ps: jdk8 才引入了这个锁实现,可见以前确实没有很好的方法直接在 java 中实现 seqlock。这篇论文发布于 2012 年。

介绍

对许多数据结构的读取比对它们的写入更为频繁。

如果此类数据结构需要由多个线程并发访问,则可以采用几种替代方法来保护它们:

互斥锁(mutexes)

互斥锁或传统的读写器锁这些锁不利用不频繁的写入。

它们还具有一个关键的缺点,即使读取访问也会更新锁的状态。

因此,如果许多线程尝试同时读取数据,它们仍将生成高速缓存争用,因为每个线程依次尝试获取对持有该锁的高速缓存行的互斥访问。

即使是传统的读写锁,也是如此。

实际的数据读取访问通常可以在共享缓存行上并行进行。

ps: 只能说优化的极限就是底层原理,我们平时用一个读写锁,就感觉已经是优化的尽头了。不知道底层原理,还是很吃亏的。

RCU

另一种机制是将所有共享数据封装在单独分配的对象中,该对象由全局可访问指针p引用。

读访问取消引用p并访问共享数据。 写访问会构造数据的副本,并自动替换p。

读取可能会读取稍微过时的数据,因为它们可能会继续遵循先前读取的p版本。

最终回收单独分配的对象需要一个非平凡的协议[16]或垃圾收集器。

seqlocks

可以通过序列号“保护”数据。

序列号从零开始,并在写入对象之前和之后递增。

每个阅读器在阅读前后都要检查序列号。

如果两个值相同且相等,则不能有任何并发的增量,并且读取器必须看到一致的数据。

ps: 这个思想也非常简单,通过一个每次操作都会递增的序列,来保证读写的数据一致性。

在这里,我们集中讨论最后一个选项。

例如,Seqlocks [12,10,17]在Linux内核中用于实现 gettimeofday()。

在java.util.concurrent的实验扩展中,它们也可以作为SequenceLock使用。 [14]

事务性内存实现通常使用类似的技术(参见[9])。

我们希望类似的技术在其他地方得到广泛使用。

为了使其尽可能具体,我们将从图1中的代码开始,该代码与文献中的描述相似。

seqlock-01

我们使用C++,因为它支持原子操作的更具表达性的规范,并且当前可以更好地定义其内存模型。

但是,我们在第8节中指出,非常相似的问题也适用于Java。

我们将看到,此代码实际上不是 C++ 11(或基本上是任何其他实际的)内存模型规则所正确的。

我们内联了锁的实现,以使内存模型的问题更加明显,但以代码结构为代价。

writers有效地使用seq的最低有效位,以确保writers之间的相互排斥。

如果设置了最低有效位,则将保持锁定,其他写入程序将等待。

除非先将seq从偶数更改为奇数,否则任何writers都不会修改seq或数据。 (比较交换弱调用将seq与seq0进行比较。仅当seq相同时,它才用seq0 + 1替换seq。否则,将seq重新加载到seq0中。)

seq的最低有效位有效地充当了简单的自旋锁,可防止多个writers进入关键部分。

在关键部分的末尾,seq的值再一次增加到下一个偶数值。

因此,读者可以判断是否有中间更新。

读者检查seq的初始值和最终值是否相同和偶数。

如果不是这样,则作者介入,然后读者重试。如果是的话,那么在此期间写程序就不能处于活动状态,并且r1和r2必须包含data1和data2的一致快照。

不幸的是,此代码按书面形式是不正确的。

在下一节中,我们将回顾C ++ 11 / C11内存模型及其不正确的原因。

同样,大多数其他实际编程语言也会出现类似问题。

这里提到的 happens-before,我们在 jmm 系列有详细介绍过。

jmm-java 内存模型 happens-before

A quick review of the C++11/C11 memory model(C++11 内存模型回顾)

在这里,我们对C++ 11内存模型进行了非常快速和非正式的概述,该概述与C11内存模型基本相同。

我们在这里大略地忽略了与我们无关的细节。

更好,更详细的描述可以在[8,11,3]中找到。

C ++ 11在程序执行中定义了内存访问之前发生的关系。

它表示对这些访问的强制排序。

如果a出现在同一线程中的b之前(“a”顺序在b之前),或者a和b是同步操作,从而与b进行同步,则访问a发生在b之前。

例如,锁定释放与下一个锁定获取同步。

发生之前关系发生转移性关闭,即a也可能发生在b之前,因为存在一个中间访问c,该中间访问“发生在a之后”并且发生在b之前。

如果程序执行中的两个数据访问a和b没有按先后顺序排列,并且其中之一是写访问,则我们之间存在数据竞争。 (由于线程顺序或同步不会强制它们之间进行排序,因此它们可能会同时发生。)

C++ 11为数据竞争提供了未定义的语义。

本质上,它们是类似于越界数组引用的错误。

在没有数据争用的情况下,执行被限制为遵守事前发生的关系。

默认情况下,这与顺序一致的[13]语义相吻合。

为了简化编写高性能的无数据争用程序的程序,C++ 11还支持原子操作。

这些被视为同步操作,因此本身不能引入数据竞争。

通常,它们还引入事前发生关系,足以确保非竞赛数据操作的预期行为。

对于任何T类型的数据,atomic<T> 类型均具有T值并支持原子加载,存储,比较交换等。

对于类型为 atomic<T> 的原子变量x,可以将x上的加载操作仅编写为x,依靠从 atomic<T> 到T的隐式转换,也可以显式地编写为 x.load()。

原子操作可以指定内存排序约束。

内存顺序释放存储操作与读取该值的内存顺序获取操作加载操作同步。

存储器顺序放松操作不增加任何顺序前的关系。

默认情况下,对原子变量的操作是顺序一致的,这意味着加载操作的内存顺序获取行为,存储操作的内存顺序释放行为,或者原子读-修改-写操作(例如访存添加或比较交换)都同时发生。

它还暗示了额外的约束,通常是更昂贵的约束,以确保完全的顺序一致性。

例如,在图2中,线程1对y的存储隐式地强制了顺序一致性,因此,除其他属性外,它还充当了内存顺序释放操作,该操作与while的y的最终(也是顺序一致的)加载同步循环。

seqlocks-02

因此,a发生在b(程序顺序或“在此之前排序”)之前,发生在c(与之同步)之前,在c之前(在序列之前)发生。

因此,发生在d之前,并且x上没有数据争用。

例如,如果b被 y.store(1, memory order release); 替换,则该语句将成立。

我们通常鼓励采用一种编程风格,其中原子操作最初依赖于默认行为,而显式排序约束(例如 x.load(memory order acquire) )则很难解决,仅用于解决特定的性能问题。

在没有任何明确的排序约束(和数据竞争)的情况下,这些语言保证了顺序的一致性。

C++ 11内存模型还对所有原子操作(即使那些具有内存顺序宽松约束的操作)都强制执行“缓存一致性”。

本质上,对单个存储位置的更新以总修改顺序进行,并且对单个存储位置的所有访问似乎均以与排序前发生的顺序一致的总顺序进行。

我们有时需要推理与各个变量关联的修改顺序。

该语言还提供了具有相当复杂语义的显式内存防护(例如 atomic thread fence(memory order acquire))。我们仅在下面需要时才会提及这些语义。

根据这些规则,图1中的代码是错误的,因为它允许数据争用。

没有什么可以阻止在进行更新时读取data1和data2的。

这场数据争用(data-race)看似良性,但语言规范显然不允许这样做。

而且,正如我们在[6]中所论述的那样,在某些更为复杂的情况下,它可能导致读者关键部分内部发生细微的错误编译。

但这也导致了更多公然的问题,我们将在第4节中进行讨论。

这些似乎对于明确的推测性同步机制(如seqlocks)是唯一的。

一个简单的修复

为了获得可以有意义地讨论的C++代码,我们必须将data1和data2转换为原子变量。

通过用data1和data2的声明替换声明 atomic<int> data1, data2;,可以得到一个简单正确的版本。

seqlocks-03

重复该结果以供图3参考。

通过消除所有数据争用,它可以保证C ++内存模型的顺序语义一致,从而保证预期的语义。

依然存在的问题

但是,这通常被认为不令人满意,原因有两个:

  1. 这是不寻常的,要求原子地访问“锁定保护”变量是不自然的。

  2. 结果代码可能无法正常运行。

在实际情况下,阅读器中可能有很多负载,而不仅仅是两个。

现在需要每个负载以确保顺序一致性,尤其是不得相对于其他任何负载明显地重新排序。

与之相关的成本范围可以从较小的编译器重新排序约束[21,20,15]到与每个负载相关的非常昂贵的篱笆指令(fence instructions )[2]。

问题 1

第一点可以说是不合理预期的结果。

至少在某些圈子[12]中已经众所周知,读者的“关键部分”从根本上不完全像关键部分那样工作。

由于它可以与编写器竞争,因此可以看到不一致的数据,这极大地限制了关键部分中显示的内容。

例如,如果要在两个seq负载之间用读取器编写:

if (data2 != 0) {
    r1 = data1/data2;
} else {
    r1 = 999999999;
}

代码可能会崩溃,因为在测试和除法之间data2可能会更改。

在这种情况下,seq测试将会失败,并且“关键部分”将被重试,但前提是已经为时已晚。

因此,在读取器“关键部分”中调用任意函数来读取数据结构是不安全的。

除了任何内存模型问题外,即使在纯粹顺序一致的环境中,程序员也必须非常特别地对待“关键部分”中共享变量的读取,并意识到值异步更改的可能性。

即使看到不一致的值,该代码也不得出错或以其他方式产生不可逆的副作用。

正是这种情况,我们通常使用原子变量至少确保我们只看到实际写入的单个值,而不是部分存储。

因此,我们将重点放在上面的第二点。

问题 2

我们可以尝试通过显式使用C++内存顺序宽松的原子负载来解决性能问题,以便我们仍然告知编译器预期在data1和data2上发生争用,但不要强制执行可能会很昂贵的其他内存顺序。

从简化的内存顺序到宽松的内存顺序,这给了我们图4所示的版本(又一次不正确)。

seqlocks-04

(写入器中存储到data1和data2的存储也可以使用宽松的内存顺序,而不会引起其他问题。但是我们想将重点放在阅读器上。)

真正的问题

有人可能会认为上述解决方案是正确的。

对seq的所有访问都使用隐式“顺序一致”的原子操作,并且数据竞争已被删除。

但是,“顺序一致”的原子仅在不存在弱序(即非顺序一致)的原子(当然也没有数据竞争)的情况下,才能确保顺序一致性。

由于我们使用的内存顺序宽松,因此此处不适用。

特别是,请考虑图1版本的阅读器中的最后两个负载,其中data2尚未声明为atomic:

int r2 = data2;
seq1 = seq;

第二条语句从seq执行“顺序一致”的原子加载。

但这并不是防止处理器或编译器重新排序这两个负载所必需的。

需要确保无数据争用程序表现出顺序一致性。

但是没有免费的数据争用程序可以判断它们是否已重新排序。

显然,任何观察到这种重新排序的线程都必须在两个负载之间写入data2,这不可避免地是数据竞争。

这个事实反映在C++(和Java)内存模型强加的排序保证中,并产生了蟑螂汽车旅馆(roach motel??好奇怪的名词)的重新排序规则,例如[18]。

较早的普通负载可以延迟到顺序一致的原子负载之后。

(相反,通常情况并非如此,因为较早的顺序一致的加载可能会影响控制流,在这种情况下,重新排序可能会导致数据争用。)

因此,图1可能在实践中中断的一种方式是,来自data2的负载似乎在seq的第二次加载之后发生,并且写入器在两者之间完全执行。

即使data1和data2的负载被编写器分开,序列号测试也可以成功进行,因此很可能不一致。

类似地,如图4所示,将数据加载更改为内存顺序宽松的加载不会抑制这种重新排序,并且容易发生相同的故障。

5.一些正确的解决方案

我们可以通过将数据加载转换为内存顺序获取操作来防止上述重新排序,为我们提供(再次缩写为 memory order … to m o …)图5中的代码。

seqlocks-05

从非正式的角度来看,这是正确的,因为获取可以防止同一线程在以后的操作中进行重新排序,从而确保data1,data2和seq的加载按顺序可见。

证明正确性

更正式地说,我们可以证明它是正确的,如下所示:

与所有其他情况一样,如果读取器r读入seq0时看到写入器的seq最终存储,则该写入器中的数据更新将在读取器中的数据访问之前发生。

因此,我们只需要证明后来的作者的更新(即我们尚未看到的seq更新)对于r是不可见的。

要了解这一点,假设r从datan加载,则看到写入者w写入了datan。

这意味着在订购之前发生以下情况:

由w进行的seq的初始更新在由w写入数据n的过程与由r的datan的读取同步之前的序列化,在由r的seq的最终读取之前进行序列化

因此,w中seq的初始更新发生在r最终读取seq之前。

因此,如果读者看到与编写者相关的更新,则至少seq的第二次加载也必须由编写者查看seq更新,从而排除了最后一部分中的失败。

请注意,这些参数实际上仅依赖于分别用于加载,存储和读-修改-写操作的一致使用内存顺序获取(memory_order_acquire),内存顺序释放(memory_order_release)和内存顺序获取(memory_order_acq_rel)。

读者和作家中对seq的操作都可以相应地减弱。 (读取器中seq的最终负载甚至可能使存储顺序放松。)

至少从理论上讲,该方法的主要缺点是我们限制了数据负载的所有负载以使其顺序可见。

显然这是没有必要的; 我们真的只关心seq的最终加载是最后执行。

C ++ 11提供了一组最小的篱笆原语(fence primitives),旨在解决此类问题。

栅栏故意设计得有些薄弱,以免在某些硬件平台上实现能力问题。

我们倾向于不鼓励使用它们,因为它们通常很难正确使用,并且该行业在生成正确的基于围栏的代码方面已经有相当糟糕的记录[5]。

但是,这里我们已经充分了解了内存模型的精妙之处,并且栅栏确实允许使用图6中通常表现更好的解决方案。

w的seq的初始更新在w的写入数据与n同步之前进行排序。r的获取隔离栅(因为在先操作中看到写入,[11]中为29.8 p4)在r的seq的最终读取之前被排序。

seqlocks-06

依然不存在的不足

在诸如x86之类的TSO机器上,负载由硬件隐式排序,并且可以在不增加负载开销的情况下强制执行原子操作的顺序一致性[21,20]。

到目前为止,我们已经看到的所有正确的seqlock实现都应该编译为避免阅读器中所有内存隔离开销的代码。

其中包括图3、5和6。

但是,到目前为止,我们提供的解决方案确实存在弱点:

(1)图5尤其是图3都会在诸如POWER [20,2]之类的体系结构上产生大量开销,这些体系结构需要昂贵的围栏(fences)来承受此类负载。

因此,它们在必须在整个体系结构中表现良好的代码中是不受欢迎的。

(2)语言的限制性

仅通过使用非常难以使用且C++ 11/C11特定的构造,图6中基于围墙的解决方案才能获得高性能。

例如,它不能在Java中使用。

(3)从理论上讲,这些解决方案都过度约束了排序。

它们都阻止了读取器线程中的后续操作进入读取器关键部分。 (通常,我们允许将内存操作移入但不能移出关键部分[5、18、7])

因此,我们探索了另一种选择。

Using read-dont-modify-write operations(读不修改写操作)

我们可以通过对数据访问使用宽松的内存顺序来避免过度约束顺序,但是可以通过对读取的第二个序列号添加更新来强制执行必要的顺序。

通过在更新之前指定内存顺序释放,我们可以轻松地确保读取在更新之前可见。

由于更新仅出于内存排序目的而存在,因此尽管没有实际修改,但我们安排该更新回写刚刚读取的值,并且将读取和写入作为单个原子的“读取-修改-写入”操作执行参与。

结果只读只读关键部分在图7中给出。

seqlocks-07

在这里,我们使用 fetch add(0, m o release) 作为必需的“read-dont-modify-write”操作; 其他大多数提取操作也可以使用适当的参数类似地执行身份操作,比较交换操作与原始操作进行比较 原始序列号。

定理(Theorem)

上面的实现保证了以下语句适用于所有引用相同seqlock的seqlock关键节,即相同的序号变量:

可以对书写器关键部分和成功的读取器关键部分进行完全排序,以便每当cs1和cs2是两个关键部分,使得cs1以此顺序位于cs2之前,并且其中至少有一个是作家关键部分时,cs1会先于(C++11 内存模型意义)cs2。

因此,seqlock临界区的行为类似于实际的临界区。

每个关键部分均会看到其之前的最新writer关键部分的更改,而不会看到其后的更改。

证明(Proof )

C++ 11内存模型确保对单个位置seq的所有更新都以单个总顺序(seq的修改顺序)发生。

因此,我们可以根据修改顺序对seq(读取器)的最终read-modify-write操作或对seq(写入器)的最终操作的外观,对关键部分进行排序。

因此,所有引用相同序号变量的关键部分都以定义良好的顺序出现,我们可以参考要执行的第n个关键部分。

写入者关键部分w之后的第一个成功的读取器关键部分读取(以存储顺序获取负载)读取紧接在前一个写入者关键部分末尾的序列号,因此发生在w之后。

如果序列中的下一个写入器之前有多个成功的读取器,则每个后续的成功读取器关键部分r要么读取w末尾写入的序列号,要么读取也跟在w后面的较早读取器写入的相同值。

在第一种情况下,w的最终写入直接与r的初始读取同步,因此发生在r之前。

在后一种情况下,w发生在与r同步的较早的读取器之前,因此可传递地发生在读取器之前。 同样,序列中的下一个写入器读取由w或其中一个读取器写入的序列号,因此必须在w之后再次发生。

仍有待证明,成功的读者关键部分发生在下一位作家w’之前,因此看不到w’的影响。

在成功的比较交换弱和对应于w’的存储操作之间,seq的修改顺序无法显示成功的关键部分对seq的任何更新(包括读取器 fetch add(0, ...))。

干预作家试图进入比较交流较弱的关键领域总是失败的。

同样,另一位作者可能无法在中间退出其关键部分,因为w’可能无法进入其关键部分。

成功读取器的取回操作不能在中间进行,因为它将产生seq的奇数值,这将导致读取器失败。

由此得出结论,如果我们根据外观按获取的修改顺序对关键部分进行排序(对读者而言),而对编写者(而不是最终存储)成功进行比较交换较弱,则得到的顺序与之前相同。

每个读取器读取添加操作以及成功写入器比较交换弱操作都是原子操作,这意味着它们必须按修改顺序读取之前的写入。

因此,每个获取操作都会添加和比较交换弱操作(尽管不一定是整个关键部分)

因此,每个读者关键部分都在下一个作家关键部分w’之前发生

我们不能确保读者完全按事前发生的顺序进行排序,但是由于假定读者只能读取共享变量,因此这是不可观察的。

与基于篱笆的方法不同,带有发布顺序的访存添加不会不必要地禁止在读者关键部分的末尾对其他操作进行重新排序。

随后的内存操作(包括存储)仍可以移至关键部分。

优化读不修改写操作(Optimizing read-dont-modify-write operations)

上面的“解决方案”具有巨大的缺点,即来自seq的最终负载已变成通常需要对缓存行进行独占访问的操作。

由于在执行只读关键节的线程之间转移了缓存行的所有权,因此重新引入了一致性缺失。

理想情况下,有可能通过让编译器专门处理诸如读,写,修改,写操作(例如 fetch add(0, memory order release) )来精确地进行原子加载操作以及所需的任何内存隔离等来解决此问题。

强制执行所需的排序。

不幸的是,这是不正确的。

为了说明这一点,请考虑图8中的代码(其中内存顺序再次缩写为m_o)。

seqlocks-08

假设x和y最初均为零。

我们声称r1 = r2 = 0是不可能的。

如果r1为零,则(b)必须按y的修改顺序在(c)之前。

因此(c)必须看到(b)的结果。

因此(b)与(c)同步,并且(a)在(d)之前发生,确保r2 = 1。

现在考虑使用[20]中的映射如何将此代码编译为x86。

使用普通存储(MOV)指令编译存储(a)。

即使对于内存顺序seq cst,原子负载也总是编译为一个简单的存储(也称为MOV)。

如果将seqlock实现所需的 fetch add(0, ...) 指令(b)也编译为普通的装入指令,则线程1的操作可能会变得无序可见,因为存储到x可以 在加载y期间保留在存储缓冲区中。

因此,将(b)编译为简单的MOV指令通常并不安全。

在seqlock情况下,在 fetch add(0, ...) 操作之前没有相关的存储。

因此,MOV将是可以接受的转换(translation)。

但是,编译器通常无法确定是否存在这种原子存储操作,特别是因为它可能在更早的时候出现在不同的编译单元中。

因此,似乎无法避免在 fetch add(0, ...) 操作中生成隔离墙。

但是,我们可以安全地将 ` x.fetch add(0,memory order release)` 编译为MFENCE,然后再进行MOV指令。

根据[21]中介绍的x86内存模型,这很容易看到。

在此模型中,将 fetch add(0, ...) 的常规编译都作为具有隐式篱笆的原子加法操作,例如锁定添加,我们建议的编译为MFENCE; MOV具有完全相同的效果:

将清除存储缓冲区,内存不变,并返回受影响的内存位置的值。

java

Java既不提供弱有序的原子负载,也不提供围栏。

因此,唯一可用的选项是图3中使用易失性运算代替顺序一致的原子的算法,以及图7中的版本,这一次是在datan上使用普通的非易失性运算以及顺序一致的访存添加。

前者要简单得多,并且不受Java内存模型中数据竞争处理的当前不确定性的影响[1,19]。

但是,如果存在适当的(但目前仍是假设的)编译器优化,则后者在具有昂贵的易失性负载实现的体系结构(例如POWER)上可能会表现出明显更好的性能。

结论与性能比较

在现代编程语言存储模型中实现时,Seqlocks可能是常见编程习惯中最具挑战性的。

我们提出了许多合理的方法来实现它们。

(1)我们可以限制数据负载不要重新排序。

这包括图3和图5。

其中第一个是现有Java实现的唯一可行解决方案。

在基于TSO的体系结构(例如x86)上,即使顺序一致的负载也是不昂贵的,并且这些解决方案可产生实质上最佳的代码。

不幸的是,在诸如POWER和v8之前的ARM的体系结构上,此类负载需要围栏,使其相对昂贵。

(2)java 中无法实现

图6中基于围栏的解决方案虽然抽象地过度约束了该问题,但它似乎与所有当前体系结构都很匹配,并且应该生成几乎最佳的代码。

但是它在Java中无法表达,并且对我们来说似乎异常自然。

(3)读不影响写

没有编译器支持,基于尾随读-修改-写(read-dont-modify-write)操作的解决方案是不可行的,因为它们将写操作引入了阅读器关键部分。

但是正确的编译器优化可以使它们在所有语言和体系结构中都可行,尽管不是最佳选择。

图3中的简单原子解决方案遵循正常的C ++ 11编程规则:

如果有意以通俗的方式访问变量,请将其设为原子。

一旦确定了竞争(race),就很容易获得。

并且,除非确定竞争(race),否则即使假设的完全顺序一致的实现,更现实的代码也不大可能正确:

阅读器“关键部分”的主体不太可能对并发更新具有鲁棒性。

不幸的是,导致更多便携式性能良好的实现仍然需要对内存模型复杂性有深刻的了解。

TSO机器上各种选件的性能如图9所示。

seqlocks-09

测量是在装有单个Xeon X5670处理器,六核并禁用“超线程”的计算机上获得的。 (这是最新的“ Westmere”处理器,具有相对较快的同步和隔离支持。)

我们一次运行一个具有1至6个线程的微基准测试,每个线程交替执行一百万次读取访问和一个写入访问。

我们测量了10秒内执行的读取器关键部分的总数,并报告了每秒执行的读取器关键部分的总数(以百万计)。

每个临界区都读取两个整数变量,如我们的示例所示。

注意y轴上的对数刻度和巨大的性能差异。

pthread读写器锁(图9中的“ pthread rwlock”)和具有未优化的read-dont-modify-write操作(“ RMW,no opt”)的seqlocks都不随处理器数量而扩展。

对于我们测试过的紧密读取器循环,这是可以预期的,因为执行读取器关键部分需要对包含锁定数据结构的缓存行进行独占访问。

关键部分具有简单加载指令(“最终加载”,可以从顺序一致(图3)生成或获取数据加载(图5),也可以从显式围栏版本(图6)生成)或围栏后面负载(“最终围栏+负载”,即从图7中的“读取-修改-写入”代码生成的优化代码)基本上与处理器数量完美匹配。

(由于对数刻度,线性加速不会产生一条直线。)请注意,在6核计算机上,优化对fetch的 fetch add(0, ...) 进行优化,然后加载的增益增加了13倍以上(在单独的32核心和32线程实验中,系数是74)。

但是,即使是在这样的现代处理器上,尽管在实际应用中这种速度要小得多,但篱笆仍然会造成明显的减速(超过3.5倍)。

不幸的是,我们无法获得一套完全值得信赖的POWER测量值进行比较。

我们能够在与其他几个用户共享的POWER 7计算机上运行微基准测试,以查看总体趋势。

不同解决方案的可伸缩性趋势与x86机器相似。

但是,关于POWER的所有正确解决方案都会在阅读器关键部分中至少造成两个弱的栅栏。

相对于无栅栏版本,那些代码已经使代码的速度降低了大约三倍。

(无栅栏版本仅在单个线程上正确运行。)

与图3对应的全围栏版本大约慢了三倍,尽管它再次缩放得很好。

未优化的读取-修改-写入实现在单个线程上击败了完全隔离的版本,但是,正如预期的那样,其吞吐量随着添加线程的增加而下降,而不是随线程数量的增长而减少。

致谢

本文得益于与Sarita Adve,Pramod Joisha,Doug Lea和Jeffrey Yasskin等人进行的关于seqlock内存模型问题的几次讨论,还受益于审阅者的评论以及关于Doug Lea并发利益的公开在线讨论。 邮件列表。

在Paul McKenney,OSU OSL和gcc编译场的帮助下,我们能够访问共享的Power 7。

小结

简单翻译下来,感觉非常的消耗精力。

发现自己原来对于 jmm 中的理解还是过于浅薄。

有时候我们使用 jdk 中的类,使用起来可能很简单,但是背后蕴藏的道理确实值得深思的。