Re: Why does dynamic memory allocation take so long?

[Roel Schroeven <rschroev_nospam_ml@fastmail.fm>]

Scotty Fitzgerald wrote:
> I was wondering why dynamic memory allocation took so long?
>
> I am getting back into programming, and thought that a good 
> first program to return to was to fool around with finding
> prime numbers.  Since I did not know how many possible factors
> I would need to generate, I started a type with a long integer
> and a memory pointer, and every time I generated a new prime
> number I added it to a list.  I discovered that to do this
> 15,000 times took about 45 seconds.  Since at the time I 
> was doing this in order to beat a brute force technique that 
> was stupidly looping though 333,333,333 million iterations, 
> I found my new routine to be a real dog.  At this point I will
> be rewriting to use an array with a depth of 30,000,000, which
> takes up about 250mb of memory, but allocates in a snap.
>
> I left out that I am programming in Pascal using GPC.  But I 
> don't think this is really relevant as I am sure that my use 
> of Pascal's new() somehow calls a linux memory allocation 
> routine.  I am guessing that there is some automatic memory
> garbage collection scheme that is a real dog to set up.

Well, dynamically allocating memory _is_ quite slow, but 45 seconds for 
15000 items seems excessive. I tried it in C using a small program, and 
it is _much_ faster:

$ time ./many_allocs 15000 > primes

real    0m0.013s
user    0m0.010s
sys     0m0.000s

Mind you, it doesn't really create primes. It just creates a listed link 
with 15000 items, prints the data part of all nodes to stdout and frees 
all items in the list.

I would expect C to be somewhat faster than Pascal, but the difference 
between 45 seconds and 0.013 seconds is, well, ridiculously large. I 
guess there must be something wrong somewhere...

Maybe it would help to post your code?

--
"Codito ergo sum"
Roel Schroeven