Pull to refresh

Как убрать все управляющие символы из строки — история одной бурной оптимизации

Reading time 8 min
Views 55K
Получилось так, что мне довелось оптимизировать код кластерной задачи, которая входила в состав Большого Кластерного Алгоритма и занималась весьма простой вещью: входной поток из n полей нужно было в зависимости от содержимого полей переразложить в выходной поток из m полей и почти успокоиться. Почти — потому что внутри полей были строчки произвольного вида, которые нужно было «очистить» — провести простейшую, казалось бы, операцию удаления всех управляющих символов из строки.

Оказалось, что эта операция совсем не такая «простейшая», как кажется, особенно если рассматривать её в современных языках с виртуальной машиной. Чуть ниже я покажу, как можно заменить решение в одну строчку на решение в пару десятков строчек, увеличив производительность алгоритма в ~10 раз. Сразу оговорюсь, что примеры будут относится к Java, но аналогичные рассуждения будут справедливы и для большинства других языков и виртуальных машин — в первую очередь, для .NET-based.

По сути вся деятельность алгоритма сводилась к:
  1. Получить извне (по сети или с диска) набор из N полей: (in1, in2, ..., inn)
  2. Сделать с десяток простейших операций типа копирования in в out с проверками простых условий
  3. Очистить все строки в (out1, out2, ..., outm) от управляющих символов
  4. Передать их дальше (записать на диск или отправить по сети)

С моей точки зрения логично было бы, чтобы такая задача упиралась в диск или сеть — нагрузка на процессор здесь должна быть минимальная. Однако, простейший профайлинг показал совсем другое. Исходный вариант содержал строчку, на которую тратилось 80-90% рабочего времени алгоритма — это была ровно одна строчка, которая и делала операцию 3, вот она:

Вариант 1
s = s.replaceAll("\\p{Cntrl}", "");

Я даже знаю, откуда взялась эта строчка — быстрый поиск в Google по фразе «java strip non-printable characters» выдает именно этот вариант. Итак, задача понятна, цели понятны, программистское самолюбие задето («как же так, неужели я не смогу разогнать эту несчастную строчку»), поехали!

Делаем на скорую руку простенькую обвязку, замеряющую время работы алгоритма, изолируем его от всего остального кода, генерируем тестовую входную строчку, которую будем прогонять миллионы раз через алгоритм и замеряем производительность. Получается, что первый вариант обрабатывает 517009 строчек в секунду. Делаем несколько замеров, понимаем, что точность наших измерений и экспериментов — порядка 2-3% — т.е. грубо говоря, на последние 4 цифры можно совсем не смотреть, а на пятую цифру с конца — смотреть, но не заглядываться. Т.е. результаты где-то между 500..540 тысячами.

Вспоминаем, что же именно у нас за строчки и что нам нужно фильтровать и что такое \p{Cntrl}. Понимаем, что этот элемент по сути равнозначен выбору символов с кодами от 0 до 31 включительно, плюс 127. На всякий случай быстро проверяем, а не дает ли что-то, если мы поменяем этот \p{Cntrl} на более банальное перечисление всех символов в регулярном выражении через оператор типа [a-z], в нашем случае:

Вариант 2
s = s.replaceAll("[\\x00-\\x1F]", "");

Нет, не дает. Всё те же 520000±3%.

Вспоминаем, что в чудесном языке Java компилятор, виртуальная машина и stdlibs зачастую живут отдельной жизнью и скорее всего такую простейшую операцию не оптимизируют — несмотря на то, что миллионы раз повторяется одно и то же регулярное выражение, оно каждый раз компилируется заново. Подглядывание в документацию на String#replaceAll эту догадку подтверждает. Пытаемся вынести эту самую компиляцию за скобки:

Вариант 3
public static final Pattern KILL_CC_PATTERN = Pattern.compile("[\\x00-\\x1F]");
...
Matcher m = KILL_CC_PATTERN.matcher(s);
s = m.replaceAll("");

Внезапно, вместо одной строчки — три, а производительность выросла до 640000±3% — не в разы, но внезапно +23% мы отыграли.

