2009/12/29 Will Ness <[email protected]>: > 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. 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? > This code is just an endpoint (so far) in a short procession of natural > stepwise > development of the famous classic Turner's sieve, through the "postponed > filters", through to Euler's sieve, the merging sieve (i.e. Richard Bird's) > and > on to the tree-fold merging, with wheel. I just wanted to see where the simple > "normal" (i.e. _beginner_-friendly) functional code can get, in a natural way. > > It's not about writing the fastest code in _advanced_ Haskell. It's about > having > clear and simple code that can be understood at a glance - i.e. contributes to > our understanding of a problem - faithfully reflecting its essential elements, > and because of _that_, fast. It's kind of like _not_ using mutable arrays in a > quicksort. > > Seeing claims that it's _either_ Turner's _or_ the PQ-based code didn't feel > right to me somehow, especially the claim that going by primes squares is "a > pleasing but minor optimization", what with the postponed filters (which > serves > as the framework for all the other variants) achieving the orders of magnitude > speedup and cutting the Turner's O(n^2) right down to O(n^1.5) just by doing > that squares optimization (with the final version hovering around 1.24..1.17 > in > the tested range). The Euler's sieve being a special case of Eratosthenes's, > too, doesn't let credence to claims that only the PQ version is somehow > uniquely > authentic and "faithful" to it. > > Turner's sieve should have been always looked at as just a specification, not > a > code, anyway, and actually running it is ridiculous. Postponed filters > version, > is the one to be used as a reference point of the basic _code_, precisely > because it _does_ use the primes squares optimization, which _is_ essential to > any basic sieve. > > >> _______________________________________________ >> Haskell-Cafe mailing list >> Haskell-Cafe <at> haskell.org >> http://www.haskell.org/mailman/listinfo/haskell-cafe >> > > > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > -- Eugene Kirpichov Web IR developer, market.yandex.ru _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
