Skip to content

Instantly share code, notes, and snippets.

@dt-rush
Created May 25, 2018 20:51
Show Gist options
  • Save dt-rush/53bf9a4695c465fd60a456d3ba2faaba to your computer and use it in GitHub Desktop.
Save dt-rush/53bf9a4695c465fd60a456d3ba2faaba to your computer and use it in GitHub Desktop.
Profiling distance functions in go
Intel(R) Core(TM) i7-6820HQ CPU @ 2.70GHz
go version go1.8.3 linux/amd64
package main
import (
"fmt"
"math"
"math/rand"
"time"
)
// octagonal distance with bitshifts, said to have been the distance function
// for the lighting in Diablo II
// taken from:
// http://www.flipcode.com/archives/Fast_Approximate_Distance_Functions.shtml
func approxDistance(a [2]int16, b [2]int16) int16 {
var min, max int16
min = int16(a[0] - b[0])
max = int16(a[1] - b[1])
if min < 0 {
min = -min
}
if max < 0 {
max = -max
}
if max < min {
min, max = max, min
}
// coefficients equivalent to ( 123/128 * max ) and ( 51/128 * min )
return (((max << 8) + (max << 3) - (max << 4) - (max << 1) +
(min << 7) - (min << 5) + (min << 3) - (min << 1)) >> 8)
}
// euclidean distance with sqrt
func distance(a [2]int16, b [2]int16) int16 {
return int16(
math.Sqrt(
float64(
(a[0]-b[0])*(a[0]-b[0]) +
(a[0]-b[0])*(a[0]-b[0]))))
}
func ProfileDistanceFunc(f func(a [2]int16, b [2]int16) int16) {
var N int64 = 1024 * 1024 * 8
distances := make([]int16, N)
var sum int64
for i := int64(0); i < N; i++ {
a := [2]int16{int16(rand.Intn(100)) - 50, int16(rand.Intn(100)) - 50}
b := [2]int16{int16(rand.Intn(100)) - 50, int16(rand.Intn(100)) - 50}
t0 := time.Now()
distances[i] = approxDistance(a, b)
sum += time.Since(t0).Nanoseconds()
}
fmt.Println(sum / N)
}
func main() {
rand.Seed(time.Now().UnixNano())
ProfileDistanceFunc(distance)
ProfileDistanceFunc(approxDistance)
}
@dt-rush
Copy link
Author

dt-rush commented May 25, 2018

Interestingly, with the CPU and compiler shown, the two functions perform identically.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment