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

    Получилось так, что мне довелось оптимизировать код кластерной задачи, которая входила в состав Большого Кластерного Алгоритма и занималась весьма простой вещью: входной поток из 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.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 81

      –2
      условное сравнение — плохо.
      лучше использовать таблицу.
      что-то типа:
      unsigned char allowedChars[256] = {
      /* 0x00 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
      /* 0x10 */ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
      /* 0x20 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
      ...
      };
      ...
              oldChars[newLen] = ch;
              newLen += allowedChars[ch];
      

      Таким образом значение в oldChars[i] будет перезатираться до тех пор, пока не увеличим счетчик, то есть не найдем корректный символ для этой позиции.

      Ну и разворот цикла, я думаю, тоже бы помог.
        0
        Ой не факт, что таблица будет лучше, учитывая тот момент, что сравнение (это все же сравнение регистра и константы), а обращение к таблице, это дополнительное обращение к памяти. Конечно в данном случае все зависит от реализации виртуальной машины, но все же использование константы и обращение к памяти. При сравнении есть усугубление в виде последующего условного перехода, так что данный вариант стоило бы просто проверить на практике.
          +4
          Очень спорно. Обычно любые манипуляции с памятью работают медленнее чем арифметические операции.

          Вообще статья напомнила «сначала напишем криво, а потом напишем нормально и обнаружим 10x прирост скорости». А ведь заголовок был интересный: «чуть ниже я покажу, как можно заменить одну строчку на пару десятков, увеличив производительность алгоритма в несколько десятков раз» — я сразу представил, как одну строчку скопировали десять раз, как то хитро удалили символы из них, учитывая особенности кеша процессора, потом соединили строчки вместе и получили то что надо, но быстрее в 10 раз. Оказалось, что в «заменить одну строчку на пару десятков» под строчкой имелась ввиду строчка кода, а не та строчка в которой надо символы удалять :)
            0
            Вы просто на другом уровне игры-квеста «Программист» уже ;)
            +1
            Вообще-то речь идет о Java. Там newLen += allowedChars[ch] выльется как минимум в два сравнения (range check). Да даже для C эта оптимизация не имеет смысла: newLen += (ch >= ' ') будет быстрее. Условных переходов в сгенерированном коде нет.
              0
              А если символ будет больше, чем 256? OutOfBoundsException
              –7
              То ли народ перестает задумываться о оптимизации, то ли что, что на оптимизацию подобного тратится столько времени, да и по этому еще пишется статья.

              TDD возможно и хорош, но хорош, когда недостаточно опыта сделать правильную оценку ситуации.

              В данном случае, сразу понятно, что необходимо минимизировать работу с памятью, исходя из этого регулярки, StringBuilder можно было отсеять на этапе постановки задачи.
                +1
                Все бы так оптимизировали…
                  +4
                  Если надо модифицировать всего 0.1% строк, то можно попробовать написать отдельный быстрый поиск управляющего символа. А если вдруг нашли, то уже работать…

                  Правда, в последнем варианте и так уже лишний действий нет.
                    0
                    В порядке бреда, C-style:

                    int okCnt = 0;
                    for (int j = 0; j < length; j++) {
                    char ch = oldChars[j];
                    okCnt += ch&128 | ch&64 | ch&32;
                    }
                    if (okCnt != length) do_wrk();

                    Будет ли это работать быстрее так? Будет ли это работать быстрее, если развернуть цикл 4 раза и использовать 4 независимых okCnt? Нет мне ответа, потому что теста в руках нету :)
                      0
                      Там ещё >> забыты в сумме:
                      okCnt += (ch&128)>>2 | (ch&64)>>1 | ch&32;
                      И при сравнении не забыть сделать >>5.

                      Никак не тестировал, пишу «из головы».
                        0
                        А где формирование стрип-строки? Достаточно тривиальное условие вы завернули серьезно, а стрип, по сути вынесли в do_wrk(). В чем профит?
                          0
                          Хотя если речь идет об отсеивании при условии, что неизвестен % фильтрации (и он явно >>0.1%, то возможно будет ускорение). Интересная идея.
                            0
                            «потока, в котором обрабатывать нужно только 0.1% строчек», т.е. отсеивается более 99.8% строчек.
                        +2
                        Ради эксперимента было бы интересно посмотреть на результат кода на C/C++
                          0
                          осталось i++ заменить на ++i
                          :)
                            +8
                            Уточните, тестировали на синтетике? Или реальные данные? Если синтетика — как формировалась. Дайте больше входных параметров, чем мы хуже stackoverflow :)
                              +2
                              Очень хорошие вопросы :) Прошу прощения, что пропустил комментарий и отвечаю с опозданием.

                              Изолированный алгоритм тестировал на синтетике. Изначально вообще брал одну константную строчку в ~130 символов и 140 UTF-8 байт, прошитую в коде и стирпал ее. В строчке было порядка 5-6 управляющих символов, для измерений прогонял по ~10 миллионов итераций «для разогрева» JIT, затем по ~100 миллионов итераций. Для того, чтобы убедиться, что JIT хотя бы по первому разу отработал — рядом еще был цикл, который не делал ничего. После JIT он, разумеется, превращался в ничто и отрабатывал за 0 мс.

                              Затем понял, что одинаковая синтетика — тоже плохо и стал поступать так: генерировал N строчек длиной от 20 до 220 символов, заполняя их случайными символами из диапазона 0..127. Пытался читать из с диска и писать на диск, но понял, что это только мешает измерениям и ничего хорошего не приносит. Оно, разумеется, лучше эмулирует поведение на практике, но в тот момент меня уже интересовал больше теоретически достижимый результат и, как следствие, наиболее «чистый» учет времени.

                              В конечном варианте, когда понял, что нужно сыграть на том, что строчка не изменяется — стал генерировать строчки с символами из диапазона 32..127, и только если Random#nextInt(100) == 0 — с символами из диапазона 0..127.

                              Все измерения проводил на
                              java version «1.6.0_24»
                              Java(TM) SE Runtime Environment (build 1.6.0_24-b07)
                              Java HotSpot(TM) 64-Bit Server VM (build 19.1-b02, mixed mode)
                              Linux 2.6.39-2-amd64 #1 SMP Wed Jun 8 11:01:04 UTC 2011 x86_64 GNU/Linux
                              +1
                              Еще немного древних методик: префиксный декремент (может тоже не оптимизируется) и обход цикла в обратном порядке.

                              // здесь проверка что length > 0

                              int pos = length - 1;
                              for (int j = pos; j >= 0; --j) {
                              char ch = oldChars[j];
                              if (ch >= ' ') {
                              oldChars[pos] = ch;
                              --pos;
                              }
                              }
                              if (pos >= 0) {
                              ++pos;
                              s = new String(oldChars, pos, length - pos);
                              }
                                0
                                Еще один вариант: проверяем на равенство нулю и упрощаем сравнение символов.

                                // здесь проверка что length > 0

                                int pos = length — 1;
                                for (int j = pos; j != 0; --j) {
                                char ch = oldChars[j];
                                if (ch > '\x1F') { // или как там пишется ascii код
                                oldChars[pos] = ch;
                                --pos;
                                }
                                }

                                char ch = oldChars[0];
                                if (ch > '\x1F') {
                                oldChars[pos] = ch;
                                }
                                else {
                                ++pos;
                                }

                                if (pos != 0) {
                                s = new String(oldChars, pos, length — pos);
                                }

                                P.S. кстати момент «что этот элемент по сути равнозначен выбору символов с кодами от 0 до 31 включительно, плюс 127» в итоговом алгоритме упущен.
                                  +2
                                  Извинияюсь, я не в теме, поэтому такой вопрос — а почему цикл в обратном порядке быстрей?
                                    0
                                    Сори, уже прочитал коммент ниже
                                  +4
                                  Городская легенда гласит, что если цикл пустить в обратную сторону, то он компилируется в чуть-более эффективный байт-код (а одну операцию вычитаня меньше, в обласли сравнения условий).

                                  Альтернативно, можно ничего не делать по-умолчанию:
                                  oldChars[newLen] = ch; очень отжирает время на запись в память.
                                  если newLen == j, то писать не нужно вообще ничего! Там и так то же самое.
                                    0
                                    Тоже подумал о лишнем копировании, вот еще один вариант (за точность не ручаюсь негде проверить):

                                    // здесь проверка что length > 0

                                    int pos = length — 1;
                                    char ch = oldChars[pos];

                                    while (pos != 0 && ch > '\x1F') {
                                    --pos;
                                    ch = oldChars[pos];
                                    }

                                    if (pos == 0) {
                                    if (ch > '\x1F') {
                                    // возвращаем исходную строку
                                    }
                                    }
                                    else {
                                    for (int j = pos — 1; j != 0; --j) {
                                    char ch = oldChars[j];
                                    if (ch > '\x1F') { // или как там пишется ascii код
                                    oldChars[pos] = ch;
                                    --pos;
                                    }
                                    }
                                    ch = oldChars[0];
                                    }

                                    if (ch > '\x1F') {
                                    oldChars[pos] = ch;
                                    }
                                    else {
                                    ++pos;
                                    }

                                    if (pos != 0) {
                                    s = new String(oldChars, pos, length — pos);
                                    }
                                      0
                                      Еще один вариант:

                                      int pos = length — 1;

                                      if (pos < 1) {
                                      if (pos == 0 && chars[0] > '\x1F') {
                                      return s;
                                      }
                                      else {
                                      return string.Empty;
                                      }
                                      }

                                      char ch = chars[pos];

                                      while(ch > '\x1F') {
                                      if (--pos == 0) {
                                      if (chars[pos] > '\x1F') {
                                      return s;
                                      }
                                      else {
                                      return new String(chars, 1, length — 2);
                                      }
                                      }
                                      ch = chars[pos];
                                      }

                                      for (int j = pos; --j != 0;) {
                                      ch = chars[j];
                                      if (ch > '\x1F') { // или как там пишется ascii код
                                      chars[pos--] = ch;
                                      }
                                      }

                                      ch = chars[0];

                                      if (ch > '\x1F') {
                                      chars[pos] = ch;
                                      }
                                      else {
                                      ++pos;
                                      }

                                      return new String(chars, pos, length — pos);
                                    0
                                    Отрадно было прочитать вот это в начале статьи:
                                      0
                                      >С моей точки зрения логично было бы, чтобы такая задача упиралась в диск или сеть — нагрузка на процессор здесь должна быть минимальная. Однако, простейший профайлинг показал совсем другое. Исходный вариант содержал строчку, на которую тратилось 80-90% рабочего времени алгоритма — это была ровно одна строчка, которая и делала операцию 3, вот она:
                                      +6
                                      Главное, чтобы потом эту функцию не начали использовать для обработки UTF-8, там много многобайтовых управляющих символов.
                                        0
                                        Если строка превратилась в Java String, то там в любом случае UTF-16. В другом виде char не хранится.
                                          0
                                          Тут стоит на самом деле уточнить задачу: мне на самом деле не нужно было вырезать все возможные управляющие символы (тем более то, что называется в Unicode с general category равной Cc, Cf и Cs), мне даже не нужно было вырезать все управляющие символы ASCII. После этой обработки данные записываются в текстовые tab-separated файлы — в минимальном варианте мне нужно было просто обеспечить удаление \t, \n, \r (9, 10, 13), чтобы они не порушили парсинг такого текстового файла дальше у пользователя — т.е. строчки оставались бы строчками, столбцы бы не съезжали.

                                          В качестве бонуса — приятно было бы, чтобы экран при просмотре файла не перекашивало от случайного наличия Esc-последовательностей (т.е. нужно резать 27) и чтобы консоль не пищала (т.е. резать 7)

                                          В итоге оказалось, что проще и эффективнее просто отрезать все, что в диапазоне 0-31.
                                            0
                                            А чем не угодил символ #127?
                                              0
                                              В смысле — «не угодил» и кому он не угодил?
                                                0
                                                Цитирую:
                                                Вспоминаем, что же именно у нас за строчки и что нам нужно фильтровать и что такое \p{Cntrl}. Понимаем, что этот элемент по сути равнозначен выбору символов с кодами от 0 до 31 включительно, плюс 127.
                                                C [0..31] всё ясно, а чем опасен «плюс 127»?
                                                  0
                                                  Видимо, тем же, чем и [0..31] — в некоторых системах он является управляющим символом, с определенной семантикой и всем полагающимся. Тут уж тогда надо или более философский вопрос «что является управляющим символом» ставить, или — в данном конкретном случае — просто не париться, потому что авторы движка регэкспов в Sun уже давно решили для себя эту проблему вот таким вот образом.

                                                  Если вдаваться в философствования — то имеет смысл либо отвечать на вопрос «для кого является» (и понимать, что в описываемом кластерном комплексе на самом деле более, чем достаточно было фильтровать всего 3 символа — \t, \r и \n), либо пытаться составить «список управляющих символов на все случаи жизни по всем возможным стандартам». Это, кстати, весьма нетривиально с учетом Unicode.
                                          +9
                                          Расскажу и я байку про оптимизацию. На одном заводе из листа цветного металла раскраивали круглые заготовки для последующей вытяжки и обрезки (делали стаканы). На завод пришли два молодца, которые на коленке и существовавшей в то время на заводе ЭВМ набросали алгоритм, который рассчитал оптимальный раскрой позволяющий экономить до 40% металла при раскрое. Внедрили в производство. А рабочие в итоге стали на них как волки смотреть, а все потому что обрезки которые раньше выкидывались шли к ним в карманы, а теперь нет :)
                                            +2
                                            Хм… мне всегда казалось что все обрезки металла отправляются на переработку. Ну а по бумагам должно быть видно сколько металла потрачено на детали, сколько осталось и сколько отправлено на переработку.
                                              +4
                                              У меня дед в свое время работал на заводе, где помимо всего прочего в одном из производственных циклов участвовал титан (какие-то корпуса из него делали, если не ошибаюсь для навигационного оборудования).
                                              Так у всего цеха дома лежали ТИТАНОВЫЕ!!! ведра, лопаты, тазы и прочая утварь. Вечная (до сих пор как новые), легкая, и безобразно дорогая.
                                                0
                                                Ну если углубляться, то у оптиков (и не только) при напылении золота любимое занятие — подложить в камеру с проволочкой, которую испаряют, свои кольца/цепочки, дабы хоть микрон, но напылить.
                                              +6
                                              Это пересказ вполне реальной истории, имевшей место:

                                              Много лет назад произошла, пожалуй, наиболее типичная — по непониманию — ситуация, которую сегодня часто вспоминают как анекдот. Но это — не анекдот. На вагоностроительном заводе имени Егорова в Ленинграде с помощью линейного программирования сделали раскрой металла. Это была пионерная работа и в мире, и у нас в стране. Делалось все в эпоху арифмометров, а не ЭВМ, вообще, вероятно, это было первое в мировой практике реальное применение методов линейного программирования.

                                              После того как были применены оптимальные методы и несколько сократился расход металла, оказалось, что резко уменьшилась возможность сдачи металлолома. В итоге был сорван план сдачи отходов металла, а раз один из показателей плана не выполнен, то предприятие не может быть премировано в полном размере. Тогда райком помог преодолеть эту трудность, и в виде исключения премия заводу была сохранена, несмотря на срыв одного из показателей. Второй казус этой ситуации: отраслевое начальство, получив рапорт о том, что завод на 4 процента увеличил использование металла при раскрое, предложило им не терять темпа и в следующем году опять подняло план использования металла на те же 4 процента. Выходило, что металл должен использоваться на 101 процент, и пришлось даже писать бумагу от академии, что больше 100 процентов не бывает.


                                              exsolver.narod.ru/Intresting/Kantor/Kantor_seetruth.html

                                              Как водится, передовые технологии (Канторович и его линейное программирование) уперлись в твердолобость бюрократов.
                                              +1
                                              > Добавление final везде, где можно, вопреки традиционно сложившемуся мнению, не дает никакого прироста

                                              «final» — это по сути дела памятка программисту самому себе и директива компилятору напомнить об этом в случае описки. байт-код будет отличаться только атрибутами, но не собственно операциями. поэтому прироста от файнала ждать не следует.

                                              да, кстати, вместо вышеуказаного кода
                                              int pos = length — 1;
                                              for (int j = pos; j >= 0; --j) {
                                              предлагаю
                                              for ( int j = length; --j >= 0; ) {
                                              Существенного прироста это не даст, но выглядит не хуже
                                                0
                                                это не везде применимо, т.к. pos используется дальше, а вообще прирост может быть, при сравнении j уже будет лежать в регистре.
                                                  +1
                                                  я хотел показвть общий принцип написания цикла задом наперед,
                                                  ибо часто цикл «переворачивают» не совсем оптимально на мой взгляд

                                                  вариант 1, прямой классический
                                                  for ( int i = 0; i < v.size ( ); i++ )

                                                  вариант 2, перевернутый неоптимальный
                                                  for ( int i = v.size ( ) — 1; i >= 0; --i )

                                                  вариант 3
                                                  for ( int i = v.size ( ); --i >= 0; )

                                                  я уже привык свой код писать по варианту 3, и остальные варианты уже «режут глаз»
                                                    +1
                                                    А вот еще более красивый вариант:
                                                    int i = v.size();
                                                    while(i --> 0){

                                                    }
                                                      0
                                                      я не считаю это «более красивым» потому что
                                                      а) с точки зрения байткода скорее всего получится примерно то же самое (задание на дом)
                                                      б) запись for ( int i… инкапсулирует переменную «i» внутри цикла
                                                      в) мне больше нравится однострочная запись цикла for, чем ваш двустрочный вариант

                                                      скажем так — это эквивалентная запись варианта 3. кому как нравится.
                                                        +2
                                                        На самом деле, for тоже можно написать в таком стиле:
                                                        for ( int i = v.size ( ); i -->0; )

                                                        Да, одна строка лучше двух, и инкапсуляция это хорошо, но когда я вижу эти идиотские точки с запятой — мне резко перестает нравиться for-версия(сейчас я про последний символ, висящий, хотя не нравятся мне они все внутри for).

                                                        Относительно байткода — думаю, результат просто обязан быть идентичным.

                                                        А вообще, у меня это осознанная необходимость — я в основном пишу на haXe, а в нем for работает только с итераторами. Канонически, это надо писать как for(i in 0...v.size()) (Да-да, тип i инферится), где 0...v.size() — сахарный конструктор итератора. Плюс — такой итератор в цикле развернется. Минус — только от меньшего к большему. Так что если хочется выжать немного больше производительности — приходится спускаться к while в любом случае. Но я начал находить в этом особый кайф — while автоматически отмечает оптимизированные места.

                                                        И, да, надо уже добавить возможность прохода от большего к меньшему. На самом деле, если я этим займусь, то итоговая версия будет идеальна, на мой взгляд, for(i in v.size()...0) в идеальную по скорости конструкцию.
                                                      0
                                                      Вы правы, но лишь частично :)

                                                      Я померял все три варианта, получаются такие средние затраты времени:

                                                      вариант 1 — 334655
                                                      вариант 2 — 335893
                                                      вариант 3 — 334851

                                                      Т.е. для Java — скорее, самым адекватным остается простой прямой цикл, хотя разница где-то на полпроцента-процент.

                                                      Байткод для первого варианта занимает 23 байта (19 инструкций), для второго — 24 байта (20 инструкций), для третьего — 22 байта (18 инструкций). С точки зрения JVM «if_icmplt» и «ifge», видимо, работают одинаково.
                                                        +1
                                                        я анализировал байткод два года назад тут:
                                                        blogs.mail.ru/corp/bachin/5D31118461B9C125.html
                                                        (по размеру для меня важнее, чем по скорости, но про скорость не забываю)
                                                        Кстати, JVM бывают разные… весьма разные…
                                                          0
                                                          Спасибо :)
                                                          JVM-то бывают, но в моем случае я относительно привязан к одной существующей — кроме как на Sun'овской 1.6.0 Hadoop работает очень странно.
                                                  +1
                                                  > я покажу, как… в несколько десятков раз.
                                                  >…
                                                  > Выводы
                                                  >…
                                                  > быстрее в 10 раз

                                                  В чем-то заядлые программисты схожи с заядлыми рыбаками…
                                                  Соблазн велик, но надо себя сдерживать. :)
                                                    +1
                                                    Статья отличная.
                                                      0
                                                      Речь идёт о алгоритме.
                                                        0
                                                        Спасибо, исправил. Осталось от старого варианта топика, где детально рассматривались еще более ужасные с точки зрения производительности способы — в частности, если делать getBytes в windows-1251, производительность падает до ~120000 строчек в секунду. Таким образом разброс между «самым худшим» и «самым лучшим» вариантом действительно начинает быть где-то в ~40 раз, но я посчитал, что приводить тучу вариантов с заведомо худшими результатами не стоит — и так много получилось — ограничился их упоминаниями %)
                                                      • UFO just landed and posted this here
                                                          +3
                                                          Такое ощущение, что вы не читали текста.
                                                          Эта проблема применима даже к ассемблеру.
                                                          • UFO just landed and posted this here
                                                              +1
                                                              Очень мало есть в жизни по-настоящему критичных вещей.
                                                              Топик как раз о том, что «и из пустой бутылки водки можно при желании выжать еще десять-двенадцать капель». Делать это или не делать — решает каждый сам исходя из собственных соображений.
                                                              • UFO just landed and posted this here
                                                                +2
                                                                Опять-же, лучше надо читать.
                                                                Это обычное такое бутылочное горлышка, и обычная такая оптимизация. Если речь идет о скорости — скорее всего таких встретится далеко не одно.

                                                                Если же говорить о конкретно этой проблеме:

                                                                Изначальный вариант был коряв в том плане, что регэксп не компилировался. Это — большая и очевидная ошибка программиста.

                                                                Второй момент, на который стоит обратить внимание — то, что мы делаем не обычную замену, а замену на подстроку, которая по размерам не превосходит заменяемой подстроки. Казалось бы, разница не велика, но это позволяет хорошо экономить на преаллокации(А если можно работать деструктивно, то мы можем вообще не преаллоцировать, а переписывать инплэйс.). На мой взгляд, в библиотеки стоило бы ввести стандартные функции замены на меньшую подстроку и замены на пустую строку. Это хорошая оптимизация, но для каждого конкретного случая писать такую функцию — немного оверкилл. Так что, как я уже сказал, я считаю, что такие должны быть в стандартных библиотеках.

                                                                Ну и последнее — это, собственно, использование регэкспов. Тут все зависит от окружениях. На многих виртуальных машинах регэкспы легко переплевывают всякие хитрые махинации с байтами. Если говорить конкретно о C++, то регэксп не получает никаких преимуществ по сравнению с вашим собственном кодом и врядли найдутся случаи, где такие простые обработки строк регэкспами будут быстрее, чем самописный вариант(даже в случае достаточно кривых рук). Но тут, опять-же, стоит подумать о том, что простых обработок строк не так уж и много, так что по-хорошему это пишется один раз, кладется в библиотеку и потом радостно используется.
                                                                  0
                                                                  Я сильно не соглашусь в том, что некэширующийся скомпилированный вариант регэкспа — это *ошибка*. У первого варианта — собственно, почему я его показал и показал всякие другие варианты — есть один огромный плюс — он очень читаемый и занимает всего одну строчку. Любому программисту, хоть немножко знакомого с Java, или вообще любому программиста, представляющему в общих чертах регэкспы и знающего 2 английских слова «replace» и «all», можно показать этот код и он поймет, что там происходит. Этот код быстро писать, его быстро читать, он занимает мало места и понятен. Его абсолютно не жалко выкинуть и заменить на что-то совсем другое. Я всеми руками за такой код — до тех пор, пока это не критично с точки зрения производительности.

                                                                  Рассуждения про строки и регэкспы — я с вами соглашусь, но, к сожалению, эти рассуждения более относятся к C/C++, нежели к managed языкам. В подавляющем большинстве современных фреймворков (Java-based, .NET-based, практически во всех скриптовых языках) строки — immutable объекты. Соответственно, они обычно банально инкапсулируют что-то типа вектора целых чисел и доступ к внутренностям этого вектора для внешних классов сознательно очень сильно ограничен. Весь смысл топика — показать то, как можно используя «мягкие» операции доступа до внутренностей этого вектора пытаться писать эффективные алгоритмы. Для того же .NET, например, результат может быть прямо противоположный (хотя альтернативы по сути очень похожие) — может быть там действительно регэкспы дадут наилучшую производительность.
                                                                    0
                                                                    Разницы между компиляцией регэкспа и использованиеем, и реплэйс олл — 1 строка. В первом случае четко прослеживается логика, во втором нет (Для меня replaceAll неочевидна, я от такой функции ожидаю строковую замену, а не регэксповую.).

                                                                    Наверное, это в некоторой степени вопрос предпочтений, но если код не для тулзы на 2 раза, использование регэкспов без прекомпиляции в циклах считал и буду считать ошибкой. Конечно, не всегда это сильно влияет на скорость исоплнения, но не вижу никаких причин искусственно замедлять софт, пусть даже и лишь на десяток миллисекунд(которые, кстати, из-за количества запусков могут вылиться в достаточно продолжительные промежутки времени). В этом вопросе я заодно с пользователями — чем быстрее работает софт, тем лучше.
                                                                      0
                                                                      Ну, на самом деле 1 против 3, плюс одна из этих строчек должна быть вынесена куда-то сильно далеко от кода — как правило, на уровень статических переменных или конструктора. И в туче языков и фреймворков — константный регэксп найдется на этапе компиляции и будет вынесен за скобки автоматически — так что ручная его прекомпиляция не даст фактически ничего.

                                                                      Вот пример для perl:

                                                                      use Benchmark qw(:all);
                                                                      $precomp = qr/([0-9]+)/;
                                                                      cmpthese(1000000, {
                                                                      	'simple' => sub { 'Sample 123 numbers' =~ /([0-9]+)/; },
                                                                      	'precompiled' => sub { 'Sample 123 numbers' =~ $precomp; },
                                                                      });
                                                                      


                                                                      Если не знать, что он выдаст — то результаты, скорее всего, будут прямо противоположные тому, что можно было подумать. Так что да — скорее вопрос предпочтений.

                                                                      А пользователи — это такие странные зверьки. Им зачастую надо не «чем быстрее, тем лучше», а «чем раньше, тем лучше», «подешевле», «попроще» и т.п.
                                                                      +1
                                                                      А относительно фреймворков, я написал же, «Тут все зависит от окружениях. На многих виртуальных машинах регэкспы легко переплевывают всякие хитрые махинации с байтами.»
                                                                        0
                                                                        Вот, собственно, абсолютно согласен — поэтому считаю нужным и правильным вариант с регэкспами не отбрасывать, а вполне себе иметь в виду и просто проверить. И *если* он медленный — тогда уже отказываться.
                                                                    0
                                                                    Это *нигде* не является критичным, до тех пор, пока это не жмет. А вот если программа начинает показывать неудовлетворительную производительность и кто-то с профайлером в руках не доказал, что проблема именно в одной этой строчке — то имеет смысл оптимизировать.

                                                                    Если же это не так — то решение в одну строчку всегда априори лучше, читабельнее, понятнее, не-жалко-выкинуть и т.д., чем весьма долбанутое решение на двадцать строчек.
                                                                +1
                                                                Автор, как заметили выше, прогоните на вашем наборе тестов вариант оптимизации

                                                                if (ch >= ' ') {
                                                                    if (newLen != j) {
                                                                        oldChars[newLen] = ch;
                                                                    }
                                                                    newLen++;
                                                                }
                                                                


                                                                У меня вроде получается быстрее. На строках не содержащих управляющих символов таким образом убирается бессмысленное копирование oldChars[x] = oldChars[x]
                                                                  +1
                                                                  это полезно только до первого управляющего символа иначе получается лишняя проверка, поэтому имеет смысл разбить на 2 отдельных цикла — пример выше.
                                                                  +1
                                                                  «Потокобезопасный» вариант сделать довольно просто. Весь алгоритм выносится в отдельный объект, и буфер создается внутри объекта.
                                                                  class Algoritm{
                                                                    public char[] buf = new char[1024];
                                                                    String run(String s){
                                                                  ...
                                                                  

                                                                  Если в каждом потоке создавать свой объект алгоритма и передавать строки в него, то они прекрасно распараллелятся.
                                                                  И ещё небольшое ускорение. Если строка оказалась длиннее массива, то новый массив можно сохранить для следующих вызовов. И если снова попадется более длинная строка, то память выделять уже не придётся.
                                                                  ...
                                                                  if(length > 1024)
                                                                    buf = new char[length];
                                                                  char[] oldChars = buf;
                                                                  ...
                                                                    0
                                                                    Как сделать thread-safe вариант — в целом-то понятно, вариантов много.

                                                                    Про сохранение длинного буфера — тогда уж так:
                                                                    ...
                                                                    if (length > buf.length)
                                                                        buf = new char[length];
                                                                    ...
                                                                    

                                                                    и дальше вообще работать только с buf, не вспоминая какой-то второй oldChars.
                                                                    0
                                                                    Встроенные Java regexps, во-первых, имеют долбанутый API (подстрекая тем самым излишне часто компилировать одни и те же выражения), во-вторых, достаточно медленны на таких простых операциях; впрочем, о том, что встроенные Java regexps медленные
                                                                    регэкспы мадленные не в Ява, а сами по себе, будь то РНР или С… например, для усокрения регэкспов придуманы всякие кодогенераторы, типа habrahabr.ru/blogs/regex/117843/ или
                                                                      0
                                                                      Регэкспы медленные не сами по себе (сами по себе регулярные выражения, будучи регулярными, обрабатываются детерминированными конечными автоматами, про оптимизацию и быстрое выполнение которых написаны многие тонны литературы). И для Java, и для C, и, я догадываюсь, для практически всего, что угодно, вполне можно сделать быстрый движок — разумеется, в первую очередь за счет куда большего объема памяти и времени компиляции регулярного выражения.

                                                                      То, что вы показали «для ускорения» — по сути и есть довольно банальный компилятор регэкспа сразу в C-код. Если уж говорить о сверхскорострельных регэкспах — то рекомендую посмотреть Pire — такая сверхоптимизированная C-библиотека, позволяет добиваться скоростей в сотни мегабайт в секунду.

                                                                      Если говорить о Java — то, опять же, если верить приведенной выше ссылке — 6556ms на Sun-овской реализации из стандартных библиотек легко сокращаются до 11ms (т.е. становится в ~600 раз быстрее) при использовании библиотек gnu.rex.Rex.
                                                                      0
                                                                      на Си задача решилась бы просто и малой кровью,
                                                                      то что можно распараллелить и на этом выиграть — ежу понятно.
                                                                      наверняка есть бинд из Java в Си (раньше, когда я изучал Java он был).

                                                                      так что, если надо — пишем небольшую Сишную программульку и вызываем ее из Java
                                                                      Прирост производительности будет еще больше :) раза в три по сравнению с последним вариантом

                                                                      я не Java программист, а РНРник. но если мне нужны производительные вычисления,
                                                                      или какая-то хитрая функция, то я их всегда реализую на С и вызываю это из языка более высокого уровня.
                                                                        0
                                                                        Прочитайте топик, пожалуйста? И про параллелизацию, и про «давайте сделаем все на JNI» (это и есть упомянутый вами «бинд из Java в Си») — там всё есть. И речь как раз о том, что можно сделать не прибегая к такому ядерному оружию.

                                                                        Есть, кстати, еще один забавный вариант — почему-то про него никто не сказал, хотя он тоже как бы нелегитимен — можно с помощью reflection лазать во внутренние структуры Java, в том числе получить доступ к полю value объекта String — который и есть искомый char[].
                                                                          +1
                                                                          Кстати не факт что вызов getChars выделение массива чаров и конструирование новой строки будет медленней чем игры с рефлекшн
                                                                            +1
                                                                            Более того, этот вариант совсем не подходит. Посмотрите на конструктор копирования строк (public String(String original)) — он по возможности пытается использовать внутренний value строки параметра, т.е. нарушая контракт string-immutable можно очень интересные баги получить.
                                                                              0
                                                                              Разумеется, можно. Разумеется, этим надо пользоваться очень аккуратно — он там не зря сделан immutable и private %) Но ускорение оно дает.

                                                                              Мой предыдущий ответ почему-то сюда ушел, извиняюсь.
                                                                          0
                                                                          Я уже подумываю на самом деле еще один топик написать с такими «запрещенными» приемами. Игры с reflection дают еще ~+30% производительности. Реализация на JNI дает на самом деле тоже рост от 50 до 100%… И т.д.
                                                                            0
                                                                            Пишите, только не забудьте прогнать те варианты, которые были в этом топике. Даже самые наркоманские.
                                                                            0
                                                                            Возможно, будет еще немного быстрее, если не копировать массив символов (getChars на самом деле вызвает System.arraycopy), а использовать String.charAt()

                                                                            Еще быстрее нужно — меняйте архитектуру. Почему у вас передаются строки, а не массивы символов? Или хотя бы Stream-ы.
                                                                              0
                                                                              Это был «вариант номер 5», на самом деле. Я тут все-таки взял все предложенные варианты, перемерял еще раз в нескольких режимах и думаю еще одну статью с более детальными исследованиями, цифрами и графиками сделать…
                                                                                0
                                                                                Да, Вы правы про charAt.

                                                                                И все же, почему String? Почему не char[] или не Reader? Ведь, по сути, вы свели весь функционал String-а к хранению массива символов.

                                                                                В целом, «правильным» было бы реализовать подкласс FilterReader и фильтровать символы в нем. Оно будет медленнее C-style решения, но универсальней. Понятно, что все зависит от задачи и выбранной архитектуры.
                                                                                  0
                                                                                  Потому что эта функциональность — лишь маленькая часть огромного комплекса. В той же парадигме кроме этой задачи работают еще сотня-другая других задач — в том числе с совершенно другими алгоритмами и сложностями. Да даже в этой задаче, кроме собственно фильтрации выходного потока (что, кстати, тоже само по себе не так тривиально — в выходном потоке там набор объектов, среди которых *иногда* встречаются String, которые надо фильтровать, иногда встречаются примитивы типа int / double, которые надо выводить как есть, а иногда — всякие другие сложные объекты типа tuples / maps, которые надо выводить еще сложнее.

                                                                                  Если говорить о «концах» этой задаче — т.е. «читалке» и «писалке» — то, зря в корень, читалка «читает» именно String, а не char[] и не byte[], потому что в исходном потоке приходит именно String. Может прийти и char[], но в этом случае на выходе он будет обработан еще более банально и просто (hex dump'ом). А посередине может быть алгоритм, который захочет этому String сделать какую-то именно строковую операцию, характерную для этого класса…

                                                                            Only users with full accounts can post comments. Log in, please.