Аннотация Прямая трансляция примитивных каждый тип представляется в виде класса, и поэтому, типов языка Kotlin в примитивные типы LLVM IR например, возможно вызывать методы из целых чисел: целевого промежуточного представления бэкенда Kotlin/Native не всегда возможна. В таких слу- 1 va l x = 1 8 . plus ( 2 4 ) // x == 42 чаях компилятору требуется сгенерировать операции запаковки для получения переменных типовоберток из переменных примитивных типов или операции распаковки для обратного преобразования, что сказывается на производительности кода и потреблении памяти. В данной статье рассматриваются источники запаковок в Kotlin/Native и предлагаются способы их возможного устранения. Полученные результаты свидетельствуют об эффективности реализованных оптимизаций.
Однако компилятор не всегда может представить значение примитивного типа в Kotlin в виде значения примитивного типа в целевом представлении. В таких случаях он генерирует операцию запаковки операцию исполнения некоторой функции, которая принимает значение примитивного типа и возвращает экземпляр класса-обертки. Например, для запаковки переменной типа Int Kotlin/JVM генерирует инструкцию
Index Terms Примитивные типы, запаковка, спе- invokestatic, которая вызывает статическую функцию циализация, статический анализ. Integer.valueOf языка Java. Kotlin/Native же сгенерирует вызов специальной функции <Int-box>, которая
I. Введение вернет специальную структуру ObjHeader, являющуюKotlin современный язык программирования, од- ся универсальным представлением классов из Kotlin. ной из ключевых особенностей которого является муль- В данном случае структура содержит само число, а типлатформенность возможность компилировать ис- также run-time информацию о классе Int, такую как ходный код в разные представления, специфичные для информация о суперклассе и полное имя пакета, в разных платформ. Первая версия языка, Kotlin 1.0, бы- котором класс объявлен. ла представлена в феврале 2016 года и поддерживала Зачастую требуется выполнить обратную операцию только компиляцию в байткод виртуальной машины и из экземпляра класса-обертки получить значение Java. В настоящее время компилятор Kotlin имеет три примитивного типа. В этой ситуации компилятору требэкенда и, помимо генерации JVM-байткода, поддер- буется сгенерировать функцию распаковки данного экживает транспиляцию в JavaScript, а также генерацию земпляра. В Kotlin/Native это обеспечивается за счет машинного кода. вызова функции <T-unbox>, где T название примиЗа последнее отвечает бэкенд, именуемый тивного типа.
Kotlin/Native1. Он компилирует Kotlin IR Таким образом, получение обертки над значением промежуточное представление, генерируемое примитивного типа требует одного или двух вызовов фронтендом компилятора Kotlin, в LLVM IR дополнительных функций, а также выделения памяти платформонезависимое промежуточное представление, в куче для хранения экземпляра класса-обертки, что, которое, в свою очередь, уже с помощью в свою очередь, увеличивает нагрузку на сборщик инфраструктуры LLVM можно скомпилировать в мусора. Еще одним неприятным фактом является то, машинный код под любую архитектуру. что в целевом представлении операции над примитивВ LLVM IR, как и в JVM-байткоде, существует под- ными типами будут представлены как вызовы методов держка примитивных типов, например, тип i32 пред- классов-оберток, а это дополнительный уровень косставляет 32-битное целое число, а тип double 64- венности и дополнительные затраты на поиск в таблице битное число с плавающей точкой. В самом Kotlin методов. нет разделения на примитивные типы и типы-обертки: Если рассматривать оптимизирующую компиляцию, выполняемую со стороны LLVM, то даже в этом случае 1https://kotlinlang.org/docs/reference/native-overview.html в скомпилированном коде остаются операции выделе
ния памяти под объект-обертку и получения значения из обертки, что мешает проводить ряд некоторых дру- 12 fun <r Tet u: r nComifpa(raab<le<b T)>>a melinse( a b: T, b : T) : T { гих оптимизаций, например, склеивание избыточных 3 } инструкций2.
Данная работа посвящена тому, как компилятор Kotlin/Native может уменьшить количество генерируемых запаковок. В разделе II рассказывается о том, каким образом осуществляется подсчет количества запаковок, и какой код привносит излишние запаковки. В разделах III-V описываются причины излишних запаковок, формулируются подходы к решению. В разделе VI обозреваются существующие решения. Раздел VII описывает реализацию предложенных оптимизаций, в разделе VIII приводится оценка их эффективности.
Однако обобщения не поддерживаются в LLVM IR, поэтому компилятор Kotlin/Native производит стирание типа. В результате параметры функции, как и возвращаемое значение, становятся указателями на ObjHeader. Ввиду того, что тело функции в LLVM IR получается слишком громоздким, ниже приведено его словесное описание: 1) Вычисляется адрес реализации метода
Comparable.compareTo для типа, указанного в структуре ObjHeader, соответствующей первому параметру функции; II. Анализ количества запаковок 2) Найденный метод вызывается с аргументами, соответствующими параметрам функции; Для измерения точного количества запаковок, со- 3) Как и в Java, результат сравнения compareTo вывершенных функцией во время ее выполнения, в ком- ражается в знаке возвращаемого целочисленного пилятор был добавлен дополнительный опциональный значения. В зависимости от этого знака, функция этап понижений (lowerings). Суть его заключается в возвращает либо первый, либо второй параметр. добавлении глобального счетчика типа Int с общим При передаче в функцию min двух целочисленных связыванием3. В начало каждой функции, выполня- значений они будут запакованы в тип-обертку, так как ющей запаковку, добавляется вызов функции Int.inc, функция не может работать с примитивными типами. увеличивающей значение счетчика. Теперь рассмотрим следующую функцию: Подсчет запаковок осуществляется только для функций, имеющих аннотацию @CountBoxings. Тело анноти- 1 fun minInt ( a : Int , b : I nt ) : I n t { 2 r e t u r n i f ( a < b ) a e l s e b рованной функции оборачивается в блок try-finally, пе- 3 } ред началом блока добавляется инструкция обнуления счетика, а в тело finally записывается вызов функции Она отличается от предыдущей только тем, что println, печатающей значение счетчика в стандартный может принимать только аргументы типа Int. Так поток вывода. как данной функции уже не требуется стирание тиАнализ осуществляется на существующих в компи- пов, Kotlin/Native генерирует довольно прямолинейное ляторе Kotlin/Native наборах тестов производительно- представление: сти. Были найдены следующие источники запаковок: 1 entry : 1) Передача значений примитивных типов в обоб- 23 %%67 == llooaadd ii3322 ,, ii 33 22 ** %%pp-- ba щенные функции и методы обобщенных классов, 4 %8 = icmp s l t i 3 2 %6, %7 в том числе и передача в лямбда-функции; 5 br i 1 %8, l a b e l %when_case , 2) Проверка на null значений примитивных типов, 6 l a b e l %when_next
не являющихся nullable-типами. 78 when_case : При этом в Kotlin/Native уже существует ряд оп- 9 %9 = load i32 , i 3 2 * %p- a тимизаций, направленных на снижение количества за- 10 br l a b e l %when_exit 11 паковок, например, наличие кеша (cache) для оберток 12 when_exit : над небольшими числами и преобразование методов 13 %10 = phi i 3 2 [ %9, %when_case ] , equals, hashCode, toString классов-оберток в функции, 1145 br l a b e l %epilo[ g%ue11 , %when_next ] принимающие вместо оберток значения примитивных 16 типов. 17 when_next : 18 %11 = load i32 , i 3 2 * %p- b 19 br l a b e l %when_exit III. Передача значений примитивных типов в 20
обобщенные функции и классы 2212 e p %il1o2g =ue p:hi i 3 2 [ %10 , %when_exit ] Язык Kotlin поддерживает концепцию обобщенных 23 r e t i 3 2 %12 (generic) классов и функций. Например, следующая функция может принимать значения любого типа, реализующего интерфейс Comparable:
2https://llvm.org/docs/Passes.html#instcombine-combineredundant-instructions 3https://llvm.org/docs/LangRef.html Буквально, два числа сравниваются при помощи встроенной инструкции icmp (строка 4), и, в зависимости от результата сравнения (phi-инструкция, строка 13), возвращается одно из этих чисел (строка 23).
Функцию minInt можно получить из функции min автоматически во время компиляции: если компилятор встречает вызов вида min(x, y), где x и y имеют тип Int, то он может создать копию функции min, изменить имя копии на minInt, удалить в ней параметр T и заменить все его вхождения на конкретный тип Int, после чего изменить сам вызов функции min на вызов функции minInt; иными словами, специализировать функцию min для типа Int.
Подобные трансформации можно осуществлять и для классов. В следующем примере класс MyPairIntDouble является специализацией класса MyPair для типов Int и Double, и создание его экземпляра не требует никаких запаковок: 1 c l a s s MyPair<S , T>( 2 va l f i r s t : S , 3 va l second : T 4 ) 5 6 c l a s s MyPairIntDouble ( 7 va l f i r s t : Int , 8 va l second : Double 9 )
Для некоторых классов в Kotlin уже существуют специализированные версии. Например, вместе с обобщенным классом Array<T> реализованы дополнительные версии для примитивных типов: IntArray, LongArray и так далее.
IV. Повторные запаковки и их удаление Одна и та же переменная может запаковываться несколько раз. Подобная ситуация может произойти не только по вине программиста, но также после других оптимизаций, таких как специализация, описанная выше, или встраивание (inlining) функций.
Для примера рассмотрим следующие две функции: 7 8 9 }
T) { i f ( x in l i s t ) r e t u r n l i s t += x 2 3 4 } 5
I nt ) { i f ( x in l i s t ) r e t u r n l i s t += x
Данная задача является частным случаем forward-анализа доступных выражений (Available Expressions) [1][2]. Для каждой вершины графа потока управления этот анализ определяет, какие подвыражения в данной вершине гарантированно уже были вычислены ранее в коде. Эта информация позволяет не пересчитывать несколько раз одно и то же выражение, а записать значение выражения в отдельную переменную и использовать ее вместо повторного вычисления.
Результат анализа для вершины v набор доступных выражений рассчитывается по формуле v = J K
\ u∈ pred(v)
JuK ∪ gen(u) \ kill(u) , где gen(u) выражения, созданные в вершине u, kill(u) выражения, изменившиеся в u и переставшие быть доступными.
То есть, чтобы получить доступные выражения для вершины v, нужно для каждой вершиныпредшественника u: 1) рекурсивно вычислить доступные выражения в u; 2) добавить к доступным выражениям те, что созда
ются в u; 3) убрать из доступных выражений те, что содержат
переменные, изменяющиеся в u, после чего оставить только те выражения, которые доступны для каждой вершины u.
Данный анализ не считает выражения, вычисляемые внутри цикла, доступными для вершин вне этого цикла, так как он не может гарантировать, что количество итераций цикла всегда строго положительное и что при каждом исполнении программы его тело будет исполнено хотя бы один раз. Как следствие, запаковку одной и той же переменной в теле цикла не получится вынести за его пределы. Для этого нужно проводить дополнительные оптимизации, такие как вынос инварианта за пределы цикла (Loop Invariant Code Motion) [1].
V. Избыточные проверки на null
Во всех трех случаях компилятор запаковывает выражение в левой части операнда, так как работает в
A. Специализация классов и функций Стоит отметить, что оптимизации LLVM удаляют Для реализации был выбран вариант явного аннотипроверки на null в данных примерах, однако операции рования классов и функций, которые требуется специазапаковок и распаковок остаются. лизировать. Была реализована аннотация @Specialized для типовых параметров, принимающая массив клас
VI. Обзор существующих решений сов примитивных типов, для которых нужно сгенериСуществует несколько способов обеспечения авто- ровать специализированные версии. Однако на данный матической специализации функций и классов. Один момент невозможно аннотировать типовые параметры из них создание специализированной версии ¾по класса, поэтому вместе со @Specialized добавлена аннонеобходимости¿, то есть, только в том случае, если ком- тация для классов @SpecializedСlass. пилятор обнаружил вызов обобщенной функции или В компилятор были добавлены два дополнительных создание экземпляра обобщенного класса с примитив- этапа понижений. На первом этапе происходит непоными типовыми аргументами. Так работает, например, средственно генерация новых функций и классов, за инстанцирование шаблонов в C++ и мономорфизация что отвечают две сущности специализатор и элиобобщений в Rust. Подобная стратегия предполага- минатор типовых параметров. Специализатор обходит ется и при специализации классов и интерфейсов в промежуточное представление кода и для текущей влоязыке Java, реализация которой находится на стадии женности объявлений запоминает, какие типовые параразработки как одна из частей Project Valhalla4. В метры заменены на конкретные примитивные типы и .NET CLR загрузка специализированных объявлений что это за примитивные типы. Таким образом, во время осуществляется на стадии связывания (linking) [3]. обхода поддерживаются две структуры: отображение Другой способ дать возможность явно указать, для M вида ¾типовой параметр аргумент, являющийся каких классов и функций, каких типовых параметров конкретным примитивным типом¿ и список L послеи для каких конкретных примитивных типов компи- довательных конкретных примитивных типов. Когда лятор должен сгенерировать специализацию. Подобная специализатор обнаруживает, что данное объявление функциональность была реализована в языке Scala в (класс или функцию) необходимо специализировать, версии 2.8 [4]. Типовой параметр может быть проанно- он передает это объявление, а также отображение M тирован специальной аннотацией @specialized, которая и список L в качестве параметров элиминатору. Элиуказывает, что компилятор должен сгенерировать по минатор копирует это объявление, заменяя типовые копии класса на каждый примитивный тип, существу- параметры на конкретные типы согласно отображеющий в языке. Аннотация может принимать парамет- нию M. Типы из L в элиминаторе используются для ры, являющиеся классами примитивных типов; в этом кодирования имени специализированной версии, что случае компилятор сгенерирует специализации только позволяет избежать конфликтов имен. для тех типов, что присутствуют среди параметров. Полученная специализированная версия передаетПри этом компилятор создает специализации, основы- ся специализатору, который осуществляет обход этоваясь на аннотации, а не на реальной необходимости. го объявления для рекурсивного поиска вложенных специализированных объявлений, после чего добавляет
cr.openjdk.java.net/~briangoetz/valhalla/specialization.html
VII. Реализация
Предположим, что это весь код, содержащийся в файле, и что структуры M и L пусты.
1) Класс A нужно специализировать. Сам класс, а также структуры M = { S → Int} и L = [Int] передаются элиминатору. 2) Элиминатор создает класс A-Int без типовых па
раметров и возвращает его специализатору; 3) Во время рекурсивного обхода класса A-Int обнаруживается, что необходимо специализировать вложенный класс B. В элиминатор передается B, а также структуры M = { S → Int, T → Float} и
L = [Int, Float]; 4) Элиминатор создает внутри класса A-Int класс
B-Int-Float без типовых параметров; 5) После посещения класса B-Int-Float специализатор добавляет этот класс в A-Int и запоминает тройку (B, [Int, Float], B-Int-Float); C. Удаление проверок на null 6) После посещения класса A-Int специализатор до- После этапа встраивания функций каждый вызов бавляет этот класс в промежуточное представле- elvis-оператора проверяется на то, имеет ли его левая ние файла и запоминает тройку (A, [Int], A-Int); часть nullable-тип, и если не имеет, то весь вызов заме7) Специализатор продолжает посещение обобщен- няется на возвращение его левого операнда. Так, тело ного класса A. Важно заметить, что структура M функции f1 заменяется на возвращение переменной x. на данном шаге пуста, а L = [null]; Трансформация вызова elvis-оператора, у которого 8) Во время обхода класса A посещается вложенный в левой части находится цепочка безопасных вызовов класс B. В элиминатор передается B, а также (safe call chain), как в функции lowered_f3 из раздела V, структуры M = { T → Float} и L = [null, Float]; использует идеи из [6]. Ее можно описать следующим 9) Элиминатор создает класс B-Float без типовых алгоритмом.
параметров; Обозначим как [tmp, a, b, c] выражение 10) После посещения класса B-Float специализатор 1 va l tmp = i f ( a == n u l l ) b e l s e c добавляет этот класс в A и запоминает тройку (B, [null, Float], B-Float); обход файла завершается. Тогда [tmp2, [tmp, a, null, c], b, tmp] эквивалентно На втором этапе происходит замена типов и выра- [tmp2, a, b, c]. Таким образом, собрав во время прохода жений в соответствии с созданными специализациями. по elvis-оператору соответствующие значения a, b Для замены используются тройки из T. Например, и c, можно получить новую, сокращенную версию если где-то в коде встретилось выражение val b = проверки на null. В частности, в функции lowered_f3 A<Int>.B<Float>(), то компилятор определяет, что a соответствует параметру value, b соответствует создается экземпляр класса B, и что типовые аргумен- числу 0, а c соответствует получению свойства ты образуют последовательность [Int, Float]. Согласно value.x. Можно заметить, что [tmp, value, 0, value.x] Таблица I: Оценка эффективности построения специализаций раскрывается в выражение, эквивалентное телу функции better_f3 из раздела V.
VIII. Эксперименты Тестирование производительности при необходимости осуществляется на псевдослучайных целых числах от 0 до 109 и на псевдослучайных числах с плавающей точкой от 0.0 до 1000000.0. Каждый из этих тестов включает в себя 1000000 итераций тестируемых действий. Компиляция тестов производительности осуществляется с флагом -opt, который включает оптимизации компилятора Kotlin/Native и набор оптимизаций -O3 на стороне LLVM. Для тестирования используется существующий в Kotlin/Native модуль измерения производительности. Подсчет запаковок производится отдельно, так как инструментирование функций может повлиять на цикл оптимизаций и исказить результаты.
Результаты измерения эффективности построения специализаций приведены в Таблице I. В тестах Matrix2 и Matrix3 осуществляется создание обобщенных матриц размером 2 × 2 и 3 × 3, параметризованных целыми числами, и вычисление сумм их элементов. В тесте ListMin осуществляется создание обобщенного списка на базе обобщенного массива Array<T>, параметризованного целыми числами, и применение к нему обобщенной функции высшего порядка reduce, которая в данном случае вычисляет минимум. В тесте SatisfiesAll осуществляется последовательное применение предикатов делимости на 2, 3 и 5 к набору чисел. Во всех этих тестах обобщенные объявления аннотированы @Specialized/@SpecializedClass и предоставляют специализацию для типа Int.
Стоит поподробнее остановиться на тестах Mapper1, Mapper2 и Mapper3. Каждый тест включает в себя обобщенный функциональный интерфейс Mapper<T>, предоставляющий функцию map: (T) → T, и три обобщенных класса-реализации: два простых и один составной, CompositeMapper, принимающий две произвольные реализации Mapper (mapperFirst и mapperSecond ) и осуществляющий их композицию: 1 fun map( v a l u e : T) = secondMapper . map(←
f i r s t M a p p e r . map( v a l u e ) ) Суть тестов заключается в применении функций описанных классов к различным числам. В тесте Mapper1 все четыре объявления предоставляют специализацию для типа Int, и функции применяются к целым числам, поэтому при включенной специализации запаковки не генерируются. Тест Mapper2 отличается от Mapper1 тем, что функции применяются к значениям типа Double, но, так как специализация для типа Double не предоставляется, вызываются обобщенные версии классов, и компилятор генерирует запаковки.
Тест Mapper3 также похож на Mapper1, но в нем класс CompositeMapper предоставляет специализацию только для типа Double, а остальные классы предоставляют специализацию только для типа Int. Если явно выделить запаковки и распаковки, то исполнение функции CompositeMapper.map будет иметь вид: 1 fun map( v a l u e : T) = box< 2 secondMapper . map( 3 unbox<box< 4 f i r s t M a p p e r . map( unbox<value >) 5 >> 6 ) 7 >
Таким образом, вызов функции CompositeMapper.map требует одну запаковку аргумента и две запаковки значений внутри самой функции. При этом все запаковки различны, и алгоритм удаления повторных запаковок не уменьшит их количество.
Заметим, что размер кода немного уменьшился при компилировании со специализацией. Это вызвано тем, что и на стороне Kotlin/Native, и на стороне LLVM производится операция удаления мертвого кода (Dead Code Elimination, DCE). При включенной специализации тесты производительности используют специализированные версии классов и функций, поэтому обобщенные версии удаляются, а размеры специализированных версий меньше, чем размеры оригиналов.
В Таблице II приведен результат проверки эффективности удаления повторных запаковок для функции putIfAbsent из раздела IV. Результат показывает, что в некоторых случаях алгоритм действительно позволяет убрать излишние запаковки, привнесенные специализацией.
В Таблице III приведен результат проверки эффекТаблица II: Оценка эффективности применения оптимизаций для функции putIfAbsent Без оптимизаций Со специализацией Со специализацией + удалением повторных запаковок Время работы 2342 ± 16.8ms 2917 ± 21.4ms 2389 ± 17.1ms
Кол-во запаковок специализированных классов и функций в неспециализированных обобщенных объявлениях, и исследование способов решения этой проблемы является интересным направлением дальнейших исследований. В частности, можно рассмотреть вариант неявной специализации подобных обобщенных объявлений и вариант поддержки подобного кода со стороны фронтенда компилятора и IDE в виде предупреждений и инспекций.
Сопутствующей работой является расширение количества специализируемых классов и функций, проверка компилируемости и сохранения семантики на все более сложных конструкциях, а также специализация коллекций стандартной библиотеки.
Второе направление исследований заключается в улучшении алгоритма удаления повторных запаковок, а именно поддержке циклов и изменяемых переменных.
Наконец, некоторые предложенные оптимизации, такие как специализация классов и функций, не являются специфичными для Kotlin/Native, и их можно реализовать и для других бэкендов.
Ссылка на репозиторий: https://github.com/ gascogen/kotlin-native/tree/opt-boxing.
Список литературы
В ходе работы была реализована метрика, позволяющая вычислить точное количество запаковок, осущественных во время исполнения тестовых функций. С помощью данной метрики было найдено несколько источников излишних запаковок, возникающих в тестах производительности, рассмотрены возможные способы их устранения. Реализованы следующие оптимизации: специализация классов и функций по явным пользовательским аннотациям, поиск и удаление повторных запаковок неизменяемых переменных, удаление избыточных запаковок при проверке на null. Выполнено измерение производительности набора программ до оптимизаций и после. Поддержана трансляция обобщенных классов и функций в существующие специализированные версии во время специализации. Реализованы некоторые специализации для функциональных интерфейсов.
При проведении экспериментов было установлено, что специализация может увеличить количество запаковок, и среди них не будет повторных (как в примере с тестом Mapper3 ). Проверка гипотезы, что такие ситуации преимущественно связаны с использованием
Abstract—Direct translation from primitive types in Kotlin to primitive types in LLVM IR — targeted intermediate representation of Kotlin/Native backend — is not always possible. In these cases compiler must generate box operations to get wrapped variables from variables of primitive types, or unbox operations to perform an inverse tranformation, which affects code performance and memory consumption. In this paper we will review some sources of boxings performed by Kotlin/Native and suggest several ways of their possible elimination. Obtained results indicate the efficiency of implemented optimizations.