Конкатенация строк, или Патчим байткод +28

Не так давно прочёл статью об оптимизации производительности Java-кода — в частности, конкатенации строк. В ней остался поднятым вопрос — почему при использовании StringBuilder в коде под катом программа работает медленнее, чем при простом сложении. При этом += при компиляции превращаются в вызовы StringBuilder.append().

У меня сразу появилось желание разобраться в проблеме.

// ~20 000 000 операций в секунду
public String stringAppend() {
    String s = "foo";
    s += ", bar";
    s += ", baz";
    s += ", qux";
    s += ", bar";
    s += ", bar";
    s += ", bar";
    s += ", bar";
    s += ", bar";
    s += ", bar";
    s += ", baz";
    s += ", qux";
    s += ", baz";
    s += ", qux";
    s += ", baz";
    s += ", qux";
    s += ", baz";
    s += ", qux";
    s += ", baz";
    s += ", qux";
    s += ", baz";
    s += ", qux";

    return s;
}

// ~7 000 000 операций в секунду
public String stringAppendBuilder() {
    StringBuilder sb = new StringBuilder();
    sb.append("foo");
    sb.append(", bar");
    sb.append(", bar");
    sb.append(", baz");
    sb.append(", qux");
    sb.append(", baz");
    sb.append(", qux");
    sb.append(", baz");
    sb.append(", qux");
    sb.append(", baz");
    sb.append(", qux");
    sb.append(", baz");
    sb.append(", qux");
    sb.append(", baz");
    sb.append(", qux");
    sb.append(", baz");
    sb.append(", qux");
    sb.append(", baz");
    sb.append(", qux");
    sb.append(", baz");
    sb.append(", qux");
    sb.append(", baz");
    sb.append(", qux");

    return sb.toString();
}

Тогда все мои рассуждения свелись к тому, что это необъяснимая магия внутри JVM, и я бросил попытки осознать происходящее. Однако в ходе очередного обсуждения различий платформ в скорости работы со строками мы с товарищем yegorf1 решили разобраться, почему и как именно эта магия происходит.

Oracle Java SE


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

  public java.lang.String stringAppend();
    Code:
       0: ldc           #2                  // String foo
       2: astore_1
       3: new           #3                  // class java/lang/StringBuilder
       6: dup
       7: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
      10: aload_1
      11: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      14: ldc           #6                  // String , bar
      16: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;

Можно заметить, что никаких оптимизаций не производилось. Странно, не так ли? Ладно, посмотрим байткод второй функции.

  public java.lang.String stringAppendBuilder();
    Code:
       0: new           #3                  // class java/lang/StringBuilder
       3: dup
       4: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
       7: astore_1
       8: aload_1
       9: ldc           #2                  // String foo
      11: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      14: pop
      15: aload_1
      16: ldc           #6                  // String , bar
      18: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;

Тут опять никаких оптимизаций? Более того, давайте присмотримся к инструкциям на 8, 14 и 15 байтах. Там происходит странная вещь — сначала в стек загружается ссылка на объект класса StringBuilder, затем она из стека выбрасывается и вновь загружается. В голову приходит простейшее решение:

  public java.lang.String stringAppendBuilder();
    Code:
       0: new           #41                 // class java/lang/StringBuilder
       3: dup
       4: invokespecial #4                  // Method java/lang/StringBuilder."<init>":()V
       7: astore_1
       8: aload_1
       9: ldc           #2                  // String foo
      11: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      14: ldc           #6                  // String , bar
      16: invokevirtual #5                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;

Выкинув лишние инструкции, мы получаем код, который работает в 1.5 раза быстрее, чем вариант stringAppend, в котором эта оптимизация уже была проведена. Таким образом, виной «магии» является недоработанный компилятор в байткод, который не может провести довольно простые оптимизации.

Android ART


upd: код собирался под sdk 28 перерелизными buildtools
Итак, выяснилось, что проблема связана с реализацией компилятора Java в байткод для стековой JVM. Тут мы вспомнили о существовании ART, который является частью Android Open Source Project. Эта виртуальная машина, а точнее, компилятор байткода в нативный код, писалась в условиях иска от Oracle, что дает нам все основания полагать: отличия от реализации Oracle значительны. Кроме того, в связи со спецификой процессоров ARM, эта виртуальная машина регистровая, а не стековая.

Давайте взглянем на Smali (одно из представлений байткода под ART):

