【译】探索 V8 的字符串：实现和优化

站长

2024年04月29日 11:32 · 阅读数 1

免责声明本文属于是本人的直男翻译加一点点的思考，仅供参考，英文原味版请临幸 Exploring V8's strings: implementation and optimizations。

iliazeus

read in russian

探索V8的字符串：实现与优化

JavaScript 从早期的网页 HTML 到现代的编译器和工具，一直都是一种文本处理语言。因此，并不奇怪大量时间被用于调整和优化大多数现代 JS 引擎中的字符串值处理。

在本文中，我将专注于 V8 对字符串的实现。我将通过在一个完全合法的基准测试中超越 C++ 来演示各种字符串优化。最后，我将展示这些实现细节可能实际上表现较差的方式，并介绍如何应对这种情况。

【译】探索 V8 的字符串：实现和优化

先决条件

为了能够确定在任何给定时刻 V8 正在使用哪种字符串实现，我将使用 V8 的调试内置功能。为了能够访问这些功能，请在运行 Node.js 时添加 --allow-natives-syntax 参数。

$ node --allow-natives-syntax
Welcome to Node.js v20.3.0.
Type ".help" for more information.
> %DebugPrint(123)
DebugPrint: Smi: 0x7b (123)

123

%DebugPrint() 内置函数在用于字符串时输出相当多的信息。在这里，我只展示最重要的部分，使用 /* ... */ 来跳过其他部分。

V8 的字符串实现

在 V8 的源代码中，有一个方便查阅的列表，列出了它使用的所有字符串实现：

String
- SeqString
  - SeqOneByteString
  - SeqTwoByteString
- SlicedString
- ConsString
- ThinString
- ExternalString
  - ExternalOneByteString
  - ExternalTwoByteString
- InternalizedString
  - SeqInternalizedString
    - SeqOneByteInternalizedString
    - SeqTwoByteInternalizedString
  - ConsInternalizedString
  - ExternalInternalizedString
    - ExternalOneByteInternalizedString
    - ExternalTwoByteInternalizedString

然而，其中大多数都是几个基本特性的组合：

`OneByte` vs `TwoByte`

ECMAScript 标准定义字符串为一个16位元素的序列。但在许多情况下，每个字符存储2字节是一种内存浪费。事实上，在大多数代码中，相当多的字符串将被限制为ASCII。这就是为什么 V8 同时有一字节和二字节字符串的原因。

以下是ASCII字符串的示例。注意它的 type：

> %DebugPrint("hello")
DebugPrint: 0x209affbb9309: [String] in OldSpace: #hello
0x30f098a80299: [Map] in ReadOnlySpace
 - type: ONE_BYTE_INTERNALIZED_STRING_TYPE
 /* ... */

这是一个非ASCII字符串的例子。它具有两字节的表示：

> %DebugPrint("привет")
DebugPrint: 0x1b10a9ba2291: [String] in OldSpace: u#\u043f\u0440\u0438\u0432\u0435\u0442
0x30f098a81e29: [Map] in ReadOnlySpace
 - type: INTERNALIZED_STRING_TYPE
 /* ... */

`Internalized`

某些字符串特别是字符串字面量会被引擎内部化，即收集到单个字符串池中。每当使用特定的字符串字面量时，将使用该池中的内部化版本，而不是每次都分配一个新的版本。这些字符串将具有 Internalized 类型：

> %DebugPrint("hello")
DebugPrint: 0x209affbb9309: [String] in OldSpace: #hello
0x30f098a80299: [Map] in ReadOnlySpace
 - type: ONE_BYTE_INTERNALIZED_STRING_TYPE
 /* ... */

如果一个字符串值只在运行时确定，它（通常）不会被内部化。请注意其 type 中缺少 INTERNALIZED：

> var fs = require("fs")

> fs.writeFileSync("hello.txt", "hello", "utf8")

> var s = fs.readFileSync("hello.txt", "utf8")

> %DebugPrint(s)
DebugPrint: 0x2c6f46782469: [String]: "hello"
0xd2880ec0879: [Map] in ReadOnlySpace
 - type: ONE_BYTE_STRING_TYPE
 /* ... */

值得注意的是，这个字符串仍然可以被内部化。您可以通过使用 eval 将其转换为字符串字面量来强制执行这一点：

