returning to cost of Integer

[Duncan Coutts]

On Mon, 2006-07-31 at 14:32 +0400, Serge D. Mechveliani wrote:
> Dear GHC developers,
> 
> Long ago you wrote that GHC has made  Integer  only about  3/2  times 
> slower than  Int.
> I tested this once, and then all this time I have been relying on this.
> Now, with   
>           ghc-6.4.1  compiled for Linux - i386-unknown,
>                      running under Debian Linux, Intel Pentium III
>                      under  ghc -O,
> 
> I have an occasion to repeat the test on a certain simple program for 
> processing lists of length 7 over  Integer.
> 
> And  Integer  shows  2.55  times slower  (11.2 sec against 4.4).
> 
> Showld we somehow agree that 
>                         cost(Integer)/cost(Int)  in GHC  is about  2.55
> 
> or maybe we are missing something?

The cost difference is varies with the context. In the case that the
Int/Integer is always boxed then we might expect a constant factor
between Int and Integer (at least for numbers that fit in an Int).

However because Int is often unboxable where as Integer is never
unboxable there are certainly programs where the factor is much much
greater than x2 or x3. If the Int can be unboxed into an Int# then the
operations are very quick indeed as they are simple machine primitives.

As an extreme example, I just tried with one of my current simple
ByteString benchmarks. If we swap Int for Integer in the inner loop of
ByteString.map then the time to evaluate (map f . map g) s increases by
37 times!

So actually that's not to say that Integer is slow, but rather that in
many cases GHC is really pretty good at optimising right down to the low
level details. The representation of Integer prevents many of these
optimisations.

So as I said, the ratio really does depend on what you're doing.

Duncan