Встраиваемые функции в Go

Go позволяет писать на ассемблере. Но авторы языка написали такую стандартную библиотеку, что бы этого делать не пришлось. Есть способы писать переносимый и быстрый код одновремено. Как? Добро пожаловат под cut.

Начать писать писать функции в на ассемблере в go очень просто. Для примера, объявим(forward declaration) функцию Add, которая складывает 2 int64:

func Add(a int64, b int64) int64

Это обычная функция, то тело функции отсутствует. Компилятор будет обосновано ругаться при попытке собрать пакет.

% go build
examples/asm
./decl.go:4:6: missing function body

Добавим файл с расширением .s и реализуем функцию на ассемблере.

TEXT ·Add(SB),$0-24
    MOVQ a+0(FP), AX
    ADDQ b+8(FP), AX
    MOVQ AX, ret+16(FP)
    RET

Теперь можно собрать, протестировать и использовать Add как обычную функцию. Этим широко пользуются сами разработчики языка в пакетах команды, не представленные в языке ^[1].
Но есть проблема — функции на asm не могут быть оптимизированы и встроены(inline). Без этого накладные расходы могут быть непозволительно большими.

var Result int64

func BenchmarkAddNative(b *testing.B) {
        var r int64
        for i := 0; i < b.N; i++ {
                r = int64(i) + int64(i)
        }
        Result = r 
}

func BenchmarkAddAsm(b *testing.B) {
        var r int64
        for i := 0; i < b.N; i++ {
                r = Add(int64(i), int64(i))
        }
        Result = r
}

BenchmarkAddNative-8   1000000000    0.300 ns/op
BenchmarkAddAsm-8       606165915    1.930 ns/op

Было несколько предложений для inline асемблера, как директива asm(...) в gcc. Ни оно из них не было принято. В место этого, в go добавили встаиваемые(intrinsic) функции.
Встраиваемые функции go написаны на обычном go. Но компилятору известно, что их можно заменить на что-то более оптимальное. В Go 1.13 встраиваемые функции содержатся в math/bits и sync/atomic.
Функции в этих пакетах имеют причудливые сигнатуры. Фактически они повторяют сигнатуры процессорных комманд. Это позволяет компилятору, если целевая архитектура поддерживает, прозрачно заменять вызовы функции на ассемблерные инструкции.
Ниже хочу рассказать о двух разных путях, которыми компилятор go создаёт более эффективный код с использовнием встроенных функций.

Population count

это количество единиц в двоичном представлении числа — важный криптографический примитив. Так как это важная операция, большинство современных cpu предосталяют реализацию в железе.
Пакет math/bits предоставляет эту операцию в функциях OnesCount*. Они распознаются и заменяются на инструкцию процессора POPCNT.
Что бы посмотреть, насколько это может быть эффективнее, давайте сравним 3 реализации. Первая — алгоритм Кернигана.

func kernighan(x uint64) (count int) {
	for x > 0 {
		count++
		x &= x - 1
	}
	return count
}     

Количество циклов алгоритма совпадает с количеством установленных бит. Больше бит — больше время выполнения, что потенциально приводит к утечке информации по сторонним каналам.
Второй алгоритм взят из книги Hacker’s Delight ^[2].

func hackersdelight(x uint64) uint8 {
	const m1 = 0b0101010101010101010101010101010101010101010101010101010101010101
	const m2 = 0b0011001100110011001100110011001100110011001100110011001100110011
	const m4 = 0b0000111100001111000011110000111100001111000011110000111100001111
	const h1 = 0b0000000100000001000000010000000100000001000000010000000100000001

	x -= (x >> 1) & m1
	x = (x & m2) + ((x >> 2) & m2)
	x = (x + (x >> 4)) & m4
	return uint8((x * h1) >> 56)
}

Стратегия «разделяй и властвуй» позволяет этой версии работать за O(log₂) от длинны числа, и за константное время от количества бит, что важно для криптографии. Давайте сравним производительность с math/bits.OnesCount64.

