Оптимизация abs() для типов int64 в Golang

Go

Оптимизирован для типа int64 в Golang.abs()функция, оригинал:Optimized abs() for int64 in Go

предисловие

В языке Go нет встроенногоabs()Стандартные функции для вычисления абсолютного значения целого числа, где абсолютное значение относится к неотрицательному представлению отрицательных и положительных чисел.

я недавно решилAdvent of Code 2017вершинаDay 20проблема, понял одинabs()функция. Если вы хотите узнать что-то новое или попробовать свои силы в этом, проверьте это.

Go на самом деле ужеmathреализовано в пакетеabs() : math.Abs, но это не относится к моей проблеме, потому что его типы входных и выходных значений обаfloat64, что мне нужно этоint64. Можно использовать преобразование параметров, но изменитьfloat64Преобразовать вint64Будут некоторые накладные расходы, и числа с большими значениями конверсии будут усечены, и то, и другое будет разъяснено в статье.

ПочтаPure Go math.Abs outperforms assembly versionОбсуждается, как оптимизировать числа с плавающей запятой.math.Abs, но эти методы оптимизации нельзя напрямую применить к целым числам из-за различных базовых кодировок.

Исходный код и тестовые случаи в статье находятся вcavaliercoder/go-abs

Преобразование типов VS метод управления ветвями

Для меня простейшая реализация функции для получения абсолютного значения: если входной параметр n больше или равен 0, он возвращает n напрямую, а если он меньше нуля, он возвращает -n (отрицательное число обратно положительное ) Эта функция получения абсолютного значения зависит от структуры управления ветвями для расчета. Абсолютное значение называется:abs.WithBranch

package abs

func WithBranch(n int64) int64 {
	if n < 0 {
		return -n
	}
	return n
}

успешно возвращает абсолютное значение n, т.е.Go v1.9.x math.AbsРеализация, которая принимает абсолютное значение float64. Однако, когда выполняется преобразование типа (int64 в float64) и берется абсолютное значение, есть ли улучшения в версии 1.9.x? Мы можем это проверить:

package abs

func WithStdLib(n int64) int64 {
	return int64(math.Abs(float64(n)))
}

В приведенном выше коде измените n сint64Превратиться вfloat64,пройти черезmath.AbsВозьмите абсолютное значение, а затем вернитесьint64, многочисленные преобразования, очевидно, влекут за собой снижение производительности. Вы можете написать тест, чтобы проверить это:

$ go test -bench=.
goos: darwin
goarch: amd64
pkg: github.com/cavaliercoder/abs
BenchmarkWithBranch-8           2000000000               0.30 ns/op
BenchmarkWithStdLib-8           2000000000               0.79 ns/op
PASS
ok      github.com/cavaliercoder/abs    2.320s

Результат теста: 0,3 нс/оп,WithBranchОн более чем в два раза быстрее и имеет то преимущество, что при преобразовании больших чисел из int64 в float64 в стандарте IEEE-754 не происходит усечения (потери неточных значений).

Например:abs.WithBranch(-9223372036854775807)правильно вернет 9223372036854775807. ноWithStdLib(-9223372036854775807)Затем происходит переполнение в диапазоне преобразования типов и возвращается -9223372036854775808. Когда вводится большое положительное число,WithStdLib(9223372036854775807)Также возвращает неверные отрицательные результаты.

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

Все мы знаем, что код, который не опирается на методы управления ветвлениями, искажает порядок выполнения программы, т.е.pipelining processorsСледующее действие программы невозможно предсказать.

Сценарии, отличающиеся от подходов, не основанных на управлении ветвями

Восторг хакераВ главе 2 представлен метод безответственного управления с помощьюДополнение до двухВычисляет абсолютное значение целого числа со знаком.

