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)
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
