Программные методы повышения производительности архитектуры picoJava-II

Актуальность темы

Язык программирования Java, получивший широкое распространение в последние годы, обладает рядом достоинств, среди которых обычно выделяют платформенную независимость Java-программ [14]. Однако, как это часто бывает, достижения в чем-то одном приводят к проигрышу в другом. В случае Java наибольшей критике подвергается низкая производительность программ, написанных на этом языке, что является следствием изначально интерпретационного стиля их исполнения: платформенная независимость достигается путем интерпретации на конкретной архитектуре промежуточного представления, называемого байт-кодом.

В ходе развития языка была предложена технология динамической перекомпиляции байт-кода под конкретную исполняющую архитектуру, что позволило в несколько раз повысить производительность Java-nporpaMM. Эта технология получила название JIT-компиляции (Just-In-Time).

Однако JIT-компиляция не может использоваться во всей области применения Java. В последние годы разработчики бытовой техники все чаще создают устройства, имеющие выход в Internet. Например, уже не редкость мобильные телефоны, обладающие этим свойством. Такие устройства получили название встроенных (embedded). Но подключение к Internet вряд ли может считаться полноценным без поддержки Java. К сожалению, из-за резкого увеличения потребления памяти, ЛТ-технология не может быть применена для встроенных устройств, поскольку они зачастую не обладают достаточными ресурсами.

Альтернативой идее ЛТ-компиляции на рынке встроенных устройств стала идея микропроцессора, который мог бы аппаратно исполнять байт-код Java. Первой попыткой реализации этой идеи стала архитектура picoJava-II, разработанная фирмой Sun Microsystems в 1999 году. В 2000 году на основе этой архитектуры фирмой Fujitsu был разработан и запущен в серийное производство микропроцессор МВ86 799 [44]. Испытания микропроцессора MB86799 показали, что при одинаковой тактовой частоте производительность архитектуры picoJava-II в 15 раз превышает производительность традиционных архитектур, использующих ЛТ-технологию.

Однако при дальнейшем анализе архитектуры picoJava-II и самого байт-кода становится ясно, что остается много возможностей дальнейшего повышения производительности picoJava-II программным путем. Частично эти возможности связаны с качеством самого исполняемого байт-кода, получаемого стандартным Java-компилятором. Другие возможности обусловлены архитектурными особенностями picoJava-II, пригодными для оптимального исполнения байт-кода. В связи с этим становятся актуальными работы, связанные с разработкой механизмов, использующих аппаратные особенности архитектуры picoJava-II для исполнения байт-кода оптимальным образом.

Целью диссертационной работы является анализ проблем, связанных с достижением наибольшей производительности Java-платформ, и практическое решение этих проблем применительно к архитектуре picoJava-II. Исходя из поставленной цели, в работе решаются следующие задачи:

• исследование возможностей увеличения производительности байт-кода Java;

• адаптация существующих алгоритмов оптимизации байт-кода к требованиям архитектуры picoJava-II;

• разработка новых алгоритмов, использующих для оптимизации байт-кода аппаратные возможности picoJava-II, в том числе динамически на этапе исполнения;

• оценка предлагаемых способов оптимизации при их реализации в составе оптимизирующего бинарного компилятора для архитектуры picoJava-II.

Предмет исследования составляют различные аспекты разработки средств программного повышения производительности для архитектуры picoJava-II:

• конкретные решения, принятые разработчиками архитектуры picoJava-II;

• методы оптимизации и их адаптация для получения оптимального байт-кода;

• методы поддержки исполнения оптимального байт-кода;

• конечная производительность байт-кода.

Методы исследования заимствованы из областей системного программирования, технологии компиляции и теории графов. Эффективность байт-кода и конечная производительность оценивалась путем замера времени исполнения пакета тестовых программ на потактовой модели архитектуры picoJava-II.

Научная новизна работы заключается в адаптации известных и разработке новых алгоритмов для решения задач повышения производительности архитектуры picoJava-II, имеющей ряд аппаратных особенностей:

• адаптирован к задаче оптимизации байт-кода для архитектуры picoJava-II целый ряд известных ранее классических алгоритмов оптимизации;

• разработан и реализован не исследовавшийся ранее алгоритм уменьшения размера Java классов с помощью переиспользования символьной информации;

• разработан и реализован новый алгоритм использования операции прямого чтения памяти вместо более медленной операции чтения элемента массива;

• разработаны и реализованы два оригинальных механизма поддержки времени исполнения, а именно: ускорение вызова методов через класс-интерфейс и встраивание «на лету» кода коротких методов по месту их вызова.

