[Haskell-cafe] Re: Simple FAST lazy functional primes

[Will Ness]

Jason Dagit <dagit <at> codersbase.com> writes:

> By the way, do you understand where the speedup with Int is coming from?  As I
understand it, there are two main places.  One is that the type class dictionary
passing can be removed (GHC might figure this out already, I'd need to check the
core to be sure).  The other is that GHC is likely unboxing to it's primitive
Int# type.
> [...]
> Good luck!
> Jason


Thanks!

Writing the super-fast sieve wasn't my objective here though. It rather was
writing the fastest possible simple functional lazy code true to the sieve's
definition, and understanding it better that way (that's the added bonus).

As it stands now, this code seems a rather faithful description of what _is_
sieve, except that it tests each number in isolation instead of counting over a
bunch of them at once (skipping over primes, getting them for free). THAT's the
crucial difference, which the article seems trying to explain but never quite
gets it in such simple terms. All the extra activity is kept to absolute minimum
here, and _now_ the main thing can be dealt with further, if so desired - like
turning to using the PQ thing, etc. 

Then if we were to compare them, it wouldn't be like comparing apples with
orange juice. :)  That's what it felt like, seeing the PQ code compared with the
classic "naive" version in that article. I'm reasonably sure that PQ-augmented,
this code will be even faster, not slower, even for the first million primes. 

This whole experience proves it that the clearest code can also be the fastest
(and may be necessarily so). Seeing it described in that article as if clarity
must be paid for with efficiency (and vice versa), didn't seem right to me.


Cheers,
 


> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe <at> haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>