Недолго думаем, можно ли сделать лучше. Пробуем, что будет, если проходить по строке вручную в цикле, анализируя символ за символом (вытаскивая их через String#codePointAt), и сохраняя в другую строку. Подсознание автоматом подсказывает, что только не в строку, а в StringBuilder или StringBuffer. В нашем случае без разницы, что использовать — у нас параллелизацию делает кластер, запуская N независимых процессов параллельно. Быстрый взгляд на документацию показывает, что рекомендуют заранее инициализировать StringBuilder с некоей capacity — числом предполагаемых символов в результате. Нет причин не верить документации, так и сделаем — нам точно известно, что в результате у нас будет явно не больше, чем было в строчке изначально.

Вариант 4
StringBuilder sb = new StringBuilder(s.length());
for (int j = 0; j < s.length(); j++) {
    int ch = s.codePointAt(j);
    if (ch >= ' ')
        sb.appendCodePoint(ch);
}
s = sb.toString();

7 строчек вместо 1, зато уже 710000±3% строчек в секунду. Это уже +37% — больше трети.

Продолжаем думать дальше. Проскакивает простенькая мысль — что будет, если убрать работу с Unicode codepoints и перейти к использованию обычных Java'овских char? Потеряем возможность смотреть на всякие суррогаты, композиты и т.п. как на целое — но с точки зрения стриппинга — ничего плохого не будет. Пробуем:

Вариант 5
StringBuilder sb = new StringBuilder(s.length());
for (int j = 0; j < s.length(); j++) {
    char ch = s.charAt(j);
    if (ch >= ' ')
        sb.append(ch);
}
s = sb.toString();

Те же 7 строчек, изменение незначительное на первый взгляд, зато производительность внезапно подскакивает до 1052000±3%! Это уже круто — это чуть больше, чем в 2 раза относительно исходного (+103%).

Можно ли сделать еще быстрее? Можно! Посмотрим внутрь StringBuilder, внезапно увидим, что это отнюдь не какая-то дикая магия, уходящая глубоко в C-код JVM, а вполне себе решение на чистой Java. Внутри StringBuilder'а хранятся банально структуры данных, увязывающие цепочки символов через массивы char. Все эти структуры в нашем случае лежат без надобности — мы не собираемся вставлять что-то там в середину строки, раздвигать и т.п. Можно действительно все тупо сделать на массивах, практически C-way:

Вариант 6
char[] res = new char[s.length()];
int newLen = 0;
for (int j = 0; j < s.length(); j++) {
    char ch = s.charAt(j);
    if (ch >= ' ') {
        res[newLen] = ch;
        newLen++;
    }
}
s = new String(res, 0, newLen);

Строчек стало 10, зато производительность выросла еще вдвое: аж 2022000±3%! Это в 4 раза быстрее, чем оригинальный вариант с regexp'ом.

Что здесь можно еще оптимизировать? Вызов append по сути мы оптимизировали, а вот можно ли как-то оптимизировать прохождение по строчке с помощью String#charAt()? Оказывается, тоже можно. Выпив очередную чашку кофе, по попробуем подсмотреть внутрь исходников класса String и того же StringBuilder. Там мы увидим, что внутри String вся работа идет с тем же char[], т.е. можно сократить число вызовов методов (операций типа invokevirtual с точки зрения байт-кода), сведя все к операциям типа aload, iload, castore и т.п. — которые весьма «дешевы» и хорошо оптимизируются JVM.

Таким образом, все банально: от многих вызовов charAt() можно уйти, заменив их одним String#getChars. Проверяем:

Вариант 7
char[] oldChars = new char[s.length()];
s.getChars(0, s.length(), oldChars, 0);
char[] newChars = new char[s.length()];
int newLen = 0;
for (int j = 0; j < s.length(); j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        newChars[newLen] = ch;
        newLen++;
    }
}
s = new String(newChars, 0, newLen);

Очередное маленькое чудо происходит: 12 строчек, зато 2500000±3%, т.е. в 5 раз быстрее оригинала.

Наверняка исходную задачу мы уже давно выполнили — кластерный алгоритм стал упираться во что-то другое, а не в эту операцию, да и потратил я на эти микрооптимизации уже совсем неприлично много времени, поэтому здесь мой собственный мозг предпочел сдаться и смириться с тем, что еще быстрее сделать уже вряд ли можно. Через некоторое время уже спортивного интереса ради я вернулся к задачке и попробовал еще несколько гипотез:
  • Что будет, если вместо String#getChars() использовать String#getBytes()? Ничего хорошего не будет, внутри Java хранит строчки именно в виде массивов 16-битных чисел типа char; операции типа getBytes() получается весьма дорогими — т.к. преобразование в какую-либо кодировку (будь то utf-8, какая-либо двухбайтная кодировка или однобайтная кодировка) — нетривиальная операция. Самым медленным, как ни странно, стал вариант с преобразованием к windows-1251.
  • Добавление final везде, где можно, вопреки традиционно сложившемуся мнению, не дает никакого прироста
  • Использование инкремента внутри операции с массивом — newChars[newLen++] — ничего, кроме сокращения кода на 1 строчку, не дает
  • Параллелизация в этом конкретном месте не дает ничего — затраты на то, чтобы порождать 2-3-4 thread'а и работать над строчкой по частям несоизмеримы с выигрышем от такой параллелизации; плюс, в исходной задаче параллелизацию и так обеспечивал кластерный фреймворк