> var ss = eval('"' + s + '"')
undefined
> %DebugPrint(ss)
DebugPrint: 0x80160fa1809: [String] in OldSpace: #hello
0xd2880ec0299: [Map] in ReadOnlySpace
 - type: ONE_BYTE_INTERNALIZED_STRING_TYPE
 /* ... */

`External`

External 字符串是在 JavaScript 堆之外分配的字符串。通常用于较大的字符串，以免在垃圾回收时将它们在内存中移动。为了演示这样的字符串，我将人为地限制 V8 的堆大小，然后分配一个大字符串：

// test.js

// a 16 megabyte string
var s = Buffer.alloc(16 * 2 ** 20, 65).toString("ascii");
console.log(s.length);

# and an 8 megabyte heap
$ node --max-old-space-size=8 test.js
16777216

`Sliced`

在V8中，大多数情况下切割字符串并不实际复制数据。相反，会创建一个切片字符串，存储对父字符串的引用、偏移量和长度。其他语言可能称之为 字符串视图 或 字符串切片。

> var s = Buffer.alloc(256, 65).toString('ascii')
undefined
> %DebugPrint(s.slice(0, 15))
DebugPrint: 0x80e9bea9851: [String]: "AAAAAAAAAAAAAAA"
0xd2880ec1d09: [Map] in ReadOnlySpace
 - type: SLICED_ONE_BYTE_STRING_TYPE
 /* ... */

然而，如果子字符串足够短，有时直接复制这小部分数据会更快：

> %DebugPrint(s.slice(0, 5))
DebugPrint: 0x18a9c2e10169: [String]: "AAAAA"
0xd2880ec0879: [Map] in ReadOnlySpace
 - type: ONE_BYTE_STRING_TYPE
 /* ... */

`Cons`

字符串拼接也以类似的方式进行了优化。它生成一个 Cons 字符串，其中存储了对其左右部分的引用：

> %DebugPrint(s + s)
DebugPrint: 0x2c6f467b3e09: [String]: c"AAAAAAAAAA/* ... */AA"
0xd2880ec1be9: [Map] in ReadOnlySpace
 - type: CONS_ONE_BYTE_STRING_TYPE

同样，通常较短的字符串会直接被复制：

> %DebugPrint(s.slice(0, 2) + s.slice(0, 3))
DebugPrint: 0xec9b3412501: [String]: "AAAAA"
0xd2880ec0879: [Map] in ReadOnlySpace
 - type: ONE_BYTE_STRING_TYPE
 /* ... */

Beating C++ with string optimizations

让我们利用到目前为止学到的知识来进行一场不公平的基准测试游戏。规则很简单：我们必须考虑一个具体的人为设定的任务，在这个任务中，JavaScript 由于其字符串优化，将比等效的 C++ 代码更快。

在我们的情况下，我们将利用 Cons 和 Sliced 字符串不复制数据的事实。

// unethical-benchmark.js
// given an ASCII string of length 1500,
// find the total length of those of its substrings
// that are longer than 200 chars

let text = "a".repeat(1500);
let result = "";

for (let i = 0; i < text.length; i++) {
  for (let j = i + 201; j < text.length; j++) {
    result += text.substr(i, j - i);
  }
}

console.log(result.length);

我们将在原生 V8 上运行它，使用 jsvu：

$ time ~/.jsvu/bin/v8 unethical-benchmark.js
535036450

real    0m0.145s
user    0m0.122s
sys     0m0.028s

这是逐行翻译的 C++ 代码：

// unethical-benchmark.cxx
// given an ASCII string of length 1500,
// find the total length of those of its substrings
// that are longer than 200 chars

#include <iostream>
#include <string>

int main() {
  std::string text(1500, 'a');
  std::string result;

  for (int i = 0; i < text.length(); i++) {
    for (int j = i + 201; j < text.length(); j++) {
      result += text.substr(i, j - i);
    }
  }

  std::cout << result.length() << std::endl;
}

$ g++ -O3 unethical-benchmark.cxx && time ./a.out
535036450

real    0m0.324s
user    0m0.176s
sys     0m0.147s

这一部分当然是一个笑话 - 无论是代码还是问题显然都很糟糕。但它成功地演示了即使是最幼稚的代码也可以通过 V8 的字符串优化大大加速。

