使用查找表在 JavaScript 中快速进行缓冲区到字符串的转换

在 Node.js 等 JavaScript 环境中编程时，您可能会从网络恢复原始数据，并需要将字节转换为字符串。在 Node.js 等系统中，您可以使用 Buffer 实例来表示此类原始字节。

您可以方便地将 Buffer 实例转换为 JavaScript ( mybuffer.toString() )。但是，也许令人惊讶的是，创建新字符串可能是一个瓶颈。因此，一个有价值的优化可能是尝试识别您的传入字节是已知字符串列表中的一个。这并不是 JavaScript 独有的问题。

此类问题的一个示例发生在解析 HTTP 标头时。这些标头包含常见的字符串，例如“accept”、“accept-encoding”、“content-encoding”、“content-language”、“content-length”、“from”、“host”等。如果我们能够识别bytes 作为这些字符串之一，我们可以直接指向现有的字符串。为了使事情变得更复杂，我们可能想忽略大小写，以便输入“Accept”和“ACCEPT”都应该映射到“accept”。

这个问题最近已在名为 undici 的库中得到解决。该库为 Node.js 提供了 HTTP/1.1 客户端。 GitHub 用户tsctx最初提出使用 JavaScript 对象实现的 trie 来解决这个问题。 trie 是一种数据结构，用于以有效的方式存储和搜索字符串。在最简单的实现中（有时称为数字搜索尝试），我们首先在第一个字符上进行分支，每个可能的字符都成为基于第二个字符的新树，依此类推。每个字符串的最后一个节点被标记为单词的结尾，并且还可以存储一些附加信息，例如指向所需输出的点。这种方法的问题是它会使用大量内存。事实上，我估计tsctx的实现可能会花费 1 MB 到 2 MB 的内存。这是否是一个问题取决于您的优先事项。根据我的评论，用户tsctx选择了一种新策略，该策略可能时间效率较低，但在内存方面明显更经济：三元。三叉树与二叉树类似，但每个节点最多可以有三个子节点，通常称为左、中、右。

我认为tsctx非常出色，但有时与一些竞争对手进行比较也很重要。

我决定实施我自己的方法，基于这样的观察：仅使用输入的长度就可以很容易地快速识别候选者。例如，只有一个长度为2的候选字符串：“TE”。所以编写这样的代码是有意义的：

函数toLowerCase ( s ) {  
   
var len = s 。长度;  
   
开关（长度） {  
   
案例2 ：  
   
// 检查缓冲区是否等于 te，如果是则返回  
   
if ( ( s [ 0 ] == 116 || s [ 0 ] == 84 ) && ( s [ 1 ] == 101 || s [ 1 ] == 69 ) ) {  
   
返回“ te ” ；  
   
}  
   
  
   

此代码是一个函数，它将字符串作为输入并返回它的小写版本。该函数的工作原理如下：它声明一个名为 len 的变量，并将输入字符串 s 的长度值赋给它。它使用 switch 语句来检查 len 的值并根据情况执行不同的代码块。
在此示例中，该函数只有一种情况，即 2。在情况 2 中，该函数检查输入字符串是否等于“te”或“TE”或“Te”或“tE”。它通过比较字符串中字符的 ASCII 代码来实现这一点。 t 的 ASCII 码为 116，T 的 ASCII 码为 84，e 的 ASCII 码为 101，E 的 ASCII 码为 69。该函数使用逻辑运算符 || (or) 和 && (and) 组合条件。如果输入字符串与这四种组合中的任何一个匹配，该函数将返回“te”。以下是该函数如何工作的示例：如果输入字符串是“te”，该函数将返回“te”。如果输入字符串是“TE”，该函数将返回“te”。如果输入字符串是“Te”，该函数将返回“te”。如果输入字符串是“tE”，该函数将返回“te”。如果输入字符串是“ta”，该函数将继续。

如果缓冲区的长度为 3，那么我有四个可能的候选字符串（age、ect、rtt、via）。我可以通过仅查看第一个字符来区分它们。逻辑大致相同：

案例3 ：  
   
开关（ s [ 0 ] ） {  
   
案例97 ：案例65 ：  
   
// 检查缓冲区是否等于年龄，如果是则返回  
   
if ( ( s [ 1 ] == 103 || s [ 1 ] == 71 ) && ( s [ 2 ] == 101 || s [ 2 ] == 69 ) ) {  
   
返回“年龄” ；  
   
}  
   
休息;  
   
案例101 ：案例69 ：  
   
// 检查缓冲区是否等于 ect，如果是则返回  
   
if ( ( s [ 1 ] == 99 || s [ 1 ] == 67 ) && ( s [ 2 ] == 116 || s [ 2 ] == 84 ) ) {  
   
返回“等” ；  
   
}  
   
休息;  
   
案例114 ：案例82 ：  
   
// 检查缓冲区是否等于 rtt，如果是则返回  
   
if ( ( s [ 1 ] == 116 || s [ 1 ] == 84 ) && ( s [ 2 ] == 116 || s [ 2 ] == 84 ) ) {  
   
返回“ rtt ” ；  
   
}  
   
休息;  
   
案例118 ：案例86 ：  
   
// 检查缓冲区是否等于via，如果是则返回  
   
if ( ( s [ 1 ] == 105 || s [ 1 ] == 73 ) && ( s [ 2 ] == 97 || s [ 2 ] == 65 ) ) {  
   
返回“通过” ；  
   
}  
   
休息;  
   
默认：  
   
休息;  
   
}  
   
  
   

手动完成很容易，但是会很乏味，所以我写了一个Python脚本。这并不复杂……我只是循环重复相同的逻辑。

首先让我们比较四种方法的内存使用情况：undici 使用的原始（简单）代码、 朴素的 switch-case 方法、三叉树和数字搜索特里树。我在 Linux 服务器上使用各种最新版本的 Node.js。我编写的脚本只包含该函数，并且仅包含该函数，然后打印内存使用情况。我重复五次并报告最低的数字。

因此，在 Node.js 21 中，只有数字搜索 trie 似乎会带来大量内存使用。如果您使用不同版本的 Node.js 或不同的操作系统，结果会有所不同……但我验证了结论与我的相同。 MacBook。

性能怎么样？我使用运行频率为 3.2 GHz 的 Intel Ice Lake 处理器。我编写了一个小型基准测试来解析一些标头。我依赖一个著名的 JavaScript 基准测试框架 (mitata)。

我不太确定为什么数字搜索树在这种情况下表现不佳。我还在我的 2022 款 MacBook（Apple M2 处理器）上进行了相同的实验。我通常反对在笔记本电脑上进行基准测试，但这些 MacBook 往往会给出非常稳定的数字。

因此，我得出的结论是，朴素交换机和三叉树始终比原始树快。原始实现比简单的切换慢大约 1.8 倍。

我没有尝试的一种方法是完美散列。我担心这可能很难实现，因为 JavaScript 可能无法有效地编译代码。完美散列的好处之一是它几乎可以无分支，因此可以提供一致的性能。

我们依赖于这个函数被确定为瓶颈的事实。我们运行了一个微基准测试，但了解这些函数是否在实际应用程序中产生影响将很有用。

我的源代码和基准测试在线。它可以改进，邀请请求。

原文： https://lemire.me/blog/2023/12/08/fast-buffer-to-string-conversion-in-javascript-with-a-lookup-table/