На пути к временной сложности

Эффективный код против конкатенации строк. Разбор кода на Java™


Октябрь 27, 2021


BellSoft запускает серию постов под названием «‎Разбор Java-кода». Все просто: инженеры дают небольшой фрагмент кода, а затем объясняют, что с ним не так.

Итак, вот наш первый пример:

  int n = 100;
  String s = "1";
  for(int i = 0; i < n; i++)
    s = s + 1;

Цикл повторяется n раз и прибавляет «‎1» к строке s с присвоенным значением «‎1».

Вы можете оценить сложность этого алгоритма?

Это не так уж и просто.

Казалось бы, временная сложность алгоритма, при котором цикл повторяется n раз, равна O(n). Но давайте запустим программу. Следует обратить внимание на то, что это конкатенация строкового аккумулятора и строкового представления целого числа. При каждом повторении цикла s увеличивается:

1
11
111
....

Поскольку строки в Java являются неизменяемым, увеличение происходит за счет копирования всего предыдущего содержимого. Количество скопированных символов составит

(1) + (1 + 1) + (1 + 1 + 1) + … ,

что представляет собой сумму n членов арифметической прогрессии, равную (n^2-n)/2. Таким образом, временная сложность алгоритма будет квадратичной O(n^2).

Давайте посмотрим, что происходит «‎под капотом», и как ведут себя бенчмарки. Следующее объяснение относится к версиям Java, более новым, чем 8, так как в них этот код более эффективен. Если вас интересует Java 8, вы можете ознакомиться с соответствующими материалами1. Все примеры составлены с применением Liberica JDK.

Если мы посмотрим на байт-код в версиях Java 9+, мы увидим такие фрагменты как вызовы invokedynamic для конкатенации строк:

  14: invokedynamic #4,  0              // InvokeDynamic #0:makeConcatWithConstants:(Ljava/lang/String;)Ljava/lang/String;

и

BootstrapMethods:
  0: #38 REF_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;

Но в целом, стандартное поведение аналогично тому, что можно увидеть в коде, который собирается для Java 8 как целевой версии, когда javac (первичный компилятор Java) генерирует код, вызывающий конкатенацию

  s = new StringBuilder().append(s).append(1).toString();

Что нас интересует в этом примере? Производительность JVM, и насколько она высокая. Давайте выполним несколько тестов.

@State(Scope.Thread)
public class ConcatBench {

  @Param({"100", "400"})
  int n;

  @Benchmark
  public String chain() {
    String s = "1";
    for(int i = 0; i < n; i++)
      s = s + 1;
    return s;
  }

  @Benchmark
  public String sameSB() {
    String s = "1";
    StringBuilder sb = new StringBuilder(s);
    for(int i = 0; i < n; i++)
      sb.append(1);
    return sb.toString();
  }

  @Benchmark
  public String newSB() {
    String s = "1";
    for(int i = 0; i < n; i++) {
      s = new StringBuilder().append(s).append(1).toString();
    }
    return s;
  }
}

Есть еще третий вариант, при котором вне цикла создается StringBuilder.

Если мы будем компилировать с помощью javac с целевой платформой Java 16 и выполним бенчмарк на JDK 16, мы получим следующий результат:

Benchmark           (n)        Score        Error  Units
ConcatBench.chain   100   940733.514 ±  39773.301  ops/s
ConcatBench.newSB   100   867987.506 ±  10770.221  ops/s
ConcatBench.sameSB  100  4937177.165 ± 166843.186  ops/s # 5.2x faster than chain

ConcatBench.chain   400   128595.073 ±    819.279  ops/s # 7.3x slower than n=100
ConcatBench.newSB   400   127075.294 ±   1383.764  ops/s
ConcatBench.sameSB  400  1403760.812 ±  37459.769  ops/s # 3.5x slower than n=100, 11x faster than chain

Когда n увеличится в 4 раза, выполнение кода, в котором повторно используется StringBuilder, замедлится в 3,5 раза (близко к линейному), а кода, где StringBuilder создается заново, — в 7,3 раза. Точное квадратичное замедление составляет 16 раз. Однако следует отметить дополнительные издержки и оптимизацию при копировании данных (см. StubRoutines::jbyte_disjoint_arraycopy в коде OpenJDK).

В качестве эксперимента можете запустить бенчмарки на своем оборудовании. Поиграйте с javac и версиями JDK и сравните байт-код 7, 8, 11 и 16 на JDK 7, 8, 11 и 16.

Итог: конкатенация дорого обходится

Сложность алгоритма будет квадратичной — выражается в виде суммы n членов арифметической прогрессии — и будет то же соотношение как количества операций, так и потребляемой памяти. Всему виной конкатенация строк, с которой в Java нужно обращаться с осторожностью. Производительность JVM — удивительная штука, не правда ли?

Хотите больше таких постов? Подпишитесь на нашу рассылку и получайте новые статьи первыми!

Полезные ссылки

  1. java.lang.String Catechism - Stay Awhile And Listen by Aleksey Shipilёv
  2. String concatenation with Java 8
  3. GitHub: jdk/stringopts.cpp
  4. StringConcatFactory#makeConcatWithConstants()
  5. src/hotspot/share/opto/stringopts.cpp
Author image

Дмитрий Чуйко

Старший инженер по производительности BellSoft

 Twitter

 LinkedIn

BellSoft LTD [email protected] BellSoft LTD logo Liberica Committed to Freedom 199 Obvodnogo Kanala Emb. 190020 St. Petersburg RU +7 812-336-35-67 BellSoft LTD 199 Obvodnogo Kanala Emb. 190020 St. Petersburg RU +7 812-336-35-67 BellSoft LTD 111 North Market Street, Suite 300 CA 95113 San Jose US +1 702 213-59-59