Implementation of (^)

Question

I was reading the code of the implementation of (^) of the standard haskell library :

(^) :: (Num a, Integral b) => a -> b -> a
x0 ^ y0 | y0 < 0    = errorWithoutStackTrace "Negative exponent"
        | y0 == 0   = 1
        | otherwise = f x0 y0
    where -- f : x0 ^ y0 = x ^ y
          f x y | even y    = f (x * x) (y `quot` 2)
                | y == 1    = x
                | otherwise = g (x * x) ((y - 1) `quot` 2) x
          -- g : x0 ^ y0 = (x ^ y) * z
          g x y z | even y = g (x * x) (y `quot` 2) z
                  | y == 1 = x * z
                  | otherwise = g (x * x) ((y - 1) `quot` 2) (x * z)

Now this part where g is defined seems odd to me why not just implement it like this:

expo :: (Num a ,Integral b) => a -> b ->a
expo x0 y0 
    | y0 == 0 = 1
    | y0 <  0 = errorWithoutStackTrace "Negative exponent"
    | otherwise = f x0 y0
    where
      f x y | even y = f (x*x) (y `quot` 2)
              | y==1 = x
              | otherwise = x * f  x (y-1)

But indeed plugging in say 3^1000000 shows that (^) is about 0,04 seconds faster than expo.

Why is (^) faster than expo?

Answer 1

As the person who wrote the code, I can tell you why it's complex. :) The idea is to be tail recursive to get loops, and also to perform the minimum number of multiplications. I don't like the complexity, so if you find a more elegant way please file a bug report.

Answer 2

A function is tail-recursive if the return value of a recursive call is returned as-is, without further processing. In expo, f is not tail-recursive, because of otherwise = x * f x (y-1): the return value of f is multiplied by x before it is returned. Both f and g in (^) are tail-recursive, because their return values are returned unmodified.

Why does this matter? Tail-recursive functions can implemented much more efficiently than general recursive functions. Because the compiler doesn't need to create a new context (stack frame, what have you) for a recursive call, it can reuse the caller's context as the context of the recursive call. This saves a lot of the overhead of calling a function, much like in-lining a function is more efficient than calling the function proper.

Answer 3

Whenever you see a bread-and-butter function in the standard library and it's implemented weirdly, the reason is almost always "because doing it like that triggers some special performance-critical optimization [possibly in a different version of the compiler]".

These odd workarounds are usually to "force" the compiler to notice that some specific, important optimization is possible (e.g., to force a particular argument to be considered strict, to allow worker/wrapper transformation, whatever). Typically some person has compiled their program, noticed it's epicly slow, complained to the GHC devs, and they looked at the compiled code and thought "oh, GHC isn't seeing that it can inline that 3rd worker function... how do I fix that?" The result is that if you rephrase the code just slightly, the desired optimization then fires.

You say you tested it and there's not much speed difference. You didn't say for what type. (Is the exponent Int or Integer? What about the base? It's quite possible it makes a significant difference in some obscure case.)

Occasionally functions are also implemented weirdly to maintain strictness / laziness guarantees. (E.g., the library spec says it has to work a certain way, and implementing it the most obvious way would make the function more strict / less strict than the spec claims.)

I don't know what's up with this specific function, but I would suggest @chi is probably onto something.