JEP 280: Indify String Concatenation

Аннотация

Изменить статическую последовательность байт-кода для конкатенации String, которую генерирует javac, так, чтобы в ней использовались вызовы invokedynamic к библиотечным функциям JDK. Это позволит в будущем оптимизировать конкатенацию String без дальнейших изменений байт-кода, генерируемого javac.

Цели

Подготовить основу для создания оптимизированных обработчиков конкатенации String, которые можно реализовать без изменения компилятора из Java в байт-код. В качестве мотивирующих примеров для этой работы следует опробовать несколько стратегий трансляции. Создание оптимизированных стратегий трансляции (и, возможно, переход на них) — амбициозная цель этого JEP, достижение которой не гарантируется.

Что не является целью

Целью не является: вводить какие-либо новые API String и/или StringBuilder, которые могли бы помочь в создании более совершенных стратегий трансляции; пересматривать поддержку оптимизации конкатенации String в JIT-компиляторе; поддерживать сложные сценарии интерполяции String; исследовать другие изменения языка программирования Java.

Критерии успеха

• javac генерирует стабильную последовательность байт-кода, рассчитанную на будущее. Предполагается менять форму байт-кода не чаще одного раза за мажорный выпуск Java.

• Производительность конкатенации String не ухудшается.

• Время запуска и время выхода на пиковую производительность ухудшаются не больше разумных пределов.

Мотивация

Сейчас javac транслирует конкатенацию String в цепочки StringBuilder::append. Иногда такая трансляция неоптимальна, а иногда нужно заранее задать подходящий размер StringBuilder. Параметр -XX:+OptimizeStringConcat включает агрессивные оптимизации в JIT-компиляторе, которые распознают цепочки вызовов append у StringBuilder, заранее задают размер и копируют данные на месте. Эти оптимизации, хотя и дают результат, хрупки, и их трудно расширять и сопровождать; см., например, JDK-8043677, JDK-8076758 и JDK-8136469. Возникает соблазн изменить трансляцию в самом javac; см., например, недавнее предложение в рассылке compiler-dev.

Когда мы рассматриваем любые изменения в javac, менять компилятор и форму байт-кода каждый раз, когда нужно улучшить производительность, кажется неудобным. Пользователи обычно ожидают, что тот же байт-код будет работать быстрее на новых JVM. Требовать от пользователей перекомпилировать свои Java-программы ради производительности неудобно для них, к тому же это резко увеличивает матрицу тестирования, поскольку JVM должны распознавать все варианты генерируемого байт-кода. Поэтому, возможно, стоит применить некий приём, чтобы объявлять в байт-коде намерение конкатенировать строки, а затем раскрывать это намерение во время выполнения.

Иными словами, мы вводим нечто похожее на новую инструкцию байт-кода «string concat». Как и в работе над Lambda, это устраняет разрыв между JLS, где языковая возможность (в данном случае конкатенация строк) разрешена, и JVMS, где для неё нет подходящих средств, из-за чего javac вынужден транслировать её в низкоуровневый код, а реализации VM, в свою очередь, вынуждены распознавать все низкоуровневые оттранслированные формы. invokedynamic позволяет одним шагом преодолеть это рассогласование, предоставив гарантированный интерфейс для конкатенации строк на уровне базовых библиотек. Этот интерфейс можно реализовать даже с помощью (потенциально небезопасных) приватных API JVM для конкатенации, например построителей строк фиксированной длины, привязанных к конкретному сценарию использования. Если использовать эти API непосредственно в javac, их пришлось бы сделать публичными.

Описание

Мы воспользуемся возможностями invokedynamic: он предоставляет средства для ленивого связывания, позволяя выполнить начальную загрузку цели вызова один раз, при первом вызове. Этот подход не нов, и мы во многом заимствуем существующий код, который транслирует лямбда-выражения.

