help with memory usage

[Décio Luiz Gazzoni Filho]

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