快速字符串补丁
 |
||
|
快速字符串补丁 |
|
它基于 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%嗯……还不错，对吧？
但当然，最好能看到一些来自真实应用程序的基准测试结果。请与邮件列表分享你可能拥有的任何见解。谢谢！
目前不支持 16 位系统，如果你尝试使用，将会出现编译错误。这更多是关于测试和支持 16 位 size_t 的问题（请注意，一些 16 位系统使用 32 位 size_t，但当前的实现没有针对这种情况进行优化，并且拒绝在任何 16 位系统上编译）。
快速字符串实现的一个重要要求是不更改 Lua/C API。这避免了重写任何 C 模块的必要性，并有助于快速获得原型实现的反馈。
然而，快速字符串和普通字符串需要在 Lua 核心内部共存，并且几乎在所有地方都需要以不同的方式处理。但从外部来看，它们之间不应该有任何明显的区别，并且应该以相同的方式处理。这需要在内部和外部标签编号之间进行区分。
内部标签编号只在 Lua 核心内部可见，并存储在所有标记值槽（堆栈和表格槽）和 GC 对象中。外部标签编号只在 Lua/C API 外部可见，并被所有 C 模块使用。
内部标签编号在 lobject.h 中定义。它们的所有名称都以 'TT' 开头（例如 TTNIL、TTBOOLEAN、...）。它们存储在一个单独的无符号字节中（struct 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 返回的指针在相应的值从堆栈中删除后仍然有效。”
以前，你有时可以侥幸地破坏常规字符串的栈槽，并仍然引用指针（因为垃圾回收器不会立即运行）。但是，这违反了 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()）如果没有此保证，可能会出现问题。
这是原型实现中固定栈大小解决方法的动机（请参阅上面的“实现细节”）。
