钻头

  Download PDF version of this article PDF

改造：原则与实践

Terence Kelly
特邀嘉宾 Borer Ziheng (Aaron) Su

为久经考验的主力软件加载意想不到的新负担，通常是抓住机遇或解决长期困扰的最佳方法，但是向生产代码添加全新的功能并非易事。一个实际案例研究突出了帮助我们将新技巧应用到老旧系统上的原则。

 

实践者指南

改造意味着向已部署的、在设计时并未考虑这些功能的工件添加主要新功能。给家用小型货车添加拖车挂钩不算在内；将后排座椅更换为按摩浴缸才算。

改造之所以困难有几个原因。首先是阅读和理解别人的代码，这比编写自己的代码要难得多。其次，它需要设计和实现与现有代码协调一致的主要新功能。打个比方，建筑商为房屋增建侧翼必须遵守许多不变性（建筑规范），并确保最终产品看起来像是原始建筑师愿景的一部分，而不是像与棚户区的碰撞。现有结构可能会抵制改造，而且肯定不会提供帮助。

在大多数编码车间中，大型改造并不常发生，这对努力磨练技能的程序员来说是个坏消息。工作中没有足够的实践机会。幸运的是，在广阔的开源软件世界中，很容易练习改造的艺术。找到一个被广泛使用、积极维护的程序，它将受益于一个您会使用的中等大小的新功能。解决您自己的痛点。如果您将该功能实现得很好，维护者可能会将其纳入官方发行版。

扎温斯基定律
每个程序都试图扩展，直到它可以读取邮件。那些无法如此扩展的程序将被可以扩展的程序所取代。

本期“钻头”栏目将带您了解这样一个练习。痛点是一个常见的数据分析任务。我们的实践揭示了指导改造项目的一般原则。最后，我们为一个历史悠久的开源实用程序交付了一个强大且通用的新功能。

 

流、精度和召回率

现代分析技术处理源源不断的事件驱动型数据流，这些数据以零散的方式到达。示例包括数据中心遥测、来自证券交易所的金融数据以及来自物联网的传感器读数。分析的第一阶段通常涉及平滑传入数据，例如，通过维护在无数个流中每个流的最新到达数据上的窗口平均值。正确进行流分析需要坚实的算术基础，这引出了我们改造项目的起点。

传统的固定宽度二进制浮点算术不适合流分析，原因有二。首先，许多严肃的应用程序需要十进制算术。像 0.1 这样的普通十进制数不允许精确的二进制表示8，这不仅仅是一个小问题或轻微的烦恼。二进制会导致金融、会计和其他必须产生正确十进制输出的领域中出现不可接受的错误。例如，在图 1 中，C double 算术错误地计算了 70 美分购买商品 5% 的税款。5 在数学上，$0.70×1.05 = $0.735，传统上四舍五入为 $0.74。图 1 中的四舍五入是错误的，因为在二进制中，四舍五入前的结果是 0.734999…。每次交易错一位美分可能会给真正的公司带来数百万美元的年度错误。5 因此，要求苛刻的金融应用程序长期以来一直采用任意精度算术。9

Drill Bits: Retrofitting: Principles and Practice
图 1：二进制浮点舍入意外

 

固定宽度算术的第二个问题是，高容量数据流可能会引发滚雪球式的数值错误。在 1991 年的海湾战争期间，固定宽度算术中的累积故障使防空系统陷入混乱，导致一枚伊拉克“飞毛腿”导弹造成 28 名美国人丧生。1 我们的示例代码 tarball 说明了类似的陷阱，这些陷阱可能会影响涉及复利和多项式求值的实际计算。

Linux 发行版捆绑的计算器实用程序 GNU bc 在符合人体工程学且朴实无华的界面背后提供了任意精度十进制算术。16 对于命令行上的快速交互式计算来说，它很难被超越，并且它也支持非交互式脚本。“钻头”栏目的上一期广泛使用了 bc 来进行阶乘产生的大整数的组合计算。13 对于分数算术，bc 可以将结果计算到任何期望的精度。