Практическая ценность результатов работы состоит в том, что на основе оценки производительности оптимизированного байт-кода подтверждена полезность программного подхода к повышению производительности архитектуры picoJava-II. Реализованы бинарный оптимизирующий компилятор и средства поддержки исполнения оптимального байт-кода для picoJava-II. Архитектурно-независимый характер части оптимизаций позволяет сделать вывод о том, что программный ресурс повышения производительности будет присутствовать и в будущих микропроцессорах, аппаратно исполняющих байт-код Java. Кроме того, некоторые представленные оптимизационные механизмы могут быть полезны и для традиционных архитектур, использующих JIT-технологию.

Основные практические результаты, выносимые на защиту.

1) Алгоритмы оптимизации размера байт-кода:

• удаление неиспользуемых записей в константном пуле;

• переиспользование записей в константном пуле.

2) Алгоритмы повышения производительности байт-кода на основе статического анализа:

• свертка константных выражений;

• распространение констант;

• арифметические упрощения;

• инлайнинг;

• удаление мертвого и недостижимого кода;

• распространение копирований;

• сбор общих подвыражений;

• вынос инварианта из цикла;

• перераспределение локальных переменных;

• обработка массивов с использованием инструкций из расширенного набора команд picoJava-II.

3) Алгоритмы динамической поддержки исполнения оптимального байт-кода:

• оптимизация вызова методов через класс-интерфейс;

• оптимизация вызова коротких невиртуальных методов.

Все разработанные алгоритмы реализованы в составе оптимизирующего бинарного компилятора для архитектуры picoJava-II. Оптимизирующий бинарный компилятор и средства поддержки времени исполнения прошли этап опытной эксплуатации в фирмах Sun Microsystems, ЗАО «МЦСТ», а также были опробованы сотрудниками фирмы Fujitsu и дали хорошие результаты.

В дальнейшем возможно использование результатов работы в составе математического обеспечения для любого микропроцессора, имеющего архитектуру picoJava-II (например, для микропроцессора МВ86 799, разработанного фирмой Fujitsu).

Публикации.

По теме диссертации опубликованы 6 работ:

• статья «Эффективность языка Java в рамках архитектуры picoJava-II: оптимизация байт-кода» (журнал «Информационные технологии и вычислительные системы», № 1, 2001) [2];

• статья «Оптимизация вызова методов через класс-интерфейс в реализации языка Java» (сборник «Высокопроизводительные вычислительные системы и микропроцессоры», № 3, 2002) [3];

• статья «Оптимизация размера байт-кода языка Java» (журнал «Компьютеры в учебном процессе», № 9, 2002) [10];

• тезисы доклада «Методы ускорения исполнения Java-nporpaMM: оптимизация байт-кода» на XLI научной конференции МФТИ (Москва, МФТИ, ноябрь 1998) [8];

• тезисы доклада «Программное моделирование архитектур как способ анализа их производительности» на XLII научной конференции МФТИ (Москва, МФТИ, ноябрь 1999) [11];

• тезисы доклада «Оптимизация вызова методов через класс-интерфейс в реализации языка Java» на XLIV научной конференции МФТИ, посвященной 50-летию создания МФТИ (Москва, МФТИ, ноябрь 2001) [9].

Апробация.

Результаты работы докладывались и обсуждались на XLI, XLII и XLIV научных конференциях Московского Физико-Технического Института, а также семинарах ЗАО «МЦСТ» .

Краткое содержание работы.

В главе 1 дается краткий обзор проблем, связанных с эффективностью языка Java. Рассматриваются основные варианты реализации виртуальной Java-машины (JVM, Java Virtual Machine). Анализируются область применения и потенциальная эффективность каждого варианта.

По результатам сравнительного анализа делается вывод о перспективности на рынке встроенных устройств варианта реализации JVM в виде микропроцессора, аппаратно исполняющего байт-код. В частности, подобные микропроцессоры могут быть спроектированы на основе одной из современных архитектурных платформpicoJava-II.

В разделе 1.2 описываются основные особенности устройства виртуальной Java-машины, существенные для дальнейшего изложения. Подробно характеризуются формат Java-класса и набор команд JVM.

В разделе 1.3 анализируется основные архитектурные особенности picoJava-II. Отдельно рассматривается расширенный набор команд, использование которого позволяет увеличить производительность байт-кода.

По результатам проведенного анализа делается вывод о том, что в архитектуре picoJava-II присутствует возможность повышения производительности программным путем.

В главе 2 анализируются возможности оптимизации размера байт-кода Java. Размер байт-кода является его важной характеристикой, поскольку оказывает прямое влияние на скорость передачи Java-nporpaMM по сети. Встроенные устройства на основе архитектуры picoJava-II не имеют жестких дисков, осуществляя все взаимодействие с внешним миром исключительно с помощью сетевых соединений. Таким образом, размер байт-кода становится одним из ключевых факторов обеспечения производительности систем, построенных на основе этой архитектуры.

