Тест проходил за миллисекунды. На настоящем файле тот же код думал минуту

Тест проходил за миллисекунды. На настоящем файле тот же код думал минуту

Это знает каждый, кто писал на JavaScript:

"привет".length   // 6"👋".length        // 2"🇺🇿".length       // 4

length считает не символы, а кодовые единицы UTF-16. Эмодзи занимает две, флаг — четыре. Обрезать такую строку через slice(0, 20) значит однажды разрубить символ пополам и показать пользователю ромб с вопросительным знаком.

Дальше все делают одно и то же: пишут честную функцию, которая ходит по строке по-настоящему. Я тоже написал. Она была корректной, проходила все тесты и однажды превратила секунду в минуту.

Честная функция

Вот она — примерно в таком виде её пишут все, включая меня:

function isPair(s, i) {  const hi = s.charCodeAt(i);  if (hi < 0xd800 || hi > 0xdbff || i + 1 >= s.length) return false;  const lo = s.charCodeAt(i + 1);  return lo >= 0xdc00 && lo <= 0xdfff;}// длина в символах, а не в кодовых единицахfunction charLength(s) {  let n = 0;  for (let i = 0; i < s.length; i += isPair(s, i) ? 2 : 1) n++;  return n;}// i-й символ, а не i-я кодовая единицаfunction charAt(s, index) {  let seen = 0;  for (let i = 0; i < s.length; seen++) {    const wide = isPair(s, i);    if (seen === index) return wide ? s.slice(i, i + 2) : s[i];    i += wide ? 2 : 1;  }  return null;}

Придраться не к чему. charLength("👋") даёт единицу, charAt("👋🌍", 1) даёт 🌍. Все тесты зелёные.

Проблема в одной строчке, которую видно, только если посмотреть на них вместе: обе функции проходят строку с начала. charLength — целиком. charAt — до нужного места.

А теперь обычный цикл, который вы писали сто раз:

