快速字符串补丁

wiki

该补丁基于 Rici Lake 的一个想法（在 2005 年 5 月的“Lua 字符串作为‘原子’”邮件列表主题中简要提及）。该想法随后在 IRC #lua 频道进行了进一步讨论和完善。我决定进行原型实现，以测试该概念的有效性。

此补丁旨在收集关于快速字符串对 Lua 应用程序有用性的反馈。欢迎任何和所有评论。特别需要的是对使用大量（不同）短字符串的实际应用程序的基准测试比较。谢谢！

为避免任何误解：此补丁*不*打算合并到 Lua 5.1 标准发行版中，我也不建议这样做（目前）。是否将此补丁中的任何内容纳入未来 Lua 版本，完全由 Lua 作者自行判断。

请将您的评论发送到 Lua 邮件列表，因为 Wiki 不太适合讨论。

-- MikePall

许可声明：我在此声明，我为 Lua 核心贡献的所有工作都将遵循与 Lua 核心本身相同的许可。

下载

点击下载[补丁本身]或[已打补丁的 Lua 5.1-work6 发行版]。

补丁中包含了一些针对基线的修复：MSVC number2int 修复，*s 性能改进，移除未定义的 lua_checkpc 断言。

理念

Lua 将所有对象存储在 Lua 堆栈或 Lua 表中的带标签值槽中。这些槽通常为 12 或 16 字节长（取决于架构和 lua_Number 的类型）。其大小主要由存储正确对齐的指针和 lua_Number 的要求决定。标签本身是一个小整数，很容易放入一个字节。这样我们就剩下 11 或 15 字节的可用空间，可以好好利用。

基本思想是将快速字符串（即最多 11 或 15 字节的短字符串）直接存储在带标签的值槽中，而不是在堆上分配它们。

这意味着快速字符串的行为更像数字，因为它们不需要分配、垃圾回收或释放。这大大减少了 VM 的开销。

兼容性

Lua API 和 Lua/C API 均未更改。您的 Lua 或 C 模块无需任何更改（但请参阅下文“注意事项”部分，了解有关 Lua/C API 一致性的说明）。

快速字符串在 Lua 核心外部的行为和外观与常规字符串完全相同。您无需进行任何特殊处理即可使用它们，并且没有外部可见的差异。

是的，这意味着 type() 返回“string”，lua_type() 返回 LUA_TSTRING，无论字符串在内部如何存储。您可以不受限制地使用所有 Lua 函数和所有 Lua/C API 函数来处理字符串。

当然，您的应用程序可能会更快，占用的内存也更少。所以您最终可能会注意到差异。但这正是此补丁的意义所在……

基本原理

许多应用程序广泛使用短字符串。众所周知，在典型应用程序使用的字符串大小分布中，短字符串占有显著的偏重（例如，名称、标签、标识符、自然语言单词等）。而且，许多这些短字符串的生命周期非常有限（例如，临时变量，仅在局部作用域中使用）。

因此，短字符串通常会产生很高的内存管理（分配和释放）、垃圾回收（标记和扫描）以及共享字符串哈希表管理的开销。此外，与其他托管对象竞争会产生额外的开销。

• 在内存分配器中，以或多或少的随机顺序分配许多小块并夹杂少量大块是其最坏的情况。
• 垃圾回收算法通常根据可回收对象的数量而不是所有对象的大小进行缩放。
• 使用共享字符串哈希表，每个创建的字符串对象至少需要哈希一次。

快速字符串避免了大部分此类开销

• 创建快速字符串就像将几个字节复制到堆栈槽中并设置标签一样简单。
• 删除是隐式的——堆栈槽通过用另一个对象覆盖而被简单地重用。
• 哈希仅对表键是必需的。对于表值或永不离开堆栈的快速字符串则不是必需的。
• 垃圾收集器将快速字符串视为不可收集对象，并简单地忽略它们。标记或扫描快速字符串没有开销。
• 由于共享字符串表不再充斥着大量短字符串，因此对共享字符串表的争用显着减少。

共享字符串表的两个关键优点是字符串相等性检查和表查找成本低廉。前者需要类型加上指针比较，后者可以重用预计算的哈希值（但需要与分配的字符串一起存储）。