Чтобы вычислить абсолютное значение x:

  1. Рассчитать сначалаx >> 63, то есть x сдвигается вправо на 63 бита (чтобы получить старший бит знака).Если вы знакомы с целыми числами без знака, вы должны знать, что если x отрицательное, то y равно 1, иначе y равно 0

  2. пересчитывать(x ⨁ y) - y: XOR x и y минус y является абсолютным значением x.

    Его можно реализовать напрямую с помощью эффективного ассемблера, код выглядит следующим образом:

func WithASM(n int64) int64

// abs_amd64.s
TEXT ·WithASM(SB),$0
  MOVQ    n+0(FP), AX     // copy input to AX
  MOVQ    AX, CX          // y ← x
  SARQ    $63, CX         // y ← y >> 63
  XORQ    CX, AX          // x ← x ⨁ y
  SUBQ    CX, AX          // x ← x - y
  MOVQ    AX, ret+8(FP)   // copy result to return value
  RET

Сначала назовем эту функцию какWithASM, отдельное наименование и реализация, использование тела функцииСборка в GoРеализация, приведенный выше код применим только к системе с архитектурой AMD64, я предлагаю вам добавить имя файла_amd64.sсуффикс.

WithASMРезультаты тестов для:

$ go test -bench=.
goos: darwin
goarch: amd64
pkg: github.com/cavaliercoder/abs
BenchmarkWithBranch-8           2000000000               0.29 ns/op
BenchmarkWithStdLib-8           2000000000               0.78 ns/op
BenchmarkWithASM-8              2000000000               1.78 ns/op
PASS
ok      github.com/cavaliercoder/abs    6.059s

Это смущает, этот простой бенчмарк показывает, что код с очень компактной структурой управления без ветвлений работает очень медленно: 1,78 нс/оп, как такое может быть?

параметры компиляции

Нам нужно знать, как компилятор Go оптимизирует выполнениеWithASMфункция, компилятор принимает-mпараметр для печати оптимизированного содержимого, вgo buildилиgo testплюс-gcflags=-mиспользовать:

текущий результат:

$ go tool compile -m abs.go
# github.com/cavaliercoder/abs
./abs.go:11:6: can inline WithBranch
./abs.go:21:6: can inline WithStdLib
./abs.go:22:23: inlining call to math.Abs

Для нашей простой функции компилятор Go поддерживаетfunction inlining, встраивание функции означает использование тела этой функции напрямую вместо вызова нашей функции. Например:

package main

import (
  "fmt"
  "github.com/cavaliercoder/abs"
)

func main() {
  n := abs.WithBranch(-1)
  fmt.Println(n)
}

будет фактически скомпилирован в:

package main

import "fmt"

func main() {
  n := -1
  if n < 0 {
  	n = -n
  }
  fmt.Println(n)
}

По выводу компилятора видно, чтоWithBranchиWithStdLibвстраивается во время компиляции, ноWithASMнет. заWithStdLib, даже если базовый вызовmath.AbsНо он все еще встроен во время компиляции.

так какWithASMФункции не могут быть встроены, и каждая вызывающая их функция влечет за собой дополнительные накладные расходы на вызов:WithASMПерераспределить память стека, скопировать параметры и указатели и т. д.

Что, если мы не будем использовать встраивание в других функциях? Можно написать простую примерную программу:

package abs

//go:noinline
func WithBranch(n int64) int64 {
	if n < 0 {
		return -n
	}
	return n
}

Перекомпилируйте, и мы увидим, что компилятор меньше оптимизирует:

$ go tool compile -m abs.go
abs.go:22:23: inlining call to math.Abs

Сравнительные результаты:

$ go test -bench=.
goos: darwin
goarch: amd64
pkg: github.com/cavaliercoder/abs
BenchmarkWithBranch-8           1000000000               1.87 ns/op
BenchmarkWithStdLib-8           1000000000               1.94 ns/op
BenchmarkWithASM-8              2000000000               1.84 ns/op
PASS
ok      github.com/cavaliercoder/abs    8.122s

Видно, что среднее время выполнения трех функций теперь составляет около 1,9 нс/операцию.

