Connecting Tech Pros Worldwide Help | Site Map

Trouble optimizing for-loop

Newbie
 
Join Date: Jun 2007
Posts: 18
#1: Sep 24 '07
This is actaully a really simple recursion (for-loop), but I'm having some trouble optimizing it so that it would run faster.

Expand|Select|Wrap|Line Numbers
  1. for (int i = 0; i < 50; i++)
  2. {
  3. a[i] = getNumber(i);
  4. }
Right now it takes around 40-50 seconds to run.

I've already tried loop unrolling, but that didn't optimize it at all.

Loop unrolling:

Expand|Select|Wrap|Line Numbers
  1. for (int i = 0; i < 50; i += 5)
  2. {
  3. a[i] = getNumber(i);
  4. a[i+1] = getNumber(i+1);
  5. a[i+2] = getNumber(i+2);
  6. a[i+3] = getNumber(i+3);
  7. a[i+4] = getNumber(i+4);
  8. }
I'm still new to C++ and out of practice at the moment, I'm sure theres a method out there that could either optimize or replace my recursion but do the same thing, could anyone care to enlighten me?

Thanks.
gpraghuram's Avatar
Expert
 
Join Date: Mar 2007
Location: Chennai
Posts: 1,256
#2: Sep 24 '07

re: Trouble optimizing for-loop


Quote:

Originally Posted by inihility

This is actaully a really simple recursion (for-loop), but I'm having some trouble optimizing it so that it would run faster.

Expand|Select|Wrap|Line Numbers
  1. for (int i = 0; i < 50; i++)
  2. {
  3. a[i] = getNumber(i);
  4. }
Right now it takes around 40-50 seconds to run.

I've already tried loop unrolling, but that didn't optimize it at all.

Loop unrolling:

Expand|Select|Wrap|Line Numbers
  1. for (int i = 0; i < 50; i += 5)
  2. {
  3. a[i] = getNumber(i);
  4. a[i+1] = getNumber(i+1);
  5. a[i+2] = getNumber(i+2);
  6. a[i+3] = getNumber(i+3);
  7. a[i+4] = getNumber(i+4);
  8. }
I'm still new to C++ and out of practice at the moment, I'm sure theres a method out there that could either optimize or replace my recursion but do the same thing, could anyone care to enlighten me?

Thanks.

HI,
Themproblem is not with the for loop.
The problem is with the function getNumber().
Use time function to calculate the time taken by the getNumber() method and then try to optimize the function

Raghuram
Newbie
 
Join Date: Jun 2007
Posts: 18
#3: Sep 24 '07

re: Trouble optimizing for-loop


I do have a timer that calculates how long the function takes, and its roughly 40-50 seconds like I said, and I haven't been able to do anything to optimize it just yet, is there any method to optimize the extraction/storage of the variables from the function to the array?
Savage's Avatar
Expert
 
Join Date: Feb 2007
Posts: 1,737
#4: Sep 24 '07

re: Trouble optimizing for-loop


Well, if you are working in c++ you can return reference, this will avoid unnecessary copying from function to your array.

Savage
Newbie
 
Join Date: Jun 2007
Posts: 18
#5: Sep 24 '07

re: Trouble optimizing for-loop


I'm still new to reference returns and pointers in general, how would I be able to imitate what the for-loop is doing using other methods that would be much more speedy?

I was thinking of something like:

1. Run function (somewhere outside of a loop)
2. Point to array
3. Fill space in array with number
...
Newbie
 
Join Date: Aug 2007
Posts: 12
#6: Sep 25 '07

re: Trouble optimizing for-loop


why cant you try this code

for( i= 50 ; i > 0 ; i--- )
{

// code
}

why I said this would when ever you say in the for loop i = 0 ..Zero flag gets initialised ..
that also consumes some extra time..

In turn my suggestion is instead of having a incremental loop use a decremental loop..
just check whether it works for you or not..
let me know about the result
Newbie
 
Join Date: Jun 2007
Posts: 18
#7: Sep 25 '07

re: Trouble optimizing for-loop


Interesting suggestion, I just ran it, its still taking some time to load...

it took 20 seconds more than my last attempt, and it ended with an error :(

I think the point of the exercise is to replace the recursion with something else...i.e. not a recursion? like I said I'm new to pointers and beyond so if anyone has an idea of how to tackle this please let us know.

(continues to attempt the problem)


edit: the solution given was a runtime of 0 seconds btw. so supposedly this "new" method should reduce run time completely, not just optimize it slightly.
Savage's Avatar
Expert
 
Join Date: Feb 2007
Posts: 1,737
#8: Sep 25 '07

re: Trouble optimizing for-loop


Quote:

Originally Posted by inihility

Interesting suggestion, I just ran it, its still taking some time to load...

it took 20 seconds more than my last attempt, and it ended with an error :(

I think the point of the exercise is to replace the recursion with something else...i.e. not a recursion? like I said I'm new to pointers and beyond so if anyone has an idea of how to tackle this please let us know.

(continues to attempt the problem)


edit: the solution given was a runtime of 0 seconds btw. so supposedly this "new" method should reduce run time completely, not just optimize it slightly.

Can you replace getNumber with something like getArray?

Savage
kreagan's Avatar
Familiar Sight
 
Join Date: Aug 2007
Location: New Hampshire
Posts: 153
#9: Sep 25 '07

re: Trouble optimizing for-loop


Quote:

Originally Posted by inihility

This is actaully a really simple recursion (for-loop), but I'm having some trouble optimizing it so that it would run faster.

I don't understand why this is recursive

Quote:

Originally Posted by inihility

Expand|Select|Wrap|Line Numbers
  1. for (int i = 0; i < 50; i++)
  2. {
  3. a[i] = getNumber(i);
  4. }
Right now it takes around 40-50 seconds to run.

50 iterations shouldn't take very long. If you took out the "getNumber" function but stilled timed it, the time should be less than 1 second. I'm guessing it takes your getNumber function about a second to complete. I would suggest analysing that function instead of the for-loop.

If you are having problems with pointers, try looking at these web resources.
Tutorial on Pointers
Tutorial on Pointers WITH PICTURES!!! :)

Pointers are good when you have many copies of a variable - but the copies will all stay the same. Instead of changing many copies, just have them point to the variable instead and change the variable instead.

A good example of a point is URL links. You give the location on where to go. Imagine if you couldn't give the location but had to store the page itself. If that page changed, you have to change ALL the locations where the page is stored. I hope that was a good analogy to explain why pointers can be quicker.
JosAH's Avatar
Expert
 
Join Date: Mar 2007
Posts: 10,611
#10: Sep 25 '07

re: Trouble optimizing for-loop


Quote:

Originally Posted by avinash jain

In turn my suggestion is instead of having a incremental loop use a decremental loop..
just check whether it works for you or not..
let me know about the result

Don't do that; if a processor prefetched pages from memory (after a cache miss)
it fetches them in a forward direction. Your suggestion kills the number of cache
hits big times.

kind regards,

Jos
Newbie
 
Join Date: Jun 2007
Posts: 18
#11: Sep 26 '07

re: Trouble optimizing for-loop


@ kreagon

The exercise only allows me to change the for-loop, or delete it and put in something new, editing the function is out of my power :(

ty for the links.
Ganon11's Avatar
Moderator
 
Join Date: Oct 2006
Location: New York, United States of America
Posts: 3,428
#12: Sep 26 '07

re: Trouble optimizing for-loop


Can you look at what getNumber(i) does and somehow replace it with hard-code here? I came to the same conclusion that getNumber is what is slowing you down, so the way to speed this code snippet up is to remove that function.
Reply