func BenchmarkKernighan(b *testing.B) {
	var r int
	for i := 0; i < b.N; i++ {
		r = kernighan(uint64(i))
	}
	runtime.KeepAlive(r)
}

func BenchmarkPopcnt(b *testing.B) {
	var r int
	for i := 0; i < b.N; i++ {
		r = hackersdelight(uint64(i))
	}
	runtime.KeepAlive(r)
}

func BenchmarkMathBitsOnesCount64(b *testing.B) {
	var r int
	for i := 0; i < b.N; i++ {
		r = bits.OnesCount64(uint64(i))
	}
	runtime.KeepAlive(r)
}

Что бы быть честным, мы передаём функциям одни и теже параметры: последовательность от 0 до b.N. Это справедливее к методу Кернигана, так как её время выполнения увеличивается с количеством бит входного аргумента. ➚

BenchmarkKernighan-4             	100000000	        12.9 ns/op
BenchmarkPopcnt-4                	485724267	         2.63 ns/op
BenchmarkMathBitsOnesCount64-4   	1000000000	         0.673 ns/op

math/bits.OnesCount64 выигрывает по скорости в 4 раза. Но действительно ли оно использует аппаратную реализацию, или компилятор просто лучше оптимизировал алгоритм из Hackers Delight? Пора залезть в assembler.

go test -c # компилируем тесты без запуска

Есть простая утилита для дизасемблирования go tool objdump, но я (в отличии от автора оригинальной статьи), воспользуюсь IDA.

Здесь много чего происходит. Самое важное: инструкция x86 POPCNT встроена в код самого теста, как мы и надеялить. Благодаря этому banchmark работает быстрее, чем альтернативы.
Интересно вот это ветвление.

cmp    cs:runtime_x86HasPOPCNT, 0
 jz    lable  

Да, это полифил на асемблере. Не все процессоры поддерживают POPCNT. При запуске программы, до вашего main функция runtime.cpuinit проверяет, есть ли необходимая инструкция и сохраняет в runtime.x86HasPOPCNT. Каждый раз программа проверяет, можно ли использовать POPCNT, или воспользоваться полифилом. Так как значение runtime.x86HasPOPCNT не меняется после инициализации, предсказание ветвления процессора отрабатывает относительно точно.

Атомарный счётчик

Встроенные(intrinsic) функции — это обычный код Go, они могут быть встроены(inline) в поток инструкций. Для примера сделаем из странных сигнатур функций пакета atomic абстракцию счётчика с методами.

package main

import (
	"sync/atomic"
)

type counter uint64

func (c *counter) get() uint64 {
	return atomic.LoadUint64((*uint64)(c))
}

func (c *counter) inc() uint64 {
	return atomic.AddUint64((*uint64)(c), 1)
}

func (c *counter) reset() uint64 {
	return atomic.SwapUint64((*uint64)(c), 0)
}

func F() uint64 {
	var c counter
	c.inc()
	c.get()
	return c.reset()
}

func main() {
	F()
}

Кто-то подумает, что такое ООП добавит накладные расходы. Но Go не Java — язык не использует связывание в runtime, если явно не использовать интерфейсы. Код выше будет свёрнут в эффективный поток процессорных инструкций. Как будет выглядеть main?

По порядку. c.inc превращается в lock xadd [rax], 1 — атомарное сложение x86. c.get становится обычной инструкцией mov, которая уже является атомарной в x86. c.reset становится атомарным обменом xchg между обнулённым регистром и памятью.

Заключение

Встраиваемые функции — аккуратное решение, которое предоставляет доступ к низкоуровневым операциям без расширения спецификации языка. Если архитектура не имеет специфических примитивов sync/atomic (как некоторые варианты ARM), или операций из math/bits, то компилятор вставляет полифил на чистом go.

Автор: Олег Шванн

Источник ^[3]