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.

Комментарии (3)


  1. mr_tron
    17.09.2019 14:04
    +1

    Не очень понятно всё-таки как это работает. Они просмо пометили в компиляторе, что вот у этих двух библиотек у конкретно этих функций есть ассемблерные реализации, которые надо использовать вместо кода на го и лежат при этом эти ассемблерные инструкции не в .s файлах а где-то еще?
    Вот просто есть у меня одна библиотека на го, которую используют в высоконагруженном коде и там очень важна производительность. И есть там очень много делений на константу дважды: один раз для получения результата деления и один раз для остатка. github.com/mr-tron/base58/blob/master/base58.go#L49
    Давно была мысль заменить это на ассемблерную инструкцию, которая возвращает сразу и результат деления и остаток.
    Ну я вот счас попробовал заменить
    tmp[j] = byte(carry % 58)
    carry /= 58


    на
    carry, t = bits.Div32(0, carry, 58)
    tmp[j] = byte(t)

    и получил сильное падение скорости.


    1. OlegSchwann Автор
      17.09.2019 23:45

      Стало интересно:
      Цикл на go

      for i = zcount; i < binsz; i++ {
      	j = size - 1
      	for carry = uint32(bin[i]); j > high || carry != 0; j-- {
      		carry = carry + 256*uint32(tmp[j])
      		tmp[j] = byte(carry % 58)
      		carry /= 58
      	}
      	high = j
      }
      Как он компилируется напрямую:
      movzx   r14d, byte ptr [r11+rsi]
      shl     r14d, 8
      add     r12d, r14d
      mov     r14d, 8D3DCB09h
      imul    r14, r12
      shr     r14, 25h
      imul    r15d, r14d, 3Ah
      sub     r12d, r15d
      mov     [rsi+r11], r12b
      dec     r11
      mov     r12, r14
      
      Как он компилируется с использованием bits.Div32:
      movzx   r14d, byte ptr [r11+rsi]
      shl     r14d, 8
      add     r14d, r12d
      nop
      mov     r15d, r14d
      shr     r14, 1
      mov     r12, rax
      mov     rax, 8D3DCB08D3DCB08Eh
      mul     r14
      shr     rdx, 4
      imul    r14, rdx, 3Ah
      sub     r15, r14
      mov     [rsi+r11], r15b
      dec     r11
      mov     rax, r12
      mov     r12, rdx
      mov     rdx, [rsp+60h+var_20]
      
      Количество вспомогательных mov инструкций стало больше, а количество умножений не уменьшилось. Но и пространства для оптимизации особо нет: 10 инструкций в нагруженном цикле.


  1. OlegSchwann Автор
    17.09.2019 23:45

    Не все intrinsic одинаково полезны.