Can I speed up this Haskell algorithm?

Question

I've got this haskell file, compiled with ghc -O2 (ghc 7.4.1), and takes 1.65 sec on my machine

import Data.Bits
main = do
    print $ length $ filter (\i -> i .&. (shift 1 (i `mod` 4)) /= 0) [0..123456789]

The same algorithm in C, compiled with gcc -O2 (gcc 4.6.3), runs in 0.18 sec.

#include <stdio.h>
void main() {
    int count = 0;
    const int max = 123456789;
    int i;
    for (i = 0; i < max; ++i)
        if ((i & (1 << i % 4)) != 0)
            ++count;
    printf("count: %d\n", count);
}

Update I thought it might be the Data.Bits stuff going slow, but surprisingly if I remove the shifting and just do a straight mod, it actually runs slower at 5.6 seconds!?!

import Data.Bits
main = do
    print $ length $ filter (\i -> (i `mod` 4) /= 0) [0..123456789]

whereas the equivalent C runs slightly faster at 0.16 sec:

#include <stdio.h>
void main() {
    int count = 0;
    const int max = 123456789;
    int i;
    for (i = 0; i < max; ++i)
        if ((i % 4) != 0)
            ++count;
    printf("count: %d\n", count);
}

Answer 1

The two pieces of code do very different things.

import Data.Bits
main = do
    print $ length $ filter (\i -> i .&. (shift 1 (i `mod` 4)) /= 0) [0..123456789]

creates a list of 123456790 Integer (lazily), takes the remainder modulo 4 of each (involving first a check whether the Integer is small enough to wrap a raw machine integer, then after the division a sign-check, since mod returns non-negative results only - though in ghc-7.6.1, there is a primop for that, so it's not as much of a brake to use mod as it was before), shifts the Integer 1 left the appropriate number of bits, which involves a conversion to "big" Integers and a call to GMP, takes the bitwise and with i - yet another call to GMP - and checks whether the result is 0, which causes another call to GMP or a conversion to small integer, not sure what GHC does here. Then, if the result is nonzero, a new list cell is created where that Integer is put in, and consumed by length. That's a lot of work done, most of which unnecessarily complicated due to the defaulting of unspecified number types to Integer.

The C code

#include <stdio.h>
int main(void) {
    int count = 0;
    const int max = 123456789;
    int i;
    for (i = 0; i < max; ++i)
        if ((i & (1 << i % 4)) != 0)
            ++count;
    printf("count: %d\n", count);
    return 0;
}

(I took the liberty of fixing the return type of main), does much much less. It takes an int, compares it to another, if smaller, takes the bitwise and of the first int with 3⁽¹⁾, shifts the int 1 to the left the appropriate number of bits, takes the bitwise and of that and the first int, and if nonzero increments another int, then increments the first. Those are all machine ops, working on raw machine types.

If we translate that code to Haskell,

module Main (main) where

import Data.Bits

maxNum :: Int
maxNum = 123456789

loop :: Int -> Int -> Int
loop acc i
    | i < maxNum = loop (if i .&. (1 `shiftL` (i .&. 3)) /= 0 then acc + 1 else acc) (i+1)
    | otherwise  = acc

main :: IO ()
main = print $ loop 0 0

we get a much closer result:

C, gcc -O3:
count: 30864196

real    0m0.180s
user    0m0.178s
sys     0m0.001s

Haskell, ghc -O2:
30864196

real    0m0.247s
user    0m0.243s
sys     0m0.003s

Haskell, ghc -O2 -fllvm:
30864196

real    0m0.144s
user    0m0.140s
sys     0m0.003s

GHC's native code generator isn't a particularly good loop optimiser, so using the llvm backend makes a big difference here, but even the native code generator doesn't do too badly.

Okay, I have done the optimisation of replacing a modulus calculation with a power-of-two modulus with a bitwise and by hand, GHC's native code generator doesn't do that (yet), so with ```rem4`` instead of.&. 3`, the native code generator produces code that takes (here) 1.42 seconds to run, but the llvm backend does that optimisation, and produces the same code as with the hand-made optimisation.

Now, let us turn to gspr's question

While LLVM didn't have a massive effect on the original code, it really did on the modified (I'd love to learn why...).

Well, the original code used Integers and lists, llvm doesn't know too well what to do with these, it can't transform that code into loops. The modified code uses Ints and the vector package rewrites the code to loops, so llvm does know how to optimise that well, and that shows.

⁽¹⁾ Assuming a normal binary computer. That optimisation is done by ordinary C compilers even without any optimisation flag, except on the very rare platforms where a div instruction is faster than a shift.

Answer 2

Few things beat a hand-written loop with a strict accumulator:

{-# LANGUAGE BangPatterns #-}

import Data.Bits

f :: Int -> Int
f n = g 0 0
  where g !i !s | i <= n    = g (i+1) (if i .&. (unsafeShiftL 1 (i `rem` 4)) /= 0 then s+1 else s)
                | otherwise = s

main = print $ f 123456789

In addition to the tricks mentioned so far, this also replaces shift with unsafeShiftL, which doesn't check its argument.

Compiled with -O2 and -fllvm, this is about 13x faster than the original on my machine.

_{Note: Testing if bit i of x is set can be written more clearly as x `testBit` i. This produces the same assembly as the above.}

Answer 3

Vector instead of list, fold instead of filter-and-length

Substituting the list for an unboxed vector and the filter-and-length for a fold (i.e. incrementing a counter) improves the time significantly for me. Here's what I used:

import qualified Data.Vector.Unboxed as UV
import Data.Bits

foo :: Int
foo = UV.foldl (\s i -> if i .&. (shift 1 (i `rem` 4)) /= 0 then s+1 else s) 0 (UV.enumFromN 0 123456789)

main = print foo

The original code (with two changes though: rem instead of mod as suggested in the comments, and adding an Int to the signature to avoid Integer) gave:

$ time ./orig 
30864196

real    0m2.159s
user    0m2.144s
sys     0m0.008s

The modified code above gave:

$ time ./new 
30864196

real    0m1.450s
user    0m1.440s
sys     0m0.004s

LLVM

While LLVM didn't have a massive effect on the original code, it really did on the modified (I'd love to learn why...).

Original (LLVM):

$ time ./orig-llvm 
30864196

real    0m2.047s
user    0m2.036s
sys     0m0.008s

Modified (LLVM):

$ time ./new-llvm 
30864196

real    0m0.233s
user    0m0.228s
sys     0m0.004s

For comparison, OP's original C code comes in at 0m0.152s user on my system.

This is all GHC 7.4.1, GCC 4.6.3, and vector 0.9.1. LLVM is either 2.9 or 3.0; I have both but can't seem to figure out which one GHC is actually using.

Answer 4

Try this:

import Data.Bits
main = do
    print $ length $ filter (\i -> i .&. (shift 1 (i `rem` 4)) /= 0) [0..123456789::Int]

Without the ::Int, the type defaults to ::Integer. rem does the same as mod on positive values, and it is the same as % in C. mod on the other hand ist mathematically correct on negative values, but is slower.

• int in C is 32bit
• Int in Haskell is either 32 or 64bit wide, like long in C
• Integer is an arbitrary-bit-integer, it has no min/max values, and its memory size depends on its value (similar to a string).