Personal tools

Shootout/SumFile

From HaskellWiki

< Shootout
Revision as of 02:16, 8 October 2006 by DonStewart (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

A Shootout Entry for the sum-file benchmark.

Each program should be implemented the same way - the same way as this Icon program. The sum-file benchmark measures line-oriented I/O and string conversion.

Each program should:

   * read integers from stdin, one line at a time
   * print the sum of those integers

Correct output for this 6KB input file is:

   500

Programs should use built-in line-oriented I/O functions rather than custom-code. No line will exceed 128 characters, including newline. Reading one line at a time, the programs should run in constant space.

Those guys tell us these benchmarks don't favor C and then impose a limit on line length? What's the purpose of that if not to allow the use of C's getline() primitive (in both senses of the word)? And if we're picky, all submitted programs are incorrect, as they assume the sum fits into a machine word, but this assumption is unwarranted. This again favors C, which lacks arbitrary precision integers. -- UdoStenzel

Contents

1 Possible Entry

Todo: Use ByteStrings. An example of a faster entry using the new Data.ByteString library.

{-# OPTIONS -cpp #-}
 
--
-- 'sums' benchmark from the great language shootout 
--
 
import System.IO
import qualified Data.ByteString as B
import Data.ByteString (ByteString,unsafeTail,unsafeIndexWord8)
import Data.Char    -- seems to help!
 
#define STRICT2(f) f a b | a `seq` b `seq` False = undefined
 
main = print . go 0 =<< B.getContents
 
STRICT2(go)
go i ps
    | B.null ps = i
    | x == 45   = neg 0 xs
    | otherwise = pos (parse x) xs
    where
        (x, xs) = (ps `unsafeIndexWord8` 0, unsafeTail ps)
 
        STRICT2(neg)
        neg n qs | x == 10     = go (i-n) xs
                 | otherwise   = neg (parse x + (10 * n)) xs
                 where (x, xs) = (qs `unsafeIndexWord8` 0, unsafeTail qs)
 
        STRICT2(pos)
        pos n qs | x == 10   = go (i+n) xs
                 | otherwise = pos (parse x + (10 * n)) xs
                 where (x, xs) = (qs `unsafeIndexWord8` 0, unsafeTail qs)
 
parse w = fromIntegral (w - 48) :: Int
{-# INLINE parse #-}

2 Current Entry

This compiles to the same code as the Submitted Entry. Additionally, the shootout includes {- -} style comments in the line count! So don't submit code with such comments.

-O2 -optc-O3

--
-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
--
-- compile with : ghc fastest.hs -o fastest
--
-- contributed by Greg Buchholz
-- Modified by Mirko Rahn, Don Stewart, Chris Kuklewicz and Lemmih
--
import Data.Char
 
main = print . new 0 =<< getContents
 
new i []       = i
new i ('-':xs) = neg 0 xs
    where neg n ('\n':xs) = new (i - n) xs
          neg n (x   :xs) = neg (parse x + (10 * n)) xs
new i (x:xs) = pos (parse x) xs
    where pos n ('\n':xs) = new (i + n) xs
          pos n (x   :xs) = pos (parse x + (10 * n)) xs
 
parse c = ord c - ord '0'

3 Old code

3.1 A shorter version of the original entry

{-# OPTIONS -O2 -optc-O3 #-}
--
-- The Computer Language Shootout
-- http://shootout.alioth.debian.org/
--
-- compile with : ghc -O2 -o SumF SumF.hs
-- To get better performance set default heap size to 10MB
-- i.e. invoke as : ./SumF +RTS -H10M <input_file.txt
-- contributed by Greg Buchholz
-- modified by Mirko Rahn and Don Stewart
--
 
import Char
 
main = getContents >>= print . accP 0 0
 
accP b t  []       =       b+t
accP b t ('\n':xs) = accP (b+t) 0                        xs
accP b t ('-' :xs) = accN  b       t                     xs
accP b t (x   :xs) = accP  b      (t*10+ord(x)-ord('0')) xs
 
accN b t  []       =       b-t
accN b t ('\n':xs) = accP (b-t) 0                        xs
accN b t (x   :xs) = accN  b      (t*10+ord(x)-ord('0')) xs


3.2 Submitted Entry

Currently ranked 7th, behind D, Clean, C and C++.

A version of Don's and Chris' using -funbox-strict-fields instead of explicit Int#. Runs about 10% faster than the original entry.

{-# OPTIONS -O2 -funbox-strict-fields #-}
{-
   The Computer Language Shootout
   http://shootout.alioth.debian.org/
 
   compile with : ghc --make fastest.hs -o fastest
 
   contributed by Greg Buchholz
   modified by Mirko Rahn
   modified by Don Stewart and Chris Kuklewicz, 5-6 Jan 2006
-}
import GHC.Base
 
data I = I !Int
 
main = print . new (I 0) =<< getContents 
 
new (I i) []       = i
new (I i) ('-':xs) = neg (I 0) xs
    where neg (I n) ('\n':xs) = new (I (i - n)) xs
          neg (I n) (x   :xs) = neg (I (parse x + (10 * n))) xs
new (I i) (x:xs) = pos (I (parse x)) xs
    where pos (I n) ('\n':xs) = new (I (i + n)) xs
          pos (I n) (x   :xs) = pos (I (parse x + (10 * n))) xs
 
parse c = ord c - ord '0'

A box around a (unboxed) strict Int? How is that smart? --Lemmih

The -funbox-strict-fields causes it to be converted to Int# without writint I# -# +# ==# everywhere -- Chris

"data I = I !Int" gives "data I = I Int#" which is exactly the same as "data Int = I# Int#". Fortunately, GHC is able to compile both 'I' and 'Int' away. --Lemmih

3.3 Chris Kuklewicz

I tried IOUArray, mallocArray, and in the end came back to to original entry, but slightly optimized with unboxed Int# so it runs ~10% faster:

{-# OPTIONS -fglasgow-exts -O2 #-}
{-
   The Computer Language Shootout
   http://shootout.alioth.debian.org/
 
   compile with : ghc -O2 -o SumF SumF.hs
 
   To get better performance set default heap size to 10MB
   i.e. invoke as : ./SumF +RTS -H10M <input_file.txt
 
   contributed by Greg Buchholz
   modified by Mirko Rahn
   modified by Chris Kuklewicz, 5 Jan 2006
-}
import GHC.Base
 
main = print . sumFile =<< getContents
    where sumFile = (\rest -> newLine rest 0#)
 
newLine [] rt = (I# rt)
newLine ('-':rest) rt = negLine rest 0#
    where negLine ('\n':rest) soFar = newLine rest (rt -# soFar) 
          negLine ( x  :rest) soFar = negLine rest (parse x +# (10# *# soFar))
newLine (x:rest) rt = posLine rest (d2i x)
    where posLine ('\n':rest) soFar = newLine rest (rt +# soFar)
          posLine ( x  :rest) soFar = posLine rest (parse x +# (10# *# soFar))
 
parse (C# c) = (ord# c) -# z
    where (I# z) = ord '0'

Yes, this is nice and fast. Here's a tiny bit of refactoring. -- Don

import GHC.Base
 
main = print . new 0# =<< getContents
 
new i []       = (I# i)
new i ('-':xs) = neg 0# xs
    where neg n ('\n':xs) = new (i -# n) xs
          neg n (x   :xs) = neg (parse x +# (10# *# n)) xs
 
new i (x:xs)   = pos (parse x) xs
    where pos n ('\n':xs) = new (i +# n) xs
          pos n (x   :xs) = pos (parse x +# (10# *# n)) xs
 
parse (C# c) = ord# c -# ord# '0'#

3.4 Don Stewart

An short alternative (but performance isn't great with the {{{read}}}). However, it's the only 1 line entry in any language, it's very Haskellish, and GHC does an excellent job compiling the foldr into a tight loop. The Int constraint doesn't seem to change performance much, but causes less code to be generated.

main = print . foldr ((+).read) (0::Int) . lines =<< getContents

Since this is an accumulation, wouldn't foldl' work better?

main = print . foldl' (+) (0::Int) . map read . lines =<< getContents

-- UdoStenzel

I tried that tweak and the speed was the same -- ChrisKuklewicz

Other options

main = print . sum . map read . lines =<< getContents
main = print . foldl ((.read).(+)) (0::Int) . lines =<< getContents

-- DonStewart

3.5 Ketil Malde

I toyed with the one liner as a starting point, and ended up with this:

import Char
import Data.List
 
main = getContents >>= print . sum . map (read'. valid) . lines
 
valid = filter (\x -> x == '-' || x >= '0' && x <= '9')
read' (x:xs) = case x of '-' -> negate $ foldl (\a b -> 10*a+ord b-ord '0') 0 xs
                         _ -> foldl (\a b -> 10*a+ord b-ord '0') 0 (x:xs)

It isn't entirely valid, but as has been pointed out, neither are any of the other entries. Like Chris, I couldn't tell any difference between foldl and foldl', nor did restricting to Ints make any impact. (Other test data may differ)

This is (with -O2) about three times slower than the current best entry, which, if it scales up, will put it in the middle of the pack, close to Ocaml byte code and CMUCL.

An improved version, this uses about 0.6 of the heap (according to -prof). Replacing sum . map with a foldr is the key. Also, why the need for `valid'? -- Don

Right, I didn't bother with heap - and I guess I expected sum to be strict enough (isn't it?) valid`s raison d'�tre is the possibility of non-numeric characters (whitespace) in the file. Perhaps the spec excludes that possibility? -k

import Char
 
main = print . foldr ((+).read') (0::Int) . lines =<< getContents
 
read' (x:xs) = if x == '-' then negate (sumify xs) else sumify (x:xs)
 
sumify = foldl (\n b -> ord b - ord '0' + 10 * n) 0

Nice and concise! I'd suggest renaming sumify, but perhaps str2int is better than my read variant? Does the ::Int buy you much? I really like to avoid the overflow bug, even if not relevant for the test data set. -k

3.6 Current entry

This entry has rather good performance, though space is a bit high. Currently placed 6th.

import Char( ord )
 
main :: IO ()
main = getContents >>= print . accP 0 0
 
accP :: Int -> Int -> String -> Int
accP before this  []       =       before+this
accP before this ('\n':xs) = accP (before+this) 0                        xs
accP before this ('-' :xs) = accN  before       this                     xs
accP before this (x   :xs) = accP  before      (this*10+ord(x)-ord('0')) xs
 
accN :: Int -> Int -> String -> Int
accN before this  []       =       before-this
accN before this ('\n':xs) = accP (before-this) 0                        xs
accN before this (x   :xs) = accN  before      (this*10+ord(x)-ord('0')) xs