If statements in FOR loops

mush

G'day all,

Does anybody know which has greater overhead?

For(x = nNumber; x; x--)
{
//Do stuff
If(x < nSmallerNumber)
{
// Do less stuff
}
}

Or this

For(x = nNumber; x; x--)
{
//Do stuff
}
For(x = nSmallerNumber; x; x--)
{
//Do stuff
}

In the first example you only have the overhead of one for loop but a conditional statement that has to be processed nNumber times.
The second example has the overhead of two for loops but no conditional.
I seem to recall being told that FOR loops in NetLinx are a bit strange.

Cheers


Mush

a_riot42

mush wrote: »

Does anybody know which has greater overhead?

I can't imagine it would make much difference. Just stay away from nested for loops if you can. There isn't much point in optimizing a for loop, since whatever you do could only have a miniscule effect on overall execution. You don't show the 'do stuff' code and that might influence my choice, but I would write it the first way since its more standard practice. But it depends on what you are trying to do as there are times when two for loops makes more sense.
Paul

mush

a_riot42 wrote: »

Just stay away from nested for loops if you can.

Why no nested loops?

ericmedley

I use nested loops quite a bit. The one thing to remember is the Netlinx processor is not truly multi-threading in the normal sense that most programmers understand. In most common computer programming, when implimenting a nested set of loops (or any other cpu consuming process) the thread will be stuck doing the loops until it's finished. But there are other threads available to keep the boat floating down the river. This thread can be stuck for a long time in both human and CPU time.

In Netlinx land, your master will pretty much stop all processes while doing the loops. I've never had anything get lost or dumped during a particularly spendy nested loop (as far as I know) but I suppose the possibility is there.

Like most things, it's a tool and you have to know when to use it and what it costs to do so.

Spire_Jeff

If you have a bit of code that you would like me to test, I will. Can you give me an idea of what is being done in each case?

Jeff

DHawthorne

I'll nest two FOR loops regularly, but try not to go deeper than that ... not for any processor load reasons, but because I have trouble keeping track of it myself.

Spire_Jeff

I decided to run the following methods through my testing code just for fun. Here are the results I got. First, the functions I tested:

define_function testSequentialFor(){
	stack_var integer x;
	stack_var integer y,z;

	TestName(1,'for(){};for(){}');
	TestStartHighRes(1);
	for(x=1000;x;x--){
		y++;
	}
	for(x=500;x;x--){
		z++;
	}
	TestFinishHighRes(1);
	send_string 0,"'y = ',itoa(y),'  z = ',itoa(z)";
}
define_function testNestedFor(){
	stack_var integer x;
	stack_var integer y,z;

	TestName(2,'for(){if(){}}');
	TestStartHighRes(2);
	for(x=1000;x;x--){
		y++;
	if(x<=500)
		z++;
	}
	TestFinishHighRes(2);
	send_string 0,"'y = ',itoa(y),'  z = ',itoa(z)";	
}
define_function testAltFor(){
	stack_var integer x;
	stack_var integer y,z;

	TestName(3,'alt for()');
	TestStartHighRes(3);
	for(x=1000;x>500;x--){
		y++;
	}
	for(x=500;x;x--){
		y++;
		z++;
	}
	TestFinishHighRes(3);
	send_string 0,"'y = ',itoa(y),'  z = ',itoa(z)";
}
define_function testAlt2For(){
	stack_var integer x;
	stack_var integer y,z;

	TestName(4,'alt2 for()');
	TestStartHighRes(4);
	for(x=500;x;x--){
		y++;
	}
	for(x=500;x;x--){
		y++;
		z++;
	}
	TestFinishHighRes(4);
	send_string 0,"'y = ',itoa(y),'  z = ',itoa(z)";
}

Line      1 (09:31:07.468)::  *********************************************************
Line      2 (09:31:07.468)::  * TEST 1 REPORT: for(){};for(){} Sequential For Loop 
Line      3 (09:31:07.468)::  * Most recent 5 runs:
Line      4 (09:31:07.468)::  * 1: 26ms
Line      5 (09:31:07.484)::  * 2: 25ms
Line      6 (09:31:07.484)::  * 3: 26ms
Line      7 (09:31:07.484)::  * 4: 25ms
Line      8 (09:31:07.484)::  * 5: 25ms
Line      9 (09:31:07.484)::  *----------------------------------------------------------
Line     10 (09:31:07.484)::  * Average run time: 25ms - over 5 tests
Line     11 (09:31:07.484)::  *********************************************************
Line     12 (09:31:07.484)::  *********************************************************
Line     13 (09:31:07.484)::  * TEST 2 REPORT: for(){if(){}} If nested in For Loop
Line     14 (09:31:07.484)::  * Most recent 5 runs:
Line     15 (09:31:07.484)::  * 1: 27ms
Line     16 (09:31:07.484)::  * 2: 28ms
Line     17 (09:31:07.484)::  * 3: 27ms
Line     18 (09:31:07.484)::  * 4: 28ms
Line     19 (09:31:07.484)::  * 5: 29ms
Line     20 (09:31:07.484)::  *----------------------------------------------------------
Line     21 (09:31:07.484)::  * Average run time: 27ms - over 5 tests
Line     22 (09:31:07.484)::  *********************************************************
Line     23 (09:31:07.500)::  *********************************************************
Line     24 (09:31:07.500)::  * TEST 3 REPORT: alt for()
Line     25 (09:31:07.500)::  * Most recent 5 runs:
Line     26 (09:31:07.500)::  * 1: 23ms
Line     27 (09:31:07.500)::  * 2: 23ms
Line     28 (09:31:07.500)::  * 3: 23ms
Line     29 (09:31:07.500)::  * 4: 22ms
Line     30 (09:31:07.500)::  * 5: 23ms
Line     31 (09:31:07.500)::  *----------------------------------------------------------
Line     32 (09:31:07.500)::  * Average run time: 23ms - over 5 tests
Line     33 (09:31:07.500)::  *********************************************************
Line     34 (09:31:07.500)::  *********************************************************
Line     35 (09:31:07.500)::  * TEST 4 REPORT: alt2 for()
Line     36 (09:31:07.500)::  * Most recent 5 runs:
Line     37 (09:31:07.500)::  * 1: 21ms
Line     38 (09:31:07.500)::  * 2: 21ms
Line     39 (09:31:07.500)::  * 3: 20ms
Line     40 (09:31:07.500)::  * 4: 20ms
Line     41 (09:31:07.515)::  * 5: 20ms
Line     42 (09:31:07.515)::  *----------------------------------------------------------
Line     43 (09:31:07.515)::  * Average run time: 20ms - over 5 tests
Line     44 (09:31:07.515)::  *********************************************************

