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

Не так давно прочёл статью об оптимизации производительности 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 работает почти в полтора раза быстрее.

FavoriteLoadingДобавить в избранное
Posted in Без рубрики

Добавить комментарий