Ещё больше строковых оптимизаций

В продолжение своей предыдущей статьи о строках (напоминаю, это была текстовая версия доклада на конференции JPoint-2020) решил дописать ещё одну заметку со строковыми оптимизациями, обнаруженными уже после вёрстки презентации (первые две есть на видео в самом конце, показывал их прямо из "Идеи").

Снова StringBuilder.append(char)

На сцене снова "Спринг", а именно o.s.u.StringUtils.deleteAny(String, String):

// org.springframework.util.StringUtils

public static String deleteAny(String inString, String charsToDelete) {
  if (!hasLength(inString) || !hasLength(charsToDelete)) {
    return inString;
  }

  StringBuilder sb = new StringBuilder(inString.length());
  for (int i = 0; i < inString.length(); i++) {
    char c = inString.charAt(i);
    if (charsToDelete.indexOf(c) == -1) {
      sb.append(c);
    }
  }
  return sb.toString();
}

В разделе "Склейка: если всё-таки нужно" рассматривая StringBuilder.append(char) я отметил невозможность оптимизации компилятором проверок внутри этого метода даже в счётном цикле с заранее известным количеством проходов. Выходом станет использование массива.

Этот же подход хорошо ложится на случаи, в которых длина преобразованной строки может быть меньше или равна исходной. Действительно, какой бы аргумент не передавался в deleteAny, длина возвращаемой строки никогда не превысит длину исходной. Следовательно, можно незначительно усложнив код избавиться от SB:

public static String deleteAny(String inString, String charsToDelete) {
  if (!hasLength(inString) || !hasLength(charsToDelete)) {
    return inString;
  }
  
  int lastCharIndex = 0;
  char[] result = new char[inString.length()];
  for (int i = 0; i < inString.length(); i++) {
    char c = inString.charAt(i);
    if (charsToDelete.indexOf(c) == -1) {
      result[lastCharIndex++] = c;
    }
  }
  return new String(result, 0, lastCharIndex);
}

Переменная lastCharIndex устраняет возможные "пустоты" в массиве при пропуске одного и более знаков.

Используя бенчмарк легко обнаруживаем существенный прирост производительности даже для небольших объёмов данных:

Benchmark                       Mode     Score     Error   Units

original                        avgt    90.203 ±   4.317   ns/op
patched                         avgt    25.391 ±   1.118   ns/op

original:·gc.alloc.rate.norm    avgt   104.000 ±   0.001    B/op
patched:·gc.alloc.rate.norm     avgt   104.000 ±   0.001    B/op

Но и это ещё не всё.

Уже после моего коммита наблюдательный пользователь Johnny Lim сообразил, что если после завершения перебора значение переменной lastCharIndex равно длине исходной строки, то ни одной замены не сделано, а значит новую строку создавать не нужно. Итого:

public static String deleteAny(String inString, String charsToDelete) {
  if (!hasLength(inString) || !hasLength(charsToDelete)) {
    return inString;
  }
  
  int lastCharIndex = 0;
  char[] result = new char[inString.length()];
  for (int i = 0; i < inString.length(); i++) {
    char c = inString.charAt(i);
    if (charsToDelete.indexOf(c) == -1) {
      result[lastCharIndex++] = c;
    }
  }
  if (lastCharIndex == inString.length()) {   // С - сообразительность
    return inString;
  }
  return new String(result, 0, lastCharIndex);
}

Похожий подход использован тут.

Коварный StringBuilder.append(Object)

Следующий пример намного менее очевиден:

// org.springframework.http.ContentDisposition

private static String escapeQuotationsInFilename(String filename) {
  if (filename.indexOf('"') == -1 && filename.indexOf('\\') == -1) {
    return filename;
  }
  boolean escaped = false;
  StringBuilder sb = new StringBuilder();
  for (char c : filename.toCharArray()) {
    sb.append((c == '"' && !escaped) ? "\\\"" : c);    // <----
    escaped = (!escaped && c == '\\');
  }
  // Remove backslash at the end..
  if (escaped) {
    sb.deleteCharAt(sb.length() - 1);
  }
  return sb.toString();
}

