|
|
|
|
|
|
| Author |
Message |
Scotty Fitzgerald
*nix forums beginner
Joined: 03 Feb 2005
Posts: 16
|
 Posted: Fri Feb 04, 2005 12:10 pm Post subject:
Re: Why does dynamic memory allocation take so long?
|
|
|
Roel Schroeven wrote:
| Quote: | 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
--
To UNSUBSCRIBE, email to debian-user-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org |
|
| Back to top |
|
 |
Scotty Fitzgerald
*nix forums beginner
Joined: 03 Feb 2005
Posts: 16
|
| Posted: Fri Feb 04, 2005 2:20 am Post subject:
Re: Why does dynamic memory allocation take so long?
|
|
|
Roel Schroeven wrote:
| Quote: | 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
--
To UNSUBSCRIBE, email to debian-user-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org |
|
| Back to top |
|
|
Roel Schroeven
*nix forums Guru Wannabe
Joined: 02 Mar 2005
Posts: 168
|
| Posted: Thu Feb 03, 2005 9:20 pm Post subject:
Re: Why does dynamic memory allocation take so long?
|
|
|
Scotty Fitzgerald wrote:
| Quote: | 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
--
To UNSUBSCRIBE, email to debian-user-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org |
|
| Back to top |
|
|
Scotty Fitzgerald
*nix forums beginner
Joined: 03 Feb 2005
Posts: 16
|
| Posted: Thu Feb 03, 2005 3:30 pm Post subject:
Why does dynamic memory allocation take so long?
|
|
|
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.
So I would like to know...
Am I right about a doggish garbage collection scheme?
Why is allocating memory this way so slow?
What are the real limits of using this kind of memory
allocation in the real world?
By the way, using the memory is just fine once I have it
allocated!
yours,
---
Scotty
--
To UNSUBSCRIBE, email to debian-user-REQUEST@lists.debian.org
with a subject of "unsubscribe". Trouble? Contact listmaster@lists.debian.org |
|
| Back to top |
|
|
Google
|
|
| Back to top |
|
|
|
|
The time now is Thu Jan 08, 2009 7:45 pm | All times are GMT
|
|
Homeowner Loans | Loan | Watch Naruto Online | Budapest hotels | Lyrics
|
|
Copyright © 2004-2005 DeniX Solutions SRL
|
|
|
|
Other DeniX Solutions sites:
Unix/Linux blog |
electronics forum |
medicine forum |
science forum |
|
|
Privacy Policy
|
Powered by phpBB © 2001, 2005 phpBB Group
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
Forum index
»
*nix
»
Linux
»
Distributions
»
Debian
