Как на Go написать очень быстрый(пусть platform-specific) abs(x int32)?

Question

[uvelichitel]

Пишу числодробилку. Скорость операции критична. abs() для int32 не реализован в stdlib. Вот это не работает (ну или не хватает способностей реализовать).
uint32(x) работает, но что там вообще лежит не интуитивно.
unsafe.Pointer() берется и что? https://play.golang.org/p/ZAAJTv3sA_
На irc #go-nuts сказали что знак точно в верхнем бите. Подскажите как к нему bitwise добраться.
Если без выдумок написать
if x<0 {x=-x}; //а это проверка сдвиг и два копирования
сообразит ли компилятор просто маскировать знак без проверок? Для float64 в stdlib.math собственно так и сделано но...
Задача частная - int32, GOOS/ARCH=linux/amd64

Answer 1

[neolink]

вот реализация на go https://play.golang.org/p/zTe6pRwx0Y (на основе "это не работает")

package main

import "fmt"

func abs(x int) int {
	m := x >> 31

	return (x + m) ^ m
}

func main() {
	fmt.Println(abs(-65580))
}

это компилируется в:

01	MOVQ	$-65580,AX
02	MOVQ	AX,DX
03	SARQ	$31,AX
04	ADDQ	AX,DX
05	XORQ	AX,DX

тут можно посмотреть на 2 канонических ассемблерных варианта для x86: www.strchr.com/optimized_abs_function
то есть отличие только в замене 02-03 на одну инструкция cdq, если хочется добится 3х инструкций - можете вручную сделать реализацию на ассемблере смотрите тот же пакет math например.

Comments

[uvelichitel]

Спасибо

[Tyranron]

uvelichitel, neolink
Сделал небольшой бенчмарк play.golang.org/p/LUD4idmK0D .
Онлайн не работает, платформа режет. Скопируйте в локальный файл и через go run.
У меня стандартный вариант через < 0 работает чуть-чуть быстрее. Платформа darwin/amd64.
Benchmark of AbsStd():
2000000000 0.68 ns/op 0 B/op 0 allocs/op
Benchmark of AbsMagic():
2000000000 0.70 ns/op 0 B/op 0 allocs/op
Отрыв варьируется от 0 до 0.03 ns/op.

[neolink]

Tyranron: если использовать тип int и не константное значение у меня одинаково, надо будет поковырять что там под капотом генерится

[Tyranron]

neolink: как поковыряете, отпишите обязательно, пожалуйста. Жуть как интересно.

Answer 2

[druid3]

int32 это фиксированная длинна слова, биты "пронумерованы" без связи с порядком байтов - "промахнуться" тяжело (:)) даже на другой архитектуре. Затираем самый старший бит(собственно знак) и вуаля. ... А приведенные Вами (uvelichitel) примеры - рабочие, как neolink уже показал.

На irc #go-nuts сказали что знак точно в верхнем бите. Подскажите как к нему bitwise добраться.

Так то оно так, но код то отрицательных чисел дополнительный до 2-x... потому мы выделяем маской старший бит и хитро пляшем с бубном еще и потому что в go нет побитового отрицания(!)
а вообще влоб нужно

Для получения из дополнительного кода самого числа....

#include <stdlib.h>
#include <unistd.h>

int i32abs4training(int x)
{
    int m;

    m = 2*((x >> 31)&1) - 1; // negative or positive (invers)
 //   printf("bits in a integer word %i\n", sizeof(x)*8);

	return ~(m*x) + 1;
}

int main()
{
 printf ("%i\n", i32abs4training(-12));
 printf ("%i\n", i32abs4training(12));
 printf ("%i\n", i32abs4training(14));
 printf ("%i\n", i32abs4training(-32768));
}

Приведенный код не претендует на быстродействие - это просто показать из чего вывели "быстрый" подход и для golang, и для C и для asm.