Save bits, save power, save the world, Part 2

The GHC Haskell and OCaml compilers do not have builtin popcount support, so again I precomputed the bit pop count for each ASCII letter. Using the same ~9 Mb 4x concatenation of /usr/share/dict/words from last time I measured the performance of the resultant code. This time, the test machine was a Macbook Pro 2.16 GHz with 2 Gb of RAM. The microprocessor is a Core Duo T7400 which has no support for the popcnt instruction anyway.

This is a follow-on post to my experiments with popcount and hash maps in Python, C++, and Ruby in Part 1

Description	Execution Time (ms)
GHC Map Lookup Only/Precomputed	2568
OCaml Map Lookup Only/Precomputed	866
Python Precomputed	5418
g++	843
g++ -O3	505

OCaml is fairly competitive with the unoptimized g++ version. GHC lags quite a bit, but fares alright all things considered. The version of GHC I used was 7.0.4. OCaml was version 3.12.1.

Haskell

import Data.Bits
import System.IO
import Data.Char
import System.IO.Error
import Control.Monad
import Data.Map ((!), insert, empty, fromList)

letters = fromList
       [('A', 2), ('C', 3),('B', 2),( 'E', 3),( 'D', 2),( 'G', 4),( 'F', 3),( 'I', 3),( 'H', 2),( 'K', 4),( 'J', 3),( 'M', 4),( 'L', 3),( 'O', 5),( 'N', 4),( 'Q', 3),( 'P', 2),( 'S', 4),( 'R', 3),( 'U', 4),( 'T', 3),( 'W', 5),( 'V', 4),( 'Y', 4),( 'X', 3),( '[', 5),( 'Z', 4),( ']', 5),( '\\', 4),( '_', 6),( '^', 5),( 'a', 3),( '`', 2),( 'c', 4),( 'b', 3),( 'e', 4),( 'd', 3),( 'g', 5),( 'f', 4),( 'i', 4),( 'h', 3),( 'k', 5),( 'j', 4),( 'm', 5),( 'l', 4),( 'o', 6),( 'n', 5),( 'q', 4),( 'p', 3),( 's', 5),( 'r', 4),( 'u', 5),( 't', 4),( 'w', 6),( 'v', 5),( 'y', 5),( 'x', 4),( 'z', 5)]

popcount :: Int -> Int
popcount n =
  let popcountAcc n acc =
       if n == 0 then acc else popcountAcc (shiftR n 1) (acc + (n .&. 1))
  in popcountAcc n 0

loop h acc =
  do
    eof <- hIsEOF h
    if eof then return acc
           else do line <- hGetLine h
                   let x = sum (map ((!) letters) line)
                   let acc' = x+acc
                   loop h acc'
                   
main = do
  h <- openFile "words4" ReadMode
  acc <- loop h 0
  hClose h
  return 0

OCaml

let h = open_in("words4")

(* From OCaml Batteries *)
let explode s =
  let rec exp i l =
    if i < 0 then l else exp (i - 1) (s.[i] :: l) in
  exp (String.length s - 1) []

let rec loop() =
    let w = try Some (input_line h) with End_of_file -> None
    in match w 
         with None -> ()
         | Some w -> 
             let n = List.fold_left (+) 0
                           (List.map (fun c -> M.find c letters)    
                                     (explode w))
             in loop()

let main =
  (loop();
   close_in h)