Hi All, I've been enjoying following the thread about the "shootout" programs and trying to understand the performance of the entries, especially the Fannkuch benchmark. I've been comparing Sebastion's and Bertram's proposals found on the wiki. On my machine (PowerBook g4 (512M), GHC 6.4.1), Bertam's is about 3x faster. I think the main reason for the difference is that Bertram's conses much less and keeps much less data live on the heap. I don't find Bertram's version especially hard to read. I tripped on '>>=', but it was easy to look it up. You can substitute "concatMap" without penalty if you hate monads. The technique used in Bertram's `flop' is known to anyone who has been introduced to streams. I think Bertram solution is an idiomatic "engineered" Haskell program. Cheers, David ------------------------------------------------- [Marcel:~/pfann] david% time ./Sebastion 9 123456789 ... Pfannkuchen(9) = 30 8.132u 0.250s 0:08.89 94.2% 0+0k 0+2io 0pf+0w ------------------------------------------------- [Marcel:~/pfann] david% time ./Bertram 9 123456789 ... Pfannkuchen(9) = 30 2.629u 0.100s 0:03.10 87.7% 0+0k 0+4io 0pf+0w ------------------------------------------------- ------------------------------------------------- ./Sebastion 9 +RTS -K256m -c -sstderr 123456789 ... Pfannkuchen(9) = 30 911,697,700 bytes allocated in the heap 3,138,348 bytes copied during GC 5,172 bytes maximum residency (2 sample(s)) 3478 collections in generation 0 ( 0.28s) 2 collections in generation 1 ( 0.01s) 2 Mb total memory in use INIT time 0.00s ( 0.00s elapsed) MUT time 7.85s ( 8.52s elapsed) GC time 0.29s ( 0.44s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 8.14s ( 8.96s elapsed) %GC time 3.6% (4.9% elapsed) Alloc rate 116,139,834 bytes per MUT second Productivity 96.4% of total user, 87.6% of total elapsed ------------------------------------------------- ./Bertram 9 +RTS -K256m -c -sstderr 123456789 ... Pfannkuchen(9) = 30 271,671,720 bytes allocated in the heap 818,676 bytes copied during GC 5,220 bytes maximum residency (1 sample(s)) 1036 collections in generation 0 ( 0.08s) 1 collections in generation 1 ( 0.00s) 1 Mb total memory in use INIT time 0.00s ( 0.01s elapsed) MUT time 2.56s ( 2.90s elapsed) GC time 0.08s ( 0.09s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 2.64s ( 3.00s elapsed) %GC time 3.0% (3.0% elapsed) Alloc rate 106,121,765 bytes per MUT second Productivity 97.0% of total user, 85.3% of total elapsed ------------------------------------------------------ -------------------------------- David F. Place mailto:d@vidplace.com
On 1/6/06, David F. Place
Hi All,
I've been enjoying following the thread about the "shootout" programs and trying to understand the performance of the entries, especially the Fannkuch benchmark. I've been comparing Sebastion's and Bertram's proposals found on the wiki. On my machine (PowerBook g4 (512M), GHC 6.4.1), Bertam's is about 3x faster. I think the main reason for the difference is that Bertram's conses much less and keeps much less data live on the heap.
I don't find Bertram's version especially hard to read. I tripped on '>>=', but it was easy to look it up. You can substitute "concatMap" without penalty if you hate monads. The technique used in Bertram's `flop' is known to anyone who has been introduced to streams.
I think Bertram solution is an idiomatic "engineered" Haskell program.
Yes, Bertram's is faster. But it's also a lot less readable, IMO. It uses explicit recursions instead of standard library functions, and extra complexities here and there. The usage of >>= (and the list monad) is one example, but have a look at the flop function. I can only speak for myself but to me that's pretty difficult to understand, and I really doubt that anyone who hasn't done a significant amount of Haskell programming will grasp it at all. So like it says on the wiki, I wrote the most obvious and clear solution I could come up with, which proved to be several times faster than the existing Haskell solution in the shootout. I do not claim that it's the fastest solution possible (in fact, I knew it wasn't) but it does *no* optimizations that hurt clarity (by design!). If you think that Bertrams solution is readible then great, then we have an optimized version that's somewhat readible (personally, I think it's pretty rough reading, and I can only imagine how a non-Haskeller would feel). If it turns out that the fastest we comes up with uses Ptrs and is written entirely in the IO monad, then we're not so lucky. /S -- Sebastian Sylvan +46(0)736-818655 UIN: 44640862
On Jan 6, 2006, at 11:48 AM, Sebastian Sylvan wrote:
Yes, Bertram's is faster. But it's also a lot less readable, IMO. It uses explicit recursions instead of standard library functions, and extra complexities here and there. The usage of >>= (and the list monad) is one example,
You can substitute this equivalent definition without penalty permutations l = foldr perm' [l] [2..length l] where perm' n l = concatMap (take n . iterate (rotate n)) l
but have a look at the flop function. I can only speak for myself but to me that's pretty difficult to understand, and I really doubt that anyone who hasn't done a significant amount of Haskell programming will grasp it at all.
However, it is just the kind of haskell programming that you might need to do to make a program run fast. It's rather elegant compared to what you would need to do in an imperative language, yes-no?
So like it says on the wiki, I wrote the most obvious and clear solution I could come up with, which proved to be several times faster than the existing Haskell solution in the shootout. I do not claim that it's the fastest solution possible (in fact, I knew it wasn't) but it does *no* optimizations that hurt clarity (by design!).
Well, if I make the following change to your program it doesn't have any effect on its performance. -- fannuch xs = foldl' max 0 $ map flop xs fannuch xs = foldl max 0 (map flop xs) The strict foldl and strict apply do seem to be examples of optimizations that hurt clarity, but in this case don't seem to help performance. Cheers, David -------------------------------- David F. Place mailto:d@vidplace.com
participants (3)
-
David F. Place -
David F.Place
-
Sebastian Sylvan