inside the GHC code generator
Benjamin.Rudiak-Gould at cl.cam.ac.uk
Fri Feb 24 12:06:21 EST 2006
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
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#).
More information about the Glasgow-haskell-users