Как ухудшить производительность, улучшая её

    Хотели как лучше, а получилось как всегда.
    Виктор Черномырдин,
    русский государственный деятель


    Бывают в жизни случаи, когда ты вроде бы всё делаешь правильно, но что-то идёт не так.
    Этот рассказ об одном из таких случаев.


    Однажды я смотрел на этот код и думал о его ускорении:


    public String appendBounds(Data data) {
      int beginIndex = data.beginIndex;
      int endIndex = data.endIndex;
    
      return new StringBuilder()
              .append('L')
              .append(data.str, beginIndex, endIndex)
              .append(';')
              .toString();
    }

    Сперва я хотел вычислять итоговую длину строки, используя переменные beginIndex и endIndex (а также тот факт, что кроме урезанной строки к StringBuilder-у будет добавлено ещё 2 знака), и передавать это значение в конструктор StringBuilder-а, чтобы сразу выделить массив нужного размера. Эта мысль показалась мне чересчур очевидной, поэтому я решил испробовать что-то ещё. К верной мысли меня подтолкнуло то обстоятельство, что данный код никак не подсвечивался "Идеей", хотя эта умница обычно предлагает заменить короткую цепочку из StringBuilder::append на сложение строк, что короче и легче воспринимается.


    Помехой для подобного упрощения является использование метода StringBuilder.append(CharSequence, int, int). Учитывая, что поле data.str является строкой, с помощью String.substring(beginIndex, endIndex) можно выделить из неё подстроку и передать методу StringBuilder.append(String).


    Код после преобразования:


    public String appendBounds(Data data) {
      int beginIndex = data.beginIndex;
      int endIndex = data.endIndex;
    
      String subString = data.str.substring(beginIndex, endIndex);
    
      return new StringBuilder()
              .append('L')
              .append(subString)
              .append(';')
              .toString();
    }

    И вот теперь "Идея" предлагает упрощение:


    public String appendBounds(Data data) {
      int beginIndex = data.beginIndex;
      int endIndex = data.endIndex;
    
      return 'L' + data.str.substring(beginIndex, endIndex) + ';';
    }

    Однако, нашей целью в данном случае является не столько читаемость, сколько производительность. Сравним оба способа:


    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @Fork(jvmArgsAppend = {"-Xms2g", "-Xmx2g"})
    public class StringBuilderAppendBenchmark {
    
      @Benchmark
      public String appendSubString(Data data) {
        String latinStr = data.latinStr;
        String nonLatinStr = data.nonLatinStr;
        int beginIndex = data.beginIndex;
        int endIndex = data.endIndex;
    
        String substring = data.nonLatin ?
                nonLatinStr.substring(beginIndex, endIndex) :
                latinStr.substring(beginIndex, endIndex);
    
        return new StringBuilder()
                .append('L')
                .append(substring)
                .append(';')
                .toString();
      }
    
      @Benchmark
      public String appendBounds(Data data) {
        String latinStr = data.latinStr;
        String nonLatinStr = data.nonLatinStr;
        int beginIndex = data.beginIndex;
        int endIndex = data.endIndex;
    
        String appended = data.nonLatin ? nonLatinStr : latinStr;
    
        return new StringBuilder()
                .append('L')
                .append(appended, beginIndex, endIndex)
                .append(';')
                .toString();
      }
    
      @State(Scope.Thread)
      public static class Data {
        String latinStr;
        String nonLatinStr;
    
        @Param({"true", "false"})
        boolean nonLatin;
    
        @Param({"5", "10", "50", "100", "500", "1000"})
        private int length;
    
        private int beginIndex;
        private int endIndex;
    
        private ThreadLocalRandom random = ThreadLocalRandom.current();
    
        @Setup
        public void setup() {
          latinStr = randomString("abcdefghijklmnopqrstuvwxyz");
          nonLatinStr = randomString("абвгдеёжзиклмнопрстуфхцчшщьыъэюя");
          beginIndex = 1;
          endIndex = length + 1;
        }
    
        private String randomString(String alphabet) {
          char[] chars = alphabet.toCharArray();
    
          StringBuilder sb = new StringBuilder(length + 2);
          for (int i = 0; i < length + 2; i++) {
            char c = chars[random.nextInt(chars.length)];
            sb.append(c);
          }
    
          return sb.toString();
        }
      }
    }

    Бенчмарк прост как две копейки: к StringBuilder-у добавляется случайная строка, размер которой определяется полем length, а поскольку на дворе 2019 год, то проверять нужно как строку, содержащую только знаки основной латиницы (т. н. сжатая строка, в которой каждому знаку соответствует 1 байт), так и строку с нелатинскими знаками (каждый символ представлен 2 байтами).


    При поверхностном рассмотрении метод appendSubString представляется нам более медленным, ибо объём приклеиваемых данных совпадает с таковым в методе appendBounds, однако в методе appendSubString есть ещё и явное создание подстроки, т. е. выделение памяти на новый объект и копирование в него содержимого из data.latinStr / data.nonLatinStr.


    Тем более удивительными (но только на первый взгляд) кажутся итоги измерения, выполненного мной с помощью JDK11 на домашней машине (Intel Core i5-4690, 3.50 ГГц):


    Benchmark                           nonLatin   length     Score   Error   Units
    appendBounds                            true        5      44,6 ±   0,4   ns/op
    appendBounds                            true       10      45,7 ±   0,7   ns/op
    appendBounds                            true       50     129,0 ±   0,5   ns/op
    appendBounds                            true      100     218,7 ±   0,8   ns/op
    appendBounds                            true      500     907,1 ±   5,5   ns/op
    appendBounds                            true     1000    1626,4 ±  13,0   ns/op
    
    appendSubString                         true        5      28,6 ±   0,2   ns/op
    appendSubString                         true       10      30,8 ±   0,2   ns/op
    appendSubString                         true       50      65,6 ±   0,4   ns/op
    appendSubString                         true      100     106,6 ±   0,6   ns/op
    appendSubString                         true      500     430,1 ±   2,4   ns/op
    appendSubString                         true     1000     839,1 ±   8,6   ns/op
    
    appendBounds:·gc.alloc.rate.norm        true        5     184,0 ±   0,0    B/op
    appendBounds:·gc.alloc.rate.norm        true       10     200,0 ±   0,0    B/op
    appendBounds:·gc.alloc.rate.norm        true       50     688,0 ±   0,0    B/op
    appendBounds:·gc.alloc.rate.norm        true      100    1192,0 ±   0,0    B/op
    appendBounds:·gc.alloc.rate.norm        true      500    5192,0 ±   0,0    B/op
    appendBounds:·gc.alloc.rate.norm        true     1000   10200,0 ±   0,0    B/op
    
    appendSubString:·gc.alloc.rate.norm     true        5     136,0 ±   0,0    B/op
    appendSubString:·gc.alloc.rate.norm     true       10     160,0 ±   0,0    B/op
    appendSubString:·gc.alloc.rate.norm     true       50     360,0 ±   0,0    B/op
    appendSubString:·gc.alloc.rate.norm     true      100     608,0 ±   0,0    B/op
    appendSubString:·gc.alloc.rate.norm     true      500    2608,0 ±   0,0    B/op
    appendSubString:·gc.alloc.rate.norm     true     1000    5104,0 ±   0,0    B/op
    
    appendBounds                           false        5      20,8 ±   0,1   ns/op
    appendBounds                           false       10      24,0 ±   0,2   ns/op
    appendBounds                           false       50      66,4 ±   0,4   ns/op
    appendBounds                           false      100     111,0 ±   0,8   ns/op
    appendBounds                           false      500     419,2 ±   2,7   ns/op
    appendBounds                           false     1000     840,4 ±   7,8   ns/op
    
    appendSubString                        false        5      25,3 ±   0,3   ns/op
    appendSubString                        false       10      25,7 ±   0,2   ns/op
    appendSubString                        false       50      36,0 ±   0,1   ns/op
    appendSubString                        false      100      52,8 ±   0,4   ns/op
    appendSubString                        false      500     206,1 ±   6,1   ns/op
    appendSubString                        false     1000     388,1 ±   1,6   ns/op
    
    appendBounds:·gc.alloc.rate.norm       false        5      80,0 ±   0,0    B/op
    appendBounds:·gc.alloc.rate.norm       false       10      88,0 ±   0,0    B/op
    appendBounds:·gc.alloc.rate.norm       false       50     320,0 ±   0,0    B/op
    appendBounds:·gc.alloc.rate.norm       false      100     544,0 ±   0,0    B/op
    appendBounds:·gc.alloc.rate.norm       false      500    2144,0 ±   0,0    B/op
    appendBounds:·gc.alloc.rate.norm       false     1000    4152,0 ±   0,0    B/op
    
    appendSubString:·gc.alloc.rate.norm    false        5      96,0 ±   0,0    B/op
    appendSubString:·gc.alloc.rate.norm    false       10     112,0 ±   0,0    B/op
    appendSubString:·gc.alloc.rate.norm    false       50     192,0 ±   0,0    B/op
    appendSubString:·gc.alloc.rate.norm    false      100     288,0 ±   0,0    B/op
    appendSubString:·gc.alloc.rate.norm    false      500    1088,0 ±   0,0    B/op
    appendSubString:·gc.alloc.rate.norm    false     1000    2088,0 ±   0,0    B/op

    Опровергая наше предположение метод appendSubString в подавляющем большинстве случаев (в т. ч. всегда для нелатинских строк) оказался и более быстрым, и менее прожорливым (и это при том, что String::substring возвращает новый объект). Как же так получилось?


    Смотрю в книгу, вижу фигу


    Приподнять завесу тайны поможет изучение исходного кода StringBuilder-а. Оба используемых метода передают вызов в такие же методы AbstractStringBuilder-а:


    public final class StringBuilder
        extends AbstractStringBuilder
        implements java.io.Serializable, Comparable<StringBuilder>, CharSequence {
    
      @Override
      public StringBuilder append(String str) {
        super.append(str);
        return this;
      }
    
      @Override
      public StringBuilder append(CharSequence s, int start, int end) {
        super.append(s, start, end);
        return this;
      }
    }

    Переходим к AbstractStringBuilder.append(String):


    public AbstractStringBuilder append(String str) {
      if (str == null) {
        return appendNull();
      }
      int len = str.length();
      ensureCapacityInternal(count + len);
      putStringAt(count, str);
      count += len;
      return this;
    }
    
    private final void putStringAt(int index, String str) {
      if (getCoder() != str.coder()) {
        inflate();
      }
      str.getBytes(value, index, coder);
    }

    Что здесь интересно? Метод AbstractStringBuilder::inflate, как следует из названия, расширяет массив AbstractStringBuilder.value при объединении разнородных строк. Перемещение же данных происходит в методе String::getBytes:


    void getBytes(byte[] dst, int dstBegin, byte coder) {
      if (coder() == coder) {
        System.arraycopy(value, 0, dst, dstBegin << coder, value.length);
      } else {    // this.coder == LATIN && coder == UTF16
        StringLatin1.inflate(value, 0, dst, dstBegin, value.length);
      }
    }

    Что важно? Если строки однородны, то для перемещения данных используется интринсифицированный System::arraycopy, в противоположном случае — StringLatin1::inflate, которые через делегирование приводит нас к методу StringUTF16::inflate:


    // inflatedCopy byte[] -> byte[]
    @HotSpotIntrinsicCandidate
    public static void inflate(byte[] src, int srcOff, byte[] dst, int dstOff, int len) {
      // We need a range check here because 'putChar' has no checks
      checkBoundsOffCount(dstOff, len, dst);
      for (int i = 0; i < len; i++) {
        putChar(dst, dstOff++, src[srcOff++] & 0xff);
      }
    }
    
    @HotSpotIntrinsicCandidate
    static void putChar(byte[] val, int index, int c) {
      assert index >= 0 && index < length(val) : "Trusted caller missed bounds check";
      index <<= 1;
      val[index++] = (byte)(c >> HI_BYTE_SHIFT);
      val[index]   = (byte)(c >> LO_BYTE_SHIFT);
    }

    Таким образом, если строки однородны, то для перемещения данных используется платформенно-зависимый метод System::arraycopy, в противном случае — цикл (тоже интринсифицированный). Это означает, что при склеивании двух строк, где все знаки входят в множество основной латиницы (проще говоря умещаются в 1 байт), производительность должна быть значительно лучше, чем при склеивании разнородных строк. Бенчмарк это подтверждает (см. вывод для nonLatin = false).


    Теперь метод AbstractStringBuilder.append(CharSequence, int, int):


    @Override
    public AbstractStringBuilder append(CharSequence s, int start, int end) {
      if (s == null) {
        s = "null";
      }
      checkRange(start, end, s.length());
      int len = end - start;
      ensureCapacityInternal(count + len);
      appendChars(s, start, end);
      return this;
    }
    
    private final void appendChars(CharSequence s, int off, int end) {
      if (isLatin1()) {
        byte[] val = this.value;
        for (int i = off, j = count; i < end; i++) {
          char c = s.charAt(i);
          if (StringLatin1.canEncode(c)) {
            val[j++] = (byte)c;
          } else {
            count = j;
            inflate();
            StringUTF16.putCharsSB(this.value, j, s, i, end);
            count += end - i;
            return;
          }
        }
      } else {
        StringUTF16.putCharsSB(this.value, count, s, off, end);
      }
      count += end - off;
    }

    Здесь подход схож с существующим в предыдущем примере: для однородных строк используется более простой механизм (тут — познаковое копирование в цикле), для разнородных — обращение к StringUTF16, однако обратите внимание, что вызываемый метод StringUTF16::putCharsSB не интринсифицирован.


    public static void putCharsSB(byte[] val, int index, CharSequence s, int off, int end) {
        checkBoundsBeginEnd(index, index + end - off, val);
        for (int i = off; i < end; i++) {
            putChar(val, index++, s.charAt(i));
        }
    }

    Итак, внутреннее устройство обоих методов и причина их разной производительности для нас более-менее понятны. Закономерно возникает вопрос — что делать с полученным знанием дальше? Есть сразу несколько вариантов:


    1) держать это в голове и при обнаружении подозрительного кода менять его руками
    2) сходить к Тагиру и попросить его запилить проверку, которая будет делать работу вместо нас
    3) внести изменения в JDK с тем, чтобы код вообще не менять.


    Разумеется, начнём мы с третьего. Готовы рискнуть?


    Погружение в пучину


    Тренироваться будем на кошках на исходниках одинадцатой явы, скачать можно здесь.


    Наиболее простой и очевидный способ улучшения — выделять подстроку уже внутри метода AbstractStringBuilder.append(CharSequence, int, int):


    // было
    public AbstractStringBuilder append(CharSequence s, int start, int end) {
      if (s == null) {
        s = "null";
      }
      checkRange(start, end, s.length());
      int len = end - start;
      ensureCapacityInternal(count + len);
      appendChars(s, start, end);
      return this;
    }
    
    // стало
    public AbstractStringBuilder append(CharSequence s, int start, int end) {
        if (s == null) {
            s = "null";
        }
        checkRange(start, end, s.length());
        return append(s.subSequence(start, end).toString());
    }

    Теперь нужно собрать JDK, прогнать тесты и запустить на нём бенчмарк StringBuilderAppendBenchmark::appendBounds, результаты которого нужно сопоставить с результатами этого же бенчмарка на исходном JDK:


    # здесь колонка before содержит данные прогона на исходном JDK,
    # after - на изменённом
    
    Benchmark           nonLatin  length     before      after    Units
    
    avgt                    true       5       44,6       64,4    ns/op
    avgt                    true      10       45,7       66,3    ns/op
    avgt                    true      50      129,0      168,9    ns/op
    avgt                    true     100      218,7      281,9    ns/op
    avgt                    true     500      907,1     1116,2    ns/op
    avgt                    true    1000     1626,4     2002,5    ns/op
    
    gc.alloc.rate.norm      true       5      184,0      264,0     B/op
    gc.alloc.rate.norm      true      10      200,0      296,0     B/op
    gc.alloc.rate.norm      true      50      688,0      904,0     B/op
    gc.alloc.rate.norm      true     100     1192,0     1552,0     B/op
    gc.alloc.rate.norm      true     500     5192,0     6752,0     B/op
    gc.alloc.rate.norm      true    1000    10200,0    13256,0     B/op
    
    avgt                   false       5       20,8       38,0    ns/op
    avgt                   false      10       24,0       37,8    ns/op
    avgt                   false      50       66,4       82,9    ns/op
    avgt                   false     100      111,0      138,8    ns/op
    avgt                   false     500      419,2      531,9    ns/op
    avgt                   false    1000      840,4     1002,7    ns/op
    
    gc.alloc.rate.norm     false       5       80,0      152,0     B/op
    gc.alloc.rate.norm     false      10       88,0      168,0     B/op
    gc.alloc.rate.norm     false      50      320,0      440,0     B/op
    gc.alloc.rate.norm     false     100      544,0      688,0     B/op
    gc.alloc.rate.norm     false     500     2144,0     2688,0     B/op
    gc.alloc.rate.norm     false    1000     4152,0     5192,0     B/op

    Что называется, внезапно! Улучшения не только не произошло, но произошло ухудшение. Чёрт возьми, но как?


    Дело в том, что в самом начале, в описании метода StringBuilder::append я сделал одно небольшое, но критически важное упущение. Метод был описан вот так:


    public final class StringBuilder {
      @Override
      public StringBuilder append(String str) {
        super.append(str);
        return this;
      }
    }

    А вот его полный вид:


    public final class StringBuilder {
      @Override
      @HotSpotIntrinsicCandidate
      public StringBuilder append(String str) {
        super.append(str);
        return this;
      }
    }

    Ява-код, который мы рассматривали выше, будучи разогретым и скомпилированным на уровне С2, не имеет никакого значения, т. к. исполняется не он, а интринсик. Это легко доказать, сняв профиль используя async-profiler. Здесь и далее профиль снимается для length = 1000 и nonLatin = true:


    # профиль метода `appendSubString`, JDK без наших изменений
    
              ns  percent  samples  top
      ----------  -------  -------  ---
     19096340914   43.57%  1897673  jbyte_disjoint_arraycopy   <---------
     13500185356   30.80%  1343343  jshort_disjoint_arraycopy  <---------
      4124818581    9.41%   409533  java.lang.String.<init>           # создание подстроки
      2177311938    4.97%   216375  java.lang.StringUTF16.compress    # создание подстроки
      1557269661    3.55%   154253  java.util.Arrays.copyOfRange      # создание подстроки
       349344451    0.80%    34823  appendSubString_avgt_jmhStub
       279803769    0.64%    27862  java.lang.StringUTF16.newString
       274388920    0.63%    27312  org.openjdk.jmh.infra.Blackhole.consume
       160962540    0.37%    15946  SpinPause
       122418222    0.28%    11795  __memset_avx2

    Кодом StringBuilder-а (да и AbstractStringBuilder-а ) тут даже не пахнет, почти 3/4 профиля занимает интринсик. Примерно такую же картину хотелось бы наблюдать в профиле "улучшенного" нами StringBuilder.append(CharSequence, int, int).


    В действительности имеем вот это:


              ns  percent  samples  top
      ----------  -------  -------  ---
     19071221451   43.78%  1897827  jbyte_disjoint_arraycopy
      6409223440   14.71%   638348  jlong_disjoint_arraycopy
      3933622128    9.03%   387403  java.lang.StringUTF16.newBytesFor
      2067248311    4.75%   204193  java.lang.AbstractStringBuilder.ensureCapacityInternal
      1929218737    4.43%   194751  java.lang.StringUTF16.compress
      1678321343    3.85%   166458  java.util.Arrays.copyOfRange
      1621470408    3.72%   160849  java.lang.String.checkIndex
       969180099    2.22%    96018  java.util.Arrays.copyOf
       581600786    1.34%    57818  java.lang.AbstractStringBuilder.<init>
       417818533    0.96%    41611  appendBounds_jmhTest
       406565329    0.93%    40479  java.lang.String.<init>
       340972882    0.78%    33727  java.lang.AbstractStringBuilder.append
       299895915    0.69%    29982  java.lang.StringBuilder.toString
       183885595    0.42%    18136  SpinPause
       168666033    0.39%    16755  org.openjdk.jmh.infra.Blackhole.consume

    Вы скажете: "Вот же они, интринсики, в самом верху!" Действительно, только это немного не те интринсики (в т. ч. сравните имя второго сверху). Вспомним:


    public final class StringBuilder {
      @Override
      @HotSpotIntrinsicCandidate
      public StringBuilder append(String str) {
        super.append(str);
        return this;
      }
    }

    Здесь интринсик подменяет вызов StringBuilder.append(String), но в нашем-то патче этого вызова нет! Вызывается AbstractStringBuilder.append(String). Наблюдаемый нами вызов jbyte_disjoint_arraycopy — это интринсик для StringLatin1::inflate, вызываемого из AbstractStringBuider::putStringAt через String::getBytes. Т. е. в отличии от StringBuilder::append отрабатывает не только платформенно-зависимый, но и ява-код,


    С причиной провала разобрались, попробуем добиться успеха иначе. Несложно догадаться, что нам необходимо каким-то образом обратиться именно к StringBuilder::append. Сделать это можно оторвав предыдущую заплатку и внеся изменения в сам StringBuilder:


    public final class StringBuilder {
      // было
      @Override
      public StringBuilder append(CharSequence s, int start, int end) {
        super.append(s, start, end);
        return this;
      }
      // стало
      @Override
      public StringBuilder append(CharSequence s, int start, int end) {
        if (s == null) {
          s = "null";
        }
        checkRange(start, end, s.length());
        return this.append(s.subSequence(start, end).toString());
      }
    }

    Вот теперь всё сделано по уму: вызывается интринсифицированный StringBuilder::append.
    Пересобираем, запускаем, сравниваем:


    # здесь колонка before содержит данные прогона на исходном JDK,
    # after - на изменённом
    
    Benchmark             nonLatin   length    before     after   Units
    
    avgt                      true        5      44,6      60,2   ns/op
    avgt                      true       10      45,7      59,1   ns/op
    avgt                      true       50     129,0     164,6   ns/op
    avgt                      true      100     218,7     276,2   ns/op
    avgt                      true      500     907,1    1088,8   ns/op
    avgt                      true     1000    1626,4    1959,4   ns/op
    
    gc.alloc.rate.norm        true        5     184,0     264,0    B/op
    gc.alloc.rate.norm        true       10     200,0     296,0    B/op
    gc.alloc.rate.norm        true       50     688,0     904,0    B/op
    gc.alloc.rate.norm        true      100    1192,0    1552,0    B/op
    gc.alloc.rate.norm        true      500    5192,0    6752,0    B/op
    gc.alloc.rate.norm        true     1000   10200,0   13256,0    B/op
    
    avgt                     false        5      20,8      37,9   ns/op
    avgt                     false       10      24,0      37,9   ns/op
    avgt                     false       50      66,4      80,9   ns/op
    avgt                     false      100     111,0     125,6   ns/op
    avgt                     false      500     419,2     483,6   ns/op
    avgt                     false     1000     840,4     893,8   ns/op
    
    gc.alloc.rate.norm       false        5      80,0     152,0    B/op
    gc.alloc.rate.norm       false       10      88,0     168,0    B/op
    gc.alloc.rate.norm       false       50     320,0     440,0    B/op
    gc.alloc.rate.norm       false      100     544,0     688,0    B/op
    gc.alloc.rate.norm       false      500    2144,0    2688,0    B/op
    gc.alloc.rate.norm       false     1000    4152,0    5187,2    B/op
    

    Мне, право, очень грустно, но лучше не стало. Теперь новый профиль:


              ns  percent  samples  top
      ----------  -------  -------  ---
     19614374885   44.12%  1953620  jbyte_disjoint_arraycopy
      6645299702   14.95%   662146  jlong_disjoint_arraycopy
      4065789919    9.15%   400167  java.lang.StringUTF16.newBytesFor
      2374627822    5.34%   234746  java.lang.AbstractStringBuilder.ensureCapacityInternal
      1837858014    4.13%   183822  java.lang.StringUTF16.compress
      1472039604    3.31%   145956  java.util.Arrays.copyOfRange
      1316397864    2.96%   130747  appendBounds_jmhTest
       956823151    2.15%    94959  java.util.Arrays.copyOf
       573091712    1.29%    56933  java.lang.AbstractStringBuilder.<init>
       434454076    0.98%    43202  java.lang.String.<init>
       368480388    0.83%    36439  java.lang.AbstractStringBuilder.append
       304409057    0.68%    30442  java.lang.StringBuilder.toString
       272437989    0.61%    26833  SpinPause
       201051696    0.45%    19985  java.lang.StringBuilder.<init>
       198934052    0.45%    19810  appendBounds_avgt_jmhStub

    Мало что изменилось. Для меня остаётся непонятным, почему интринсик не сработал при обращении к StringBuilder.append(String) изнутри StringBuilder-а. Есть подозрение, что вклеивание (инлайнинг) тела метода StringBuilder.append(String) в тело StringBuilder.append(CharSequence, int, int) что-то меняет в обработке ВМ обращений к методам.


    Как бы там ни было, это фиаско, братан. Подлатать JDK не удалось, но мы по прежнему можем делать замену вручную там, где это имеет смысл.


    Литературное отступление о неудачах
    Ответная шифровка пришла через два дня. Навигатору совсем не хочется расставаться с «Ото Велара», с фирмой, которая строит удивительно быстрые и мощные военные корабли. Навигатору не хочется читать шифровку мне. Он просто повторяет ответ командного пункта: «Нет». Шифровка не разъясняет, почему «нет». «Нет» в любом случае означает, что он –личность известная большому компьютеру. Если бы о нем ничего не было известно, то ответ был бы положительным: пробуйте. Жаль. Жаль такого, интересного человека терять. А командиру, наверное, жаль меня. Может быть, первый раз жаль. Он видит, что я рвусь в варяги. И ему совсем не хочется вновь толкать меня в борзые.
    Он молчит. Но я-то знаю, что в обеспечении дикая нехватка рабочих рук:
    — Я, товарищ генерал, завтра в обеспечении работаю. Разрешите идти?
    — Иди. — И вдруг улыбается. — Ты знаешь, нет худа без добра.
    — У меня, товарищ генерал, всегда худо без добра.
    — А вот и нет. Тебе запретили его встречать, это плохо. Но к сокровищам нашего опыта мы добавили еще одну крупицу.

    Выводы:


    • код методов JDK в некоторых случаях не имеет отношения к настоящему исполнению, т. к. вместо тела метода может выполнится интринсик, который укрыт в недрах ВМ.
    • подобные методы можно распознать, в частности на них указывает метка @HotSpotIntrinsicCandidate, хотя некоторые методы интринсифицированы без каких бы то ни было намёков, например String::equalsмногие-многие другие).
    • вывод, проистекающий из первых двух, — наши рассуждения о том, как работает код JDK могут противоречить действительности. C'est la vie

    P. S.
    Другая возможная замена:


    StringBuilder sb = new StringBuilder();
    sb.append(str, 0, endIndex);
    // -->
    StringBuilder sb = new StringBuilder(str.substring(o, endIndex));

    P. P. S.
    Разработчики "Оракла" справедливо указывают, что


    It seems to me rather odd and surprising to introduce a code path into
    sb.append(cs,int,int) that allocates memory in order to get at an intrinsic that
    only sometimes makes things run faster. As you observed, the performance
    tradeoffs aren't obvious.

    Instead, if we want to optimize sb.append(cs,int,int) maybe we should just go
    ahead and do that, possibly by adding or rearranging the intrinsics.

    Предложенное решение — интринсификация StringBuilder.append(CharSequence, int, int).


    Задача
    Обсуждение


    P. P. S.
    Интересно, что в настоящий момент при написании чего-то вроде


    StringBuilder sb = new StringBuilder();
    sb.append(str.substring(0, endIndex));

    "Идея" предлагает упростить код до


    StringBuilder sb = new StringBuilder();
    sb.append(s, 0, endIndex);

    Если производительность именно в этом месте вам не очень важна, наверно более правильным будет использовать второй, упрощённый вариант. Всё-таки большую часть кода мы пишем для наших товарищей, а не для машин.

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 11

      +2
      Для меня остаётся непонятным, почему интринсик не сработал при обращении к StringBuilder.append(String)
      А это и не интринсик. По крайней мере, сам по себе. Только лишь в составе выражений вида
      new StringBuilder().append()...append().toString();

      JIT компилятор распознаёт подобные цепочки и транслирует их как единое целое. Называется OptimizeStringConcat. Про это уже писали и на Stack Overflow, и на Хабре.
        0

        Спасибо за ссылку, я упустил эту особенность. Интересно, почему тогда javac не превращает


        StringBuilder sb = new StringBuilder();
        sb.append(a1);
        sb.append(a2);
        sb.append(a3);
        sb.toString();

        в


        new StringBuilder().append(a1).append(a2).append(a3).toString();

        ещё на этапе компиляции исходного кода? Что мешает такому преобразованию?

          0
          Во-первых, это неэквивалентное преобразование. Во-вторых, javac — прямолинейный компилятор, оптимизации — не его задача.
            0

            Вы имеете ввиду неэквивалентность байт-кода? Поведение обоих методов, насколько я понимаю, одинаковое:


            String foo(String a1, String a2, String a3) {
              StringBuilder sb = new StringBuilder();
              sb.append(a1);
              sb.append(a2);
              sb.append(a3);
              return sb.toString();
            }
            
            String _foo(String a1, String a2, String a3) {
              return new StringBuilder()
                      .append(a1)
                      .append(a2)
                      .append(a3)
                      .toString();
            }
              +2
              Не совсем. Например, в первом случае есть переменная sb, которую можно найти по имени и посмотреть значение в дебаггере на середине выражения. А ещё код StringBuilder может быть инструментирован и вернуть внезапно не this.
                0

                Спасибо! Уже не первый год работаю, но не устаю удивляться, как много тонкостей стоит вроде бы за простым кодом.

        0

        Первое, что бросается в глаза — не указана capacity в конструкторе StringBuilder. Она известна, и если её указать, для выходных строк длиной >16 память под StringBuilder не будет выделяться лишний раз, и будет меньше нагрузка на gc.
        С хитрыми оптимизациями JIT, возможно, это не будет иметь значения, но, мне кажется, стоит попробовать.

          +1

          Действительно, передав размер конечной строки сразу в конструктор StringBuilder-а можно выделить память только один раз и ровно столько, сколько нужно. Но это почти не даёт прироста.
          Представьте такой код:


          public class ToHexStringConverter {
          
            private static final char[] HEX_CHARS = {
                    '0', '1', '2', '3',
                    '4', '5', '6', '7',
                    '8', '9', 'A', 'B',
                    'C', 'D', 'E', 'F'
            };
          
            public String toHexString(byte[] bytes) {
              StringBuilder sb = new StringBuilder();
              for (byte b : bytes) {
                int temp = (int) b & 0xFF;
                sb.append(HEX_CHARS[temp / 16]);
                sb.append(HEX_CHARS[temp % 16]);
              }
              return sb.toString();
            }
          
            public String patched_toHexString(byte[] bytes) {
              StringBuilder sb = new StringBuilder(bytes.length * 2);
              for (byte b : bytes) {
                int temp = (int) b & 0xFF;
                sb.append(HEX_CHARS[temp / 16]);
                sb.append(HEX_CHARS[temp % 16]);
              }
              return sb.toString();
            }
          }

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


          Но увы, это не даёт значимого прироста. Возьмём 20 Мб и скормим обоим методам:


          @State(Scope.Thread)
          @BenchmarkMode(Mode.AverageTime)
          @OutputTimeUnit(TimeUnit.MILLISECONDS)
          @Fork(jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms2g", "-Xmx2g"})
          public class SizedStringBuilderBenchmark {
          
            private byte[] bytes;
            private ToHexStringConverter converter;
          
            @Setup
            public void init() {
              bytes = new byte[1024 * 1024 * 20];
              converter = new ToHexStringConverter();
              ThreadLocalRandom.current().nextBytes(bytes);
            }
          
            @Benchmark
            public String original() {
              return converter.toHexString(bytes);
            }
          
            @Benchmark
            public String patched() {
              return converter.patched_toHexString(bytes);
            }
          }

          На выходе имеем


          Benchmark                        Mode  Cnt          Score   Error   Units
          
          original                         avgt   25        124,766 ± 1,610   ms/op
          patched                          avgt   25        113,763 ± 3,432   ms/op
          
          original:·gc.alloc.rate.norm     avgt   25  192938425,434 ± 0,886    B/op
          patched:·gc.alloc.rate.norm      avgt   25   83886183,845 ± 1,341    B/op

          Действительно, выигрыш по памяти более чем двукратный, но разница во времени не столь велика.


          Конкретно в этом случае ощутимый прирост даст выбрасывание StringBuilder-a:


          public class ToHexStringConverter {
          
            private static final char[] HEX_CHARS = {
                    '0', '1', '2', '3',
                    '4', '5', '6', '7',
                    '8', '9', 'A', 'B',
                    'C', 'D', 'E', 'F'
            };
          
            //...
          
            public String chars_toHexString(byte[] bytes) {
              char[] result = new char[bytes.length * 2];
              int idx = 0;
              for (byte b : bytes) {
                int temp = (int) b & 0xFF;
                result[idx++] = HEX_CHARS[temp / 16];
                result[idx++] = HEX_CHARS[temp % 16];
              }
              return new String(result);
            }
          }

          Берём тот же замер:


          @State(Scope.Thread)
          @BenchmarkMode(Mode.AverageTime)
          @OutputTimeUnit(TimeUnit.MILLISECONDS)
          @Fork(jvmArgsAppend = {"-XX:+UseParallelGC", "-Xms2g", "-Xmx2g"})
          public class SizedStringBuilderBenchmark {
          
            private byte[] bytes;
            private ToHexStringConverter converter;
          
            @Setup
            public void init() {
              bytes = new byte[1024 * 1024 * 20];
              converter = new ToHexStringConverter();
              ThreadLocalRandom.current().nextBytes(bytes);
            }
          
            @Benchmark
            public String original() {
              return converter.toHexString(bytes);
            }
          
            @Benchmark
            public String patched() {
              return converter.patched_toHexString(bytes);
            }
          
            @Benchmark
            public String chars() {
              return converter.chars_toHexString(bytes);
            }
          
          }

          И вот тут получаем почти 4-х кратный прирост по времени:


          Benchmark                        Mode  Cnt          Score   Error   Units
          
          original                         avgt   25        124,766 ± 1,610   ms/op
          patched                          avgt   25        113,763 ± 3,432   ms/op
          chars                            avgt   25         32,367 ± 0,656   ms/op
          
          original:·gc.alloc.rate.norm     avgt   25  192938425,434 ± 0,886    B/op
          patched:·gc.alloc.rate.norm      avgt   25   83886183,845 ± 1,341    B/op
          chars:·gc.alloc.rate.norm        avgt   25  125829182,781 ± 0,242    B/op
            0

            Оригинальная ваша задача


            код
            public String appendBounds(Data data) {
              int beginIndex = data.beginIndex;
              int endIndex = data.endIndex;
            
              return new StringBuilder()
                      .append('L')
                      .append(data.str, beginIndex, endIndex)
                      .append(';')
                      .toString();
            }

            отличается от тестируемой в сообщении тем, что в "оригинале" происходит лишь копирование данных, без доступа к массиву (HEX_CHARS) по 2 раза на каждый символ. Полагаю, в "оригинале" соотношение скоростей в вариантах с переданным capacity и без будет несколько больше.

              0

              Вы правы, передача размера в StringBuilder даёт неплохой прирост в данном случае


              @Benchmark
              public String appendBoundsSized(Data data) {
                int beginIndex = data.beginIndex;
                int endIndex = data.endIndex;
              
                return new StringBuilder(endIndex - beginIndex + 2)
                        .append('L')
                        .append(data.str, beginIndex, endIndex)
                        .append(';')
                        .toString();
              }

              Вывод


              Benchmark                             length nonLatin   Score   rror Units
              appendBounds                              10     true    41,3 ±  0,9 ns/op
              appendBounds                             100     true   143,6 ±  8,1 ns/op
              appendBounds                            1000     true  1206,5 ± 48,7 ns/op
              
              appendBoundsSized                         10     true    42,6 ±  0,7 ns/op
              appendBoundsSized                        100     true   116,2 ± 17,1 ns/op
              appendBoundsSized                       1000     true   880,9 ± 33,7 ns/op
              
              appendBounds                              10    false    28,4 ±  0,2 ns/op
              appendBounds                             100    false    99,0 ±  3,9 ns/op
              appendBounds                            1000    false   663,3 ± 44,5 ns/op
              
              appendBoundsSized                         10    false    29,5 ±  0,9 ns/op
              appendBoundsSized                        100    false    68,7 ±  3,9 ns/op
              appendBoundsSized                       1000    false   485,6 ± 11,2 ns/op
              
              appendBounds:·gc.alloc.rate.norm          10     true   200,0 ±  0,0  B/op
              appendBounds:·gc.alloc.rate.norm         100     true  1192,0 ±  0,0  B/op
              appendBounds:·gc.alloc.rate.norm        1000     true 10200,0 ±  0,0  B/op
              
              appendBoundsSized:·gc.alloc.rate.norm     10     true   192,0 ±  0,0  B/op
              appendBoundsSized:·gc.alloc.rate.norm    100     true   736,0 ±  0,0  B/op
              appendBoundsSized:·gc.alloc.rate.norm   1000     true  6144,0 ±  0,0  B/op
              
              appendBounds:·gc.alloc.rate.norm          10    false   112,0 ±  0,0  B/op
              appendBounds:·gc.alloc.rate.norm         100    false   544,0 ±  0,0  B/op
              appendBounds:·gc.alloc.rate.norm        1000    false  4152,0 ±  0,0  B/op
              
              appendBoundsSized:·gc.alloc.rate.norm     10    false   112,0 ±  0,0  B/op
              appendBoundsSized:·gc.alloc.rate.norm    100    false   288,0 ±  0,0  B/op
              appendBoundsSized:·gc.alloc.rate.norm   1000    false  2096,0 ±  0,0  B/op

              Интересно, что в этом случае (малое количество вызовов StringBuilder.append) точное выделение памяти даёт очень хороший прирост, чего не скажешь о случае, когда вызовов StringBuilder.append значительно больше.

              0

              Мне кажется что даже в этом примере если вы будете не один 10 мб массив конвертировать, а по очереди 10000 массивов по 1 кб разница уже будет заметна. Потому что стрингбилдер скорее всего когда кончается буффер увеличивает буфер в 2 раза в итоге при конвертации 10 мб новых выделений памяти происходит всего несколько раз (java не знаю просто из общих рассуждений)

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

          Самое читаемое