Вы можете подумать, что накладные расходы на вызов каждой функции составляют около 1,5 нс, появление этих накладных расходов нас сводит на нет.WithBranchПреимущество скорости в функциях.

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

Используйте только одну встроенную функцию

Компилятор Go не может встраивать функции, реализованные на ассемблере, но нашу обычную функцию легко встроить после перезаписи:

package abs

func WithTwosComplement(n int64) int64 {
	y := n >> 63          // y ← x >> 63
	return (n ^ y) - y    // (x ⨁ y) - y
}

Результат компиляции показывает, что наш метод встроенный:

$ go tool compile -m abs.go
...
abs.go:26:6: can inline WithTwosComplement

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

$ go test -bench=.
goos: darwin
goarch: amd64
pkg: github.com/cavaliercoder/abs
BenchmarkWithBranch-8               2000000000               0.29 ns/op
BenchmarkWithStdLib-8               2000000000               0.79 ns/op
BenchmarkWithTwosComplement-8       2000000000               0.29 ns/op
BenchmarkWithASM-8                  2000000000               1.83 ns/op
PASS
ok      github.com/cavaliercoder/abs    6.777s

Теперь накладные расходы на вызов функции исчезли,WithTwosComplementреализация, чемWithASMреализация намного лучше. Посмотрим, что компилирует компилятор.WithASMчто ты сделал?

использовать-SАргумент говорит компилятору распечатать процесс сборки:

$ go tool compile -S abs.go
...
"".WithTwosComplement STEXT nosplit size=24 args=0x10 locals=0x0
        0x0000 00000 (abs.go:26)        TEXT    "".WithTwosComplement(SB), NOSPLIT, $0-16
        0x0000 00000 (abs.go:26)        FUNCDATA        $0, gclocals·f207267fbf96a0178e8758c6e3e0ce28(SB)
        0x0000 00000 (abs.go:26)        FUNCDATA        $1, gclocals·33cdeccccebe80329f1fdbee7f5874cb(SB)
        0x0000 00000 (abs.go:26)        MOVQ    "".n+8(SP), AX
        0x0005 00005 (abs.go:26)        MOVQ    AX, CX
        0x0008 00008 (abs.go:27)        SARQ    $63, AX
        0x000c 00012 (abs.go:28)        XORQ    AX, CX
        0x000f 00015 (abs.go:28)        SUBQ    AX, CX
        0x0012 00018 (abs.go:28)        MOVQ    CX, "".~r1+16(SP)
        0x0017 00023 (abs.go:28)        RET
...

компилятор компилируетWithASMиWithTwosComplementВ это время то, что сделано, слишком похоже, и компилятор имеет преимущество правильной настройки и кроссплатформенности в это время.Можно добавитьGOARCH=386возможность повторной компиляции для создания программ, совместимых с 32-битными системами.

Наконец, что касается распределения памяти, реализация всех вышеперечисленных функций — идеальная ситуация.go test -bench=. -benchme, и наблюдение за выводом каждой функции показывает, что выделения памяти не произошло.

Суммировать

WithTwosComplementРеализация обеспечивает лучшую переносимость в Go, обеспечивая встраивание функций, код без ветвлений, нулевое выделение памяти и избегая усечения значений, вызванного преобразованием типов. Тесты не показывают преимущества управления без ветвления по сравнению с управлением с ветвлениями, но теоретически код без управления ветвлениями во многих случаях будет работать лучше.

Наконец, моя реализация abs для int64 выглядит следующим образом:

func abs(n int64) int64 {
	y := n >> 63
	return (n ^ y) - y
}

Наконец

Это первая статья, в переводе которой я участвовал после присоединения к GCTT, спасибо автору оригинала.Ryan Armstrong. Я научился писать тест-кейсы, правильно использовать бенчмарк-тесты и т. д. Постараюсь в будущем каждую неделю качественно переводить блог :-D

с помощью:Optimized abs() for int64 in Go

автор:Ryan Armstrong
Переводчик:wuYinBest
Вычитка:rxcai

Категории