On Sun, 2009-08-30 at 06:30 -0400, Gwern Branwen wrote:

On Sun, Aug 30, 2009 at 6:14 AM, Steve wrote:

...

Hi, I'm tackling a Sphere Online Judge tutorial question where it tests how fast you can process input data. You need to achieve at least 2.5MB of input data per second at runtime (on an old machine running ghc 6.6.1). This is probably close to the limit of Haskell's ability.

https://www.spoj.pl/problems/INTEST/

I can see that 24 haskell programmers have solved it, but most are very close to the 8 secs limit (and 6/24 are even over the limit!).

Here's my code. It fails with a "time limit exceeded" error. (I think it would calculate the correct result, eventually).

module Main where

import qualified Data.List as DLi import qualified System.IO as SIO

main :: IO () main = do line1 <- SIO.hGetLine SIO.stdin let k = read $ words line1 !! 1 s <- SIO.hGetContents SIO.stdin print $ count s k

count :: String -> Int -> Int count s k = DLi.foldl' foldFunc 0 (map read $ words s) where foldFunc :: Int -> Int -> Int foldFunc a b | mod b k == 0 = a+1 | otherwise = a

I tried using Data.ByteString but then found that 'read' needs a String, not a ByteString. I tried using buffered IO, but it did not make any difference.

Any suggestions on how to speed it up?

Regards, Steve

Did you try readInt? http://hackage.haskell.org/packages/archive/bytestring/0.9.1.4/doc/html/Data...

Thanks. I didn't see readInt. It allows me to use ByteString and produce results about 10 times faster than System.IO hGetContents. It makes me wonder why the System.IO functions have not been replaced by Data.ByteString. My program runs in 8.56 seconds (its over the 8 secs limit but it was accepted). I compared the top 10 C/C++ results against the top 10 Haskell results: C/C++ ~0.4 secs Haskell ~5.0 secs So it looks like Haskell is ~13 slower for IO than C/C++, even (I assume) when using Data.ByteString or other speed-up tricks. Steve

Well, Steve wrote:

I compared the top 10 C/C++ results against the top 10 Haskell results:

So to me it seems he's not talking about his code. Anyway, I thought Haskell's ByteString IO should not be that much slower anyway. Not sure how lazy ByteString IO is implemented, but if it performs async (aka overlapped) IO, it could be very very fast (faster than C), since the reading of the next buffer from (or writing of the previous buffer to) the file is then completely parallel with the computation (when done inplace you even don't need a memcpy, although these days the overhead of copying 64KB of memory might be very tiny, it used to be different in the old days :-) At least that's how I did it in the past in C++ with templates, which was faster than the C approach. On Sun, Aug 30, 2009 at 2:15 PM, Bulat Ziganshin wrote:

Hello Steve,

Sunday, August 30, 2009, 3:54:53 PM, you wrote:

...

So it looks like Haskell is ~13 slower for IO than C/C++, even (I assume) when using Data.ByteString or other speed-up tricks.

it means that *your* program is 13x slower than C one and nothing more. in particular, your program may be constrained by readInt speed

-- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Sun, Aug 30, 2009 at 2:51 PM, Bulat Ziganshin wrote:

these all are different things, and talking about ByteString IO speed is the same as talking of speed of red cars

Okay, but statistically, most red cars are very fast Ferrari's no? :-)

Here's my version that works in 0.7s for me for a file with 10^7 "999999999"'s but for some reason gets a 'wrong answer' at SPOJ :) {-# LANGUAGE BangPatterns #-} module Main where import qualified Data.ByteString.Lazy as B import Data.Word answer :: Int -> B.ByteString -> Int answer k = fst . B.foldl' f (0, 0) where f :: (Int,Int) -> Word8 -> (Int,Int) f (!countSoFar, !x) 10 | x`mod`k==0 = (countSoFar+1, 0) | otherwise = (countSoFar, 0) f (!countSoFar, !x) c = (countSoFar, 10*x+(fromIntegral c)-48) readInt :: B.ByteString -> Int readInt = B.foldl' (\x c -> 10*x+fromIntegral c-48) 0 main = do (line, rest) <- B.break (==10) `fmap` B.getContents let [n, k] = map readInt . B.split 32 $ line putStrLn . show $ answer k rest - 1 2009/8/30 Steve :

On Sun, 2009-08-30 at 06:30 -0400, Gwern Branwen wrote:

...

On Sun, Aug 30, 2009 at 6:14 AM, Steve wrote:

...

Hi, I'm tackling a Sphere Online Judge tutorial question where it tests how fast you can process input data. You need to achieve at least 2.5MB of input data per second at runtime (on an old machine running ghc 6.6.1). This is probably close to the limit of Haskell's ability.

https://www.spoj.pl/problems/INTEST/

I can see that 24 haskell programmers have solved it, but most are very close to the 8 secs limit (and 6/24 are even over the limit!).

Here's my code. It fails with a "time limit exceeded" error. (I think it would calculate the correct result, eventually).

module Main where

import qualified Data.List as DLi import qualified System.IO as SIO

main :: IO () main = do  line1 <- SIO.hGetLine SIO.stdin  let k = read $ words line1 !! 1  s <- SIO.hGetContents SIO.stdin  print $ count s k

count :: String -> Int -> Int count s k = DLi.foldl' foldFunc 0 (map read $ words s)  where    foldFunc :: Int -> Int -> Int    foldFunc a b      | mod b k == 0  = a+1      | otherwise     = a

I tried using Data.ByteString but then found that 'read' needs a String, not a ByteString. I tried using buffered IO, but it did not make any difference.

Any suggestions on how to speed it up?

Regards, Steve

Did you try readInt? http://hackage.haskell.org/packages/archive/bytestring/0.9.1.4/doc/html/Data...

Thanks. I didn't see readInt. It allows me to use ByteString and produce results about 10 times faster than System.IO hGetContents. It makes me wonder why the System.IO functions have not been replaced by Data.ByteString.

My program runs in 8.56 seconds (its over the 8 secs limit but it was accepted).

I compared the top 10 C/C++ results against the top 10 Haskell results: C/C++   ~0.4 secs Haskell ~5.0 secs So it looks like Haskell is ~13 slower for IO than C/C++, even (I assume) when using Data.ByteString or other speed-up tricks.

Steve

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru

Thanks :) I wonder why SPOJ didn't accept the same thing from me. I think that in order to obtain even higher performance we need to resort to low-level IO: raw reading into a byte buffer and parsing the very buffer to avoid memcpy'ing. Or, better, to use Oleg's iteratees with a file handle enumerator. I'll probably give it a try when I have time, but there's a 70% chance that I won't, so someone please try it, it should work :) 2009/8/30 Steve :