如果正确处理，快速字符串的相等性检查同样便宜：带标签值槽的批量比较很快，标签数字比较也可以优化（例如，通过保留快速字符串长度）。快速字符串哈希可以使用整个槽的快速批量哈希。通过避免对小型表的查找生成哈希值，可以进一步减少剩余的哈希开销（线性批量比较更快）。

基准测试

显然，在选择合适的基准测试时，几乎可以证明任何东西。因此，我省略了一些有针对性的基准测试，例如：lua -e 'for i in io.lines() do end' </usr/share/dict/words 或过度使用 string.gfind() 或 string.gsub()。

这些显示出巨大的加速（根据架构的不同，从 +60% 到 +200% 不等），但可能无法代表典型的应用程序行为。

相反，在不广泛使用短字符串的标准基准测试中（例如，斐波那契数或矩阵乘法），您不会看到任何差异。

因此，我只是从“计算机语言大比拼”基准测试中选择了显而易见的候选者，并在不同的架构上进行了比较。

Benchmark   |   x86      x64     PPC32    PPC64
------------+----------------------------------
hash        | +38.2%   +55.8%   +40.9%   +38.7%
spellcheck  | +23.6%   +45.8%   +17.7%   +25.2%
reversefile |  +6.2%   +22.7%   +10.2%   +13.6%
wordfreq    |  +2.2%    +8.3%   +10.6%    +8.6%   

当然，最好能看到实际应用程序的基准测试结果。请将您的任何见解分享到邮件列表。谢谢！

限制

• 此补丁仅在 32 位和 64 位系统上进行了测试。

目前不支持 16 位系统，如果您尝试这样做，将收到编译器错误。这更多是关于测试和支持 16 位 size_t 的问题（请注意，一些 16 位系统使用 32 位 size_t，但当前实现并未针对此进行优化，并且在任何 16 位系统上都会拒绝编译）。

• 仅使用标准 lua_Number 类型（double）进行了测试。我不期望与其他类型出现问题（这可能会影响带标签值槽的大小和对齐）。

• 原型实现使用了固定的堆栈大小（请参阅 luaconf.h 中的 LUAI_FIXEDSTACK）。这目前只是一个简单的解决方法（见下文）。如果您有许多协程或需要深度嵌套的递归函数，可能需要调整此值。

实现细节

快速字符串实现的一个重要要求是不要更改 Lua/C API。这避免了重写任何 C 模块的必要性，并有助于为原型实现获得快速反馈。

但是，快速字符串和常规字符串必须在 Lua 核心内部共存，并且几乎在所有地方都必须区别对待。但从外部看，它们之间不应有任何可见差异，并且应被视为相同。这使得内部和外部标签号之间必须进行区分。

内部标签号仅在 Lua 核心内部可见，并存储在所有带标签的值槽（堆栈和表槽）和 GC 对象中。外部标签号仅在 Lua/C API 外部可见，并由所有 C 模块使用。

内部标签号在 lobject.h 中定义。它们的所有名称都以“TT”（例如，TTNIL、TTBOOLEAN……）开头。它们存储在一个无符号字节中（TValue 结构中的 tt）。标签号分为 4 位主号和 4 位副号。主号包含基本对象类型，副号包含附加详细信息。副号目前仅用于布尔值（存储 false (0) 或 true (1)）和快速字符串（存储字符串长度）。

在 Lua/C API 边界，所有内部标签号都被映射到 lua.h 中定义的外部标签号。它们的名称以“LUA_T”（例如，LUA_TNIL、LUA_TBOOLEAN……）开头，并保持与标准 Lua 核心相同的含义。快速字符串和常规字符串都映射到相同的外部类型（LUA_TSTRING）。相同的 API 调用适用于这两种字符串，并且编写良好的 C 模块永远不会注意到任何差异（但请参阅下文“注意事项”）。

内部标签号的巧妙分配有助于加速许多常见检查。例如，ttixstring() 在一次操作中通过一个条件即可检查两种字符串。l_isfalse() 宏同样如此，它对性能敏感。最大长度的快速字符串的标签号始终为零 (0x00)，它也充当 C 字符串的终止符。这意味着 lua_tolstring() 可以直接返回指向堆栈槽的指针以用于快速字符串。

