Детальная информация

Тема выпускной квалификационной работы: «Реализация оптимизации Stream Fusion для языка Kotlin». Предметом исследования является оптимизация stream fusion и её применимость к языку программирования Kotlin. Целью данной работы является реализация оптимизации Stream Fusion для языка Kotlin. В рамках данной цели были поставлены следующие задачи: 1. Изучить существующие подходы к решению проблемы Stream Fusion оптимизации; 2. Рассмотреть имеющиеся реализации предложенных подходов; 3. На основе рассмотренных решений предложить собственную реализацию Stream Fusion оптимизации, применимую к языку Kotlin. В результате выполнения выпускной квалификационный работы была предложена реализация оптимизации Stream Fusion для языка Kotlin. Полученное решение позволяет описывать преобразования над списками лаконично в функциональном стиле, при этом получая высокопроизводительный императивный код в результате компиляции. На тестовых примерах решение с использованием написанной библиотеки работает в среднем в 8 раз быстрее аналогичных примеров с использованием средств стандартной библиотеки Kotlin и в 12 раз быстрее Java Stream API, уступая в производительности императивным циклам в общем случае только в 2 раза.

The theme of the final qualifying work: «Implementation of Stream Fusion optimization for the Kotlin language». The subject of the research is stream fusion optimization and its applicability to the Kotlin programming language. The aim of this work is to implement Stream Fusion optimization for the Kotlin language. The following tasks were set within the subject of this research: 1. Examine existing approaches to solving the problem of Stream Fusion optimization; 2. Consider the available implementations of the considered approaches; 3. Based on the considered solutions, propose an implementation of Stream Fusion optimization applicable to the Kotlin language; As a result of the final qualifying work, an implementation of Stream Fusion optimization for the Kotlin language was proposed. The resulting solution allows to describe transformations over lists in a laconic functional style, while obtaining high-performance imperative code as a result of compilation. On test examples, the solution using the written library works on average 8 times faster than similar examples using the tools of the Kotlin standard library and 12 times faster than the Java Stream API, yielding in performance to imperative loops in the general case only 2 times.

• ВВЕДЕНИЕ
• 1. Существующие подходы к оптимизации Stream Fusion
  • 1.1. Unfold/fold framework
  • 1.2. Deforestation оптимизация
  • 1.3. Shortcut Fusion
  • 1.4. Shortcut fusion — destroy/unfoldr
  • 1.5. Stream Fusion
  • 1.6. Staged Stream Fusion
  • 1.7. Резюме
• 2. Реализация оптимизации Stream Fusion для языка Kotlin
  • 2.1. Трансдьюсеры
  • 2.2. Оптимизация Stream Fusion на основе трансдьюсеров
  • 2.3. Реализация Stream Fusion оптимизации на основе трансдьюсеров
  • 2.4. Расширение базовой функциональности
    • 2.4.1. Ленивая функция transduce
    • 2.4.2. Слияние нескольких контекстов
  • 2.5. Промежуточные результаты
  • 2.6. Расширение компилятора Kotlin дополнительной фазой инлайнинга
    • 2.6.1. Реализация фазы инлайнинга для компилятора Kotlin
    • 2.6.2. Результаты
  • 2.7. Резюме
• 3. Тестирование производительности
  • 3.1. Тестовые примеры
  • 3.2. Тестовые данные
  • 3.3. Метод тестирования
  • 3.4. Системная информация
  • 3.5. Результаты экспериментов
  • 3.6. Холодный запуск тестов
  • 3.7. Аллокация объектов
  • 3.8. Резюме
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
• ПРИЛОЖЕНИЕ 1. ТАБЛИЦЫ
• ПРИЛОЖЕНИЕ 2. ЛИСТИНГИ