Главная

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

2018-07-07 в 18:53, admin, рубрики: bytecode, Dalvik, java, string, высокая производительность

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

Автор: assusdan

Источник