[email protected]
[Top] [All Lists]

Re: [Haskell-cafe] Re: FASTER primes (was: Re: Code and Perf. Data for

Subject: Re: [Haskell-cafe] Re: FASTER primes was: Re: Code and Perf. Data for Prime Finders (was: Genuine Eratosthenes sieve)
From: Daniel Fischer
Date: Tue, 29 Dec 2009 20:35:21 +0100

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
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
<Prev in Thread] Current Thread [Next in Thread>