Больное место находится в строке 10, а заключение звучит так: поскольку тернарный оператор возвращает либо String, либо char, то аргументом метода StringBuilder.append() фактически является Object. И всё бы ничего, да преобразование знака в объект происходит с помощью String.valueOf() и мы на ровном месте получаем множество мелкого мусора по схеме:

Character.valueOf(c) 
  -> StringBuilder.append(Object) 
    -> String.valueOf()
      -> Character.toString()

Отдельно доставляет реализация Character.toString:

public final class Character {

  private final char value;

  public String toString() {
    char buf[] = {value};
    return String.valueOf(buf);
  }
}

Таким образом, достаточно избавиться от тернарного оператора:

for (int i = 0; i < filename.length() ; i++) {
  char c = filename.charAt(i);
  if (!escaped && c == '"') {
    sb.append("\\\"");    // append(String)
  }
  else {
    sb.append(c);         // append(char)
  }
  escaped = (!escaped && c == '\\');
}

И вновь очень простое изменение приносит впечатляющий прирост (бенчмарк по ссылке):

JDK 8

Benchmark                             latin   len   Score          Units

appendCovariant                        true    10   180.2 ± 10.3   ns/op
appendExact                            true    10    68.5 ±  1.4   ns/op

appendCovariant                       false    10   177.7 ±  4.4   ns/op
appendExact                           false    10    67.7 ±  1.3   ns/op

appendCovariant:·gc.alloc.rate.norm    true    10   688.0 ±  0.0    B/op
appendExact:·gc.alloc.rate.norm        true    10   112.0 ±  0.0    B/op

appendCovariant:·gc.alloc.rate.norm   false    10   816.0 ±  0.0    B/op
appendExact:·gc.alloc.rate.norm       false    10   112.0 ±  0.0    B/op

JDK 14

Benchmark                             latin   len    Score         Units

appendCovariant                        true    10    228.8 ± 18.6  ns/op
appendExact                            true    10     57.9 ±  2.6  ns/op

appendCovariant                       false    10    292.8 ± 12.4  ns/op
appendExact                           false    10     90.2 ±  2.2  ns/op

appendCovariant:·gc.alloc.rate.norm    true    10    688.0 ±  0.0   B/op
appendExact:·gc.alloc.rate.norm        true    10    112.0 ±  0.0   B/op

appendCovariant:·gc.alloc.rate.norm   false    10   1096.0 ±  0.0   B/op
appendExact:·gc.alloc.rate.norm       false    10    200.0 ±  0.0   B/op

Обратите внимание, что исполнение не смогло выбросить мусорные объекты, хотя их область видимости крайне ограничена. Закономерно возникает вопрос: могёт ли Грааль?

Коварный String.substring

Давно известно, что метод String.substring всегда возвращает новую строку, и тем не менее в задачах на "выкусывание" он всё ещё пользуется незаслуженной популярностью:

// org.springframework.web.util.UrlPathHelper

/**
 * Sanitize the given path replacing "//" with "/"
 */
private String getSanitizedPath(String path) {
  String sanitized = path;
  while (true) {
    int idx = sanitized.indexOf("//");
    if (idx < 0) {
      break;
    }
    else {
      sanitized = sanitized.substring(0, idx) + sanitized.substring(idx + 1);
    }
  }
  return sanitized;
}

Здесь даже если исполнение каким-то чудом сможет распознать шаблон склеивания строк и подставить StringBuilder этот метод всё равно останется чертовски неэффективным.

В такого рода задачах очень важно посмотреть на алгоритм с высокого уровня и описать простыми словами выполняемую работу. Здесь получается так: "заменить все двойные вхождения косой черты на единичные". Из строки знаки мы удалять не можем, но можем удалять из StringBuilder-а, а значит код выше можно превратить в этот:

private static String getSanitizedPath(String path) {
  int index = path.indexOf("//");
  if (index >= 0) {
    StringBuilder sanitized = new StringBuilder(path);
    while (index != -1) {
      sanitized.deleteCharAt(index);
      index = sanitized.indexOf("//", index); //не начинай сначала ;)
    }
    return sanitized.toString();
  }
  return path;
}

В некоторых случаях использование StringBuilder.deleteCharAt(int) позволяет существенно облегчить понимание кода:

// org.springframework.web.util.UrlPathHelper

private String removeSemicolonContentInternal(String requestUri) {
  int semicolonIndex = requestUri.indexOf(';');
  while (semicolonIndex != -1) {
    int slashIndex = requestUri.indexOf('/', semicolonIndex);
    String start = requestUri.substring(0, semicolonIndex);
    requestUri = (slashIndex != -1) ? start + requestUri.substring(slashIndex) : start;
    semicolonIndex = requestUri.indexOf(';', semicolonIndex);
  }
  return requestUri;
}

Логика здесь довольно запутанная, но на высоком уровне метод удаляет содержимое, выделенное ; внутри ссылки, превращая строку вроде /foo;f=F;o=O;o=O/bar;b=B;a=A;r=R в /foo/bar;b=B;a=A;r=R.

Можно избавиться от взятия подстроки и склейки переписав метод вот так:

private static String removeSemicolonContentInternal(String requestUri) {
  int semicolonIndex = requestUri.indexOf(';');
  if (semicolonIndex == -1) {
    return requestUri;
  }
  StringBuilder sb = new StringBuilder(requestUri);
  while (semicolonIndex != -1) {
    int slashIdx = sb.indexOf("/", semicolonIndex + 1);
    if (slashIdx == -1) {
      return sb.substring(0, semicolonIndex);
    }
    sb.delete(semicolonIndex, slashIdx);
    semicolonIndex = sb.indexOf(";", semicolonIndex);
  }
  return sb.toString();
}

На первый взгляд, кода стало больше: 12 строк превратились в 16. С другой стороны, он стал выразительнее и проще для понимания, что идёт приятной добавкой к улучшенной производительности.

Все изменения по теме, а также бенчмарк можно увидеть здесь.

Мопед не мой

В этом разделе описано улучшение, автором которого я не являюсь, но которое представляет интерес.

// org.springframework.util.StringUtils

public static String trimLeadingWhitespace(String str) {
  if (!hasLength(str)) {
    return str;
  }
  StringBuilder sb = new StringBuilder(str);
  while (sb.length() > 0 && Character.isWhitespace(sb.charAt(0))) {
    sb.deleteCharAt(0);
  }
  return sb.toString();
}

Чтобы улучшить этот код нужно вновь понять его высокоуровневый смысл (к счастью он полностью соответствует имени метода). Код удаляет все пробелы в начале строки, а значит вместо познакового удаления можно взять подстроку начиная от первого знака-непробела:

public static String trimLeadingWhitespace(String str) {
  if (!hasLength(str)) {
    return str;
  }
  int idx = 0;
  while (idx < str.length() && Character.isWhitespace(str.charAt(idx))) {
    idx++;
  }
  return str.substring(idx);
}

Этот код значительно быстрее первоначальной версии, а также потребляет меньше памяти, ведь в худшем случае создаётся только один объект (в лучшем при idx = 0 метод str.substring()вернёт строку, на которой он был вызван).

Данный подход был использован для улучшения нескольких методов, больше подробностей тут.

Мелочь

Если в коде есть что-то вроде

char[] chars;
//...
return new String(chars, 0, chars.length);

то это всегда можно переписать в виде

char[] chars;
//...
return new String(chars);

Производительность это сильно не улучшит, однако, перефразируя рекламу моющего средства из 90-х, "если не видно разницы, то зачем писать больше?" :)

Заключение

На этом всё, надеюсь примеры были вам интересны и полезны. Описывайте свои улучшения в комментариях, самые интересные добавлю в статью. До новых встреч!