As you can see, I added a couple more approaches. All approaches are fairly close, so it might be dependent on the code running within.

The first alt test uses a little less efficient for loop, but by cutting out the redundant passes through the low range, you pick up more speed than you sacrifice. This is of course dependent on the size of the redundant portion of the loops.

The second test uses two efficient for loops to accomplish the same thing, but if you need to use the x value of the for loop, this might not be more efficient.

Hope this helps,
Jeff

ericmedley

What about a nested loop?

something like

for(x=5000;x>0:x--)
{
for(y=500;y>0;y--)
  {
  // do something
  dummy[x][y]=!dummy[x][y]
  } // end for y
} // end for x

Spire_Jeff

ericmedley wrote: »

What about a nested loop?

something like

for(x=5000;x>0:x--)
{
for(y=500;y>0;y--)
  {
  // do something
  dummy[x][y]=!dummy[x][y]
  } // end for y
} // end for x

Not sure what you are asking me to test here? I you are asking that I perform the various tests within a loop to 5000, I can do that when I get back to the office, but I am thinking that the results will be something in the area of currentTestResult * 5000. Or do you have a couple of different ways to parse what you are describing?

Jeff

a_riot42

My point about nested for loops was misinterpreted I fear. I didn't mean to say to never use nested for loops when there is no alternative, as sometimes there is no other way. However, a nested for loop is often a big red flag for poor design and can often be reduced to a single for loop instead, just like gotos are often a sign of lazy design being kludged in implementation. Considering that nested for loops take polynomial time to complete, its likely better to avoid them when cpu time is a consideration like in a RTOS.

for (i = 1; i<= 10000;i++)
{
for (j = 1; j<= 10000;j++)
{
// do some text searching
}
}

Although an array of 10000 bytes isn't very big, if you are processing this nested for loop (in a text search for example) you are now running it 100,000,000 times. The cpu time needed increases as the square of the input so things can get slow really fast. If you added another for loop it would run 1,000,000,000,000 times. See how long 3 nested for loops takes. I think you will likely be waiting a long time for it to complete.
Paul

mush

Spire_Jeff wrote: »

I decided to run the following methods through my testing code just for fun. Here are the results I got.

Hope this helps,
Jeff

Thanks for that Jeff!
Very interesting result, your second alternate represents a time saving of up to ≈31%
Whilst this is not significant when talking about test passes that take only ≈20ms it could represent significant savings in very large programs.

How did you resolve your test results? Are you using timelines?

Thanks again

Mush

mush

a_riot42 wrote: »

My point about nested for loops was misinterpreted I fear. I didn't mean to say to never use nested for loops when there is no alternative, as sometimes there is no other way. However, a nested for loop is often a big red flag for poor design and can often be reduced to a single for loop instead, just like gotos are often a sign of lazy design being kludged in implementation. Considering that nested for loops take polynomial time to complete, its likely better to avoid them when cpu time is a consideration like in a RTOS.

for (i = 1; i<= 10000;i++)
{
for (j = 1; j<= 10000;j++)
{
// do some text searching
}
}

Although an array of 10000 bytes isn't very big, if you are processing this nested for loop (in a text search for example) you are now running it 100,000,000 times. The cpu time needed increases as the square of the input so things can get slow really fast. If you added another for loop it would run 1,000,000,000,000 times. See how long 3 nested for loops takes. I think you will likely be waiting a long time for it to complete.
Paul

Thanks for clarifying Paul, I thought there was another NetLinx idiosyncrasy that I didn't know about.
I regularly use nested loops but never anywhere near that order of magnitude.

Cheers

Mush

Spire_Jeff

mush wrote: »

How did you resolve your test results? Are you using timelines?

Yes, I am using timelines as they seemed to have the highest resolution. I also decided to keep the testing to a small enough run time to distinguish results without (hopefully) introducing other processor overhead into the mix.

Here is a link to the code I am using (I think it's current with what I have): http://www.amxforums.com/showthread.php?5297-Benchmark-Code&highlight=benchmark

I will post the latest code I am using, when I have a chance, if it is different.

Jeff

mush

Spire_Jeff wrote: »

Here is a link to the code I am using (I think it's current with what I have): http://www.amxforums.com/showthread.php?5297-Benchmark-Code&highlight=benchmark
Jeff

Thanks Jeff!