"История одной оптимизации"

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

Каждый раз жалею, что там еще не зарегистрирован -- полдня бы точно потратил на веселье в комментах :)

По-правде говоря, статья произвела фиговое впечатление. Я не хочу вдаваться в подробности оптимизаций, дело не в этом -- мне не понравилось отсутствие какой-то системы. Т.е. если первые 5 шагов оптимизации еще как-то понятны -- это переделка алгоритма с использованием априорной информации о задаче -- то дальше идет почти в чистом виде попытка переплюнуть JIT. И вот уже эта часть -- просто какая-то каша. Раз за разом все более странный код, все более в C-style, но главное -- нет никакой системы, просто набор слепых попыток "а если вот эдак?".

Две вещи мне особенно понравились. Автор сам задает, что 99.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++;
    }
}
if (newLen != length)
    s = new String(oldChars, 0, newLen);

Потрясающе -- на этом самом коротком маршруте мы дважды копируем символы исходной строки -- первый раз внутри getChars(), второй руками, внутри цикла -- и все это для того, чтобы в 999 случаях из 1000 обнаружить, что ни первое, ни второе копирование нам не нужно, потому что newLen == length. Мне это кажется немного странным.

Я не поленился прогнать бенчмарки дюжины разных реализаций. Вот лидер:

public class PlainScanLazyReplacer {

    public String replaceControls( final String str ) {
        final int length = str.length();
        for ( int i = 0; i < length; i++ ) {
            final char ch = str.charAt( i );
            if ( Util.isControlChar( ch ) ) {
                return realReplace( str, i );
            }
        }
        return str;
    }

    protected String realReplace( final String s,
                                  final int startWithIndex ) {
        final int length = s.length();
        final StringBuilder sb = new StringBuilder( s );
        int newLen = startWithIndex;
        for(int i=startWithIndex;i < length;i++){
            final char ch = sb.charAt( i );
            if ( Util.isNonControlChar( ch ) ) {
                sb.setCharAt( newLen, ch );
                newLen++;
            }
        }
        sb.setLength( newLen );
        return sb.toString();
    }

Метод realReplace() можно оптимизировать, но смысла в этом нет (я проверял) -- он ведь вызывается 1 раз из 1000. Обратите внимание, что основной цикл -- самый классический прогон по строке с помощью charAt(). Ничего больше -- не нужно.

Версия с reflection:

private static final Field buffField;
    private static final Field offsetField;

    static {

        try {
            buffField = String.class.getDeclaredField( "value" );
            buffField.setAccessible( true );
            offsetField = String.class.getDeclaredField( "offset" );
            offsetField.setAccessible( true );
        } catch ( NoSuchFieldException e ) {
            throw new RuntimeException( e );
        }

    }

    public String replaceControls( final String s ) {
        try {
            final char[] buff = ( char[] ) buffField.get( s );
            final int offset = ( Integer ) offsetField.get( s );
            final int length = s.length();

            for ( int i = 0; i < length; i++ ) {
                final char ch = buff[offset + i];
                if ( Util.isControlChar( ch ) ) {
                    return realReplace( s, i );
                }
            }
            return s;
        } catch ( IllegalAccessException e ) {
            throw new RuntimeException( e );
        }
    }

работает (у меня) за то же время, что и более простая и очевидна версия выше. Лично меня это даже и не удивляет -- потому что charAt() будет почти наверняка встроен JIT-ом, и получится тот же самый проход по массиву -- только уже безо всякой магии reflection.

Мораль сей басни: чтобы быть умнее JIT-a надо в самом деле быть очень, очень умным :)

Вторая вещь еще интереснее. "Важно не то, почему код работает быстро, важно то, почему он не может работать быстрее -- во что мы здесь уперлись?" (Алексей Шипилев). Во что мы упираемся в коде из листинга 1? Мне пришла в голову такая вот идея: когда я генерирую входные данные для бенчмарка, обычно я создаю строки каждую по-отдельности -- со своим внутренним массивом char[] value. А что будет, если я солью все строки в одну большую строку, а потом "нарежу" ее на отдельные строки -- так, что все строки будут разделять один-единственный массив символов (и, более того, их данные будут идти в этом массиве по порядку)? По-идее, это должно давать идеальный шаблон доступа к памяти. Если мы упираемся в какие-то вычисления (в скорость CPU) -- изменение шаблона доступа к памяти не должно особо влиять на производительность. А вот если мы упираемся в память -- должно.

Результат бенчмарка: cache-friendly код выполняется на треть быстрее обычного. Это, конечно, не 100% доказательство, но уже серьезный повод подумать, имеет ли смысл дальше пытаться оптимизировать код разными трюками типа изменения порядка обхода массива, если мы, похоже, упираемся в скорость доступа к памяти?