[Haskell-cafe] Re: A suggestion for the next high profile Haskell project

[Chris Kuklewicz]

Hi all (and Don!),

  I have some rewritten versions of readInt below...

Bulat Ziganshin wrote:
> Hello Donald,
> 
> Monday, December 18, 2006, 3:51:48 AM, you wrote:
>>>> Haskell can't provide fast execution speed unless very low-level
>>>> programming style is used (which is much harder to do in Haskell than in C,
>>>> see one of my last messages for example) AND jhc compiler is used
> 
>> I have to dispute this Bulat's characterisation here. We can solve lots
>> of nice problems and have high performance *right now*. Particularly
>> concurrency problems, and ones involving streams of bytestrings.
>> No need to leave the safety of GHC either, nor resort to low level evil
>> code.
> 
> let's go further in this long-term discussion. i've read Shootout problems
> and concluded that there are only 2 tasks which speed is dependent on
> code-generation abilities of compiler, all other tasks are dependent on
> speed of used libraries. just for example - in one test TCL was fastest
> language. why? because this test contained almost nothing but 1000 calls to
> the regex engine with very large strings and TCL regex engine was fastest
> 
> the same applies to the two above-mentioned areas - GHC wins in concurrency
> tests just because only built-in libraries considered, and GHC has a
> lightweight threads library built-in while C compilers don't
> 
> with ByteString library, i know at least one example, where you have added
> function - readInt - to the library only to win in Shootout test
> 
>> This obsession with mutable-variable, imperative code is unhealthy, Bulat ;)
> 
> so why your readInt routine is written in imperative way? ;)
> 
> 
>>> ajb:
>>> The PGP format is heavily character stream-based.  We know how horrible
>>> the performance of character streams are in Haskell.  On one hand, this
>>> would be an excellent test case.  On the other hand, performance would
>>> indeed suck now.
> 
>> Unless you used a stream of lazy bytestrings! 
>> As Duncan did for his pure gzip and bzip2 bindings:
> 
> these are binding to existing C libs. if you try to convince us that to get
> fast FPS routines one need to write them in C and then provide Haskell
> binding, i will 100% agree
> 
> otherwise, please explain me why your own function, readInt, don't use
> these fascinating stream fusion capabilities? ;)
> 
>> P.S.  The comments on this thread makes me think that the state of the
>> art high perf programming in Haskell isn't widely known. Bulat-style 
>> imperative Haskell is rarely (ever?) needed in the GHC 6.6 Haskell code
>> I'm writing in these days. Solving large data problems is feasible
>> *right now* using bytestrings.
> 
> may be it's me who wrote FPS library? :)  let's agree that high-performance
> code can be written in C and then called from Haskell. and when *you* want
> to have real performance, you write something very far from your optimistic
> words:
> 
> readInt :: ByteString -> Maybe (Int, ByteString)
> readInt as
>     | null as   = Nothing
>     | otherwise =
>         case unsafeHead as of
>             '-' -> loop True  0 0 (unsafeTail as)
>             '+' -> loop False 0 0 (unsafeTail as)
>             _   -> loop False 0 0 as
> 
>     where loop :: Bool -> Int -> Int -> ByteString -> Maybe (Int, ByteString)
>           STRICT4(loop)
>           loop neg i n ps
>               | null ps   = end neg i n ps
>               | otherwise =
>                   case B.unsafeHead ps of
>                     w | w >= 0x30
>                      && w <= 0x39 -> loop neg (i+1)
>                                           (n * 10 + (fromIntegral w - 0x30))
>                                           (unsafeTail ps)
>                       | otherwise -> end neg i n ps
> 
>           end _    0 _ _  = Nothing
>           end True _ n ps = Just (negate n, ps)
>           end _    _ n ps = Just (n, ps)
> 
> 
>> Trying to write code using an imperative style is likely to do more harm
>> than good, and certainly not something to suggest to beginners on the
>> mailing list ;)
> 
> of course, if you want to fool beginners, you can continue to sing these
> songs :D
> 

That code for readInt has no mutable state or IO, and it may be imperative
style, it is not much like c-code.

I liked my readInt1 version below, which actually benchmarks faster than the GHC
6.6 Data.ByteString.Char8.readInt (on the little "test r" below).  What a
pleasant surprise.

The readInt2 version below is even more functional, but takes about 1.7 times as
long to run "test r".  (gaged from running "time ./ReadInt.2" on Mac OS X on a
G4 cpu).  The latest fusion in darcs fps might be better...

> module Main(main) where
> 
> import Control.Arrow((***))
> import Data.Char(chr,ord)
> import Data.ByteString(ByteString)
> import qualified Data.ByteString as B(null,foldl',span)
> import qualified Data.ByteString.Char8 as C (readInt,pack)
> import qualified Data.ByteString.Base as B(unsafeHead,unsafeTail)
> import Data.Ix(inRange)
> import Data.Maybe(fromJust)
> import Data.Word(Word8)
> 
> default ()
> 
> {-# INLINE chr8 #-}
> chr8 :: Word8 -> Char
> chr8 = chr . fromEnum
> {-# INLINE ord8 #-}
> ord8 :: Char -> Word8
> ord8 = toEnum . ord
> 
> {-# INLINE decompose #-}
> decompose :: a -> (Word8 -> ByteString -> a) -> ByteString -> a
> decompose whenNull withHeadTail bs =
>   if B.null bs then whenNull else (withHeadTail $! (B.unsafeHead bs)) $! (B.unsafeTail bs)
> 
> -- This does not do any bound checking if the Int overflows
> readInt1 :: ByteString -> Maybe (Int, ByteString)
> readInt1 bs = decompose Nothing (\h t ->
>     case h of
>       0x2d -> fmap (negate *** id) $ first t -- '-'
>       0x2b -> first t                        -- '+'
>       _    -> first bs) bs
>   where first :: ByteString -> Maybe (Int, ByteString)
>         first = decompose Nothing (\h t ->
>             if inRange (0x30,0x39) h
>               then Just (loop t $! (fromIntegral h-0x30))
>               else Nothing)
>         loop :: ByteString -> Int -> (Int, ByteString)
>         loop bs n = decompose (n,bs) (\h t ->
>             if inRange (0x30,0x39) h
>               then loop t $! (n*10+(fromIntegral h-0x30))
>               else (n,bs)) bs
> 
> 
> readInt2 :: ByteString -> Maybe (Int,ByteString)
> readInt2 bs =  decompose Nothing (\h t ->
>     case h of
>       0x2d -> fmap (negate *** id) $ toInt t -- '-'
>       0x2b -> toInt t                        -- '+'
>       _    -> toInt bs) bs
>   where toInt :: ByteString -> Maybe (Int,ByteString)
>         toInt bs = let (digits,rest) = B.span (inRange (0x30,0x39)) bs
>                    in if B.null digits then Nothing else Just (convert digits,rest)
>         convert :: ByteString -> Int
>         convert = B.foldl' (\n h -> n*10 + (fromIntegral h - 0x30)) 0
> 
> test r = let a = take 1000000 $ cycle [C.pack "13247897",C.pack "-13247896"]
>          in (sum . map (fst . fromJust . r) $ a
>             , take 4 a
>             , map r $ take 4 a)
> 
> main = print $ test $ (readInt2)