由于现有 Lua/C API 提供的字符串指针稳定性保证（见下文），因此要求避免堆栈重新分配。对于原型实现，我决定使用固定的堆栈大小（请参阅 luaconf.h 中的 LUAI_FIXEDSTACK）。这当然不是长远之计，存在几种更好的解决方案：堆栈分块、惰性堆栈复制/释放或更改/扩充 Lua/C API 保证。然而，这超出了此原型实现的范围（抱歉）。

除了内部类型系统所需的更改外，所有创建或访问字符串的地方都需要更改以同时处理这两种变体。ttixstring()、xsvalue() 和 xslen() 宏以及 luaS_set* 函数和宏就是为此而设计的。对象复制已更改为复制整个带标签值槽。对象比较和哈希表也需要一些更改。转储/取消转储函数始终在预编译的代码块中存储外部类型值。

Lua 编译器（llex.c、lparser.c、lcode.c）仅处理 TString 指针形式的字符串。为了避免在没有任何明显好处的情况下进行大量修改，这一点尚未改变。这意味着编译器在内部始终使用常规字符串（即使是短字符串）。只有当它们用作函数原型中的常量时，它们才会被转换为带标签的值（常规字符串或快速字符串）。所有用于调试信息（如变量名）的字符串仍为常规字符串。事实证明这不是问题，因为调试 API 无论如何都只返回字符串指针。

补丁由于许多微小的更改而显得冗长。但它对生成代码的大小影响很小：它仅将 Lua 核心增加了约 1.8K（在 x86 + gcc 3.3 上使用默认设置）。

有一个可调参数（luaconf.h 中的 LUAI_FSTRINGWORDS），允许您在 32 位系统上将快速字符串的最大默认大小从 11 个字符更改为 15 个字符。请注意，64 位系统始终使用 15 个字符的限制（这也是最大值）。在设置此值之前，请仔细阅读 luaconf.h 中的描述。

当您的大部分字符串落在 12..15 个字符的范围内时，这可能会有所帮助。但在我的测试中，我没有发现任何显著的性能提升。因此，在默认配置中，我选择了较小的堆栈/表槽（将 LUAI_FSTRINGWORDS 设置为未定义）。

注意事项

从 Lua/C API 边界外部使用时，快速字符串的行为与常规字符串类似。但有一些微妙的差异可能会影响那些（可能不知不觉地）利用标准 Lua VM 的某些实现细节的程序。

1. lua_tostring()/lua_tolstring() 的规范说明：“由于 Lua 有垃圾回收，因此不能保证 lua_tostring 返回的指针在相应值从堆栈中移除后仍然有效。”

以前，您有时可以销毁常规字符串的堆栈槽并仍然引用该指针（因为 GC 没有立即运行）。然而，这违反了 API，并可能导致难以发现的错误。

由于快速字符串返回指向堆栈槽本身的指针，因此不符合规范的 C 模块*肯定*需要修复。

一个额外的限制是，如果堆栈槽被移动（lua_insert()），快速字符串指针可能会变得过时。但这非常罕见，并且很容易避免。

2. Lua/C API 不保证相同字符串的字符串*指针*相等性。

一些作者可能错误地认为，由于所有字符串都是共享的，因此对于相同的字符串总是返回相同的指针。在一般情况下并非如此。如果字符串在 Lua 堆栈或表中没有任何引用，它可能会被释放并重新分配。

使用快速字符串，根据所引用的堆栈槽，您可能会为相同的字符串获得不同的指针。您也可能为不同的字符串获得相同的指针，如果您碰巧重用了同一个堆栈槽。

无论如何，Lua/C API 规范的任何地方都没有保证字符串*指针*相等性。唯一正确的相等性测试是使用 lua_equal() 或 lua_rawequal() API 函数。

做出关于字符串指针相等性错误假设的 C 模块将*肯定*在快速字符串补丁下中断。

3. Lua/C API 规范并未明确说明 Lua 堆栈重新分配。这暗示从活动的堆栈槽检索的字符串指针在 Lua 堆栈重新分配（移动）时仍然是稳定的。

这几乎是必要的，因为几乎任何 API 调用都可能重新分配堆栈。某些 C 库调用（例如 string.gsub()）可能会在没有此保证的情况下中断。

这就是原型实现中固定堆栈大小的原因（见上文“实现细节”）。

这种方法听起来类似于一些 C++ STL 的 basic_string 实现中使用的“小型字符串优化 (SSO)”[1]。--DavidManura