Идея в том, чтобы заменить всю пляску с вызовами append у StringBuilder простым вызовом invokedynamic к java.lang.invoke.StringConcatFactory, который будет принимать значения, требующие конкатенации. Например,

String m(String a, int b) {
  return a + "(" + b + ")";
}

сейчас компилируется в:

java.lang.String m(java.lang.String, int);
       0: new           #2                  // class java/lang/StringBuilder
       3: dup
       4: invokespecial #3                  // Method java/lang/StringBuilder."<init>":()V
       7: aload_1
       8: invokevirtual #4                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      11: ldc           #5                  // String (
      13: invokevirtual #4                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      16: iload_2
      17: invokevirtual #6                  // Method java/lang/StringBuilder.append:(I)Ljava/lang/StringBuilder;
      20: ldc           #7                  // String )
      22: invokevirtual #4                  // Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
      25: invokevirtual #8                  // Method java/lang/StringBuilder.toString:()Ljava/lang/String;
      28: areturn

Но даже при наивной трансляции через indy, доступной в предлагаемой реализации через -XDstringConcat=indy, код может быть значительно проще:

java.lang.String m(java.lang.String, int);
       0: aload_1
       1: ldc           #2                  // String (
       3: iload_2
       4: ldc           #3                  // String )
       6: invokedynamic #4,  0              // InvokeDynamic #0:makeConcat:(Ljava/lang/String;Ljava/lang/String;ILjava/lang/String;)Ljava/lang/String;
      11: areturn

BootstrapMethods:
  0: #19 invokestatic java/lang/invoke/StringConcatFactory.makeConcat:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/String;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;

Обратите внимание, что мы передаём аргумент int без упаковки. Во время выполнения запускается bootstrap-метод (BSM), который связывает вызов с фактическим кодом, выполняющим конкатенацию. Он заменяет вызов invokedynamic соответствующим вызовом invokestatic. При этом константная строка загружается из пула констант, но мы можем использовать статические аргументы BSM, чтобы передавать эту и другие константы прямо в вызов BSM. Именно это делает предлагаемый вариант -XDstringConcat=indyWithConstants:

java.lang.String m(java.lang.String, int);
       0: aload_1
       1: iload_2
       2: invokedynamic #2,  0              // InvokeDynamic #0:makeConcat:(Ljava/lang/String;I)Ljava/lang/String;
       7: areturn

BootstrapMethods:
  0: #15 invokestatic java/lang/invoke/StringConcatFactory.makeConcatWithConstants:(Ljava/lang/invoke/MethodHandles$Lookup;Ljava/lang/String;Ljava/lang/invoke/MethodType;Ljava/lang/String;[Ljava/lang/Object;)Ljava/lang/invoke/CallSite;
    Method arguments:
      #16 \u0001(\u0001)

Обратите внимание, что в BSM мы передаём только динамические аргументы ("a" и "b"). Статические константы уже будут обработаны при связывании. Методу BSM передаётся рецепт, в котором указано, в каком порядке конкатенировать динамические и статические аргументы и каковы статические аргументы. Эта стратегия также отдельно обрабатывает null, примитивы и пустые строки.

Открытым остаётся вопрос, какой вариант байт-кода должен использоваться по умолчанию. Подробнее о формах байт-кода, вариантах конкатенации и данных о производительности можно прочитать в экспериментальных заметках. Предлагаемый API bootstrap-метода можно найти здесь. Полная реализация находится в ветке sandbox:

$ hg clone http://hg.openjdk.java.net/jdk9/sandbox sandbox 
$ cd sandbox/ 
$ sh ./common/bin/hgforest.sh up -r JDK-8085796-indyConcat
$ sh ./configure 
$ make images

Разницу между базовой и изменённой средой выполнения можно увидеть с помощью:

$ hg diff -r default:JDK-8085796-indyConcat
$ cd langtools/
$ hg diff -r default:JDK-8085796-indyConcat
$ cd jdk/
$ hg diff -r default:JDK-8085796-indyConcat