Python 和其他脚本语言具有任意精度十进制算术库，但是对于简单的任务来说，bc 脚本更清晰、更小、更方便。精简的 bc 解释器也明显比 Python 快，并且内存占用更小，这在关注性能的情况下是重要的优势。

bc 脚本可以轻松计算数据流上的窗口平均值。图 2 中的脚本将非负输入数字读入变量 x，将最近的 w=3 个输入窗口保存在数组 a 中，计算接收到的输入总数 n，并维护窗口内容的 sum。if/else 行确保用于计算窗口平均值的分母 d 在窗口填充前后都是正确的；此行还从 sum 中减去“老化”出完整窗口的数字。在脚本本身下方，shell 变量 IN1 和 IN2 包含示例输入。将这些输入通过管道传递到脚本，然后传递一个负数，将生成精度由 scale 参数指定的输出。脚本的 mod() 函数是必要的，因为当 scale 非零时，bc 的模运算符无法执行我们想要的操作；auto 将 p 和 r 指定为局部变量。

Drill Bits: Retrofitting: Principles and Practice
图 2：使用 bc 的窗口平均值

 

如果所有输入都一次可用，则图 2 中的脚本就足够了，但是它无法处理零散到达的无限数据流。在图 3 中，脚本分别摄取两个输入序列，并在第二次填充窗口时发出不正确的输出。当然，问题在于当脚本的第一次调用终止时，窗口消失了。

Drill Bits: Retrofitting: Principles and Practice
图 3：间歇性到达导致问题

 

一个糟糕的解决方案是修改图 2 中的脚本，以便在脚本终止时将窗口转储到持久存储，并在下次调用脚本时将窗口读回。这种方法有两个缺点。首先，它可能是一场无谓的性能灾难。如果输入数字一次到达一个，它将为每个输入数字执行与窗口大小成比例的工作，而手头任务的固有计算负担仅为每个输入的恒定工作量（O(窗口大小) 与 O(1)）。一个永恒的普遍原则在这里引导我们远离麻烦：强烈偏好渐近高效的解决方案。

糟糕解决方案的第二个问题是，使用相同的基本问题——健忘症——来修改每个脚本是一场无谓的编程灾难。无数的脚本将因针对单个根本问题的不同自制创可贴而膨胀。第二个原则指向一个更好的解决方案：在正确的位置，完全一次性地解决一类普遍问题。

 

保持状态并继续

最好通过在 bc 解释器上改造新功能来一次性地、高效且良好地解决健忘症问题：使解释器能够在调用之间保存足够的脚本执行状态，以便脚本可以简单地从上次停止的地方继续执行。这项新功能将是纯粹的可选加入：如果调用 bc 的用户没有请求它，则 bc 将以其传统的健忘方式运行。脚本本身将不包含任何代码来享受新的暂停/恢复功能；解释器将完成所有工作，用户将在运行时激活（或不激活）新功能。最后，暂停/恢复不仅适用于脚本；它也适用于交互式 bc 会话。

当然，所有这些都说起来容易做起来难。新功能的描述可能简洁明了，但是改造代码可能会变得棘手。此外，执行最少必要工作的有效设计可能难以捉摸。幸运的是，bc 代码库相当小巧整洁，因此我们没有太害怕深入研究并开始考虑不同的改造策略。

我们确定了一组变量，这些变量共同代表 bc 脚本或交互式会话的执行状态。跨调用保留这些变量对于支持我们的新暂停/恢复功能是必要且充分的。方便的是，关键变量的声明和定义已经合并在 global.h 和 global.c 中，但是许多其他源文件也访问了这些变量。

我们拒绝了在 bc 即将终止时将执行状态变量写入持久存储，然后在下次调用时将它们读回内存的简单权宜之计，这会遭受与前面针对窗口平均值脚本指出的相同的渐近低效性：O(数据大小) 与 O(增量大小)。显式地仅保存解释器状态的更改的另一种不太笨拙的替代方案将是困难且容易出错的；这种方法会将更改跟踪逻辑分散在整个 bc 代码中，从而违反了“一次性解决/正确位置”原则。

那么，我们应该在 bc 代码中的哪个位置改造暂停/恢复？一个迂回的答案源于第三个一般原则：尊重现有的软件架构。解释器必须以某种方式持久化并稍后恢复足够的状态才能恢复执行。尊重架构意味着在 bc 已经管理持久状态的位置执行此操作。

但是没有这样的位置！bc 解释器没有模块，没有软件层，没有位置来管理持久状态。相反，bc 只是像我们在计算器中期望的那样，在传统的匿名/短暂的 DRAM 支持的内存中操作普通数据结构（C 变量和 struct）。尊重架构意味着我们不能用新的持久性逻辑来混乱操作内存数据的代码，也不能在一个没有任何此类架构的架构中硬塞一个新的持久存储模块。

但是，我们可以交换现有的软件层以进行直接替换，而不会轻视该架构。

 

门诊分层手术

要交换的正确层位于 bc 解释器正下方：内存分配器。必须跨调用保留的大部分关键执行状态都驻留在由标准 malloc 和 free 管理的传统堆上；例外情况可以轻松地移动到堆上。然后，原则上，将暂停/恢复改造到解释器上所需要做的就是将传统的短暂堆替换为持久堆。

说起来容易做起来难？是的，但也没那么难。

我们的改造使用了持久内存分配器 pma，该分配器已在广泛使用的软件中部署多年。11,12,14 pma 库为标准 malloc 和 free 提供了直接替换的 pma_*。我们通过在所有源模块中 #include 的标头中将 malloc 和 free #define 为它们的 pma_ 对等项来交换新的持久分配器。在底层，pma 从文件支持的内存映射中分配内存。包含 pma 持久堆的支持文件称为堆文件。

为了在改造后的 bc 解释器中激活持久内存模式，用户将一个新的特殊环境变量 BC_PM_HEAP_FILE 设置为堆文件的名称。如果设置了此环境变量，则 pma 初始化例程会将给定的堆文件映射到内存中，并为持久内存模式做好准备。如果未设置环境变量，则初始化例程会将 pma 库置于“回退到 malloc”模式，这意味着 pma_malloc 将责任传递给传统的 malloc，而 pma_free 类似地调用普通的 free。换句话说，如果未设置新的特殊环境变量，则 bc 的行为就好像我们的持久性改造从未发生过一样。

改造最棘手的方面是使现有的 bc 代码能够访问持久堆上的数据。像所有现代持久堆一样，pma 要求应用程序确保所有已分配的持久内存都可以从持久堆的根指针访问。因此，如果现有的 bc 代码操作一个名为“foo”的变量，该变量现在驻留在持久堆上，那么 bc 代码如何找到 foo 呢？

两步更改解决了通过根指针访问的问题。我们首先在持久堆上分配一个新结构，以包含所有必须跨调用持久化的变量。持久堆的根指针始终指向这个新的 struct。其次，我们在所有 bc 源文件中 #include 一个新的标头，该标头将对以前短暂变量的直接访问替换为对改造后的持久变量的间接访问

#define foo root_pointer->foo

当 pma 在回退到 malloc 模式下运行时，新的 struct 最终会出现在传统堆上，并且一切正常运行。

最终结果是，现有的 bc 源代码几乎没有变化。对现有代码的少数更改之一涉及标准库函数 strdup，该函数在传统堆上分配内存。我们将少数 strdup 替换为调用 pma_malloc 和 strcpy 的代码片段。总的来说，改造向 bc 添加了大约 110 行代码，并在大约 6 KLOC 的原始代码库中修改了大约 50 行代码。

风格仲裁者可能会对使用 C 预处理器 #define 来重定向函数调用和变量访问感到不满。但是，对于我们的 bc 改造，宏最大限度地减少了对原始代码的干扰，从而保持了其清晰度。它们还使我们很容易在以后不喜欢它时删除改造。对于我们的中型项目来说，过度思考问题或过度设计解决方案不会产生更好的结果。

 

