为什么 STM 只能是研究玩具¶

标题：Software Transactional Memory: Why is it Only a Research Toy?

日期：2008/10/24

作者：Călin Cașcaval, Colin Blundell, Maged Michael, Harold W. Cain, Peng Wu, Stefanie Chiras, Siddhartha Chatterjee

链接：https://queue.acm.org/detail.cfm?id=1454466

注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。

STM带来的开销很可能会掩盖它的前景。

TM（事务内存）1 是一种并发控制范式，它为代码区域提供原子性和隔离性的执行。TM被许多研究人员认为是解决多核处理器编程问题最有希望的方案之一。它最吸引人的特点是，大多数程序员只需要局部推理共享数据访问，标记要以事务方式执行的代码区域，然后让底层系统确保正确的并发执行。这种模型有望提供细粒度锁的扩展性，同时避免锁组合的常见陷阱（如死锁）。在本文中，我们探讨了一个高度优化的STM的性能，并观察到在低并行度下TM的整体性能明显较差，这可能会限制这种编程范式的采用。

事务内存系统的不同实现会在影响性能和可编程性的设计上做出权衡。Larus和Rajwar 2 概述了事务内存系统实现的设计权衡。以下是一些设计选择：

STM（纯软件的TM） 3,4,5,6,7,8,9 是本文的重点。虽然它提供了灵活性且没有硬件成本，但它带来的开销超出了大多数用户的容忍度。
HTM（纯硬件的TM） 10,11,12,13,14,15,16 受到两个主要障碍的制约：高昂的实现和验证成本导致设计风险过大，难以在一个小众的编程模型上证明其合理性；硬件容量限制在发生溢出时会导致显著的性能下降，而管理溢出的提案（例如签名 17）会引入误报（false positives），从而增加编程模型的复杂性。因此，从工业界的角度来看，HTM设计必须在更多样化的工作负载（具有不同的事务特征）上提供高于其成本的收益，硬件设计师才会考虑去实现它。（将硬件重新用于其他目的也可以证明其包含的合理性，正如Sun在Rock处理器中实现Scout Threading的情况一样。18）
混合系统 19,20,21,22 是TM最终被广泛受众采用的最可能平台，尽管硬件和软件支持的确切比例仍不清楚。混合系统的一个特例是硬件加速的STM。在这种场景下，事务语义由STM提供，而硬件原语仅用于加速STM系统中的关键性能瓶颈。如果硬件原语的成本适中，并且可能通过其他用途进一步摊销成本，那么这类系统可能会提供一个有吸引力的解决方案。

独立于这些实现决策之外，还存在破坏社区所期望的理想事务编程模型的事务语义问题。TM引入了许多基于锁的互斥中所没有的编程问题。例如，由于以下原因，语义变得混乱：

与非事务代码的交互，包括从事务外部访问共享数据（容忍弱原子性），以及在事务内部使用锁（打破隔离性，使锁定操作在事务外部可见）。
异常与可串行化（serializability）——如何处理异常并在事务上下文中传播一致的异常信息，以及如何保证事务执行遵循正确的操作顺序。
与无法事务化的代码产生交互，这通常是由于与其他线程的通信或禁止推测的要求导致的。
活锁，即系统保证所有事务即使在存在冲突的情况下也能取得进展。

除了固有的语义问题外，还有受高事务开销驱动的特定于实现的优化，例如用于排除私有数据的程序员注解（annotations）。此外，由中止事务（aborting transactions）引入的非确定性使调试复杂化——事务代码可能会被执行并在发生冲突时中止，这使得程序员很难找到具有可重复行为的确定性路径。这两种情况都削弱了事务（尤其是纯软件的TM实现）在生产力方面的论点。

鉴于所有这些问题，我们得出结论：TM尚未成熟到能够呈现出引人注目的价值主张以触发其广泛采用的程度。虽然TM可以是并行程序员工具组合中的一个有用工具，但它本身并不能解决并行编程的困境。有证据表明，它有助于构建某些并发数据结构，例如哈希表和二叉树。此外，还有传闻声称它对某些工作负载有帮助；然而，尽管在该领域进行了数年的积极研究和论文发表，我们很失望地发现，在研究文献中并未提及使用TM的大规模应用程序。STAMP 23 (Stanford Transactional Applications for Multiprocessing) 和 Lonestar 24 基准测试套件是充满希望的开始，但要成为完整应用程序的代表还有很长的路要走。

