help with memory usage
Décio Luiz Gazzoni Filho
decio at decpp.net
Tue Mar 10 13:15:16 CET 2009
On Mar 9, 2009, at 2:42 PM, Christ Schlacta wrote:
> I've got the following simple struct:
> class prime_t { //prime list element type.
> public:
> prime_t();
> mpz_class *value;
> prime_t *next;
> };
>
> prime_t::prime_t(){
> this->value = new mpz_class;
> this->next = NULL;
> }
>
> it ends up being a linked list of mpz_class elements, each of which
> ends up being a prime number.
> The problem: I can get several hundred megabytes worth of prime
> numbers.. 250MB at my last count. But in memory, 250MB of prime
> numbers (stored as newline-delimited strings) ends up being more than
> 1600MB in memory using this structure. there are a few other structs,
> but the memory usage spikes only on loading the data file, and never
> goes down. I've already used valgrind to check for leaks, there are
> none.
Are you storing consecutive primes? Then store just a starting value v
and a bitmap with indices relative to this starting value, i.e. bit n
of the bitmap is 1 if v+n is prime and 0 if it is composite. This is
orders of magnitude more efficient than your data structure. If even
so you're pressed for memory, then drop the even integers from your
bitmap, i.e. force v to always be an odd integer and change the
indexing of your bitmap such that bit n is 1 if v+2n is prime and 0 if
it is composite. You can extend this trick -- for instance, modulo 30
= 2*3*5, only 8 (= (2-1)*(3-1)*(5-1) = 1*2*4) residue classes can give
rise to primes, while the remaining 22 only produce composites, so you
can cover regions of 30 integers in size using only 8 bits per region.
Depending on what you want to do, existing libraries like djb's
primegen may be fast enough and very space efficient, although
primegen is limited to primes 64 bits in size.
Décio
More information about the gmp-discuss
mailing list