for (let i = 0; i < charLength(s); i++) {  const ch = charAt(s, i);  // ...}

Каждое обращение — проход с нуля. Строка длиной n обходится за n²/2 шагов. Это квадрат, и он спрятан в коде, где нет ни одного вложенного цикла.

Почему этого не видит ни один тест

Я замерил. Функции выше, строка из латиницы, Node 25:

Длина вдвое — время вчетверо. Ровно то, чего и ждёшь от квадрата.

Теперь посмотрите на первую строку таблицы. Десять тысяч символов — это текст этой статьи целиком, и он обходится за 70 миллисекунд. Ни один тест на такой цифре не остановится.

А тесты обычно короче. В моём наборе самая длинная строка была меньше килобайта, и её обход занимал доли миллисекунды. Дефект жил в коде полгода, был покрыт тестами и не проявлял себя нигде: все строки в тестах короткие, потому что их пишут руками.

Вот эта же картинка целиком — вместе с тем, что стало после починки:

Где оно вылезло

Я пишу язык программирования. Не ради языка — ради обвязки вокруг него, но это отдельная история. Важно другое: в какой-то момент лексер этого языка я переписал на нём же самом.

И у меня впервые появилась программа, которая читает не тестовую строчку, а настоящий исходник в 300 килобайт. Первый же прогон: вместо секунды — минуты.

Это и есть главное, что я вынес из истории. Не «квадрат — это плохо», а вот что:

Самая длинная строка, которую видел ваш код, — это самая длинная строка в ваших тестах.

Пока вход придумываете вы, он остаётся вежливым. Настоящий вход приходит снаружи и вежливым не бывает: лог на сто мегабайт, CSV от бухгалтерии, склеенный JSON, чужой исходник. Квадрат, который в тестах стоит доли миллисекунды, там стоит минуты.

Починка

Чинить лобовой кэш «индекс → позиция» не хочется: он растёт вместе со строкой и живёт неизвестно сколько.

Но у задачи есть асимметрия, которой грех не воспользоваться. Суррогатные пары — редкость. В подавляющем большинстве строк, которые проходят через программу, их нет вовсе: имена, ключи, пути, код, латиница, кириллица. А если пары в строке нет, то символ и есть кодовая единица, и по строке можно ходить обычным индексом за постоянное время.

Значит, вопрос ровно один: есть ли в этой строке хоть одна суррогатная пара? Один проход на всю строку вместо прохода на каждое обращение.

const WIDE = /[\uD800-\uDBFF]/;// две ячейки памяти, а не Map — почему, нижеconst seen = ['', ''];const wasPlain = [true, true];let slot = 0;function isPlain(s) {  if (s.length < 64) return !WIDE.test(s);   // короткие проверяем заново  for (let i = 0; i < 2; i++) {    if (s.length !== seen[i].length || s !== seen[i]) continue;    seen[i] = s;              // см. ниже    return wasPlain[i];  }  const answer = !WIDE.test(s);  seen[slot] = s;  wasPlain[slot] = answer;  slot ^= 1;  return answer;}

Дальше charLength для простой строки — это s.length, а charAt — это s[i].

Две детали здесь неочевидные, и обе я поставил не сразу.

Почему не Map. Кажется, что запоминать ответы надо в Map<string, boolean>. Но ключи-строки Map сравнивает по содержимому: чтобы найти запись, ей придётся пройти строку целиком — ровно ту цену, которую мы и убираем. Двух ячеек хватает: посимвольный цикл идёт по одной-двум строкам за раз, дальше памяти не нужно.

Почему seen[i] = s при совпадении. Совпадение могло стоить полного сравнения текстов: две разные строки JavaScript с одинаковым содержимым сравниваются посимвольно, и каждый раз заново. Запомнив именно этот объект, следующее сравнение движок сделает по ссылке.

Результат на той же машине: 320 000 символов — 0,6 мс вместо экстраполированных 69 секунд.

А теперь то, ради чего это стоило писать

Починить — полдела. Дефект такого рода вернётся: кто-нибудь добавит нормализацию, поправит обработку пар, и проход снова станет квадратичным. Тесты об этом не скажут — они и в первый раз ничего не сказали.

Напрашивается тест на время: «обход мегабайта укладывается в 200 мс». Так делают, и так делать не надо. На чужой машине, в контейнере с урезанным CPU, на загруженном раннере он покраснеет без всякого дефекта. Его отключат через неделю, и правильно сделают.

Мерить надо не время, а его рост.

const SHORT = 20_000;const LONG = SHORT * 4;const LIMIT = 8;              // линия даёт 4, квадрат даёт 16const ratio = time('a'.repeat(LONG)) / time('a'.repeat(SHORT));assert(ratio < LIMIT, `рост ${ratio.toFixed(1)}× — похоже на квадрат`);

Порог посередине между четвёркой и шестнадцатью выбран не на глаз. Он должен быть достаточно высоко, чтобы шум машины не валил набор, и достаточно низко, чтобы возврат дефекта не проскочил. Между линией и квадратом разрыв четырёхкратный — в такой зазор порог ставится без нервов.

Ключевое свойство: отношение двух замеров не зависит от скорости машины. Медленный раннер сделает медленнее оба, и частное останется тем же. Тест перестаёт быть флапающим, потому что перестаёт утверждать что-либо про абсолютное время.

Вот что он печатает у меня сейчас:

✓ обращение по индексу: вчетверо длиннее — 3.5× дольше✓ обращение по индексу, кириллица: вчетверо длиннее — 4.1× дольше✓ длина в цикле: вчетверо длиннее — 3.8× дольше✓ срез в цикле: вчетверо длиннее — 3.9× дольше✓ строка с эмодзи: 1 мс, предел 2000сложность: 5/5 прошло

Не «быстро». Линейно. Это разные утверждения, и второе — то, которое имеет смысл защищать тестом.

Что забрать

1. length в JavaScript — это не длина. Если строка приходит от пользователя, обрезка по slice однажды разрубит символ.

2. Честная починка про символы легко оказывается квадратичной. Проверьте: если функция «дай i-й символ» ходит с начала, то цикл по ней — квадрат, даже когда вложенных циклов в коде нет.

3. Тесты этого не покажут никогда. Их входные данные пишут руками, а руками пишут короткое.

4. Тест на время флапает, тест на показатель роста — нет. Вчетверо длиннее обязано быть вчетверо дольше. Это утверждение выживает на любой машине.

5. И общее: дайте своему коду вход, которого вы не писали. Мой квадрат нашёлся, когда программа впервые прочитала настоящий файл вместо тестовой строчки.

---

Код, о котором речь, открыт: github.com/BOTIROFF-D/sable — язык на TypeScript без зависимостей. Замок на сложность лежит в tests/scale.ts, разбор строк — в src/values.ts. Всё меряется командой npm test.