Re: Why does dynamic memory allocation take so long?
Roel Schroeven wrote:
> 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?
>
I'll be damned! brute force actually works better than storing
the primes in an array and then only using those primes as
test-factors! I've tested it out to over a quintrillian!
Here is my comparison, the first case is just looping up to
the square root and dividing all those numbers into the targets.
the second case builds an arry of primes in memory, takes 34
seconds to do 11,520 primes this way. So what I originally
posted as taking 45s to allocate 15,000 items in memory, was
really taking 45s to actually select those 15,000 numbers.
I honestly truly expected brute force to lose, I guess my
expectation was wrong!
Heres my output, if you want to see the programs, let me know
and I will post them into this thread.
---
Scotty
21:49:48 up 1:52, 3 users, load average: 0.01, 0.08, 0.21
enter first number to test for enter last number to test for
15000000007 15000000013 15000000047 15000000077 15000000089
Quit (y to exit)?
21:49:49 up 1:52, 3 users, load average: 0.01, 0.08, 0.21
Enter starting number? Enter ending number?
15000000007 15000000013 15000000047 15000000077 15000000089
Quit (y to exit)?
11520 primes ranging from 2 through 122477 with a max reliable test of
15000615529
21:50:23 up 1:53, 3 users, load average: 0.45, 0.18, 0.24
Reply to: