Re: [Haskell-cafe] g++ std:map vs GHC IntMap
On Thursday 26 March 2009 15:39:12 Manlio Perillo wrote: I also tried with Data.HashTable: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2902 but memory usage is 703 MB, and execution time is about 4.5 times slower! This is due to a perf bug in GHC's GC implementation that causes it to traverse entire arrays when a single element has been changed. Hence the Haskell is over an order of magnitude slower than most languages and even slower than Python (!). The purely functional trees that you also used are apparently the idiomatic Haskell workaround but, of course, they are extremely inefficient and still over an order of magnitude slower than any decent hash table. For comparison: Haskell hash table: 44s Haskell map: 7s F# hash table: 0.7s -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] g++ std:map vs GHC IntMap
On Sat, Apr 4, 2009 at 12:42 PM, Jon Harrop j...@ffconsultancy.com wrote: For comparison: Haskell hash table: 44s Haskell map: 7s F# hash table: 0.7s Ouch! That's pretty insane. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] g++ std:map vs GHC IntMap
So how does F# IntMap version compares to Haskell's IntMap? On Sat, Apr 4, 2009 at 2:58 PM, Peter Verswyvelen bugf...@gmail.com wrote: On Sat, Apr 4, 2009 at 12:42 PM, Jon Harrop j...@ffconsultancy.com wrote: For comparison: Haskell hash table: 44s Haskell map: 7s F# hash table: 0.7s Ouch! That's pretty insane. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] g++ std:map vs GHC IntMap
On Saturday 04 April 2009 14:02:48 Peter Verswyvelen wrote: On Sat, Apr 4, 2009 at 12:42 PM, Jon Harrop j...@ffconsultancy.com wrote: For comparison: Haskell hash table: 44s Haskell map: 7s F# hash table: 0.7s So how does F# IntMap version compares to Haskell's IntMap? F# map: 43.5s -- Dr Jon Harrop, Flying Frog Consultancy Ltd. http://www.ffconsultancy.com/?e ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] g++ std:map vs GHC IntMap
Hi. I have tried to compare performance of the g++ std::map versus the GHC IntMap. The test consists in adding 1000 elements to an empty map. Haskell code is here: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2899 C++ code is here: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2900 The execution time and CPU usage is almost the same. However the C++ version requires 305 MB, the GHC version 617 MB. gcc 4.3.2 ghc 6.8.2 on Debian Linux Lenny, i386. Isn't really possible to optimize memory usage in cases like this? I also tried with Data.HashTable: http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2902 but memory usage is 703 MB, and execution time is about 4.5 times slower! Thanks Manlio Perillo ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] g++ std:map vs GHC IntMap
On 2009 Mar 26, at 11:39, Manlio Perillo wrote: The execution time and CPU usage is almost the same. However the C++ version requires 305 MB, the GHC version 617 MB. I wonder how much of that is due to lifting (i.e. laziness). -- brandon s. allbery [solaris,freebsd,perl,pugs,haskell] allb...@kf8nh.com system administrator [openafs,heimdal,too many hats] allb...@ece.cmu.edu electrical and computer engineering, carnegie mellon universityKF8NH PGP.sig Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] g++ std:map vs GHC IntMap
Hello Manlio, Thursday, March 26, 2009, 6:39:12 PM, you wrote: The test consists in adding 1000 elements to an empty map. +RTS -c -F1.1 then read about garbage collection -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] g++ std:map vs GHC IntMap
Brandon S. Allbery KF8NH ha scritto: On 2009 Mar 26, at 11:39, Manlio Perillo wrote: The execution time and CPU usage is almost the same. However the C++ version requires 305 MB, the GHC version 617 MB. I wonder how much of that is due to lifting (i.e. laziness). http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2911 Performances are the same; but I'm not sure if this removes all laziness. I have changed ins t (k,x) = insert k x t to ins t (k,x) = k `seq` x `seq` insert k x t Manlio ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] g++ std:map vs GHC IntMap
Bulat Ziganshin ha scritto: Hello Manlio, Thursday, March 26, 2009, 6:39:12 PM, you wrote: The test consists in adding 1000 elements to an empty map. +RTS -c -F1.1 then read about garbage collection It now requires 386 MB of memory, but is 4.7 times slower. So, now memory required is about the same as the C++ version, but how can I optimize memory usage without having to tweak the garbage collector? Thanks Manlio ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] g++ std:map vs GHC IntMap
Hello Manlio, Thursday, March 26, 2009, 8:17:03 PM, you wrote: So, now memory required is about the same as the C++ version, but how can I optimize memory usage without having to tweak the garbage collector? C++ doesn't use GC so why you compare? -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] g++ std:map vs GHC IntMap
manlio_perillo: Bulat Ziganshin ha scritto: Hello Manlio, Thursday, March 26, 2009, 6:39:12 PM, you wrote: The test consists in adding 1000 elements to an empty map. +RTS -c -F1.1 then read about garbage collection It now requires 386 MB of memory, but is 4.7 times slower. So, now memory required is about the same as the C++ version, but how can I optimize memory usage without having to tweak the garbage collector? You'll need similar data structures. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re[2]: [Haskell-cafe] g++ std:map vs GHC IntMap
Hello Don, Thursday, March 26, 2009, 8:26:18 PM, you wrote: +RTS -c -F1.1 It now requires 386 MB of memory, but is 4.7 times slower. So, now memory required is about the same as the C++ version, but how can I optimize memory usage without having to tweak the garbage collector? You'll need similar data structures. can +RTS -A400m be consider as similar data structure ? :) -- Best regards, Bulatmailto:bulat.zigans...@gmail.com ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe