Duncan Coutts wrote:

On Fri, 2008-04-25 at 17:30 +0100, Richard Kelsall wrote:

...

I've just been investigating a performance oddity in using splitAt on a long stream of random numbers. I don't understand why GHC appears to want to traverse the first part of the list twice.

GHC seems to implement the splitAt function something like

splitAt n xs = (take n xs, drop n xs)

whereas Hugs is something like

splitAt n (x : xs) = (x : xs', xs'') where (xs', xs'') = splitAt (n-1) xs

which seems much more sensible to me. Wouldn't it be better to change GHC to the Hugs method? Have I misunderstood something?

Actually GHC uses this definition, in GHC.List:

#ifdef USE_REPORT_PRELUDE

splitAt n xs = (take n xs, drop n xs)

#else /* hack away */

splitAt (I# n#) ls | n# <# 0# = ([], ls) | otherwise = splitAt# n# ls where splitAt# :: Int# -> [a] -> ([a], [a]) splitAt# 0# xs = ([], xs) splitAt# _ xs@[] = (xs, xs) splitAt# m# (x:xs) = (x:xs', xs'') where (xs', xs'') = splitAt# (m# -# 1#) xs

#endif /* USE_REPORT_PRELUDE */

So ghc's version should be of equivalent strictness to the hugs version.

What's interesting here is that the H98 specification of splitAt is silly. It got 'simplified' from a previous version of the Haskell spec and is so doing it was made less strict.

With this definition: splitAt n xs = (take n xs, drop n xs)

splitAt _|_ _|_ = (_|_, _|_)

but with the sensible definition it'd return _|_

and that's really the only point of having splitAt, so that you can walk down the list once rather than twice. If someone needs the very lazy version there's always take and drop.

Duncan

That looks good, I didn't see this 'hack away' version when I found splitAt on the web. I'm now wondering why my splitAtRK function in the following code makes it run in 11 seconds given a parameter of 2500000 but it takes 14 seconds when I change it to splitAt. Am I accidentally invoking the (take, drop) version of splitAt? Why is mine so much faster than the built-in version? (Using GHC 6.8.2, W2K, Intel Core 2 Duo 2.33GHz) Maybe mine isn't working properly somehow. (I hadn't intended to post this code just yet because I wanted to do a bit more testing etc then ask for suggestions for simplifying and improving it. I actually want to get rid of the line containing splitAt because it's ugly. All suggestions for improvement gratefully received. The time function is just temporary. This code is about three or four times slower that the current fastest Haskell entry for the Fasta shootout benchmark. I'll elaborate it for speed when I've got down to the simplest version possible.) Richard. {-# OPTIONS -O2 -fexcess-precision #-} -- -- The Computer Language Shootout : Fasta -- http://shootout.alioth.debian.org/ -- -- Simple solution by Richard Kelsall. -- http://www.millstream.com/ -- import System import Text.Printf import System.CPUTime time :: IO t -> IO t time a = do start <- getCPUTime v <- a end <- getCPUTime let diff = (fromIntegral (end - start)) / (10 ^12) printf "Calc time %0.3f \n" (diff :: Double) return v main = do time $ comp comp :: IO () comp = do n <- getArgs >>= readIO . head title "ONE" "Homo sapiens alu" writeLined (cycle alu) (n * 2) title "TWO" "IUB ambiguity codes" let (r1, r2) = splitAtRK (fromIntegral (n * 3)) (rand 42) writeLined (map (look iubs) r1) (n * 3) title "THREE" "Homo sapiens frequency" writeLined (map (look homs) r2) (n * 5) splitAtRK n xs | n <= 0 = ([], xs) splitAtRK _ [] = ([], []) splitAtRK n (x : xs) = (x : xs', xs'') where (xs', xs'') = splitAtRK (n - 1) xs title :: String -> String -> IO () title a b = putStrLn $ ">" ++ a ++ " " ++ b look :: [(Char, Float)] -> Float -> Char look [(c, _)] _ = c look ((c, f) : cfs) r = if r < f then c else look cfs (r - f) lineWidth = 60 writeLined :: [Char] -> Integer -> IO () writeLined cs 0 = return () writeLined cs n = do let w = min n lineWidth (cs1, cs2) = splitAt (fromInteger w) cs putStrLn cs1 writeLined cs2 (n - w) rand :: Int -> [Float] rand seed = newran : (rand newseed) where im = 139968 ia = 3877 ic = 29573 newseed = (seed * ia + ic) `rem` im newran = fromIntegral newseed / fromIntegral im alu = "GGCCGGGCGCGGTGGCTCACGCCTGTAATCCCAGCACTTTGGGAGGCCGAGGCGGGCGGA\ \TCACCTGAGGTCAGGAGTTCGAGACCAGCCTGGCCAACATGGTGAAACCCCGTCTCTACT\ \AAAAATACAAAAATTAGCCGGGCGTGGTGGCGCGCGCCTGTAATCCCAGCTACTCGGGAG\ \GCTGAGGCAGGAGAATCGCTTGAACCCGGGAGGCGGAGGTTGCAGTGAGCCGAGATCGCG\ \CCACTGCACTCCAGCCTGGGCGACAGAGCGAGACTCCGTCTCAAAAA" iubs = [('a', 0.27), ('c', 0.12), ('g', 0.12), ('t', 0.27), ('B', 0.02), ('D', 0.02), ('H', 0.02), ('K', 0.02), ('M', 0.02), ('N', 0.02), ('R', 0.02), ('S', 0.02), ('V', 0.02), ('W', 0.02), ('Y', 0.02)] homs = [('a', 0.3029549426680), ('c', 0.1979883004921), ('g', 0.1975473066391), ('t', 0.3015094502008)]

Brandon S. Allbery KF8NH wrote:

On Apr 26, 2008, at 9:02 , Richard Kelsall wrote:

...

I'm now wondering why my splitAtRK function in the following code makes it run in 11 seconds given a parameter of 2500000 but it takes 14 seconds when I change it to splitAt. Am I accidentally invoking

It's somewhat unusual to build the standard libraries with -O2, I think. (It can be done but the build takes a very long time.)

Also, 11 vs. 14 seconds seems not that much of a difference when you're talking 2500000 items, especially given how inefficient Haskell lists (Strings are lists) are.

Yes, well spotted. If I lower the compile level from -O2 to -O the splitAtRK version takes 14.5 seconds vs 14 seconds for the built-in version. Thank you. That solves the puzzle. For the benchmarks I expect they use a default packaged GHC, I don't imagine I could get them to use specially compiled libraries to bump up the GHC score. Which gives an interesting dilemma of whether I could get away with adding a small relevant snippet of library code to the program in order to give it -O2 level compilation. I wonder how much the other compilers optimise their library code. Richard.