Встраиваемые функции в 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 как обычную функцию. Этим широко пользуются сами разработчики языка в пакетах runtime, math, bytealg, syscall, reflect, crypto. Это позволяет использовать аппаратные оптимизации процессора и команды, не представленные в языке.

Но есть проблема — функции на 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.

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.
Источник: https://habr.com/ru/post/467673/


Интересные статьи

Интересные статьи

Компании переполнили рынок товаров и услуг предложениями. Разнообразие наблюдается не только в офлайне, но и в интернете. Достаточно вбить в поисковик любой запрос, чтобы получить подтверждение насыще...
Бизнес-смыслы появились в Битриксе в начале 2016 года, но мало кто понимает, как их правильно использовать для удобной настройки интернет-магазинов.
«Функции высшего порядка» — это одна из тех фраз, которыми часто разбрасываются. Но редко кто может остановиться и объяснить, что это такое. Возможно, вы уже знаете, что называют функциями высш...
Реализация ORM в ядре D7 — очередная интересная, перспективная, но как обычно плохо документированная разработка от 1с-Битрикс :) Призвана она абстрагировать разработчика от механики работы с табл...
Мы публикуем видео с прошедшего мероприятия. Приятного просмотра.