30.11.2020 18:20:43 |
Автор: В продолжение своей предыдущей статьи о строках (напоминаю, это была текстовая версия доклада на конференции JPoint-2020) решил дописать ещё одну заметку со строковыми оптимизациями, обнаруженными уже после вёрстки презентации (первые две есть на видео в самом конце, показывал их прямо из "Идеи").
Снова StringBuilder.append(char)
На сцене снова "Спринг", а именно
o.s.u.StringUtils.deleteAny(String, String):
// org.springframework.util.StringUtilspublic 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 Unitsoriginal avgt 90.203 4.317 ns/oppatched avgt 25.391 1.118 ns/oporiginal:gc.alloc.rate.norm avgt 104.000 0.001 B/oppatched: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.ContentDispositionprivate 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 8Benchmark latin len Score UnitsappendCovariant true 10 180.2 10.3 ns/opappendExact true 10 68.5 1.4 ns/opappendCovariant false 10 177.7 4.4 ns/opappendExact false 10 67.7 1.3 ns/opappendCovariant:gc.alloc.rate.norm true 10 688.0 0.0 B/opappendExact:gc.alloc.rate.norm true 10 112.0 0.0 B/opappendCovariant:gc.alloc.rate.norm false 10 816.0 0.0 B/opappendExact:gc.alloc.rate.norm false 10 112.0 0.0 B/opJDK 14Benchmark latin len Score UnitsappendCovariant true 10 228.8 18.6 ns/opappendExact true 10 57.9 2.6 ns/opappendCovariant false 10 292.8 12.4 ns/opappendExact false 10 90.2 2.2 ns/opappendCovariant:gc.alloc.rate.norm true 10 688.0 0.0 B/opappendExact:gc.alloc.rate.norm true 10 112.0 0.0 B/opappendCovariant:gc.alloc.rate.norm false 10 1096.0 0.0 B/opappendExact: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.UrlPathHelperprivate 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.StringUtilspublic 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-х, "если не видно разницы, то зачем писать больше?" :)
Заключение
На этом всё, надеюсь примеры были вам интересны и полезны. Описывайте свои улучшения в комментариях, самые интересные добавлю в статью. До новых встреч!
Категории: 