持久内存 bc

回到窗口平均值，图 4 显示持久内存 bc (pm-bc) 通过跨调用保留脚本执行状态（包括最近到达的窗口）来正确处理零散输入。用户通过创建一个堆文件（最初是由 truncate 实用程序创建的大型零字节文件）并将堆文件的名称通过一个新的特殊环境变量传递给 pm-bc 来激活持久性。传递环境变量的另一种方法是在每次调用 pm-bc 之前 export 一次。但是，忘记他们已 export 环境变量的用户可能会在 pm-bc 跨调用保留状态时感到惊讶。

Drill Bits: Retrofitting: Principles and Practice
图 4：pm-bc 正确处理间歇性到达

 

持久内存 bc 是渐近高效的，因为 pma 分配器在内存映射文件中布局持久堆。11 当 pm-bc 更新其持久堆时，底层操作系统执行的工作量与更改的内存页数成正比，而不是与持久堆的大小成正比。更简洁地说，它执行 O(增量大小) 工作，而不是 O(数据大小)。当然，如果用户没有显式激活持久性，则持久性改造不会施加任何开销。

我们的 pm-bc 改造展示了原则的力量。一位没有接触过 bc 或持久内存的初级程序员 (Su) 在一位持久内存资深人士 (Kelly) 和 bc 维护者 (Phil Nelson) 的少量指导下，在几周内完成了整个改造。维护者计划将持久性包含在即将发布的 GNU bc 官方版本中。成功的关键是对少量永恒原则的深思熟虑的应用：寻求渐近效率，在正确的位置以最小的努力解决问题，并尊重现有软件的架构。在您自己的改造项目中考虑这些原则。

 

深入挖掘

改造通过添加到现有代码来创建新功能。另一种创新策略是通过删除代码。例如，Ken Thompson 通过剥离交互式文本编辑器 ed 创建了非交互式 grep 实用程序。18 多年来，Brian Kernighan 要求他在普林斯顿大学的高级编程课程中的学生复制 Thompson 从 ed 创建 grep 的过程，尽管是从 C 版本开始，而不是原始汇编语言。15

完美不是当没有什么可以添加时达到，而是当没有什么可以删除时达到。
— 安托万·德·圣埃克苏佩里

持久内存不是实现暂停/恢复的唯一方法。替代方案的范围从旧式的 SIGSTOP/SIGCONT 到更现代的选择，例如 CRIU (用户空间中的检查点/恢复)6 和 DMTCP (分布式多线程检查点)。7 不幸的是，这些替代方案不适合持久脚本，因为它们使复活的解释器难以处理新输入。17

戈德堡的经典调查目录列出了传统固定宽度二进制浮点算术的优点和局限性。8 无法接受传统算术权衡的苛刻应用程序可能会转而使用 Boehm 的毫不妥协的库，该库通过计算中间结果到保证最终结果中所需精度的任何精度来评估表达式。2,3 如果固定宽度不是问题但需要十进制算术，则 C23 中最近标准化的十进制浮点类型可能符合要求。4

 

位

在 https://queue.org.cn/downloads/2024/Drill_Bits_14_example_code.tar.gz 获取示例代码 tarball。您将获得一个内部 tarball，其中包含 pm-bc、图 2 的 winavg.bc 脚本、等效的 Python 脚本、用于比较 .bc 和 .py 脚本性能的 shell 脚本以及描述固定宽度浮点算术的另一个陷阱的 PDF 文档。

 

演练

  1. 比较 bc、Python 和 Perl 脚本的运行时间和内存占用。在类 Unix 系统上，快速而简陋的方法是
    /usr/bin/time python3 -c 'print(f"hello")'
    思考在多核处理器上并行运行多个脚本的含义。
  2. 使用持久堆在不相关的 bc 脚本之间传输数据结构。
  3. 为持久内存 bc 添加崩溃容错能力。考虑 gdbm 的机制。10
  4. 将持久性改造到另一个脚本语言解释器（例如，Python 或 Perl）上。
  5. 使用预处理器宏来帮助千禧一代/Z 世代程序员在婴儿潮一代/X 世代语言中感到宾至如归，例如，#define YEET throw

 