Бенчмарки находятся здесь: http://cr.openjdk.java.net/~shade/8085796/

С предлагаемой реализацией JDK успешно собирается, регрессионные тесты (включая новые, проверяющие конкатенацию String) выполняются, а smoke-тесты проходят на всех платформах. Для самой конкатенации можно использовать несколько стратегий. Наша предлагаемая реализация показывает, что пропускная способность не снижается, если перенести последовательность байт-кода, генерируемую javac, в BSM, который внедряет тот же байт-код, и это подтверждает правильность подхода. Оптимизированные стратегии работают не хуже базовой, а то и лучше, особенно когда длины StringBuilder по умолчанию недостаточно и/или оптимизации VM не срабатывают.

Больше данных см. в экспериментальных заметках.

Альтернативы

У этого предложения есть три альтернативы.

Первая, очевидная альтернатива: изменить последовательность байт-кода в самом javac, перенеся в него одну из стратегий генерации байт-кода из предлагаемой реализации. В краткосрочной перспективе это просто, но нарушает негласный договор со всем Java-сообществом: JVM достаточно умны, чтобы распознавать и оптимизировать существующий байт-код. Мы не можем просто так вынуждать пользователей перекомпилировать свои Java-программы каждый раз, когда хотим настроить трансляцию конкатенации String. Каждый раз, когда меняется форма байт-кода, JIT-компиляторы вынуждены распознавать новую форму, а это значительно увеличивает матрицу тестирования и к тому же подвергает ничего не подозревающих пользователей странным (и неправильным) эффектам производительности. Если уж менять форму байт-кода из соображений производительности, то лучше сделать это один раз в мажорном выпуске и с расчётом на будущее. Использовать приватные API для оптимизированной конкатенации строк тоже нельзя: код, сгенерированный javac, должен использовать только публичные API.

Вторая альтернатива: ввести метод StringConcat.concat(Object... args) с переменным числом аргументов и использовать его для конкатенации аргументов. Главный недостаток — упаковка примитивов, а затем упаковка всех аргументов в Object[]. Продвинутые JIT-компиляторы могут распознавать такие идиомы, но тогда мы оказываемся во власти новых и непроверенных оптимизаций в и без того сложных оптимизирующих компиляторах. invokedynamic делает примерно то же самое, но из коробки поддерживает различные сигнатуры целевых методов.

Третья альтернатива: продолжать делать то же, что и сейчас, и расширить -XX:+OptimizeStringConcat, чтобы охватить больше случаев. Недостаток в том, что для оптимизации в JIT-компиляторе нужно явно расписывать преобразования toString и управление памятью на промежуточном представлении (IR) компилятора, из-за чего такую оптимизацию трудно расширять, а для её правильной реализации нужна редкая квалификация. Кроме того, малейшие отличия и странности в форме байт-кода ломают -XX:+OptimizeStringConcat, и в javac приходится проявлять особую осторожность, чтобы этого избежать. См., например, JDK-8043677, JDK-8076758, JDK-8136469.

По сути, все три альтернативы ставят нас в зависимость от хрупких оптимизаций компилятора.

Тестирование

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

Риски и допущения

Другие изменения, связанные с String. Это изменение может конфликтовать с другими изменениями, связанными с String, в частности с Compact Strings (JEP 254). Для снижения риска планируется генерировать ровно ту же последовательность байт-кода, что и текущий JDK; тогда JVM с включённым режимом Compact Strings будет выполнять тот же путь кода, не зная ни о каких изменениях в трансляции конкатенации String. И действительно, наши предварительные эксперименты показывают, что наше предложение хорошо сочетается с Compact Strings.