# virtual methods
.method public stringAppend()Ljava/lang/String;
    .registers 4
    .prologue
    .line 6
    const-string/jumbo v0, "foo"
    .line 7
    .local v0, "s":Ljava/lang/String;
    new-instance v1, Ljava/lang/StringBuilder;
    invoke-direct {v1}, Ljava/lang/StringBuilder;-><init>()V

    invoke-virtual {v1, v0}, Ljava/lang/StringBuilder;->append(Ljava/lang/String;)Ljava/lang/StringBuilder;

    move-result-object v1
    const-string/jumbo v2, ", bar"

    invoke-virtual {v1, v2}, Ljava/lang/StringBuilder;->append(Ljava/lang/String;)Ljava/lang/StringBuilder;

    move-result-object v1

//...

.method public stringAppendBuilder()Ljava/lang/String;
    .registers 3
    .prologue
    .line 13
    new-instance v0, Ljava/lang/StringBuilder;
    invoke-direct {v0}, Ljava/lang/StringBuilder;-><init>()V

    .line 14
    .local v0, "sb":Ljava/lang/StringBuilder;
    const-string/jumbo v1, "foo"

    invoke-virtual {v0, v1}, Ljava/lang/StringBuilder;->append(Ljava/lang/String;)Ljava/lang/StringBuilder;

    .line 15
    const-string/jumbo v1, ", bar"

    invoke-virtual {v0, v1}, Ljava/lang/StringBuilder;->append(Ljava/lang/String;)Ljava/lang/StringBuilder;

//...

В этом варианте stringAppendBuilder больше нет проблем со стеком — машина регистровая, и их не может возникнуть в принципе. Впрочем, это не мешает существованию абсолютно магических вещей:

move-result-object v1

Эта строка в stringAppend делает ничего — ссылка на нужный нам объект StringBuilder уже лежит в регистре v1. Было бы логичным предположить, что именно stringAppend будет работать медленнее. Это и подтверждается опытным путём — результат аналогичен результату «пропатченной» версии программы для стековой JVM: StringBuilder работает почти в полтора раза быстрее.

Вы можете помочь и перевести немного средств на развитие сайта

Теги:



Комментарии (8):

  1. vektory79
    /#18858737 / +3

    На самом деле всё "просто": JVM знает некоторые паттерны и умеет генерировать для них более оптимальный машинный код.


    Попробуйте, например, протестировать вот такой код:


    // ~7 000 000 операций в секунду
    public String stringAppendBuilder() {
        StringBuilder sb = new StringBuilder();
        sb.append("foo")
          .append(", bar")
          .append(", bar")
          .append(", baz")
          .append(", qux")
          .append(", baz")
          .append(", qux")
          .append(", baz")
          .append(", qux")
          .append(", baz")
          .append(", qux")
          .append(", baz")
          .append(", qux")
          .append(", baz")
          .append(", qux")
          .append(", baz")
          .append(", qux")
          .append(", baz")
          .append(", qux")
          .append(", baz")
          .append(", qux")
          .append(", baz")
          .append(", qux");
    
        return sb.toString();
    }

    На уровне байткода должно получиться то же самое, что и при конкатенации строк. Ну и по скорости тоже.
    P.S. И да. Если хотите мерить реальную скорость выполнения таких методов, а не погоду на марсе, то крайне советую использовать JMH, чтобы потом не удивляться непредсказуемым результатам.

    • assusdan
      /#18858743 / -1

      Более того, приведённый код куда более оптимизирован, чем stringAppend, т.к. пропали периодические создания нового StringBuilder и перенос в него старой строки.

    • edd_k
      /#18858869

      Но тестовый пример — это по сути упрощенный пример сборки строки в цикле. Иначе бы вы просто «в уме» собрали эту строку и записали её сразу собранной. Так что ваш вариант ничем не поможет в полевых условиях. Разве что, количество кусочков фиксировано и цикл действительно можно будет развернуть, но это уже частный случай.

      • assusdan
        /#18858873 / +1

        Всё же интересно, почему для фиксированного числа кусочков (пример со stringAppend) не производится склеивание в 1 строку.

  2. SOLON7
    /#18859329

    Все довольно тривиально, проблема в том что при контатенации происходит создание новой памяти и копируются туда два значения, вместо того чтобы увеличить объем указателя и дописать туда 2-ое значение! А так получается при множественном конкатенации происходит много кратное копирование памяти, Как говорил кто-то копирование дорогая операция! Довольно часто встречается в непрофессиональных велосипедах!

    • avost
      /#18860061 / +1

      Так тут обратная ситуация. Конкатенация выполняется быстрее аппендов. Вы статью совсем не читали?

  3. alnikor
    /#18863577

    shipilev.net

    Оставлю это тут, у него целое выступление было по данной теме.