На основе анализа размера составных частей классов из тестового пакета JavaSpec 98 [47] делается вывод о том, что компонентом класса, занимающим подавляющую часть в общем объеме, является константный пул.

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

В конце главы приводятся результаты применения предлагаемых алгоритмов для оптимизации размера байт-кода программ из тестового пакета JavaSpec 98. Из полученных результатов видно, что объем классов уменьшается в среднем на 20%.

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

Подробно рассматриваются способы адаптации традиционных алгоритмов для оптимизации байт-кода, а именно:

• свертка константных выражений;

• распространение констант;

• арифметические упрощения;

• инлайнинг;

• удаление мертвого и недостижимого кода;

• распространение копирований;

• сбор общих подвыражений;

• вынос инварианта из цикла;

• перераспределение локальных переменных.

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

После проведения оптимизационных преобразований необходимо преобразовать промежуточное представление в байт-код. В разделе 3.4 предлагается генератор байт-кода из используемого промежуточного представления.

В конце главы приводятся результаты применения рассматриваемых алгоритмов на программах тестовых пакетов CaffeineMark 3.0 [46] и JavaSpec 98 [47], адаптированных для программного симулятора архитектуры picoJava-II. Для программ, мало использующих классы из стандартной библиотеки, получено существенное сокращение времени исполнения — в среднем на 25%. Для программ, активно использующих стандартную библиотеку языка, сокращение времени исполнения не столь заметно и составляет около 2−3%.

В главе 4 предлагаются способы динамической поддержки исполнения оптимального байт-кода на архитектуре picoJava-II: Поздняя линковка, принятая в Java, позволяет от запуска к запуску менять реализации отдельных классов при сохранении их интерфейса. Поэтому межклассовые оптимизации байт-кода на основе статического анализа могут оказаться некорректными. Однако некоторые межклассовые оптимизации могут быть осуществлены на основе динамического анализа поведения программы.

Одним из слабых мест архитектуры picoJava-II является вызов метода через класс-интерфейс (команда invokeinterfacequick из набора команд JVM). Эта команда реализована в виде программного прерывания, которое в среднем исполняется более 600 тактов. При некоторых динамически определяемых условиях ее можно заменить другими командами JVM, исполнение которых требует существенно меньшего времени.

Технология написания программ на объектно-ориентированных языках, к которым относится и Java, поощряет сокрытие членов-данных объекта и доступ к ним с помощью методов типа «getx ()». Поскольку инлайнинг между классами может быть некорректным, такой подход к написанию программ, хотя и позволяет писать менее подверженный ошибкам код, наносит ущерб производительности. В разделе 4.2 предлагается способ динамического инлайнинга методов типа «getx ()» .

В конце главы оценивается оптимизационный эффект, который может быть получен за счет применения динамической поддержки при исполнении байт-кода. На отдельных тестах пакета JavaSpec 98 достигается сокращение времени исполнения программы в пять раз.

В Заключении приводятся основные результаты диссертационной работы. Делаются выводы об эффективности разработанных алгоритмов. Даются рекомендации по применению тех или иных оптимизационных алгоритмов и их месте в составе математического обеспечения для архитектуры picoJava-II.

В Приложении дана методика проведения замеров на потактовой модели архитектуры picoJava-II.

4.3 Выводы.

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

2. Некоторые простые межклассовые оптимизации могут быть реализованы в местах вызова методов в случаях, когда вызываемый метод определяется однозначно. Динамический анализ количества реализаций методов позволяет увеличить число таких мест за счет методов, являющихся виртуальными лишь формально.

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

4. Оптимизация вызова коротких невиртуальных методов позволяет в большинстве случаев производить встраивание кода методов типа «getXO» и «putXO» по месту вызова. На некоторых программах тестового пакета JavaSpec 98 оптимизация дает существенное уменьшение времени исполнения теста (до 40%).

5. Предложенные методы оптимизации позволяют разработчикам программного обеспечения использовать современные методы разработки программ, такие как разделение интерфейса/реализации и сокрытие членов-данных, не заботясь о производительности получающегося кода.

Заключение

.

Диссертационная работа посвящена вопросам, связанным с повышением производительности архитектуры picoJava-II программным путем. Исследованы проблемы, имеющие отношение к получению оптимального байт-кода и разработке методов динамической поддержки его исполнения. Поставленные задачи решены практически в виде реализации бинарного оптимизирующего компилятора байт-кода для архитектуры picoJava-II и средств поддержки исполнения оптимального байт-кода. В ходе решения поставленных задач были достигнуты следующие результаты:

