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

Это знает каждый, кто писал на 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, квадрат даёт 16

const 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.