我们的这些结论基于过去两年构建最先进的STM运行时系统和编译器框架（免费提供的IBM STM）25 的工作经验。在这里，我们描述这一经验，首先讨论STM算法和设计决策。然后，我们将该STM的性能与另外两个最先进的实现（Intel STM 26 和 Sun TL2 STM 27）进行比较，并剖析IBM STM执行的操作，提供对STM性能热点的详细分析。

软件事务内存 (SOFTWARE TRANSACTIONAL MEMORY)¶

STM在软件中实现了所有的事务语义。这包括冲突检测、保证事务读取的一致性、保持原子性和隔离性（防止其他线程在事务成功之前观察到推测性写入），以及冲突解决（事务仲裁）。

典型STM执行的主要操作的伪代码如图1所示。它展示了两种STM算法：一种执行完全验证（full validation），另一种使用全局版本号（在代码中用 gv# 注释标记了附加语句）。

/* ---------------- 图 1：STM 操作 ---------------- */

// 伪代码：STM开始 (STM begin)
STM_BEGIN()
  读取全局版本号 /* gv# */

// 伪代码：STM验证 (STM validate)
STM_VALIDATE()
  读取全局版本号 /* gv# */
  如果全局版本号已改变 /* gv# */
    对于读集(read set)中的每个条目
      如果元数据(metadata)已改变 返回 FALSE
  返回 TRUE

// 伪代码：STM读屏障 (STM read barrier)
STM_READ(A)
  如果已经写入，跳转到写入路径
  读取 A 的元数据
  如果元数据被锁定，跳转到冲突路径
  将 A 及其元数据记录在读集中
  读取 A 处的值
  如果 ! STM_VALIDATE() 跳转到冲突路径
  返回 val

// 伪代码：STM结束 (STM end)
STM_END()
  锁定写集(write set)的元数据
  如果已经被锁定，跳转到冲突路径
  如果 ! STM_VALIDATE() 跳转到冲突路径
  /* 成功得到保证 */
  增加全局版本号 /* gv# */
  执行写入
  更新/解锁写集的元数据

对于系统程序员来说，STM的优势在于它为这些操作实现不同的机制和策略提供了灵活性。对于最终用户而言，STM的优势在于它提供了一个环境，使其应用程序能够事务化（即移植到TM），而无需产生额外的硬件成本或等待这种硬件的开发。

另一方面，STM在性能和编程语义方面也带来了不可忽视的缺点：

开销 (Overheads)。 总的来说，与传统的共享内存编程或HTM相比，STM会导致更高的串行开销。这是因为在事务内部，对共享可变位置的加载和存储的软件扩展导致了数十条构成STM实现的额外指令（例如，图1中的 STM_READ 代码）。根据工作负载的事务特征，这些开销可能会成为STM实现高性能的高门槛。串行开销（即无冲突情况下的开销，无论其他并发线程的行为如何都会产生）必须被事务内存的并发特性所克服。

语义 (Semantics)。 为了避免产生高昂的STM开销，通常不会对非事务访问（即事务外部发生的加载和存储）进行扩展。这产生了弱化（并因此复杂化）事务语义的效果，这可能要求程序员比支持强事务语义时更加小心。以下是通常与这类STM相关联的一些弱化保证：

弱原子性 (Weak atomicity)。 通常，STM运行时库无法检测事务和非事务访问之间的冲突。因此，原子性语义被弱化，允许发生与非事务访问的未检测到的冲突（称为弱原子性 28），或者等同于将保证不可能发生此类冲突的负担推给了程序员。
私有化 (Privatization)。 一些STM设计禁止内存位置的无缝私有化（即从以事务方式访问过渡到一般而言以私有方式或非事务方式访问，如使用锁）。对于某些STM设计，一旦一个位置被事务性地访问，它就必须继续以这种方式被访问。有时，程序员可以通过保证对私有化位置的首次访问（例如在该位置不再可被其他线程访问之后）是事务性的，来缓解这种过渡。
内存回收 (Memory reclamation)。 一些STM设计禁止为任意重用（例如使用 malloc 和 free）而无缝回收被事务性访问的内存位置。在这些STM设计中，用于事务性访问位置的内存分配和释放的处理方式与其他位置不同。
遗留二进制文件 (Legacy binaries)。 STM需要观察事务区域的所有内存活动以确保原子性和隔离性。通过代码插桩实现这种观察的STM设计，通常无法在不严重限制并发性（例如通过串行化事务）的情况下，支持事务调用未被插桩的遗留代码（例如第三方库）。

评估 (EVALUATION)¶

在本节中，我们将使用以下基准测试集：