致谢

我们感谢 bc 维护者 Phil Nelson 提供的宝贵建议；Jon Bentley、John Dilley、Alan Karp 和 Kevin O'Malley 提供的头脑风暴；以及 Brian Kernighan 提供的有关 ed 和 grep 的历史信息。Bentley、Dilley、Karp、Nelson、O'Malley 和 Charlotte Zhuang 审阅了草稿并提供了宝贵的反馈。Dilley 和 O'Malley 审阅了我们的代码，Lucas Stevenson 在 Python 中重新实现了我们的“winavg.bc”脚本。

 

参考文献

  1. Arnold, D. N. 2000. Patriot 导弹失败； http://www.ima.umn.edu/~arnold/disasters/patriot.html。
  2. Boehm, H.-J. 2017. 小数据计算：正确的计算器算术。《 通讯》60(8), 44–49; https://dl.acm.org/doi/pdf/10.1145/2911981。
  3. Boehm, H.-J. 2020. 面向实数 API。在第 41 届 SIGPLAN 编程语言设计与实现会议 (PLDI) 会议记录中； https://dl.acm.org/doi/pdf/10.1145/3385412.3386037。
  4. C23 标准（草案 n3054）。 https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3054.pdf。
  5. Cowlishaw, M. 2007. 十进制算术 FAQ 第 1 部分 — 一般问题。IBM Corp.; https://speleotrove.com/decimal/decifaq1.html。
  6. CRIU (用户空间中的检查点/恢复)； https://criu.org/Main_Page。
  7. DMTCP (分布式多线程检查点)； https://dmtcp.sourceforge.io/。
  8. Goldberg, D. 1991. 每个计算机科学家都应该了解的浮点算术。《 计算调查》23(1), 5–48; https://dl.acm.org/doi/pdf/10.1145/103162.103163。
  9. Hanson, D. R. 1997. C 接口和实现。Addison-Wesley。有关高精度价格跟踪，请参阅第 323 页。
  10. Kelly, T. 2021. 崩溃保护原始 NoSQL 数据存储。《acmqueue》18(4); https://dl.acm.org/doi/pdf/10.1145/3487019.3487353。
  11. Kelly, T. 2022. pm-gawk 用户手册。可在参考文献 [12] 中找到。有关渐近效率，请参阅第 4.1 节。
  12. Kelly, T. 2022 pma：持久内存分配器； http://web.eecs.umich.edu/~tpkelly/pma/。
  13. Kelly, T. 2024. 零容忍偏差。《acmqueue》22(2), 19–38; https://dl.acm.org/doi/pdf/10.1145/3664645。
  14. Kelly, T., Tan, Z. F. Li, J., Volos, H. 2022. 持久内存分配：推动软件世界。acmqueue 20(2), 16–30; https://dl.acm.org/doi/pdf/10.1145/3534855。
  15. Kernighan, B. 2024. 个人沟通。
  16. Nelson, P. 2024. GNU bc 任意精度计算器； https://gnu.ac.cn/software/bc/。
  17. Tan, Z. F., Li, J., Volos, H., Kelly, T. 2022. 持久脚本。《非易失性内存研讨会 (NVMW) 会议记录》中； http://nvmw.ucsd.edu/nvmw2022-program/nvmw2022-data/nvmw2022-paper35-final_version_%20your_extended_abstract.pdf。
  18. Wikipedia. 2024. grep； https://en.wikipedia.org/wiki/Grep。

 

Terence Kelly ([email protected]) 喜欢在他的小型货车的按摩浴缸里嬉戏。

Ziheng (Aaron) Su 喜欢将新技巧应用到老旧系统上。

版权 © 2024 归所有者/作者所有。出版权已授权给 。

acmqueue

最初发表于 Queue 第 22 卷，第 6 期—
在 数字图书馆 中评论本文





© 保留所有权利。

© . All rights reserved.