1. Проведен анализ проблем, касающихся эффективности языка Java. Рассмотрены основные варианты реализации виртуальной Java-машины, их область применения и потенциальная эффективность. Результатом анализа является вывод о перспективности на рынке встроенных устройств варианта реализации JVM в виде микропроцессора, аппаратно исполняющего байт-код, в том числе на основе одной из современных архитектурных платформ — picoJava-II.

2. Для решения задачи повышения производительности архитектуры picoJava-II предложены три основные стратегии:

• оптимизация размера Java-классов;

• повышение эффективности байт-кода на основе статического анализа;

• повышение эффективности байт-кода с использованием средств динамической поддержки.

3. В рамках решения задачи оптимизации размера Java-KnaccoB проведен анализ размера составных частей 1ага-классов. На основе этого анализа сделан вывод о том, что подавляющую часть размера байт-кода классов занимает константный пул. Предложены два алгоритма построения компактного константного пула, а именно:

• удаление неиспользуемых записей в константном пуле;

• переиспользование записей в константном пуле.

Реализация предложенных алгоритмов построения компактного константного пула в составе бинарного оптимизатора байт-кода показала, что их применение совместно с традиционными подходами к уменьшению размера Java-KnaccoB позволяет сократить объем классов в среднем на 20%, что приблизительно на 10% лучше, чем применение только традиционных способов.

4. Java-компиляторы обычно не оптимизируют байт-код, откладывая оптимизации до стадии работы JIT-компиляторов, вследствие чего появляется возможность оптимизации байт-кода для архитектуры picoJava-II на основе статического анализа. При этом могут быть применены как традиционные оптимизирующие алгоритмы, так и специальные алгоритмы, учитывающие архитектурные особенности picoJava-II. Адаптация к специфике байт-кода целого ряда классических алгоритмов оптимизации и реализация специального алгоритма, ускоряющего за счет использования особенностей архитектуры регулярную обработку массивов, показали, что статическая оптимизация байт-кода для архитектуры picoJava-II позволяет получить сокращение времени исполнения на 2−3% для программ, активно использующих стандартную библиотеку языка. Для программ, мало использующих классы из стандартной библиотеки, сокращение времени исполнения может быть гораздо более существенным и достигать 25% и более.

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

• оптимизация вызова методов через класс-интерфейс;

• оптимизация вызова коротких невиртуальных методов.

Реализация предлагаемых способов оптимизации для архитектуры picoJava-II показала, что их эффективность сильно зависит от структуры оптимизируемой программы. Предложенные методы оптимизации наиболее эффективны для программ, использующих разделение интерфейса/реализации методов и сокрытие членов-данных. Таким образом, они позволяют разработчикам программного обеспечения использовать эти современные методы разработки программ, не заботясь о производительности получающегося кода. На отдельных тестовых программах, для которых критической является операция вызова метода, было получено уменьшение времени исполнения до пяти раз.

Опытная эксплуатация бинарного статического оптимизатора и средств динамической поддержки показала, что все разработанные алгоритмы могут быть использованы в составе математического обеспечения, поставляемого для микропроцессоров, имеющих архитектуру picoJava-II. Алгоритмы уменьшения размера Java-KnaccoB и адаптированные к байт-коду традиционные алгоритмы оптимизации на основе статического анализа имеют платформенно-независимый характер и могут использоваться в любом микропроцессоре, аппаратно исполняющем байт-код Java. Кроме того, для любого такого микропроцессора могут быть реализованы средства динамической поддержки, использующие те же идеи, что и в случае picoJava-II.

Работа над исследованием и реализацией статических методов оптимизации байт-кода, предлагаемых в третьей главе, осуществлялась в рамках проекта ВСО (Byte Code Optimizer), проводившегося совместно фирмами ЗАО «МЦСТ» и Sun Microsystems в 1997/1998 годах. Автором было разработано большинство алгоритмов, использованных в проекте, и выполнено около 30% работ, связанных с реализацией этих алгоритмов в составе статического бинарного оптимизатора байт-кода.

В заключение мне бы хотелось поблагодарить всех людей, принимавших участие в проекте ВСО. Я выражаю глубокую признательность сотруднику фирмы Sun Microsystems, руководителю проекта бинарной оптимизации Яну Цивлину за проявленное понимание и предоставленную возможность работать над диссертацией. Отдельно хочу поблагодарить начальника отдела ЗАО «МЦСТ», к.т.н. А. Д. Доброва и проф. В. В. Шилова, помогавших мне в течение всего времени написания этой работы, и без которых она была бы невозможна.