Re: Re[2]: [Haskell-cafe] Climbing up the shootout...
On Mon, Sep 22, 2008 at 2:07 PM, Bulat Ziganshin [EMAIL PROTECTED] wrote: this overall test is uselles for speed comparison. afair, there are only 2-3 programs whose speed isn't heavily depend on libraries. in DNA test, for example, Tcl (or PHP?) was leader just because it has better regexp library On the regex-dna benchmark, I'll have to agree. It's unfortunate to have a benchmark so dependent on the set of libraries included in the distribution, and e.g. Text.Regex.PCRE kicks Text.Regex.Posix's behind in this benchmark - but we probably can't use it only because one's bundled and the other isn't. Maybe we could roll our own regexp engine for this specific benchmark though (for example, Text.Regex.TDFA is within 10% or something of PCRE and AFAIK pure Haskell - a customized and downsized version of that could probably be made quite competitive). to make things even funnier, this test allows to use libs bundled to compiler, but not 3rd-arty ones. so ghc (not Haskell!) what includes more built-in libs than gcc looks like a leader. of course, noone uses bare ghc or gcc in real world I don't think it's ever claimed that the shootout is a fair benchmark of real-world problems :D 2) there uis a fashion in Haskell world to write for shootout in the very low-level style, which isn't actually used in real programming and actually understood only by a few wizards developing high-performance haskell code That is certainly the case with a few of the benchmark implementations, and in the past it was required to get the performance. In some cases it's also due simply to the haskell implementation being a straight-from-C port - which necessitates using pointers and putting everything in IO etc... Some of that haskell code is among the least readable code I've ever read (see e.g. the fannkuch benchmark at http://shootout.alioth.debian.org/u64q/benchmark.php?test=fannkuchlang=ghc). But that's what you get when porting pointer-rich C code directly into Haskell :) With bytestrings, unboxed arrays, light-weight threads and other tricks, we can usually replace all those ugly low-level programs with nice high-level haskell ones - it's all about allowing the compiler to do good stuff with naive (or at least naive-looking) code, and teaching it how to cut through the abstractions. (As well as using the right abstractions, of course...) // Simon ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Climbing up the shootout...
--- Simon Brenner [EMAIL PROTECTED] wrote: On Mon, Sep 22, 2008 at 2:07 PM, Bulat Ziganshin [EMAIL PROTECTED] wrote: this overall test is uselles for speed comparison. afair, there are only 2-3 programs whose speed isn't heavily depend on libraries. in DNA test, for example, Tcl (or PHP?) was leader just because it has better regexp library On the regex-dna benchmark, I'll have to agree. It's unfortunate to have a benchmark so dependent on the set of libraries included in the distribution, and e.g. Text.Regex.PCRE kicks Text.Regex.Posix's behind in this benchmark - but we probably can't use it only because one's bundled and the other isn't. Maybe we could roll our own regexp engine for this specific benchmark though (for example, Text.Regex.TDFA is within 10% or something of PCRE and AFAIK pure Haskell - a customized and downsized version of that could probably be made quite competitive). You could always suggest use of Text.Regex.PCRE, provide a program and instructions on how to install Text.Regex.PCRE on Ubuntu. -snip- With bytestrings, unboxed arrays, light-weight threads and other tricks, we can usually replace all those ugly low-level programs with nice high-level haskell ones ... Go do! ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Climbing up the shootout...
igouy2: --- Simon Brenner [EMAIL PROTECTED] wrote: On Mon, Sep 22, 2008 at 2:07 PM, Bulat Ziganshin [EMAIL PROTECTED] wrote: this overall test is uselles for speed comparison. afair, there are only 2-3 programs whose speed isn't heavily depend on libraries. in DNA test, for example, Tcl (or PHP?) was leader just because it has better regexp library On the regex-dna benchmark, I'll have to agree. It's unfortunate to have a benchmark so dependent on the set of libraries included in the distribution, and e.g. Text.Regex.PCRE kicks Text.Regex.Posix's behind in this benchmark - but we probably can't use it only because one's bundled and the other isn't. Maybe we could roll our own regexp engine for this specific benchmark though (for example, Text.Regex.TDFA is within 10% or something of PCRE and AFAIK pure Haskell - a customized and downsized version of that could probably be made quite competitive). You could always suggest use of Text.Regex.PCRE, provide a program and instructions on how to install Text.Regex.PCRE on Ubuntu. -snip- With bytestrings, unboxed arrays, light-weight threads and other tricks, we can usually replace all those ugly low-level programs with nice high-level haskell ones ... Go do! All is in hand. Tim Newsham's uploaded a regex-pcre and regex-posix entry to the wiki, and I'm testing now on quad core. If it survives testing, we'll submit it to Isaac. -- Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Climbing up the shootout...
igouy2: --- Simon Brenner [EMAIL PROTECTED] wrote: On Mon, Sep 22, 2008 at 2:07 PM, Bulat Ziganshin [EMAIL PROTECTED] wrote: this overall test is uselles for speed comparison. afair, there are only 2-3 programs whose speed isn't heavily depend on libraries. in DNA test, for example, Tcl (or PHP?) was leader just because it has better regexp library On the regex-dna benchmark, I'll have to agree. It's unfortunate to have a benchmark so dependent on the set of libraries included in the distribution, and e.g. Text.Regex.PCRE kicks Text.Regex.Posix's behind in this benchmark - but we probably can't use it only because one's bundled and the other isn't. Maybe we could roll our own regexp engine for this specific benchmark though (for example, Text.Regex.TDFA is within 10% or something of PCRE and AFAIK pure Haskell - a customized and downsized version of that could probably be made quite competitive). You could always suggest use of Text.Regex.PCRE, provide a program and instructions on how to install Text.Regex.PCRE on Ubuntu. I've now submitted a Text.Regex.PCRE parallelised entry written by Tim Newsham. It is by far the fastest haskell regex entry so far (down to 9s on quad core, from 100+ seconds on single core for the old entry), http://alioth.debian.org/tracker/index.php?func=detailaid=311132group_id=30402atid=411646 It does require the regex-pcre library, which if it isn't in your package system on Ubuntu, you can certainly build, $ wget http://hackage.haskell.org/packages/archive/regex-pcre-builtin/0.94.2.0.7.7/regex-pcre-builtin-0.94.2.0.7.7.t ar.gz $ tar xzf regex-pcre-builtin-0.94.2.0.7.7.tar.gz $ cd regex-pcre-builtin-0.94.2.0.7.7 $ runhaskell Setup.hs configure --prefix=$HOME $ runhaskell Setup.hs build $ sudo runhaskell Setup.hs install I also included these details on the ticket. It uses a simple parMap strategy. Cheers, Don ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Climbing up the shootout...
2008/9/23 Bulat Ziganshin [EMAIL PROTECTED]: http://haskell.org/haskellwiki/Wc seems to do fine; you'll notice it drops lines after the first version. actually it counts lines using built-in function. you may find that naive C is 6x fatser than naive Haskell and difference is so small only because C version is bound by memory speed So what ? Strings represented as lists of character are slow ? What an incredible discovery ! The ByteString versions are fast, ByteString was invented especially for IO intensive situation, it's a library you can use pretty naively and mostly get excellent performances, what exactly isn't Haskelly enough for you in this solution ? The guts of ByteString aren't idiomatic Haskell ? And ? The guts of the JVM aren't written in Java either... At least ByteString was built over GHC which means it can be done. Besides a part of the performances of ByteString comes from stream fusion and that's specifically something that is hard to achieve outside of Haskell... What exactly is your point ? - Haskell is slow, we can't make it faster ? That's obviously false as demonstrated by the progress in the latest years. - Haskell is slower than C ? Well that's probably true, because C can touch the hardware directly and can always optimize every single aspects of a computation... On the other hand that kind of uber optimization has a cost that I am unwilling to pay, I would rather write high level Haskell and pay a little hit on execution time. - We shouldn't center ourselves around performance to promote Haskell (or should we even promote Haskell) ? Well there you may have a point, but maybe it would be better to just make it and avoid denying other peoples efforts to make Haskell faster ? -- Jedaï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Climbing up the shootout...
2008/9/23 Bulat Ziganshin [EMAIL PROTECTED]: Hello Don, Tuesday, September 23, 2008, 4:22:19 AM, you wrote: bulat.ziganshin: when gcc developers will start to add to C libraries functions performing shootout benchmarks we will continue this discussion :D atoi(3). it isn't the same as readInt which was added specifically for this test. it doesn't support arbitrary-size streams and doesn't return rest of stream Yeah, readInt has a more useful type than atoi() in most circumstances so obviously it's a default which somehow disqualify this function... (I wasn't aware that this function was only useful in the shoutout context, I should probably scrap it from my other programs now) I think we should write all the entries in Haskell98 and disable any optimisation in GHC too, that would gives us a much fairer vision of Haskell current performances. -- Jedaï ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: Re[2]: [Haskell-cafe] Climbing up the shootout...
At the risk of getting sucked into a silly discussion, I'd like to point out that the c code uses the following really simple and naive function: http://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/strtol.c?rev=1.42.2.2content-type=text/x-cvsweb-markupcvsroot=glibc http://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/strtol_l.c?rev=1.4.2.3content-type=text/x-cvsweb-markupcvsroot=glibc Oh, and it simply and naively loops with the following: while (fgets_unlocked (line, MAXLINELEN, stdin)) If Bulat's point is that the shootout has inspired work on Haskell performance, and in the stdlibs no less, then lovely, and that's all to the good. Below every high level interface is lots of low level pain. If his point is anything else, this is getting absurd. --S On Mon, Sep 22, 2008 at 8:16 PM, Bulat Ziganshin [EMAIL PROTECTED]wrote: Hello Don, Tuesday, September 23, 2008, 3:12:37 AM, you wrote: for the same reason i don't feed 5000 men with 7 breads - it's not my business ;) Ok. So I'll just say: high level, efficient code is an overriding theme of many individuals working on Haskell. Things are better and better each year. We do not stand still. yes. when we say that things are greatly improving each year, this means that they was bad previously ;) For example, Bulat cites a paper talking about naive list code from 2002, however, by 2008 we know how to do fusion on lists, so it runs in the same time as low level loops, the technique is implemented and you can download it from hackage, http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion someone can ask why this great code isn't used in ghc by default. probably it is just work in progress which isn't yet ready to replace old slow code. then we can see tha fusion isn't magic wand which improves speed of every haskell code that's slower than C one. it just makes C-speed code sometimes Simon Marlow is busy adding more efficient GC and parallelism to GHC, and there's a summer project to rewrite the native code generator. well, i'm sais about *current* real situation. if you consider this as attack against Haskell developers, it's your mistake. the problem is that i many years wrote about slowness of ghc code, every time you cosider this as attack and write that in future Haskell will become much faster. we still wait for this future, however GHC gained pointer tagging in the last release cycle, dramatically reducing the cost of algebraic data types. 10-20% speed improvement, on average. it's the only real improvement (for my own program) i know. i think that ByteString-related libs gived more improvements but their use isn't automatic and they doesn't help in any situation. they just provide fast library code for solving some concrete (although very frequent) situations, such as counting lines At the same time, we're writing books about how to program naively in Haskell, such that your code doesn't suck. That is: training. Teaching people how to write Haskell. it is what i say - if naive code was effective and automagically optimized by ghc, we don't need all those tutorials. anyone looked into your tutorial on writing efficient Haskell code, will never say that it's easier than in C. so we can conclude that optimized haskell programs are several times slower than C ones and need several times more to write We can see it paying off, where naive code performs very very well, http://shootout.alioth.debian.org/gp4/benchmark.php?test=sumcollang=all yes! it's my beloved example of elegant haskell code entirely based on the readInt function added to ghc libs specifically to win in this test. it's implementation is really simple and naive: -- - -- Reading from ByteStrings -- | readInt reads an Int from the beginning of the ByteString. If there is no -- integer at the beginning of the string, it returns Nothing, otherwise -- it just returns the int read, and the rest of the string. 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) when gcc