Приложение D. Производительность

"Это приложение было предоставлено Джо Шарпом и опубликовано с его согласия. Для связи используйте SharpJoe@aol.com."

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

"(Сначала сделайте это, а затем улучшите. К счастью, обычно требуется немного времени)" (Steve McConnell, "О производительности"[16]). Цель этого приложения — помочь вам найти и оптимизировать те части программы, которые требуют улучшения.

D.1 Основные методы

Перед тем как приступить к решению проблем производительности, следует правильно и полностью протестировать программу:

(1) Протестируйте производительность программы в реальных условиях. Если она удовлетворяет требованиям, цель достигнута. В противном случае переходите к следующему шагу.

(2) Найдите самое серьёзное производительное узкое место. Это может потребовать определённых навыков, но все усилия будут вознаграждены. Если просто догадываться о месте узкого места и пытаться его оптимизировать, вы можете потратить время зря.(3) Используйте методы ускорения, представленные в этом приложении, и вернитесь к шагу 1.

Чтобы ваши усилия не были напрасными, важно точно определить местонахождение узкого места. Дональд Кнут [9] улучшил один программный код, который тратил 50% своего времени на примерно 4% от общего объема кода. За час работы он изменил несколько строк кода, что значительно повысило скорость выполнения программы. Однако дальнейшая работа над остальной частью кода была бы бесполезной. У Кнута есть известная цитата среди программистов: "Преждевременная оптимизация — корень всех зол" ("Premature optimization is the root of all evil"). Самый разумный подход — отказаться от стремления к преждевременной оптимизации, так как это может пропустить множество полезных техник программирования, сделать код труднее понять и обслуживать, а также увеличить затраты на поддержание.

D.2 Поиск узких мест

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

D.2.1 Вставка собственного тестового кода

Добавьте следующий "явный" код для замера времени выполнения:``` long start = System.currentTimeMillis(); // Код, который нужно замерить, помещается здесь long time = System.currentTimeMillis() - start;

Используйте `System.out.println()`, чтобы редко используемый метод выводил накопленное время в окно консоли. Поскольку компилятор может игнорировать ошибки, можно использовать "статическое константное логическое значение" (`static final boolean`) для включения или отключения временной метки, что позволит оставить этот код в финальной версии программы для использования в случае необходимости. Хотя существуют более сложные методы анализа производительности, это самый простой способ измерения времени выполнения конкретной задачи.

`System.currentTimeMillis()` возвращает время в миллисекундах (тысячных долей секунды). Однако, некоторые системы имеют временную точность ниже одного миллисекунда (например, Windows ПК), поэтому требуется повторять вызов `n` раз, а затем разделить общее время на `n`, чтобы получить более точное значение времени.
```### D.2.2 Оценка производительности JDK [2]

JDK предоставляет встроенный инструмент для оценки производительности, который отслеживает затраченное время на каждом методе и записывает результаты в файл. К сожалению, этот инструмент нестабилен. Он работал корректно в JDK 1.1.1, но стал очень нестабилен в последующих версиях.

Чтобы запустить инструмент оценки производительности, следует добавить опцию `-prof` при вызове незавершенной версии Java интерпретатора. Например:

java_g -prof MyClass

или добавить апплет:

java_g -prof sun.applet.AppletViewer applet.html

Понимание вывода инструмента оценки производительности может быть сложным. В действительности, в JDK 1.0 он даже обрезал имена методов до 30 символов. Поэтому возможно, что некоторые методы будут трудноразличимыми. Тем не менее, если ваша платформа действительно поддерживает опцию `-prof`, вы можете попробовать "HyperProf" Владимира Булатова [3] или "ProfileViewer" Грега Уайта для анализа результатов.

### D.2.3 Специальные инструменты

Если вы хотите всегда следить за новыми инструментами для оптимизации производительности, лучшим способом будет регулярное посещение специализированных сайтов. Например, сайт "Инструменты для оптимизации Java", созданный Джонатаном Хардвиком:

http://www.cs.cmu.edu/~jch/java/tools.html

### D.2.4 Советы по оценке производительности+   Поскольку оценка производительности использует системные часы, рекомендуется не запускать никакие другие процессы или программы во время тестирования, чтобы избежать влияния на результаты.

+   Если вы внесли изменения в свой код с целью улучшения производительности, проведите замеры времени выполнения как до, так и после внесения изменений (хотя бы на разработочной машине).

+   По возможности проводите все замеры времени в одинаковых условиях.