意外的副作用，或者：如何清理字符串

这种隐式优化的缺点当然是你无法真正控制它们。在许多其他语言中，程序员可以选择在真正需要时明确使用字符串视图或字符串构建器。但在JS中，程序员要么希望引擎足够聪明，要么使用黑魔法来强制其按照他们的意愿执行。

为了演示一个这样的情况，我将首先编写一个简单的脚本，该脚本将获取几个网页，然后从中提取所有链接的URL：

// urls-1.js

async function main() {
  let pageUrls = [
    "https://habr.com/ru/companies/ruvds/articles/346442/comments/",
    "https://habr.com/ru/articles/203048/comments/",
  ];

  let linkUrls = [];

  for (let pageUrl of pageUrls) {
    let html = await (await fetch(pageUrl)).text();

    for (let match of html.matchAll(/href="(.*?)"/g)) {
      let linkUrl = match[1];

      linkUrls.push(linkUrl);
    }
  }

  for (let linkUrl of linkUrls) {
    console.log(linkUrl);
  }
}

main();

让我们找出它能够运行的最小堆大小：

$ node --max-old-space-size=10 urls-1.js > /dev/null # works

$ node --max-old-space-size=9 urls-1.js > /dev/null

<--- Last few GCs --->

[252407:0x55b40628dbb0]     2894 ms: Mark-Compact 10.8 (13.7) -> 8.5 (16.9) MB, 9.22 / 0.00 ms  (average mu = 0.989, current mu = 0.683) allocation failure; scavenge might not succeed
[252407:0x55b40628dbb0]     2906 ms: Mark-Compact (reduce) 9.7 (16.9) -> 9.1 (10.4) MB, 2.68 / 0.00 ms  (+ 0.9 ms in 12 steps since start of marking, biggest step 0.1 ms, walltime since start of marking 10 ms) (average mu = 0.984, current mu = 0.681) fina

<--- JS stacktrace --->

FATAL ERROR: Reached heap limit Allocation failed - JavaScript heap out of memory

看起来10兆字节就足够了，但9兆字节则不够。

让我们尝试进一步降低内存消耗。例如，当不再需要 html 数据时，是否可以强制引擎进行垃圾回收？

// urls-2.js

async function main() {
  let pageUrls = [
    "https://habr.com/ru/companies/ruvds/articles/346442/comments/",
    "https://habr.com/ru/articles/203048/comments/",
  ];

  let linkUrls = [];

  for (let pageUrl of pageUrls) {
    let html = await (await fetch(pageUrl)).text();

    for (let match of html.matchAll(/href="(.*?)"/g)) {
      let linkUrl = match[1];

      linkUrls.push(linkUrl);
    }

    html = null; // <---
  }

  for (let linkUrl of linkUrls) {
    console.log(linkUrl);
  }
}

main();

$ node --max-old-space-size=9 urls-2.js > /dev/null

<--- Last few GCs --->

[252792:0x5576c8da8bb0]     3078 ms: Mark-Compact 8.9 (12.3) -> 7.3 (12.3) MB, 6.65 / 0.02 ms  (average mu = 0.997, current mu = 0.994) allocation failure; scavenge might not succeed
[252792:0x5576c8da8bb0]     3101 ms: Mark-Compact 10.7 (13.4) -> 8.5 (17.4) MB, 6.27 / 0.00 ms  (average mu = 0.992, current mu = 0.725) allocation failure; scavenge might not succeed


<--- JS stacktrace --->

FATAL ERROR: Reached heap limit Allocation failed - JavaScript heap out of memory

什么都没改变！原因实际上就是我们之前讨论的那些字符串优化。所有的 urls 实际上都是 Sliced 字符串，这意味着它们都保留了对整个 html 数据的引用！

解决方案是将这些字符串清理干净！

// urls-3.js

async function main() {
  let pageUrls = [
    "https://habr.com/ru/companies/ruvds/articles/346442/comments/",
    "https://habr.com/ru/articles/203048/comments/",
  ];

  let linkUrls = [];

  for (let pageUrl of pageUrls) {
    let html = await (await fetch(pageUrl)).text();

    for (let match of html.matchAll(/href="(.*?)"/g)) {
      let linkUrl = match[1];
      linkUrl = JSON.parse(JSON.stringify(linkUrl)); // <---

      linkUrls.push(linkUrl);
    }

    html = null;
  }

  for (let linkUrl of linkUrls) {
    console.log(linkUrl);
  }
}

main();

看起来确实像黑魔法。但它有效吗？

$ node --max-old-space-size=9 urls-3.js > /dev/null
# it works!

$ node --max-old-space-size=8 urls-3.js > /dev/null

$ node --max-old-space-size=7 urls-3.js > /dev/null

<--- Last few GCs --->

[253130:0x5566636cdbb0]     1621 ms: Scavenge 6.0 (8.8) -> 4.8 (8.8) MB, 1.45 / 0.00 ms  (average mu = 1.000, current mu = 1.000) task;
[253130:0x5566636cdbb0]     1631 ms: Mark-Compact 4.9 (8.8) -> 4.4 (9.0) MB, 5.01 / 0.00 ms  (average mu = 0.997, current mu = 0.997) allocation failure; GC in old space requested
[253130:0x5566636cdbb0]     1642 ms: Mark-Compact 7.3 (11.8) -> 7.0 (11.8) MB, 1.94 / 0.00 ms  (average mu = 0.996, current mu = 0.827) allocation failure; GC in old space requested


<--- JS stacktrace --->

FATAL ERROR: Reached heap limit Allocation failed - JavaScript heap out of memory

正如你所看到的，现在的代码在一个9兆字节的堆上运行得很好，只有在7兆字节时才OOM。通过强制引擎使用特定的字符串实现，我们回收了两兆字节的RAM。

通过强制所有字符串使用一字节表示，我们甚至可以回收更多内存。尽管这些字符串实际上并不是ASCII，但UTF-8的魔力将确保我们的代码像之前一样工作：

// urls-4.js

async function main() {
  let pageUrls = [
    "https://habr.com/ru/companies/ruvds/articles/346442/comments/",
    "https://habr.com/ru/articles/203048/comments/",
  ];

  let linkUrls = [];

  for (let pageUrl of pageUrls) {
    let html = await (await fetch(pageUrl)).arrayBuffer(); // <---
    html = Buffer.from(html).toString("ascii"); // <---

    // this regular expression will still work as intended
    // when applied to individual bytes of a UTF-8 string
    // instead of proper code points

    for (let match of html.matchAll(/href="(.*?)"/g)) {
      let linkUrl = match[1];

      // in case a URL did actually contain non-ASCII chars
      linkUrl = Buffer.from(linkUrl, "ascii").toString("utf-8");

      linkUrls.push(linkUrl);
    }

    html = null;
  }

  for (let linkUrl of linkUrls) {
    console.log(linkUrl);
  }
}

main();

有了这个，我们又回收了另外一个兆字节：

$ node --max-old-space-size=7 urls-4.js > /dev/null
# it works!

$ node --max-old-space-size=6 urls-4.js > /dev/null

<--- Last few GCs --->

[253789:0x563785444bb0]     1749 ms: Mark-Compact 4.9 (9.3) -> 4.4 (9.5) MB, 2.12 / 0.00 ms  (average mu = 0.996, current mu = 0.831) allocation failure; GC in old space requested
[253789:0x563785444bb0]     2530 ms: Mark-Compact 7.5 (10.1) -> 5.5 (10.3) MB, 5.66 / 0.01 ms  (average mu = 0.994, current mu = 0.993) allocation failure; scavenge might not succeed


<--- JS stacktrace --->

FATAL ERROR: Reached heap limit Allocation failed - JavaScript heap out of memory

In conclusion

大多数现代的JavaScript引擎，包括V8，在优化各种字符串操作上都投入了相当多的心思。在我的文章中，我探讨了其中一些优化。虽然可能难以明确地利用它们，但记住它们存在仍然是相当有用的 - 即使只是为了调试奇怪和意外的性能问题。

【译】探索 V8 的字符串：实现和优化

iliazeus

探索V8的字符串：实现与优化

先决条件

V8 的字符串实现

OneByte vs TwoByte

Internalized

External

Sliced

Cons

Beating C++ with string optimizations

意外的副作用，或者：如何清理字符串

In conclusion

`OneByte` vs `TwoByte`

`Internalized`

`External`

`Sliced`

`Cons`