b+tree 是对 B-树数据结构上的数据库索引操作的实现，其数据仅存储在树的叶子上（b+树）。此实现对每一个树操作使用粗粒度的事务。每个 b+树操作从树根开始并向下遍历到叶子。叶子更新可能会触发结构修改以重新平衡树。重新平衡操作通常涉及在子-父边上向上递归。在最坏的情况下，重新平衡操作会修改整棵树。我们的工作负载将 2,048 个项目插入到一个 20 阶的 b+树中。对于这段代码，我们只有一个未经手动插桩的事务版本；因此，仅在可以使用我们的编译器提供插桩的配置中给出实验结果。
delaunay 实现了 Kulkarni 等人 29 描述的 Delaunay 网格细化算法。该代码生成一个有保证质量的 Delaunay 网格。这是一种带有附加约束的 Delaunay 三角剖分，即网格中没有任何角度小于 30 度。该基准测试将一个未细化的 Delaunay 三角剖分作为输入，并生成一个满足此约束的新三角剖分。在该算法的 TM 实现中，多个线程从工作队列中选取它们的元素，并将空洞细化作为独立的事务进行。
genome, kmeans, 和 vacation 是 STAMP 基准测试套件 30 0.9.4 版本的一部分。有关这些基准测试的详细描述，请参阅 STAMP。31

(注：此处忽略原文档中的图2“四核Intel Xeon服务器上三个STM运行时的可扩展性结果”及图3“AIX PowerPC上手动和编译器插桩基准测试的可扩展性”可视化折线图)

基线性能。 图2展示了三个STM的性能比较：IBM 32,33、Intel 34 和 Sun TL2 35。测试运行在一台运行Linux Fedora Core 6的四核、双向超线程Intel Xeon 2.3-GHz机器上。在这些测试中，我们使用了代码的手动插桩版本，这极大地最小化了IBM和TL2 STM的屏障数量。由于我们无法访问Intel STM的底层API，因此其曲线来自由Intel STM编译器插桩的代码，由于编译器插桩，这会产生额外的屏障开销。36 这些图表是相对于串行、非事务化版本的可扩展性曲线。因此，y轴上的值1表示性能等同于串行版本。

这些STM的性能大多相当，IBM STM在 delaunay 上表现出更好的可扩展性，而TL2在 genome 上获得了更好的可扩展性。然而，获得的整体性能非常低：在 kmeans 上，IBM STM在四个线程时勉强达到单线程的性能；而在 vacation 上，即使使用八个线程，也没有任何STM能够克服事务内存的开销。

编译器插桩 (Compiler instrumentation)。 编译器是STM编程环境的一个必要组件，如果它要被广大程序员所采用的话。它的基本作用是消除程序员手动插桩内存引用以加入STM读写屏障的需要。虽然提供了便利，但编译器插桩往往由于编译器分析的保守性（如Yoo 37 所观察到的那样），通过引入冗余屏障，为STM系统增加了一层额外的开销。

图3提供了另一个基准：编译器插桩的开销。该性能是在运行AIX 5.3的16路POWER5上测量的。对于STMXLC曲线，我们使用代码的未插桩版本，并使用编译器提供的语言扩展 38 对事务区域和函数进行注解。

在C和C++等传统的非托管语言中，编译器的过度插桩更为明显，其中典型的缺乏过程间分析的编译器插桩最终可能会对事务区域中的每一个内存引用（堆栈访问除外）进行插桩。例如，我们的编译器插桩使 delaunay、genome 和 kmeans 中的动态读屏障数量增加了一倍以上。过程间分析可以帮助改善某些情况下编译器插桩的紧凑性，但通常受到全局分析准确性的限制。

STM操作性能。 鉴于这一基准，我们现在详细分析STM中的哪些操作导致了开销。为此，我们使用了一个周期精确的PowerPC架构模拟器，它提供了用于插桩的钩子（hooks）。STM操作和子操作都使用这些模拟器钩子进行了插桩。选择这种环境的原因是我们希望捕获指令级别的开销，并消除由真实硬件引入的任何其他非确定性。模拟器消除了由插桩引入的所有其他簿记（bookkeeping）操作，并提供了STM开销的准确细分。

我们研究了两种STM算法的性能：一种在每次事务读取后对读集进行完全验证（fv）；另一种使用全局版本号（gv#）以避免完全验证，同时维持操作的正确性。fv算法以高得多的代价提供了更多的并发性。gv#被认为是STM实现中最好的折衷方案之一。