+   Если это возможно, спроектируйте тест, независимый от входных данных пользователя, чтобы минимизировать влияние различных реакций пользователей на результаты.

## D.3 Методы повышения производительности

Теперь ключевые точки снижения производительности должны быть выявлены. Далее можно применить два типа оптимизации: общие методы и методы, зависящие от Java.### D.3.1 Общие методы  
Обычно эффективный способ ускорения программы заключается в более реалистичной переформулировке задачи. Например, в книге "Programming Pearls" [14] Bentley использует набор данных с текстами рассказов, что позволяет создать очень быстрый и компактный проверщик правописания, основываясь на описании английского языка Doug McIlroy. Кроме того, лучший алгоритм может привести к значительно большему повышению производительности по сравнению с другими методами — особенно при увеличении размера входных данных. Подробнее о таких общих подходах можно узнать в списке рекомендательной литературы в конце данного приложения.

### D.3.2 Методы зависимого от языка подходаДля объективной оценки лучше всего точно знать время выполнения различных операций. В результате полученный показатель будет независимым от используемой машины — путём деления на время локального присваивания, в конце концов, мы получаем "стандартное время".

| Операция | Пример | Стандартное время |
| --- | --- | --- |
| Локальное присваивание | `i=n;` | 1.0 |
| Инстанциальное присваивание | `this.i=n;` | 1.2 |
| Увеличение `int` | `i++;` | 1.5 |
| Увеличение `byte` | `b++;` | 2.0 |
| Увеличение `short` | `s++;` | 2.0 |
| Увеличение `float` | `f++;` | 2.0 |
| Увеличение `double` | `d++;` | 2.0 |
| Пустой цикл | `while(true) n++;` | 2.0 |
| Тернарное условие | `(x<0) ? -x : x` | 2.2 |
| Арифметический вызов | `Math.abs(x);` | 2.5 |
| Присваивание массива | `a[0]=n;` | 2.7 |
| Увеличение `long` | `l++;` | 3.5 |
| Вызов метода | `funct();` | 5.9 |
| Бросание или пойманное исключение | `try { throw e; }` или `catch(e) {}` | 320 |
| Синхронизированный вызов метода | `synchMethod();` | 570 |
| Создание объекта | `new Object();` | 980 |
| Создание массива | `new int[10];` | 3100 |

Эти относительные времена, вычисленные на моей системе (например, Pentium 200 Pro с Netscape 3 и JDK 1.1.5), показывают, что создание объектов и массивов является самым затратным процессом, а синхронизация — более затратным, чем простое обращение к методу. Обзорные материалы [5] и [6] содержат веб-адреса программ для замера времени, которые можно запустить на вашей машине.(1) Общие рекомендации

Ниже приведены некоторые общие советы по ускорению ключевых частей Java-программ (не забудьте сравнить результаты до и после модификаций).

| Измените... | На... | Причина |
| --- | --- | --- |
| Интерфейсы | Абстрактные классы (когда требуется только один родитель) | Множественное наследование интерфейсов может препятствовать оптимизации производительности |
| Нелокальные или массивные циклические переменные | Локальные циклические переменные | По таблице выше, время одного инстанциального целочисленного присвоения составляет 1.2 раза больше времени локального целочисленного присвоения, но время присвоения массива равно 2.7 раза времени локального целочисленного присвоения |
| Связанные списки (фиксированного размера) | Сохранение выброшенных связей или замена списка на циклический массив (приблизительно известного размера) | Каждое новое создание объекта эквивалентно 980 локальным присваиваниям. См. раздел "Переиспользование объектов" (следующий раздел), Van Wyk [12], стр. 87 и Bentley [15], стр. 81 |
| `x / 2` (или любой степени двойки) | `x >> 2` (или любой степени двойки) | Используйте более быструю аппаратную команду |### D.3.3 Особые случаи+