Исключения для java.base. Поскольку эта возможность использует возможность базовой библиотеки (java.lang.invoke) для реализации базовой возможности языка (конкатенации String), модуль java.base приходится исключить из использования конкатенации String через indy. Иначе возникает циклическая зависимость: механизму java.lang.invoke.* для работы нужна конкатенация String, которой, в свою очередь, нужен механизм java.lang.invoke.*. Это исключение может ограничить прирост производительности от этой возможности, поскольку многие классы java.base не смогут её использовать. Мы считаем это приемлемым недостатком, который должны компенсировать оптимизирующие компиляторы VM.

Стоимость сопровождения. Устаревшая трансляция конкатенации String никуда не исчезает, поэтому нам придётся сопровождать в VM и -XX:+OptimizeStringConcat, и оптимизации для новых стратегий трансляции. javac по-прежнему должен будет предоставлять запасной вариант для случаев, когда конкатенацию String через indy использовать нельзя, в частности для некоторых системных классов. Это не создаёт серьёзной проблемы, поскольку наш подход к производительности предполагает использование -XX:+OptimizeStringConcat в большинстве стратегий.

Совместимость: платформы, не поддерживающие invokedynamic. Что им делать, когда они встретят конкатенацию String через indy? Опыт уже есть с Lambda: платформы, не поддерживающие indy, должны убирать indy через рассахаривание и статически заново генерировать тот же самый код, который indy сгенерировал бы на лету. Последовательность кода, генерируемая для наивной конкатенации String, проще, чем для LambdaFactory, но всё равно усложняет код VM. Поскольку javac в любом случае сохраняет код, генерирующий устаревшую последовательность конкатенации String, упомянутые платформы могут использовать этот запасной вариант.

Совместимость: другие компиляторы. Должны ли другие компиляторы (не javac) генерировать тот же байт-код? Предлагаем ли мы изменить все реализации компиляторов, чтобы они использовали новую стратегию трансляции? Поскольку устаревшая конкатенация String никуда не исчезает, другие компиляторы могут по-прежнему генерировать ту же последовательность байт-кода, что и сегодня. Они могут постепенно переводить часть трансляций на предлагаемую схему трансляции на основе indy, как сочтут нужным.

Совместимость: инструменты для манипуляции байт-кодом и вплетения кода (weavers). Инструментам придётся обрабатывать новые вызовы indy в непривычных для них местах даже без изменений исходного кода, просто вследствие перекомпиляции. Мы не считаем это серьёзной проблемой, поскольку инструменты уже должны обрабатывать Lambda и, следовательно, распознавать invokedynamic. Исправления потребуются для инструментов, которые инструментировали цепочки StringBuilder::append, генерируемые javac.

Статический объём. Размер class-файлов, вероятно, станет проблемой в коде с большим количеством конкатенаций String. Существуют машинно сгенерированные файлы, которые занимают почти все записи в пуле констант (CP) и выполняют огромное количество конкатенаций строк. Похоже, что объём байт-кода методов при конкатенации String через indy значительно меньше, при этом в пуле констант появляются дополнительные статические накладные расходы на механизм java.lang.invoke, плюс небольшие накладные расходы на каждую форму конкатенации. Больше данных см. в заметках выше.

Накладные расходы при запуске. Есть риск, что накладные расходы при запуске окажутся настолько большими, что эту работу нельзя будет продолжить. Такие стратегии трансляции появились вместе с реализацией Lambda, но за них платят, только если используют Lambda. В случае конкатенации строк, как только invokedynamic скомпилирован в байт-код, использованиям + в существующем коде деваться некуда (если только не изменить код так, чтобы избежать + и явно вызывать StringBuilder). Этот риск связан с инициализацией механизма invokedynamic (см. JDK-8086045), поэтому, если здесь смириться с ухудшением времени запуска, это означало бы, что ухудшений времени запуска не будет в других изменениях, которым требуется инициализация invokedynamic, в частности в модульной системе (JEP 261). И наоборот, если модульная система появится раньше этого изменения, то затраты на запуск распределятся.

Зависимости

• JEP 254: Compact Strings

• Затраты на инициализацию java.lang.invoke (JDK-8086045)