Оптимизация представления байт-кода JVM для встраиваемых систем
Описание алгоритма сжатия байт-кода JVM, основанного на генерации новых инструкций для часто встречающихся последовательностей байт-кодов исходной программы. Минимизация суммарного размера программы и интерпретатора, необходимого для её исполнения.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 15.01.2019 |
| Размер файла | 18,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Оптимизация представления байт-кода JVM для встраиваемых систем
Пилипенко А. В., аспирант кафедры информатики математико-механического факультета СПбГУ, artur.pilipenko@gmail.com
Аннотация
байт код последовательность интерпретатор
В докладе описан алгоритм сжатия байт-кода JVM, основанный на генерации новых инструкций для часто встречающихся последовательностей байт-кодов исходной программы. Этот алгоритм минимизирует суммарный размер программы и интерпретатора, необходимого для её исполнения. Наилучших результатов этот подход позволяет добиться в закрытой модели, когда весь исполняемый код доступен на этапе построения, и не стоит задачи обеспечить совместимость интерпретатора со стандартным байт-кодом.
Для встраиваемых систем выполняемые задачи не отличаются вычислительной сложностью, но общий размер программного обеспечения является критически важным параметром. Другой особенностью встраиваемых устройств является то, что в редких случаях на таких устройствах необходимо исполнять произвольные приложения. Обычно такое устройство имеет вполне конкретное применение, и конкретное приложение для исполнения. Этот факт позволяет использовать специализированное представление для Java приложений, без необходимости поддерживать совместимость со стандартным байт-кодом.
В докладе описывается алгоритм сжатия Java приложений, основанный на автоматической генерации специализированного набора инструкций на основе стандартного байт-кода JVM. [1] Специализированный набор инструкций минимизирует суммарный размер приложения и интерпретатора, необходимого для его исполнения. Он представляет собой подмножество стандартного байт-кода JVM, используемое приложением, дополненное “суперинструкциями”, кодирующими часто встречающиеся последовательности байт-кодов исходной программы. По сути, этот алгоритм является применением методов словарного сжатия к коду программ. Аналогичный подход к сжатию кода программ рассмотрен в работах [2, 3].
Генерация оптимизированного набора инструкций
Построение словаря
Процесс генерации специализированного набора инструкций начинается с построения словаря всех последовательностей байт-кодов исходной программы, которые могут быть использованы для создания “суперинструкций”. Это последовательности небольшой длины (обычно не более 10 инструкций) с одной точкой входа и выхода. Для каждой последовательности в словаре хранится то, сколько раз она встречается в исходной программе программы.
Для хранения словаря используется префиксное дерево, в узлах которого записываются байт-коды. Каждый узел такого дерева представляет элемент словаря - последовательность инструкций исходной программы, которую можно восстановить, выписав байт-коды всех вершины от узла до корня в обратном порядке.
Словарь наполняется в процессе итерации по байт-коду всех методов программы. В процессе итерации, на каждом шаге вычисляется множество последовательностей инструкций, которые оканчиваются в просматриваемой позиции. В начале просмотра каждого метода это множество содержит только пустую последовательность. На каждом последующем шаге множество состоит из пустой последовательности и всех последовательностей множества из предыдущего шага, дополненных текущим байт-кодом. В дерево добавляются последовательности, которые могут быть использованы для создания “суперинструкций”. Так как все новые последовательности получаются путем добавления одного байт-кода к существующей последовательности, операции поиска и добавления в дерево сводятся к поиску и добавлению потомка для существующей вершины.
Выбор набора инструкций
Задача выбора оптимального словаря для методов словарного сжатия является NP-полной [4], поэтому на практике используются различные эвристики. Достаточно простым и эффективным является частотный подход, когда в словарь включается самые часто встречающиеся подстроки исходного текста. Аналогичный подход используется и в описываемом алгоритме.
В байт-коде JVM все инструкции кодируются одним байтом, следовательно, набор инструкций ограничен 256 элементами. В набор включаются все инструкции исходного байт-кода, которые использует приложение, затем набор дополняется до 256 элементов последовательностями словаря с максимальным весом, где вес последовательности считается по следующей формуле:
patternCount * (patternLenght - 1) - interpreterSize, где,
patternCount - сколько раз данная последовательность встречается в коде программы;
patternLength - длина последовательности в байтах;
interpreterSize - размер кода интерпретатора для данной последовательности.
Нахождение оптимального покрытия
Для заданного набора инструкций может существовать более одного представления исходной программы. Выбор оптимального представления сводится к нахождению такого покрытия кода исходной программы последовательностями из набора инструкций, при котором суммарная длина использованных последовательностей максимальна. Оптимальное покрытие вычисляется отдельно для каждого метода.
Вычисление оптимального покрытия метода осуществляется последовательно для каждой позиции в теле метода. Для каждой позиции хранится сумма длин использованных последовательностей и указатель на последнюю использованную последовательность. Тогда, при известном оптимальном покрытии для всех предыдущих позиций нахождение оптимального покрытия для текущей позиции сводится к выбору последовательности, заканчивающейся в текущей позиции. Из множества последовательностей, заканчивающихся в данной позиции, выбирается такая последовательность, принадлежащая набору инструкций, для которой максимально значение
length(pattern) + lengths[pos - length(pattern)], где,
length(pattern) - длина последовательности;
lengths[i] - сумма длин последовательностей оптимального покрытия для i-ой позиции;
pos - текущая позиция.
Представление метода в оптимизированном байт-коде восстанавливается с конца метода по указателям на использованные последовательности.
Заключение
Описанный в статье подход позволяет уменьшить размер байт-кода Java программы на 15-30% в зависимости от приложения. В отличие от многих других алгоритмов сжатия программ, описанная оптимизация не оказывает влияния на скорость исполнения программы.
Данный подход может быть применен и для открытой модели, например, для уменьшения размера системных классов. Но в открытой модели совместимость со стандартным набором инструкций существенно ограничивает количество свободных байт-кодов.
Литература
1. Tim Lindholm, Frank Yellin, Gilad Bracha, Alex Buckley “The Java® Virtual Machine Specification” http://docs.oracle.com/javase/specs/jvms/se7/jvms7.pdf [дата просмотра: 21.04.2013]
2. Lars Raeder Clausen , Ulrik Pagh Schultz, Gilles Muller, Charles Consel “Java Bytecode Compression for Low-End Embedded Systems”, ACM Transactions on Programming Languages and Systems, 2000
3. Dimitris Saougkos , George Manis, Konstantinos Blekas, Apostolos V. Zarras, “Revisiting Java Bytecode Compression for Embedded and Mobile Computing Environments”, IEEE Transactions on Software Engineering, 2005
4. Michael Garey, David Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness”, 1990
Размещено на Allbest.ru
...Подобные документы
Приобретение практических навыков по определению объема памяти, отводимого на внешнем запоминающем устройстве под файл данных. Расчет производительности поиска информации, хранящейся в файле на ВЗУ. Вычисление использованных кластеров и байт памяти.
лабораторная работа [31,2 K], добавлен 26.11.2011Написание программы, реализующей алгоритм RLE, позволяющий кодировать, декодировать файлы любого формата и размера, предоставлять пользователю информацию о степени их сжатия. Анализ эффективности кода. Экспериментальная оценка алгоритма программы.
контрольная работа [151,7 K], добавлен 29.05.2013Общее описание и особенности использования программы, предназначенной для определения нечетных чисел, находящихся в массиве чисел. Листинг и методы оптимизации данной компьютерной программы. Источники оптимизации кода, описание выполненных команд.
лабораторная работа [17,4 K], добавлен 25.03.2011Семантика языков программирования. Процедурные и объектно-ориентированные языки программирования. Стандартная библиотека шаблонов. Независимость байт-кода от операционной системы и оборудования и возможность выполнения Java-приложения на любом устройстве.
реферат [50,5 K], добавлен 24.11.2009Архитектура уровня команд платформы Java, формат файла класса Java. Компилятор ассемблероподобного языка, позволяющий создавать файлы классов, корректно обрабатываемые реальной JVM, поддерживающий все команды байт-кода Java и важнейшие возможности JVM.
курсовая работа [292,6 K], добавлен 17.09.2008Разработка программы для выполнения арифметических операций с комплексными числами. Разработка эскизного проекта. Диаграмма последовательностей и классов. Разработка и описание программы. Разработка программного кода и руководства пользователя.
курсовая работа [1,2 M], добавлен 25.11.2011Процесс создания программы, разработка проекта программы и программирование. Лексическая обработка, синтаксический анализ, поэтапная генерация кода, использование библиотечного файла и кода. Стандартные функции библиотечного кода, математические ошибки.
курсовая работа [26,4 K], добавлен 01.12.2009Обзор существующих программ сжатия данных без потерь. Анализ методов сжатия: алгоритмов группы, KWE, Lossless JPEG, кодирование Хаффмана. Обзор составляющих компонентов. Разработка кода программы-архиватора, работающей на основе алгоритма Хаффмена.
курсовая работа [487,3 K], добавлен 14.07.2011Практическое решение технических задач и логического проектирования узлов ЭВМ: операция деления целых чисел в формате "Упакованное десятичное" на сумматоре прямого кода: блок-схемы алгоритма программы и её код. Понятие об инвертировании числа и кода.
курсовая работа [479,0 K], добавлен 24.06.2012Разработка утилиты кодирования и декодирования формата Base 64 в программной среде Linux с использованием компилятора. Написание программы на языке С++. Кодирование символьной строки любого набора байт в последовательность печатных ASCII символов.
курсовая работа [1,4 M], добавлен 10.09.2013Основные компоненты среды Delphi, используемые в программе для сжатия и восстановления файлов. Код программы, разбивка массива на промежутки. Проверка определенных элементов кодовых слов. Поиск кодовых слов в остатке. Результаты тестирования приложения.
курсовая работа [94,1 K], добавлен 19.12.2010Проектирование преобразователя кода (ПК), рассчет его энергопотребления и быстродействия. Составление таблицы истинности ПК. Написание булевых функций, минимизация и преобразование к выбранному базису. Составление структурной схемы преобразователя кода.
курсовая работа [775,3 K], добавлен 09.02.2009Файл как конечное количество последовательных байт, являющееся главной структурной единицей операционных систем, особенности и направления его использования, Основные режимы работы с файлами, порядок их открытия, принципы форматирования и закрытие.
презентация [382,2 K], добавлен 22.10.2013Создание программы для хранения и обработки данных о съеме/сдаче жилья. Написание программы на языке C++ с использованием библиотеки Qt; использование исходного кода для создания приложения под Windows, Linux, Mac OS X без дополнительных изменений кода.
курсовая работа [60,4 K], добавлен 07.03.2013Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.
курсовая работа [212,6 K], добавлен 25.02.2009Особенности разработки программы для ведения автоматизированной базы данных, организованной на информационных файлах. Тестовые наборы, проектирование кода программы. Принципы проведения испытаний и принципы проверки алгоритма на работоспособность.
лабораторная работа [1,6 M], добавлен 23.11.2014Расчет необходимого объема памяти для записи книги, количества символов в тексте. Создание шестнадцатеричного кода фамилии с помощью таблицы кодировки. Описание алгоритма получения электронного письма. Расположение чисел в порядке их возрастания.
контрольная работа [16,1 K], добавлен 05.07.2014Написание алгоритма приема 10 пакетов по 12 байт из последовательного порта и размещение их в памяти PRAM. Создание управляющего блока PTSCB для режима блоковой передачи данных. Аппаратная обработка прерываний в режима аналого-цифрового сканирования.
практическая работа [2,0 M], добавлен 25.04.2012Процесори ІA-32 дозволяють реалізувати різні моделі пам'яті. Найпростішу організацією має плоска модель пам'яті: уся пам'ять представляється єдиною лінійною послідовністю байт. Найскладнішою є сегментована захищена модель - основна модель пам'яті.
лекция [39,6 K], добавлен 13.04.2008Понятие фрактала, принципы создания изображения. Разработка алгоритма и режимов генерации ландшафта. Описание программы FracLandscapes.exe. в среде разработки Delphi 10. Примеры построения ландшафта с использованием различных режимов и количества изгибов.
курсовая работа [688,9 K], добавлен 04.05.2014
