inside the GHC code generator

[Ben Rudiak-Gould]

Rene de Visser wrote:
> Integer is about 30 times slower than it needs to be on GHC if you have 
> over half the values between 2^-31 and 2^31. On i386 can you basically 
> can test the low bit for free (it runs in parallel to the integer add 
> instruction). This would allow only values outside this range to 
> required calling the long integer code. Such an optimization is not 
> easily done in C.

Currently GHC defines

     data Integer = S# Int# | J# Int# ByteArray#

So it already avoids using GMP for small integers. There's a "will this 
multiplication overflow" primitive, but I'm not sure how it's implemented.

I think that changing this to use magic pointers would be pretty easy. You'd 
need to introduce a new primitive type, say Int31#, and then:

     1. anytime you previously constructed a WHNF S# on the heap, make a
        magic pointer instead

     2. anytime you dereference a pointer that might be an S#, check for a
        magic pointer first.

Even if a lot of code needs to be changed, it's straightforward because the 
changes are local. You're just changing the meaning of a pointer such that 
there's a statically allocated S# n at address 2n+1.

It would also be worth trying this for Char#, which is already a 31-bit 
type, to see if it would speed up text-processing code.

> If only simple loops are optimized it will encourage people to always 
> code loops in their haskell rather than perhaps using more appropriate 
> constructs.

You could say that about any language. When your code needs to be fast it 
needs to be fast. I'd rather write ugly Haskell code than ugly C code, if it 
comes to that.

> Also take the Maybe data type with Nothing and Just ... or any other 
> datatypes with 0 and 1 variable constructors. Here these could be 
> represent by special values for the 0 variable case and bit marking on 
> the single constructor values.

I'm not sure this would help much. Nullary constructors are already 
allocated statically, so they're already represented by special values. You 
could check for those values instead of dereferencing the pointer, but in 
time-critical code the static object will presumably be in L1 cache anyway. 
I could be wrong of course, and it would be easy enough to extend the Int31# 
idea to nullary constructors (Int0#).

-- Ben