Микрооптимизация, которая вам никогда не понадобится

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

Все началось с куска кода на Kotlin, который выглядел примерно так (в оригинальной версии использовались именованные константы, но я заменил их реальными значениями для наглядности в данном контексте):

fun bitsForSize(value: Int): Int {
    return when {
        value <= 0x01FFF -> 13
        value <= 0x07FFF -> 15
        value <= 0x0FFFF -> 16
        value <= 0x3FFFF -> 18
        else -> 0
    }
}

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

Вот результат компиляции в aarch64 с помощью ART:

mov  w16, #0x1fff
cmp  w1, w16
b.gt #+0xc (addr 0x1024)
mov  w0, #0xd
b    #+0x40 (addr 0x1060)
mov  w16, #0x7fff
cmp  w1, w16
b.gt #+0xc (addr 0x1038)
mov  w0, #0xf
b    #+0x2c (addr 0x1060)
mov  w2, #0x12
mov  w0, #0x10
mov  w16, #0xffff
cmp  w1, w16
cset w3, gt
mov  w16, #0x3ffff
cmp  w1, w16
csel w2, w2, wzr, le
cmp  w3, #0x0 (0)
csel w0, w2, w0, ne
ret

В нем нет ничего особенно интересного, но если присмотреться, то можно увидеть, что наши магические константы загружаются прямо в регистр w16 (например, в mov w16, #0x3ffff).

Мы можем немного улучшить этот код, сделав нечто противоположное интуиции — добавив дополнительный шаг перед тестами:

fun bitsForSize(value: Int): Int {
    val bits = value.countLeadingZeroBits()
    return when {
        bits >= 32 - 13 -> 13
        bits >= 32 - 15 -> 15
        bits >= 32 - 16 -> 16
        bits >= 32 - 18 -> 18
        else -> 0
    }
}

Вместо того чтобы проверять value напрямую, мы подсчитываем количество ведущих нулей в двоичном представлении value. Если посмотреть на двоичное представление всех целых чисел от 0 до 0x01FF, то можно заметить, что в нем всегда будет не менее 19 ведущих нулевых битов. Аналогичное наблюдение справедливо и для других магических констант в исходном коде.

Теперь, когда мы считаем биты, константы в наших тестах представляют собой гораздо меньшие числа. Например, вместо 0x3FFFF (262,143) мы теперь используем 14. Это помогает, потому что, когда константы достаточно малы, компилятор может закодировать их непосредственно внутри инструкции сравнения (cmp).

Каждое из ответвлений в исходной функции давало код aarch64 такого вида:

mov  w16, #0x7fff
cmp  w1, w16
b.gt #+0xc (addr 0x1038)

Сначала мы загружаем константу в регистр w16, затем сравниваем ее с регистром w1 и, наконец, выполняем ветвление.

Однако с нашей новой функцией каждое ответвление теперь выглядит следующим образом:

cmp  w0, #0x11 (17)
b.lt #+0xc (addr 0x1114)

Мы напрямую сравниваем константу (здесь 17) с регистром w0, а затем выполняем ветвление. Используя меньшие константы, мы смогли избавиться от mov на каждое ветвление, ценой дополнительного clz (подсчет ведущих нулей) в верхней части функции:

clz  w0, w1
cmp  w0, #0x13 (19)
b.lt #+0xc (addr 0x1104)
mov  w0, #0xd
b    #+0x34 (addr 0x1134)
cmp  w0, #0x11 (17)
b.lt #+0xc (addr 0x1114)
mov  w0, #0xf
b    #+0x24 (addr 0x1134)
mov  w2, #0x10
mov  w1, #0x12
cmp  w0, #0x10 (16)
cset w3, lt
cmp  w0, #0xe (14)
csel w1, w1, wzr, ge
cmp  w3, #0x0 (0)
csel w0, w1, w2, ne
ret

Поскольку clz занимает место одного из исходных mov, это чистый выигрыш, пока у нас есть более одного ответвления (а чем больше ответвлений, тем лучше). Оригинальная функция компилируется в 21 инструкцию aarch64, а новая версия — в 18.

Имеет ли это значение с точки зрения производительности? На современных устройствах вроде Pixel 8 разница составляет около ~0.5 % именно в этой функции. На старых/маломощных устройствах разница гораздо больше. На Pixel 2 она составляет около 11%.

Обратите внимание, что в оригинальной функции требовался один mov на константу, но это не значит, что так будет всегда. Например, если бы мы использовали константу 0x1_FFFF_0003_FFFEL, скомпилированный код выглядел бы так:

mov  x16, #0xfffffffffffffffe
movk x16, #0x3, lsl #16
movk x16, #0x1, lsl #48

Интересно, что компилятор «патчит» два 16-битных слова в более крупную константу, где все биты, кроме одного, уже установлены. Это позволяет компилятору минимизировать количество инструкций. С константой 0x5555_5555_5555_5555_5556L компилятор не может использовать этот трюк и вместо этого должен выдать 4 загрузки:

mov  x16, #0x5556
movk x16, #0x5555, lsl #16
movk x16, #0x5555, lsl #32
movk x16, #0x5555, lsl #48

Итак, теперь вы знаете, что меньшие константы могут быть дешевле — для какого-то крайне низкоуровневого и, скорее всего, не имеющего значения определения «дешевле».