Just want to point out that this is actually surprisingly less of an impact than I thought. As I did the step-by-step break down (you can see my blog post), this one (changing `quotRem` to `quotInt#` and `remInt#`) yielded almost negligible differences. Every other change had more impact than this, including turning the `Data.Array.Unboxed` into "lookup functions" (like `lenOnes 0 = 0; lenOnes 1 = 3; lenOnes 2 = 3; ...`)

On Wed, Aug 10, 2011 at 2:16 AM, Bryan O'Sullivan <bos@serpentine.com> wrote:

On Tue, Aug 9, 2011 at 9:47 AM, Chris Yuen <kizzx2+haskell@gmail.com> wrote:

- I was using GHC 32-bit. Int is 32-bit there, so I needed Int64. It turns out 64-bit operations in 32-bit programs are just darn slow. Maybe it's a Windows problem.

No, GHC calls out to C for 64-bit integer ops on all 32-bit platforms.

On Linux 64 bit GHC Int is 64 bit so everything just works. Changing Int64 to Int liberates me from many `fromIntegral` which saved 20%

Actually, fromIntegral is usually a no-op, so chances are you're seeing the effect of something else.

- Changing `divMod` to `quotRem` saved another 20%

It's cheaper again to use quotInt# and remInt# as I did in my code.

1. Why are bangs needed on the length arrays?

GHC has to deconstruct the Vector in order to get at the real underlying array, so that unsafeIndex can perform the actual index into the real underlying array.

Without bang patterns, the code performs at least one deconstruction on every iteration through the loop. Each deconstruction has a cost. With the bang patterns, they're all hoisted out and performed just once.