On Sat, 2007-12-15 at 14:34 +0000, Duncan Coutts wrote:
Ok, I presume this is a guessing game and we're supposed to just look at the code without running and timing them.
Precisely :)
All they do is read from stdin and count the number of spaces they see. There are two that use strict bytestrings, two that use lazy bytestrings, and two that use the standard Haskell strings. Three use a recursive function with an accumulator parameter and three use a foldl with a lambda function.
Say the fastest one takes the time 1. How much time will the others take?
And how about memory? How much memory do you think they require? Let's say we feed a 150MB(*) file into each of them, how many megabytes do you think they end up using (as seen from the OS, not in terms of how big the live heap is)?
I'm going to post full benchmarks + analysis on Wednesday.
Right'o. I'll have a go. Lets see if I can't embarrass myself with being completely inaccurate.
Thanks for biting! You were, thankfully, only almost completely inaccurate ;)
PS: For extra credit, what do you think is the peak memory use for this program when given an input file of 150MB?
Hmm. So that should work in constant memory, a few 64 chunks at once. I'd expect this to be pretty fast.
You are right about the speed. Can you guess a number in kilobytes?
============================== hs/space-bs-c8-acc-1.hs: {-# LANGUAGE BangPatterns #-}
import qualified Data.ByteString.Char8 as B
cnt :: Int -> B.ByteString -> Int cnt !acc bs = if B.null bs then acc else cnt (if B.head bs == ' ' then acc+1 else acc) (B.tail bs)
main = do s <- B.getContents print (cnt 0 s)
This uses strict bytestrings so will use at least 150Mb and that'll make it a good deal slower. In fact it'll be worse than that since getContents does not know in advance how big the input will be so it has to play the doubling and copying game. So it'll end up copying all the data roughly twice. cnt is strict and tail recursive so that shouldn't be any problem, though it's probably not as fast as the first length . filter since head, tail, null all have to do bounds checks.
You are right about the memory. It is actually slightly faster than the "extra credit" (length/filter combination) above.
============================== hs/space-bslc8-acc-1.hs: {-# LANGUAGE BangPatterns #-}
import qualified Data.ByteString.Lazy.Char8 as B
cnt :: Int -> B.ByteString -> Int cnt !acc bs = if B.null bs then acc else cnt (if B.head bs == ' ' then acc+1 else acc) (B.tail bs)
main = do s <- B.getContents print (cnt 0 s)
For the same reason as above, I'd expect this cnt to be slower than B.length . B.filter (== ' ')
It is slower but not for the same reason as above.
============================== hs/space-xxxxx-acc-1.hs: {-# LANGUAGE BangPatterns #-}
cnt :: Int -> String -> Int cnt !acc bs = if null bs then acc else cnt (if head bs == ' ' then acc+1 else acc) (tail bs)
main = do s <- getContents print (cnt 0 s)
Lazy, so constant memory use, but much higher constant factors due to using String.
Spot on.
============================== hs/space-bs-c8-foldlx-1.hs: {-# LANGUAGE BangPatterns #-}
import qualified Data.ByteString.Char8 as B
cnt :: B.ByteString -> Int cnt bs = B.foldl' (\sum c -> if c == ' ' then sum+1 else sum) 0 bs
main = do s <- B.getContents print (cnt s)
This is of course still strict so that's going to make the reading slow.
Nope.
This is a manually fused B.length . B.filter (== ' ') which hopefully is the same speed as the automatically fused one if the fusion is working ok. If not, then the B.length . B.filter (== ' ') will be doing a extra copy, and memory writes are expensive.
============================== hs/space-bslc8-foldlx-1.hs: {-# LANGUAGE BangPatterns #-}
import qualified Data.ByteString.Lazy.Char8 as B
cnt :: B.ByteString -> Int cnt bs = B.foldl' (\sum c -> if c == ' ' then sum+1 else sum) 0 bs
main = do s <- B.getContents print (cnt s)
As above but now in constant memory space.
Nope.
============================== hs/space-xxxxx-foldl.hs: {-# LANGUAGE BangPatterns #-}
cnt :: String -> Int cnt bs = foldl (\sum c -> if c == ' ' then sum+1 else sum) 0 bs
main = do s <- getContents print (cnt s)
Oh, no! not foldl that's a killer.
You think it's worse than the program just above?
Ok, so best way to summarise I think is to organise by data type since I think that'll dominate.
So I think the lazy bytestring versions will be fastest due to having the best memory access patterns and doing the least copying. I think the foldl's will be faster than the explicit accumulators due to having fewer bounds checks.
space-bslc8-foldlx-1 space-bslc8-acc-1
space-bs-c8-foldlx-1 space-bs-c8-acc-1
space-xxxxx-acc-1 space-xxxxx-foldl
I'll try guessing at some ratios:
1.0 space-bslc8-foldlx-1 1.1 space-bslc8-acc-1
2.0 space-bs-c8-foldlx-1 2.1 space-bs-c8-acc-1
4.0 space-xxxxx-acc-1 15 space-xxxxx-foldl
I've done the measurements on a 2GHz Athlon64 3000+, a 1667 MHz Core Duo, and a 600MHz Pentium III. They all show the same pattern (with a few minor aberrations for the PIII). You did got one of the relative speeds right ;) (and some of the memory usages) I've tested with ghc 6.8.1 and 6.9.20071119 and 6.9.20071208 (or thereabouts). 6.6.1 won't run my benchmarks and it also won't let me install bytestring-0.9.0.1 to replace its built-in version. -Peter