С самого рождения 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 // найти суммарную длину тех её подстрок, у которых длина больше 200 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 // найти суммарную длину тех её подстрок, у которых длина больше 200 #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 Разумеется, это отвратительный код и отвратительное сравнение. Однако на нём хорошо виден именно эффект от 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 и постами о ретроиграх ?️
ссылка на оригинал статьи https://habr.com/ru/articles/745008/
Добавить комментарий