Why is math.Pow performance worse than bitshifting?

user_14323664 0
Viewed 335

When solving this exercise on Exercism website, I have used the standard math.Pow package function to get the raising powers of two.

return uint64(math.Pow(2, float64(n-1)))

After checking the community solutions, I found a solution using bit shifting to achieve the same thing:

return uint64(1 << uint(n-1)), nil

What surprised me is that there is a big performance difference between the two: bit-shifting math-pow

I thought that the Go compiler would recognize that math.Pow uses a constant 2 as the base and just utilize bit shifting on its own, without me explicitly doing it so. The only other difference I can see is the conversion of the float64 and that math.Pow is operating on floats and not on integers.

Why doesn't the compiler optimize the power operation to achieve performance similar to bit shifting?

compiler-optimization go bit-shift
3 Answers

First, note that uint64(1) << (n-1) is a better version of the expression uint64(1 << uint(n-1)) that appears in your question. The expression 1<<n is an int, so valid shift values are between 0 and either 30 or 62 depending on the size of int. uint64(1) << n allows n between 0 and 63.

In general, the optimization you suggest is incorrect. The compiler would have to be able to deduce that n is within a particular range.

See this example (on playground)

package main

import (
    "fmt"
    "math"
)

func main() {
    n := 65
    fmt.Println(uint64(math.Pow(2, float64(n-1))))
    fmt.Println(uint64(1) << uint(n-1))
}

The output demonstrates that the two methods are different:

9223372036854775808
0
user_14007930

math.Pow() is implemented to operate on float64 numbers. Bit shifting to calculate powers of 2 can only be applied on integers, and only on a tiny subset where the result fits into int64 (or uint64).

If you have such special case, you're more than welcome to use bit shifting.

Any other case where the result is bigger than math.MaxInt64 or where the base is not 2 (or a power of 2) requires floating point arithmetic.

Also note that even if detection of the above possible tiny subset would be implemented, the result is in 2's complement format, which also would have to be converted to IEEE 754 format because the return value of math.Pow() is float64 (although these numbers could be cached), which again you'd most likely convert back to int64.

Again: if you need performance, use explicit bit shifting.

user_17055980

Because such optimization was never implemented.

The go compiler aims to have fast compile time. Thus, some optimizations are decided to be not worth it. This saves compilation time at the expense of some run-time.

user_146369320
Related