Gee, seems my mail server reads your posts very thoroughly today :) Am Dienstag 29 Dezember 2009 14:58:10 schrieb Will Ness: > Eugene Kirpichov <ekirpichov <at> gmail.com> writes: > > 2009/12/29 Will Ness <will_n48 <at> yahoo.com>: > > > Daniel Fischer <daniel.is.fischer <at> web.de> writes: > > >> Am Dienstag 29 Dezember 2009 04:38:21 schrieb Will Ness: > > >> > Now _this_, when tested as interpreted code in GHCi, runs about 2.5x > > >> > times faster than Priority Queue based code from Melissa O'Neill's > > >> > ZIP package mentioned at the haskellwiki/Prime_Numbers page, with > > >> > about half used memory reported, in producing 10,000 to 300,000 > > >> > primes. > > >> > > > >> > It is faster than BayerPrimes.hs from the ZIP package too, in the > > >> > tested range, at about 35 lines of code in total. > > >> > > >> That's nice. However, the important criterion is how compiled code > > >> (-O2) > > > > > > fares. Do the relations continue to hold? How does it compare to a > > > bitsieve? > > > > > > > > > Haven't gotten to that part yet. :) > > > > > > But why is it more important? Would that not tell us more about the > > > compiler performance than the code itself? > > > > If you mean "algorithmic complexity", you shouldn't care about a > > difference of 2.5x. > > It's not just at one point; the asymptotics are _the_same_ across the range > that I've tested (admittedly, somewhat narrow). I measure local behavior > simply as logBase in base of ratio of problem sizes, of the ratio of run > times. > > > If you mean "actual performance for a particular task", you should > > measure the performance in realistic conditions. Namely, if you're > > implementing a program that needs efficient generation of primes, > > won't you compile it with -O2? > > If I realistically needed primes generated in a real life setting, I'd > probably had to use some C for that.
If you need the utmost speed, then probably yes. If you can do with a little less, my STUArray bitsieves take about 35% longer than the equivalent C code and are roughly eight times faster than ONeillPrimes. I can usually live well with that. > If OTOH we're talking about a tutorial > code that is to be as efficient as possible without loosing it clarity, > being a reflection of essentials of the problem, then any overly > complicated advanced Haskell wouldn't be my choice either. +1 Though perhaps we view mutable array code differently. In my view, it's neither advanced nor complicated. > And seeing that > this overly-complicated (IMO), steps-jumping PQ-based code was sold to us > as the only "faithful" rendering of the sieve, I wanted to see for myself > whether this really holds water. I can understand that very well.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
