Ещё больше строковых оптимизаций
В продолжение своей предыдущей статьи о строках (напоминаю, это была текстовая версия доклада на конференции 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-х, «если не видно разницы, то зачем писать больше?» :)
Заключение
На этом всё, надеюсь примеры были вам интересны и полезны. Описывайте свои улучшения в комментариях, самые интересные добавлю в статью. До новых встреч!