On Sun, 2009-08-30 at 16:34 +0400, Eugene Kirpichov wrote:

...

Here's my version that works in 0.7s for me for a file with 10^7 "999999999"'s but for some reason gets a 'wrong answer' at SPOJ :)

{-# LANGUAGE BangPatterns #-} module Main where

import qualified Data.ByteString.Lazy as B import Data.Word

answer :: Int -> B.ByteString -> Int answer k = fst . B.foldl' f (0, 0)   where f :: (Int,Int) -> Word8 -> (Int,Int)         f (!countSoFar, !x) 10           | x`mod`k==0 = (countSoFar+1, 0)           | otherwise  = (countSoFar,   0)         f (!countSoFar, !x) c = (countSoFar, 10*x+(fromIntegral c)-48)

readInt :: B.ByteString -> Int readInt = B.foldl' (\x c -> 10*x+fromIntegral c-48) 0

main = do   (line, rest) <- B.break (==10) `fmap` B.getContents   let [n, k] = map readInt . B.split 32 $ line   putStrLn . show $ answer k rest - 1

Eugene, I ran your code on one of my test files and it gave the same answer as my code. So I submitted it and it was accepted. Its fast - twice as fast as my solution, using much less memory. Overall its the 4th fastest Haskell solution. (but its still 10 * slower than C/C++) I'll have to read up on BangPatterns to try to understand what its doing!

I submitted it as:

{-# LANGUAGE BangPatterns #-} module Main where

import qualified Data.ByteString.Lazy as B import qualified Data.Word            as DW

answer :: Int -> B.ByteString -> Int answer k = fst . B.foldl' f (0, 0)  where f :: (Int,Int) -> DW.Word8 -> (Int,Int)        f (!countSoFar, !x) 10          | x`mod`k==0 = (countSoFar+1, 0)          | otherwise  = (countSoFar,   0)        f (!countSoFar, !x) c = (countSoFar, 10*x+(fromIntegral c)-48)

readInt :: B.ByteString -> Int readInt = B.foldl' (\x c -> 10*x+fromIntegral c-48) 0

main :: IO () main = do  (line, rest) <- B.break (==10) `fmap` B.getContents  let [_, k] = map readInt . B.split 32 $ line  putStrLn . show $ answer k rest - 1

-- Eugene Kirpichov Web IR developer, market.yandex.ru

I've updated Don Stewart's solution to compile with the modern ByteString libs. I'll be looking at ways to improve the performance of the `bytestring-nums` package. -- Jason Dusek http://github.com/jsnx/bytestring-nums/blob/d7de9db83e44ade9958fb3bfad0b29ed...

Good work guys. If you can abstract out a common function for lexing ints out of bytestrings, we could add it to the bytestring-lexing package. ekirpichov:

Hm, on my machine Don's code has exactly the same performance my code above.

Also, replacing the 'test' and 'parse' functions with this one

add :: Int -> Int -> S.ByteString -> Int add k i s = fst $ S.foldl' f (i, 0) s where f (!i, !n) '\n' | n`divisibleBy`k = (i+1, 0) | otherwise = (i, 0) f (!i, !n) w = (i, 10*n+ord w-ord '0')

increases performance by another 15% (0.675s vs 0.790s)

2009/9/1 Jason Dusek :

...

 I've updated Don Stewart's solution to compile with the modern  ByteString libs. I'll be looking at ways to improve the  performance of the `bytestring-nums` package.

-- Jason Dusek

http://github.com/jsnx/bytestring-nums/blob/d7de9db83e44ade9958fb3bfad0b29ed... _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Eugene Kirpichov Web IR developer, market.yandex.ru _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Tue, 2009-09-01 at 08:45 +0400, Eugene Kirpichov wrote:

Hm, on my machine Don's code has exactly the same performance my code above. That's strange.

Also, replacing the 'test' and 'parse' functions with this one

add :: Int -> Int -> S.ByteString -> Int add k i s = fst $ S.foldl' f (i, 0) s where f (!i, !n) '\n' | n`divisibleBy`k = (i+1, 0) | otherwise = (i, 0) f (!i, !n) w = (i, 10*n+ord w-ord '0')

increases performance by another 15% (0.675s vs 0.790s)

On my system I get a 50% slowdown using this add function! I guess is just shows that benchmarking code on one single CPU/memory/OS/ghc combination does not give results that apply widely. I'm using: AMD Athlon X2 4800 2GB memory Linux (Fedora 11, 64-bit version) ghc 6.10.3 Steve

On 02/09/2009, at 2:26 PM, Eugene Kirpichov wrote:

...

I've got a Centrino Duo 2000 (I'm on a notebook), Ubuntu 9.04 and ghc 6.10.2.

However, we have not set up on what exact input file we're using :) I'm using one where it is written "10000000 3" and then 10000000 lines of "999999999" follow.

Also, I wonder what one'd get if one compiled this program with jhc, but I don't know whether jhc is able to compile Data.ByteString.

It couldn't last time I tried - choked on some INLINE pragmas. Might not be a massive job, but there aren't enough hours in the day... mark

Bang patterns are easy: they make a part of the pattern strict by seq'ing it. f (x, !y) = ... ~ f (x, y) = y `seq` ... 2009/8/30 Steve :

On Sun, 2009-08-30 at 16:34 +0400, Eugene Kirpichov wrote:

...

Here's my version that works in 0.7s for me for a file with 10^7 "999999999"'s but for some reason gets a 'wrong answer' at SPOJ :)

{-# LANGUAGE BangPatterns #-} module Main where

import qualified Data.ByteString.Lazy as B import Data.Word

answer :: Int -> B.ByteString -> Int answer k = fst . B.foldl' f (0, 0)   where f :: (Int,Int) -> Word8 -> (Int,Int)         f (!countSoFar, !x) 10           | x`mod`k==0 = (countSoFar+1, 0)           | otherwise  = (countSoFar,   0)         f (!countSoFar, !x) c = (countSoFar, 10*x+(fromIntegral c)-48)

readInt :: B.ByteString -> Int readInt = B.foldl' (\x c -> 10*x+fromIntegral c-48) 0

main = do   (line, rest) <- B.break (==10) `fmap` B.getContents   let [n, k] = map readInt . B.split 32 $ line   putStrLn . show $ answer k rest - 1

Eugene, I ran your code on one of my test files and it gave the same answer as my code. So I submitted it and it was accepted. Its fast - twice as fast as my solution, using much less memory. Overall its the 4th fastest Haskell solution. (but its still 10 * slower than C/C++) I'll have to read up on BangPatterns to try to understand what its doing!

I submitted it as:

{-# LANGUAGE BangPatterns #-} module Main where

import qualified Data.ByteString.Lazy as B import qualified Data.Word            as DW

answer :: Int -> B.ByteString -> Int answer k = fst . B.foldl' f (0, 0)  where f :: (Int,Int) -> DW.Word8 -> (Int,Int)        f (!countSoFar, !x) 10          | x`mod`k==0 = (countSoFar+1, 0)          | otherwise  = (countSoFar,   0)        f (!countSoFar, !x) c = (countSoFar, 10*x+(fromIntegral c)-48)

readInt :: B.ByteString -> Int readInt = B.foldl' (\x c -> 10*x+fromIntegral c-48) 0

main :: IO () main = do  (line, rest) <- B.break (==10) `fmap` B.getContents  let [_, k] = map readInt . B.split 32 $ line  putStrLn . show $ answer k rest - 1

-- Eugene Kirpichov Web IR developer, market.yandex.ru

I've uploaded a new version of bytestring-nums that, while still slower than the fast/custom codes, allows Eugene's earlier program to a little more than 20% faster than it did before. It no longer handles spurious characters in the input by skipping over them (this is probably not a common requirement, anyways). http://hackage.haskell.org/package/bytestring-nums-0.3.0 I suspect that splitting the string into pieces and then mapping the parser over the pieces will never be faster than an all-in-one parser/tester/incrementer like the fast programs have. -- Jason Dusek