Расходы при использовании оператора конкатенации строк `+`: хотя этот оператор выглядит простым, он требует значительных системных ресурсов. Компилятор может эффективно соединять строки, но использование переменных типа `String` требует значительного времени процессора. Например, если `s` и `t` являются строковыми переменными:```java
System.out.println("heading" + s + "trailer" + t);

Эта строка требует создания объекта StringBuilder, добавления аргументов и последующего преобразования результата обратно в строку с помощью метода toString(). Таким образом, как диск, так и процессор будут значительно нагружены. Если планируется объединение нескольких строк, рекомендуется использовать объект StringBuilder напрямую — особенно полезно это делать внутри цикла, чтобы избежать повторной инициализации объекта StringBuilder. Это позволяет экономить до 980 единиц времени на создание новых объектов (как было указано ранее). Также можно улучшить производительность с помощью методов substring() и других методов работы со строками. В некоторых случаях массив символов может работать быстрее. Кроме того, следует отметить, что метод StringTokenizer также может вызвать значительные затраты из-за необходимости синхронизации.

• Синхронизация: в JDK интерпретаторе вызов синхронизированного метода обычно медленнее несинхронизированного метода примерно в 10 раз. После компиляции JIT эта разница увеличивается до 50–100 раз (учитывая время, указанное в таблице выше, которое составляет около 97 раз). Поэтому стоит избегать использования синхронизированных методов, когда это возможно. Если же избежать этого невозможно, то лучше использовать синхронизацию уровня метода вместо синхронизации уровня блока кода.+ Переделка существующих объектов: создание нового объекта занимает много времени (по данным таблицы выше, создание нового объекта занимает 980 раз больше времени, чем присвоение значения, а создание нового маленького массива — 3100 раз больше времени). Поэтому наиболее разумным решением будет обновление полей старых объектов вместо создания новых. Например, не создавайте новый объект Font в своем методе paint(). Вместо этого объявите его как экземплярный объект и инициализируйте один раз. Затем вы можете обновлять его каждый раз, когда это требуется в методе paint(). См. книгу J. Bentley "Программистское жемчуг", стр. 81 [15].+ Исключения: обработка исключений должна применяться только в случае возникновения ошибки. Какие случаи считаются ошибками? Обычно это ситуации, когда программа сталкивается с проблемой, которую она не может обработать, поэтому производительность уже не является главным приоритетом. При оптимизации объедините небольшие блоки try-catch. Эти блоки делят код на небольшие отдельные части, что мешает компилятору выполнять оптимизацию. Однако слишком большое стремление удалить блоки обработки исключений может привести к снижению надежности программы.

• Хэширование: сначала, стандартный "хеш-таблица" (Hashtable) класс Java версий 1.0 и 1.1 требует преобразования вместе со специальным потреблением системных ресурсов синхронизацией (570 единиц времени выполнения). Во-вторых, ранние библиотеки JDK не могут автоматически определять оптимальный размер таблицы. В-третьих, хеш-функции должны быть спроектированы в соответствии с характеристиками реальных ключей (Key). Учитывая все эти причины, можно специально создать хеш-класс, который будет работать с конкретным приложением, чтобы улучшить производительность обычной хеш-таблицы. Обратите внимание, что хеш-карта (HashMap) в коллекциях Java 1.2 более гибкая и не синхронизируется автоматически.+ Встраивание методов: компилятор Java может встроить этот метод только если он является final (финальный), private (приватный) или static (статический). Кроме того, в некоторых случаях требуется, чтобы у него не было локальных переменных. Если код тратит много времени на вызов метода, который не имеет ни одного из этих свойств, рассмотрите возможность создания его final версии.

• Ввод/вывод: следует использовать буферизацию по возможности. В противном случае, это может привести к последствиям, когда каждый раз происходит чтение/запись всего лишь одного байта. Обратите внимание, что I/O классы JDK 1.0 используют множество синхронизационных мер, поэтому использование "больших" вызовов, таких как readFully(), а затем самостоятельное объяснение данных, может повысить производительность. Также обратите внимание, что классы Reader и Writer Java 1.1 были оптимизированы для производительности.

• Преобразование и экземпляры: преобразование может занять от 2 до 200 единиц времени присваивания. Большие затраты также требуют восхождения по наследственной структуре. Другие дорогостоящие операции могут ограничивать способность восстановления более низкого уровня структуры.+ Графика: используйте вырезание, чтобы уменьшить объем работы в repaint(). Увеличьте буфер, чтобы увеличить скорость приема; используйте графическое сжатие, чтобы ускорить время загрузки. Примеры хороших руководств можно найти в "Java Applets" от JavaWorld и "Performing Animation" от Sun. Помните, что важно использовать наиболее подходящую команду. Например, для рисования полигона по набору точек drawPolygon() работает быстрее, чем drawLine(). Если вам нужно нарисовать линию шириной один пиксель, drawLine(x,y,x,y) работает быстрее, чем fillRect(x,y,1,1).+ Использование классов API: по возможности используйте классы из Java API, так как они уже оптимизированы для производительности компьютера. Это сложно сделать на Java. Например, при копировании массива любой длины методом arrayCopy() работает намного быстрее, чем цикл.

• Замена API-класса: порой API-класс предоставляет больше возможностей, чем требуется, что приводит к увеличению времени выполнения. Поэтому можно создать специальную версию, которая будет выполнять меньше действий, но быстрее. Например, предположим, что приложение требует контейнер для хранения большого количества массивов. Чтобы ускорить выполнение, можно заменить исходный Vector более быстрым динамическим массивом объектов.

(1) Другие рекомендации

• Перемещение повторяющихся вычислений констант за пределы ключевых циклов — например, вычисление buffer.length фиксированной длины буфера.

• Константы с модификаторами static final помогают компилятору оптимизировать программу.

• Реализация циклов с фиксированным размером.

• Использование опций оптимизации компилятора javac: -O. Это позволяет встроить методы static, final и private, тем самым оптимизируя скомпилированный код. Обратите внимание, что длина класса может увеличиться (только для JDK 1.1 — ранние версии могут не поддерживать проверку байтов). Новые "Just-In-Time" (JIT) компиляторы позволяют динамически ускорять код.+ Уменьшение счетчиков до нуля — это использование специального JVM-байткода.

D.4 Прочие ресурсы

D.4.1 Инструменты производительности

[1] MicroBenchmark для Pentium Pro 200, Netscape 3.0, JDK 1.1.4 (см. ниже ссылку [5])

[2] Страница документации Sun для JDK Java интерпретатора:

http://java.sun.com/products/JDK/tools/win32/java.html

[3] HyperProf В. Булатовой

http://www.physics.orst.edu/~bulatov/HyperProf

[4] ProfileViewer Г. Уайта

http://www.inetmi.com/~gwhi/ProfileViewer/ProfileViewer.html

D.4.2 Веб-сайты

[5] Лучший онлайн-ресурс для оптимизации Java-кода — сайт Jonathan Hardwick "Java Optimization":

http://www.cs.cmu.edu/~jch/java/optimization.html

"Сайт Java-оптимизатора":

http://www.cs.cmu.edu/~jch/java/tools.html

И "Java Microbenchmarks" (с процессом тестирования продолжительностью 45 секунд):

http://www.cs.cmu.edu/~jch/java/benchmarks.html

D.4.3 Статьи

[6] "Делаем Java быстрее: Оптимизация! Как получить максимальную производительность вашего кода через низкоуровневую оптимизацию в Java" (Автор: Doug Bell).

http://www.javaworld.com/javaworld/jw-04-1997/jw-04-optimize.html

(включает полный набор тестовых примеров с подробными комментариями)

D.4.4 Профессиональные книги по Java

[11] «Продвинутый Java: Идиомы, ловушки, стили и советы программиста». Автор: Chris Laffra. Издательство Prentice Hall, 1997 год (Java 1.0). Глава 11, раздел 20.

D.4.5 Общие книги

[12] «Структуры данных и программы на C». Автор: J.Van Wyk. Издательство Addison-Wesley, 1998 год.

[13] «Написание эффективных программ». Автор: Jon Bentley. Издательство Prentice Hall, 1982 год. В особенности смотрите страницы 110, 145-151.[14] «Еще Programming Pearls» (второе издание Programming Pearls). Автор: Jon Bentley. «Association for Computing Machinery», февраль 1998 года.

[15] «Programming Pearls» (Programming Pearls). Автор: Jon Bentley. Издательство Addison-Wesley, 1989 год. Вторая часть акцентирует внимание на типичных проблемах повышения производительности.

[16] «Комплексное программирование: практическое руководство по созданию программного обеспечения». Автор: Steve McConnell. Издательство Microsoft Press, 1993 год. Глава 9.

[17] «Разработка объектно-ориентированных систем». Авторы: Champeaux, Lea и Faure. Глава 25.

[18] «Искусство программирования». Автор: Donald Knuth. Первое издание "Основные алгоритмы", третье издание; третье издание "Сортировка и поиск", второе издание. Издательство Addison-Wesley. Это энциклопедия по алгоритмам программирования.

[19] «Алгоритмы в C: основы, структуры данных, сортировка, поиск». Третье издание. Автор: Robert Sedgewick. Издательство Addison-Wesley, 1997 год. Автор является учеником Knuth. Это одно из семи изданий, специализирующихся на различных языках. Алгоритмы объясняются простым языком.