Trouble optimizing for-loop

[inihility]

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

for (int i = 0; i < 50; i++)
{
a[i] = getNumber(i);
}

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:

for (int i = 0; i < 50; i += 5)
{
a[i] = getNumber(i);
a[i+1] = getNumber(i+1);
a[i+2] = getNumber(i+2);
a[i+3] = getNumber(i+3);
a[i+4] = getNumber(i+4);
}

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]

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

for (int i = 0; i < 50; i++)
{
a[i] = getNumber(i);
}

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:

for (int i = 0; i < 50; i += 5)
{
a[i] = getNumber(i);
a[i+1] = getNumber(i+1);
a[i+2] = getNumber(i+2);
a[i+3] = getNumber(i+3);
a[i+4] = getNumber(i+4);
}

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

[inihility]

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]

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

Savage

[inihility]

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
...

[avinash jain]

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

[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.

[Savage]

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]

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

for (int i = 0; i < 50; i++)
{
a[i] = getNumber(i);
}

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]

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

[inihility]

@ 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]

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.