В продолжение спортивного интереса, я закинул эту задачку на stackoverflow и там мне подсказали несколько довольно древних, но, к моему удивлению, действенных методик, по сути в чистом C-стиле:

Вариант 8
int length = s.length();
char[] oldChars = new char[length];
s.getChars(0, length, oldChars, 0);
int newLen = 0;
for (int j = 0; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);

Как ни странно, дает аж 3100000±3% строчек в секунду, т.е. почти в 6 раз быстрее оригинала, и быстрее предыдущего лучшего варианта еще на 24%.

Основной выигрыш достигается за счет двух банальных, известных с C, но до сих пор вполне работающих конструкций: предпросчет длины строки в переменной length (экономия на вызовах String#length() — я почему-то наивно надеялся, что JVM это сделает за меня) и использование одного и того же массива oldChars одновременно для хранения и старой, и новой строчки (пользуясь тем, что из старой строчки нам всегда нужен j-тый символ, причем на момент чтения j-того символа всегда j <= newLen).

Казалось бы куда дальше — но есть еще и девятый вариант. На самом деле можно избежать вообще любого выделения памяти, пожертвовав thread safety этой функции и выделив заранее статический буфер. Играть будем на том, что большинство строчек в исходном потоке в целом ограничены каким-то определенным значением сверху — например, 1024 символами. Лишь для очень единичных случаев нужно будет выделять буфер побольше — соответственно, это и проделаем:

Вариант 9
public static char[] buf = new char[1024];
...
int length = s.length();
char[] oldChars = (length < 1024) ? buf : new char[length];
s.getChars(0, length, oldChars, 0);
int newLen = 0;
for (int j = 0; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;
        newLen++;
    }
}
s = new String(oldChars, 0, newLen);

Мелочь вроде бы, но дает аж 3490000±3% строчек в секунду, т.е. 6.7× прирост (или +12.5% относительно предыдущего варианта).

Окончательный вариант, на котором я пока остановился — десятый. Фактически последнее, на чем тут можно сэкономить — это на создании нового объекта String — особенно жалко это делать, если на практике 99.9% строчек, проходящие через алгоритм, не нуждаются в стриппинге и выход равняется входу.

Вариант 10
public static char[] buf = new char[1024];
...
int length = s.length();
char[] oldChars = (length < 1024) ? buf : new char[length];
s.getChars(0, length, oldChars, 0);
int newLen = 0;
for (int j = 0; j < length; j++) {
    char ch = oldChars[j];
    if (ch >= ' ') {
        oldChars[newLen] = ch;
        newLen++;
    }
}
if (newLen != length)
    s = new String(oldChars, 0, newLen);

Это немножко читинг, потому что используются априорные знания о входном потоке, но оно того стоит. Итоговый лучший результат — 5350000 строчек в секунду при обработке потока, в котором обрабатывать нужно только 0.1% строчек. Прирост — уже 10× от оригинала или +53% от предыдущего варианта.

Выводы и мораль

  • 5-6 часов работы над 1 строчкой могут превратить ее в 15 строчек и сделать быстрее в 10 раз; высокая цена, но она адекватна, если речь идет о действительно узком месте
  • Чтение кода Java stdlibs и JVM может быть весьма полезным
  • Далеко не всегда нужно бросаться опрометчиво в религию «как же все медленно, давайте все перепишем на JNI» — зачастую задачу можно решить и без JNI
  • Работа с codepoints в Java почти всегда будет медленнее работы с char; стоит взять себе за правило — мотивировать, зачем нужны codepoints, если уж так хочется их применить
  • Встроенные Java regexps, во-первых, имеют долбанутый API (подстрекая тем самым излишне часто компилировать одни и те же выражения), во-вторых, достаточно медленны на таких простых операциях; впрочем, о том, что встроенные Java regexps медленные — и так все знают
  • Любые сложные структуры данных (StringBuffer, StringBuilder, String) в Java зачастую работают внутри с базовыми массивами примитивных типов, и зачастую делают это менее оптимально, чем хотелось бы
  • Масса старых трюков (final, работа с байтами вместо wide characters) не работают
  • Масса старых трюков (вынесение результата часто используемого метода в переменную, экономия на выделении памяти, повторное использование) очень даже работают

Хм. Может быть кто-нибудь знает способы, как можно сделать это еще быстрее?

P.S. Автор замечательной фотографии в начале статьи — JcOlivera.com, фотография распространяется под CC-BY-NC-ND.
Tags:
Hubs:
+101
Comments 81
Comments Comments 81

Articles