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?
>
wooo! Woooo! After turning off the computer last night
and lying in bed waiting to zonk out, my error came to me!
I was cutting out at the right time for checking primes but
not for generating them! So my last reply, that brute force
is better in this case is wrong, here is my new test output that
shows that brute force loses!
06:41:36 up 24 min, 3 users, load average: 0.21, 0.17, 0.16
enter first number to test for enter last number to test for
105000000011 105000000059 105000000073 105000000109 105000000139
105000000197 105000000221 105000000229 105000000241 105000000283
105000000323 105000000377 105000000389 105000000467 105000000491
105000000509 105000000559 105000000577 105000000587 105000000613
105000000617 105000000631 105000000671 105000000697 105000000767
105000000773 105000000839 105000000841 105000000851 105000000901
105000000943 105000000967 105000000971 105000000977 105000000997
105000001003 105000001009 105000001019 105000001031 105000001063
105000001081 105000001087 105000001109 105000001121 105000001159
105000001163 105000001177 105000001187 105000001219 105000001229
105000001241 105000001277 105000001291 105000001391 105000001399
105000001409 105000001417 105000001423 105000001427 105000001453
105000001481 105000001493
Quit (y to exit)?
06:42:00 up 24 min, 3 users, load average: 0.68, 0.28, 0.19
Enter starting number? Enter ending number?
105000000011 105000000059 105000000073 105000000109 105000000139
105000000197 105000000221 105000000229 105000000241 105000000283
105000000323 105000000377 105000000389 105000000467 105000000491
105000000509 105000000559 105000000577 105000000587 105000000613
105000000617 105000000631 105000000671 105000000697 105000000767
105000000773 105000000839 105000000841 105000000851 105000000901
105000000943 105000000967 105000000971 105000000977 105000000997
105000001003 105000001009 105000001019 105000001031 105000001063
105000001081 105000001087 105000001109 105000001121 105000001159
105000001163 105000001177 105000001187 105000001219 105000001229
105000001241 105000001277 105000001291 105000001391 105000001399
105000001409 105000001417 105000001423 105000001427 105000001453
105000001481 105000001493
Quit (y to exit)?
27922 primes ranging from 2 through 324053 with a max reliable test of
105010346809
06:42:04 up 24 min, 3 users, load average: 0.68, 0.28, 0.19
thats, brute force 26 seconds, logic 4 seconds!
---
Scotty
Reply to: