Внутреннее представление и оптимизации строк в JavaScript-движке V8: «отмываем» строки, «обгоняем» C++
С самого рождения JavaScript в каком-то смысле был языком для манипулирования текстом — от веб-страничек в самом начале до полноценных компиляторов сейчас. Неудивительно, что в современных JS-движках достаточно много сил уделено оптимизации внутреннего представления строк и операций над ними.
В этой статье я хочу рассмотреть, как могут быть представлены строки в движке V8. Попытаюсь продемонстрировать их эффект, обогнав C++ в очень честном бенчмарке. А также покажу, в каких случаях они могут, наоборот, привести к проблемам с производительностью, и что в таких случаях можно сделать.
Инструменты для исследования
Чтобы наглядно увидеть, какая реализация строк используется в каждый конкретный момент, будем использовать отладочные функции 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
Для строк эта функция печатает довольно много информации, поэтому я буду заменять на /* ... */ то, что не важно для рассмотрения.
Какие в V8 есть строки?
Список внутренних реализаций строк можно найти в исходниках V8:
- String
- SeqString
- SeqOneByteString
- SeqTwoByteString
- SlicedString
- ConsString
- ThinString
- ExternalString
- ExternalOneByteString
- ExternalTwoByteString
- InternalizedString
- SeqInternalizedString
- SeqOneByteInternalizedString
- SeqTwoByteInternalizedString
- ConsInternalizedString
- ExternalInternalizedString
- ExternalOneByteInternalizedString
- ExternalTwoByteInternalizedString
Большая часть этого многообразия получается из комбинации нескольких основных признаков.
▍ OneByte и TwoByte
Стандарт определяет строки как последовательности 16-битных значений. Но зачастую хранить по 2 байта на символ бывает слишком расточительно. На практике очень многие строки не выходят за рамки ASCII. Поэтому внутри V8 строки могут быть как одно-, так и двухбайтовыми.
К примеру, вот ASCII-строка. Обратите внимание на её type:
> %DebugPrint("hello")
DebugPrint: 0x209affbb9309: [String] in OldSpace: #hello
0x30f098a80299: [Map] in ReadOnlySpace
- type: ONE_BYTE_INTERNALIZED_STRING_TYPE
/* ... */
▍ Internalized
Если значение строки известно только в рантайме, то она, как правило, не будет интернироваться. Обратите внимание на отсутствие INTERNALIZED в её type:
> 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 + '"')
> %DebugPrint(ss)
DebugPrint: 0x80160fa1809: [String] in OldSpace: #hello
0xd2880ec0299: [Map] in ReadOnlySpace
- type: ONE_BYTE_INTERNALIZED_STRING_TYPE
/* ... */
▍ External
External-строки хранятся не на куче, а в отдельных областях памяти, специально для них выделенных. Как правило, это применяется для очень больших строк. Для примера давайте запустим Node.js с очень маленьким размером кучи, но выделим для строки много памяти:
// test.js
// создаём строку размером в 16 МБ
var s = Buffer.alloc(16 * 2 ** 20, 65).toString("ascii");
console.log(s.length);
Запустим c ограничением кучи в 8 МБ:
$ node --max-old-space-size=8 test.js
16777216
▍ Sliced
Для экономии памяти и времени на копирование данных операция взятия подстроки возвращает Sliced-строку. Это аналог string view из других языков — то есть просто указатель на строку-родителя, смещение и длина.
> var s = Buffer.alloc(256, 65).toString('ascii')
> %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
/* ... */
Преимущества оптимизаций: «обгоняем» C++
Итак, мы разобрались с тем, как именно представлены строки в V8. Давайте применим это на практике в одной из моих любимых дисциплин: нечестных сравнениях разных языков!
Правила просты: нам нужно придумать такую задачу, в которой JS-код окажется быстрее, чем строчка в строчку аналогичный код на C++. К примеру, давайте эксплуатировать то, что Cons-строки дают нам очень быструю конкатенацию, а Sliced-строки — очень быстрое взятие подстроки.
// unethical-benchmark.js
// дана строка text длиной 1500, найти суммарную длину её подстрок
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
// дана строка text длиной 1500, найти суммарную длину её подстрок
#include
#include
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
Разумеется, это отвратительный код и отвратительное сравнение. Однако на нём хорошо виден именно эффект от Cons‑ и Sliced-строк. А именно: максимально наивный код без всяких оптимизаций может получить значительное ускорение.
Недостатки оптимизаций: учимся «отмывать» строки
Недостаток таких оптимизаций в том, что ими довольно трудно управлять. В других языках программист может явно указать, где ему нужен string view, где string builder, а где однобайтовые строки —, но в JS приходится либо терпеть умолчания движка, либо заниматься колдунством.
Для примера давайте напишем небольшой скрипт, который вытащит нам все адреса ссылок из пары страниц комментов Хабра:
// 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 # работает
$ 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 — подстроки html, представленные как 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
# работает!
$ 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
Как видно выше, код стал падать только при ограничении в 7 МБ — мы выиграли порядка 2 МБ!
Потребление памяти можно улучшить ещё больше, если вспомнить про ещё одну особенность представления строк — TwoByte и OneByte. Воспользуемся тем, что Хабр, как и почти все остальные, отдаёт свои страницы в кодировке 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"); // <---
// наша регулярка прекрасно сработает
// на уровне отдельных байтов UTF-8
for (let match of html.matchAll(/href="(.*?)"/g)) {
let linkUrl = match[1];
// на случай, если в адресах были не-ASCII символы
linkUrl = Buffer.from(linkUrl, "ascii").toString("utf-8");
linkUrls.push(linkUrl);
}
html = null;
}
for (let linkUrl of linkUrls) {
console.log(linkUrl);
}
}
main();
Выиграли ещё около 1 МБ:
$ node --max-old-space-size=7 urls-4.js > /dev/null
# работает!
$ 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
Что в итоге?
Движок V8, как и другие современные среды исполнения JavaScript, включает множество оптимизаций для разных сценариев работы. Сегодня мы рассмотрели его внутреннее устройство строк. Намеренно эксплуатировать их, скорее всего, не получится — хоть мы и «обогнали» C++ на нашем нечестном бенчмарке. Но, с другой стороны, знание внутренностей строк может помочь отловить совершенно неожиданные проблемы с производительностью кода.
Telegram-канал с розыгрышами призов, новостями IT и постами о ретроиграх
