[internals] строки в js
Итак, сижу, почитываю код. Нахожу паттерн, за который в C# можно бить в рожу: чуваки берут и просто конкатенируют кучу строк через +. Оказывается, в js это нормально. Извращенцы.
Решил поизучать поподробнее, обнаружил кучу интересного.
Веревки
Оказывается что, строки реализованы с помощью структуры данных подобной Ropes. Это значит, что объединение строк в js является почти бесплатной операцией (т.е. O(1)).
Представление о том, как работает такая структура данных можно получить в следующих статьях:
См. пруф: https://twitter.com/mourner/status/973664460291411969. Там же говорится, что самые лучшие результаты достигаются, если строки имеют длину ≥ 12. Ну или читайте исходники.
Примечание: исходники v8 говорят, что для создания ConsString (при объединении строк) первая строка должна иметь длину ≥ 13.
Интересные особенности
Дальше, еще более внезапно, но это не совсем Ropes.
В теории извлечение символа из строки должно быть не бесплатное. Но почему-то получаются странные результаты: первое извлечение платное (O(n)), второе бесплатное (O(1)).
Исходники говорят о том, что V8 просто превращает ConsString в нормальную строку. См. код функции “Runtime_StringCharCodeAt”. Функция charCodeAt является потенциальной перфоманс проблемой.
Т.е. это Ropes, но только до тех пор пока не начнешь трогать строки.
Комментарии автора
У меня двоякое ощущение от этой оптимизации. С одной стороны это пиздец как круто, что кто-то подумал и сделал хорошо за тебя. С другой стороны, есть потенциальные редкие проблемные сценарии.
Тем не менее, в контексте сайтиков и говноаппликух это очень хорошее решение.
Слайсы
А для того, чтобы в js быстро работала операции substring и slice, чуваки тоже зафигачили оптимизацию.
Если после такой операции получится строка длины ≥ 13, то v8 делает такой трюк: вместо честной новой строки создается объект такого вида: SlicedString(*parentString, offset, len).
Ловим лулзы
Что внезапно вылезает боком: мы задерживаем ссылку на parentString, т.е. GC не может её собрать. Потенциальный memory leak для того, чтобы обеспечить O(1) вместо O(n) от длины итоговой строки.
На эту штуку даже заведен баг: “Substring of huge string retains huge string in memory”. Там зачетный workaround предложен:
function unleakString(s) { return (' ' + s).substr(1); }Судя по всему, достаточно много проектов словили эту проблему.
Бонус. В треде упомянута статья “A Tale of a JavaScript Memory Leak”, в которой рассказывается: регулярки работают через SlicedString. Также результаты выполнения regexp доступны через глобальное свойство RegExp.lastMatch. GC смотрит на всех в этой истори как на говно.
Ловим больше лулзов
Но! Если внимательно почитать код, то можно обнаружить интересную деталь. В конечном счете мы придем к функции “NewProperSubString”. В которой есть вызов Flatten. А он будет отрабатывать O(n) от длины исходной строки, если она представлена ConsString.
Этот Flatten и объясняет, почему костыль выше вообще работает.
Комментарии автора
И вот это очень странная оптимизация. Пиздец какая сранная оптимизация.
С моей точки зрения, немного странно так жопу рвать, чтобы по итогу две оптимизации между собой так конфликтовали.
P.S: Совет дня: не пишите на JS обработку текстов.
