[Haskell-cafe] Re: FASTER primes (was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve))

Eugene Kirpichov ekirpichov at gmail.com
Tue Dec 29 08:37:13 EST 2009

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.
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
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

Eugene Kirpichov
Web IR developer, market.yandex.ru

More information about the Haskell-Cafe mailing list