[Haskell-cafe] ANN: combinatorics

[Daniel Fischer]

On Wednesday 01 February 2012, 07:53:03, wren ng thornton wrote:
> > The primes function in the combinat package is based on an old Cafe
> > thread, and actually seems to be faster than the one in the
> > combinatorics package.

Yes, but it has a memory leak. On my box at least, with ghc 6.12, 7.0 and 
7.2.

> 
> The primes generator was some old code I had laying around for one of 
> those online programming challenges; fast enough for the task.
> I'll  probably trade it in for your algorithm though.

Why not use one of the packages on hackage which offer faster prime 
generators?

I'm aware of the following usable packages:

- primes: decentish performance if you don't need to sieve high, but not 
recommendable if you want to sieve above ~10^7, in my measurements about 
the same performance as the algorithm used in combinat, but without memory 
leak.

- NumberSieves: The O'Neill sieve, about twice as fast as the primes sieve, 
uses less memory (and scales better if you want to sieve to higher limits).

- arithmoi: A segmented Eratosthenes sieve using mutable unboxed arrays. 
Much faster than the above and uses less memory.
If you don't like arrays, it also has a priority queue sieve similar to the 
O'Neill sieve, but with a more efficient PQ implementation.

> One of the things
> I'm disappointed by about the current implementation is the memory
> overhead for storing the primes. It'd be nice to use chunked arrays of
> unboxed integers in order to remove all the pointers; but my attempt at
> doing so  had catastrophic performance...

arithmoi's Eratosthenes sieve offers the option to get a list of sieve 
chunks, basically UArray Int Bool, which gives far more compact storage 
than a list of Integers (~33KB per million range, much more compact than an 
unboxed array of primes for the reachable ranges) from which the list of 
primes can rather efficiently obtained when needed. That may do what you 
want well enough.

Cheers,
Daniel