加速字符串
 |
||
|
加速字符串 |
|
在 lua-l 上（例如 [1]）已经反复讨论过将字符串从 C 传递到 Lua 的成本，并暗示这是一个主要的开销。本页面旨在记录一项修改 Lua 以通过实现“预字符串”——延迟内部字符串来减少字符串创建开销的实验。概述了一个示例 API，并展示了对该 API 的概念验证实现进行基准测试的结果。
建议的 API 在没有严重限制的情况下无法安全地用于多线程环境，而这些限制可能难以保证。此外，基准测试结果并未表明在常见用例中存在显著加速的潜力。
简而言之，这更像是一次失败的实验，而不是一个建议，但报告失败也很有用，以避免重复造轮子。
基本上，Lua API 在将字符串导入 Lua 时遵循的过程，无论是使用 lua_pushlstring() 还是作为创建新字符串的原语的结果，都是
1) 从字符串中最多 32 个字符的样本计算出一个哈希值。
2) 使用哈希值，在全局内部字符串哈希表中查找字符串。
3) 如果找到现有字符串，则使用它。
4) 否则，将分配一个新的 TString 对象，并将字符串复制到其中。使用步骤 1 中计算的哈希值将新对象插入内部表中。
这对于可能已存在于内部表中的较短字符串（例如全局变量名和其他表键）特别有效，因为它避免了不必要地分配或复制提供的字符串，尽管它会产生将新字符串与一个现有字符串进行完整比较的成本。
对于不太可能已存在于内部表中的字符串，它也运行得相当好，因为哈希查找可能永远不会比较链上任何现有字符串的几个字符以上，尽管它会产生内存分配和复制的成本。
尽管如此，仍然存在一些用例，这些用例中的开销似乎可能过高。有些人担心内部字符串的成本对于永远不会用作表键的字符串来说太高，而另一些人则关注步骤 4 中的复制，如果字符串将被逐段构建或由期望固定长度缓冲区的其他库（例如 fread）创建，则该复制可能是多余的。
由于我属于第二组，我认为找到一种方法来允许创建新字符串而不进行复制可能很有用。从表面上看，这似乎很容易：你只需创建一个看起来像字符串的东西（或者至少与字符串大小相同），并提供起始地址；然后，API 消费者可以根据需要填充内容，然后通过将其内部化将对象转换为真正的字符串。
这建议了一个简单的 API
lua_newprestring(L, size);
lua_tostring(L, index);
/* Note that lua_tostring is a macro which expands
* to lua_tolstring(L, index, NULL);
*/
lua_tolstring来实现这个目的似乎很清晰明了。
现在，预字符串是一个真正的 Lua 对象，因此理论上可以从 C 函数中返回为未内部化的字符串。由于它是通过调用lua_tolstring将其转换为真正的字符串，并且由于lua_tostring是用于提取字符串地址和长度的 API，因此无需修改标准库函数即可使用预字符串，尽管事实证明，拥有一个允许使用预字符串而不进行内部化的 API 调用非常有用。
lua_rawtolstring(L, index, &len);
我本可以劫持lua_topointer，但lua_topointer不会返回字符串长度；此外，知道堆栈索引处的对象实际上是一个字符串，而不仅仅是任何可能具有指针的东西，这一点很重要。
我第一次尝试使用 API 是编写一个file方法:buffers，它是:lines的固定长度模拟。
for b in f:buffers(2000) do -- #b is 2000 unless there are fewer than -- 2000 characters to read end
:buffers可以只返回一个字符串，但返回一个预字符串似乎更有趣，以防返回值的使用不需要内部化：例如，如果它只是要发送到某个输出。在这种情况下，:buffer甚至可以在每次迭代时重用同一个预字符串，前提是它没有被字符串化。（这并不完全安全，因为客户端程序可能会保留对缓冲区的引用，即使它没有被内部化，并且可能会对值发生变化感到惊讶。）
这意味着:buffer的实现需要能够知道预字符串是否已被字符串化，这需要另一个 API。
lua_rawtoprestring(L, index, &len);
使用lua_rawtoprestring和lua_newprestring，:buffer可以决定是回收预字符串还是创建一个新的预字符串，但出于现在看来难以解释的原因，我添加了另一个 API，它将这两个操作结合在一起；实现中最具语义复杂性的 API 调用。
lua_toprestring(L, index, &len);
index处的对象，并
1) 如果它是预字符串，则不修改它；
2) 如果它是字符串，则创建一个具有相同长度的新预字符串（不复制内容），并将堆栈槽index替换为新的预字符串；
3) 如果是其他任何东西，则创建一个新的预字符串，其长度为当前由 &len 参数指向的值，并将堆栈槽 index 替换为新的预字符串；
4) 最后，无论执行了上述哪一项，都返回堆栈槽 index 中的预字符串的地址和长度
虽然这很难解释，也可能很难理解，但使用起来却非常容易。例如，:buffers 的实现如下
static int io_readbuf (lua_State *L) {
FILE *f = *(FILE **)lua_touserdata(L, lua_upvalueindex(1));
if (f == NULL)
luaL_error(L, "file is already closed");
else {
size_t nread;
size_t toread = lua_tointeger(L, lua_upvalueindex(2));
char *buf = lua_toprestring(L, lua_upvalueindex(3), &toread);
nread = fread(buf, 1, toread, f);
if (nread == toread)
lua_pushvalue(L, lua_upvalueindex(3));
else if (nread > 0)
lua_pushlstring(L, buf, nread);
else if (ferror(f))
luaL_error(L, "%s", strerror(errno));
else
lua_pushnil(L);
}
return 1;
}
static int f_buffers (lua_State *L) {
size_t bufsize;
tofile(L);
bufsize = luaL_optinteger(L, 2, LUAL_BUFFERSIZE);
lua_settop(L, 1);
lua_pushinteger(L, bufsize);
lua_pushnil(L);
lua_pushcclosure(L, io_readbuf, 3);
return 1;
}
整个过程的关键部分是，预字符串被就地转换为字符串，无论是显式转换还是在需要时转换。预字符串没有单独的类型；它们始终看起来像普通的字符串，除非使用上述预字符串感知的 API 调用。现有的 C 模块和 Lua 程序不需要以任何方式修改以考虑预字符串的存在，如果您希望 C 模块避免自动将预字符串内部化，只需要将 lua_tolstring 替换为 lua_rawtolstring 即可。
由于预字符串实际上是一个延迟内部化的字符串，因此它必须表现得像 Lua 环境中的字符串一样。这意味着它必须被内部化才能用作表键。（概念验证实现还自动内部化作为 == 参数的预字符串。）
一旦预字符串被内部化为字符串，就不能再修改它。因此，修改已发布到 Lua 环境中的预字符串并不安全。您必须在让任何 Lua 或 CFunction 看到预字符串之前完成创建预字符串的内容。
在非线程环境中这很好，上面的 :buffers 实现将起作用；它很小心地不修改预字符串，除非确保它仍然是预字符串。但它不能在多线程环境中安全地工作；:buffers 迭代函数不在 lua_lock 内运行，另一个拥有缓冲区引用的进程可以在调用 fread 期间将其字符串化。
这很不幸，因为我对概念验证实现进行的基准测试表明，唯一可用的显著加速是通过在硬循环中循环使用预字符串。内部化甚至复制字符串的开销不足以证明实现的复杂性（在我看来）。
我尝试的第一个基准测试是读取和写入文件缓冲区，使用一个与上面显示的 :buffers 非常相似的函数。iolib 通过添加 :buffers 迭代器并用 lua_rawtostring 替换对 lua_tolstring 的一些调用来修改。但是，所有计时都被 I/O 系统调用所支配，因此结果并不确定，除了它们表明在使用文件 I/O 的正常情况下，节省的开销甚至不会被注意到。
为了更准确地衡量潜在的益处，我创建了一个伪文件，它包含一个环形缓冲区中近 16K 个随机可打印字符。环形缓冲区通过复制请求的字节数并推进内部“文件”位置来“读取”，始终对环形缓冲区大小（为素数）取模。环形缓冲区会定期重新随机化；最终结果是，给定的“读取”极不可能导致现有字符串。
使用上述 API，至少有四种可能的字符缓冲区返回方式
1) “recycle”：始终返回相同的预字符串，但内容更新
2) “prestring”：每次返回一个新的预字符串，但不将其内部化
3) “inplace”：通过首先创建一个正确大小的预字符串，然后将数据读入其中，最后将预字符串转换为字符串来创建新字符串，然后返回。
4) “string”：当前机制：将文件读入预字符串（虽然它也可以是预分配的缓冲区），然后调用 lua_pushlstring 以正常方式创建字符串。
比较这四种策略的时间揭示了以下成本
1) 内存分配（“prestring”和“recycle”之间的差异）
2) 内部化（“inplace”和“prestring”之间的差异）；以及
3) 复制（“string”和“inplace”之间的差异）。
基准测试是在运行 Xubuntu 的笔记本电脑上进行的，方法相当不科学（我尝试在基准测试运行时避免使用机器，但仍然有很多进程处于活动状态）。Lua 使用 -O2 -DLUA_USE_APICHECK 编译（它应该在没有 LUA_USE_APICHECK 的情况下编译，尽管我认为这不会影响相对时间；显然，报告的执行时间比生产版本中的速度慢。机器是运行在 64 位环境中的 AMD Turion。对于每个缓冲区大小，模拟文件大小设置为 1,000,000 个缓冲区，并使用 os.clock 收集执行时间，因此结果可以读作每个缓冲区的 µs。每个测试运行十次，并选择最快的运行时间进行汇总；结果汇总在 Files:wiki_insecure/users/rici/buftest.pdf 中。如您所见，内部化时间约为每个字符串 200-250 纳秒，这仅对非常短的字符串才显着；复制时间最多为总时间的 13%，测试的最大缓冲区也是如此。
实现并不特别完善，而且由于结果并不出色，我可能不会继续开发它。如果有人感兴趣，我已经将补丁放在 Files:wiki_insecure/users/rici/prestring.diff
关于实现的一些说明
每个可垃圾收集的对象都有一个 next 成员，Lua 使用它来执行垃圾收集的清除阶段。除了字符串之外的对象都保存在一个单链表中，该链表的头位于全局状态中。但是，字符串保存在字符串内部表中，next 成员用于将哈希链链接在一起。（实际上，每个哈希链的头部都是垃圾收集根的一部分。）
一旦预字符串被内部化，它必须从分配的对象链接列表中删除，并链接到内部表中的适当哈希链中。我能想到的唯一方法是双向链接分配的预字符串列表。反向指针保存在一个与 hash 成员的 union 中，而 hash 成员对于预字符串来说是不需要的。在 32 位架构上，这没有成本，但在 64 位架构上，它将字符串开销从 24 字节增加到 32 字节，因为 hash 是一个 int。也许最好假设永远不会有太多预字符串，并将它们保存在一个单链表中，当内部化预字符串时，只需线性搜索该链表即可。
除此之外，我认为没有 GC 问题。与字符串一样，预字符串总是创建在堆栈上，并且可以创建为白色，因为堆栈是原子标记的。
lua_lock 和 lua_unlock 宏提供的锁定机制旨在避免垃圾收集或表调整干扰 API 调用或 VM 执行。即使在理论上，Lua 也不会试图阻止来自其他对象变异的竞争条件。
预字符串引入了新的变异形式：将可变对象（预字符串）更改为不可变对象（字符串）。如上所述，lua_lock 机制无法阻止更改预字符串内容和将预字符串更改为字符串之间的竞争。
预字符串与字符串具有相同的类型（LUA_TSTRING）并且除了hash成员之外具有相同的内存布局。在对象头中添加了一个标志来区分预字符串和字符串。
当预字符串被内联时，结果可能是现有的字符串。在这种情况下，我们将得到两个对象：预字符串和旧字符串。这可能导致相同的预字符串被多次内联。为了减少这种情况发生的可能性，由键查找和相等运算符执行的自动内联都会将字符串指针重置为旧字符串；实现这一点需要将许多内部原型从 const 更改为非 const，并且没有做太多工作来解决问题。
我认为最好在预字符串中存储一个转发指针（使用重载的回指针/哈希）并在垃圾回收期间重写字符串指针。（垃圾收集器无法重写 C 调用堆栈帧中的指针，但应该能够重写其他地方的指针。重写 C 调用堆栈帧中的指针可能会导致预字符串在 C 函数使用指向预字符串的指针时被垃圾收集器释放。）
--RiciLake