(注：此处忽略原文档中的图4“STM算法的单线程开销”以及图5“在不同STM操作上花费的时间百分比”柱状图)

图4展示了这些算法相比于顺序运行的单线程开销，再次说明了这些算法引起的实质性性能下降。图5将这些开销细分到各个STM组件中。对于这两种算法，事务读取的开销占主导地位，这是因为读取操作相对于所有其他操作的频率较高。全局版本号在降低开销方面的有效性体现在gv#较低的读取开销上。

(注：此处忽略原文档中的图6“在STM读取子操作上花费的时间百分比”以及图7“在STM结束子操作上花费的时间百分比”堆叠柱状图)

图6对事务读取操作的开销进行了细粒度的细分。正如预期的那样，验证读集的开销在fv配置的事务读取时间中占据主导地位。对于这两种算法，isync操作（用于对元数据读取和数据读取，以及数据读取和验证进行排序）构成了实质性的部分。在同一事务中写入先于读取发生的应用程序（delaunay, kmeans）中，检查一个位置是否已被同一事务中先前的事务写入所修改所花费的时间，占据了总时间的很大一部分。有趣的是，读取数据本身仅占总时间的极小部分，这表明了为了使这些算法的性能具有吸引力所必须克服的障碍。

图7给出了事务提交（commit）操作的类似细分。和前面一样，fv配置受到必须验证读集的影响。两种配置的其他主要开销在于获取写集的元数据（涉及一系列 load-linked/store-conditional 操作），以及对元数据获取、数据写入和元数据释放进行排序所需的 sync 操作。再一次，数据写入本身仅占总时间的一小部分。

开销优化 (Overhead optimizations)¶

已经有许多关于通过编译器或运行时技术降低STM开销的提案。大多数这些技术与STM的硬件加速是互补的。

冗余屏障消除 (Redundant barrier elimination)。 一种技术是通过逃逸分析（escape analysis）消除对线程局部对象的屏障。这种分析在识别靠近对象分配点的线程局部访问时通常非常有效。它可以消除读屏障和写屏障，但通常对写屏障更有效。例如，我们观察到过程内逃逸分析可以消除 vacation、genome 和 b+tree 中 40% 到 50% 的写屏障。然而，它对性能的影响更有限：从微不足道到12%不等。为了针对冗余读屏障，一种被称为“事务内未访问”(Not-Accessed-In-Transaction) 39 的全程序分析消除了事务中只读对象的一些屏障。
屏障强度降低 (Barrier strength reduction)。 这些优化并不消除屏障，而是在运行时识别只需要轻量级屏障处理的特殊位置，例如动态跟踪线程局部对象 40,41 以及对堆栈引用和重复引用进行运行时过滤。42
代码生成优化 (Code generation optimizations)。 一种常见的技术是内联（inline）屏障的快速路径。它具有减少函数调用开销、增加指令级并行（ILP）和暴露常见子屏障操作重用的潜在好处。在我们的实验中，编译器内联在我们的基准测试套件中实现了不到2%的整体改进。
提交序列优化 (Commit sequence optimizations)。 消除不必要的全局版本号更新 43 可将几个微基准测试的整体性能提高多达14%。

这些优化对STM性能有积极影响。然而，这里呈现的结果表明，为了使STM系统的性能普遍吸引用户，还需要多大的进一步创新。

结论 (CONCLUSION)¶

基于我们的结果，我们认为STM的前进道路充满挑战。将STM的开销降低到普遍具有吸引力的程度是一项艰巨的任务，必须证明有显著更好的结果。如果我们需要强调进一步研究的单一方向，那就是消除动态不必要的读写屏障——这可能是进一步降低STM开销的最有力杠杆。鉴于研究界探索过的类似问题（如别名分析、逃逸分析等）的难度，这可能是一场艰苦的战斗。由于TM的论点建立在其简单性和生产力效益之上，我们对任何要求程序员付出额外工作来解决性能问题的提议深表怀疑。

我们观察到，TM编程模型本身（无论是在硬件还是软件中实现）引入的复杂性限制了预期的生产力增益，从而降低了目前迁移到事务性编程的动力，并且就目前而言，除了少量硬件支持外，不足以证明采用更复杂系统的合理性。

致谢 (ACKNOWLEDGMENTS)¶

我们要感谢 Pratap Pattnaik 的持续支持，感谢 Christoph von Praun 参与的多次讨论以及在基准测试和运行时方面的工作，同时感谢 Rajesh Bordawekar 进行的 b+tree 代码实现。