if(): howe much time consuming it is?

[arras]

Does anybody know howe time/CPU consuming if() statement is? Should I awoid it in case it is going to be repeated many times each loop or is it relatively unhurting?

[Acki]

Hmm, I think the if() statement isn't really time consuming...
But the expression you're checking could be...

something like this should be fast:

Code: Select all

bool foo;
.
.
if(foo){
  .
  .
}

but something like this would be verry slow:

Code: Select all

double foo;
.
.
if(sqr(foo) * sin(foo) > sqr(foo) / cos(foo)){
  .
  .
}

But off course also the first example takes time...
Best would be to make a benchmark test with your code...
For example store the starting time, make 1000000 loops with the same statement and substract the starting time from the ending time...

[hybrid]

It does hurt much, however medium sized loops can make use of the speculative execution if the branch is always the same (because always the last branch is taken again). So if you can avoid it avoid it. Many people duplicate the high performance loops for the two cases of the if. But don't think that you can double your FPS by that

[arras]

What I want to know is statement itself so what I am interested is more like if(foo) example. If expresion inside is time consuming than statement itself is, this I understant.

To be specific let say I have 2d array of pointers to objects. Most of the pointers points to objects but few are NULL. What I need is to check if pointer is valid and if yes I execute some operations on object. Array can be quit large, say 100 x 100 or more.

Way to avoid using if() would be to create second array of pointers, this time one dimensional. All pointers would be valid because its size would be equal to number of objects. Like this I can awoid if() but I will end up useing more memory. I want to know if it is worth doing or not.

Code: Select all

MyObject* array1[100][100];
...
...
for(int j=0; j<100; j++)
   for(int i=0; i<100; i++)
      if(array1[i][j])
      {
          ...do something...;
      }

[Saturn]

Ignore the costs of if, they are negligible. Learn assembler, it will tell you a bit about CPU computation costs in general.

[vitek]

The only way to actually tell is to profile the code in question.

The cost of the if itself is very small in terms of assembly. It is just one instruction. Unfortunately this instruction is probably running on a pipelined microprocessor, so the instruction is in a pipeline with many others. When a branch is reached, the processor will 'guess' the branch result, and will push instructions from the side of the condition that it thinks will be selected. If, after a few instructions, the cpu discovers that the 'guess' was wrong, the instructions after the branch must be flushed and new instructions must be queued. This can be expensive if the 'guess' is wrong very often.

Fortunately most programs have bigger performance problems than the efficiency of a simple if statement.

If it is a problem, there are ways to eliminate them. You could not allow insertion of null pointers at all, or you could use the null object pattern.

Travis

[arras]

OK thank you all

[Warchief]

The problem there is not the if sentence itself, but the fact that you want to do something with the 100x100 objects every frame. What are the chances of an object in the array to be null?

If most of the objects will be null then you should think on other structure to contain them, because you are looping the 10000 objects array for a few objects. If it's supposed that all are initialized (not null) the if its costless, as you are probably doing something inside the if that takes N times the time took the if (with N >>> 1) [you may even assume that all are not null an remove the 'if', leaving the program crash if an object fails]

Code: Select all

#define CHECK_OBJECT_ERROR 1
// ..
#if CHECK_OBJECT_ERROR
  if( array[i][j] ) {
#endif
         DoSomething();
#if CHECK_OBJECT_ERROR
  }
#endif

So you active it only if find a crash.

[arras]

2d array is there to allowe objects to be accesed via position index ...[j] which give area of objects square in shape. However objects itself are round in shape aranged. Means several pointers in corners of array are going to be NULL. It will not be majority but still significant enough.

[Warchief]

I'm not sure if i understand you. Do you mean that you will have the same object over more than 1 "tile" and its shape is round? Or that small objects that have 1 tile size are placed together into a bigger round shape?

If one object is over more than 1 tile, i would change the container (why loop the tiles when you can loop the objects?)

If a lot of objects have a size of 1 tile and are placed together i would ask myself, is it really needed? Would anyway be better loop them with another container.

In a nutshell:
If you have the tiles and some tiles have objects, it isn't a good idea to loop all the tiles just to call some method for those that are not null ( this is what hybrid told you about. If it misses the condition many times, it will lose some time, note that you will be failing a lot of times every frame because of the loop). In this case it would be better to have two structures:
a) Tiles array (if you need it) with a pointer to the object in the tile
b) Another array with all the objects in the scene/map

So you can access the object from its tile

Code: Select all

tiles[i][j]->object->DoSomething()

but loop the objects from the other container which never misses

Code: Select all

for( int i=0; i<numObjects; ++i)
   objects[i]->DoSomethingEachFrame()

Of course it depends if you need speed or small memory size.

[arras]

yes, that is something I was thinking about and proposed at the topof this post ...what I want to find is if gain in speed would be enought to sacrifice memory.

I did not wanted to be too specific and owerload you with too much info, but here is it:

that 2d array is realy array of pointers to tiles ...mean objects of 4 vertices and 2 polygoons each. Tiles together represent terrain.
However since camera is always in the middle tiles are "placed together into a bigger round shape" ...this will save few polygoons to be drawn on screen making rendering terrain fasther ...a bit.
Look at my project if you want to know more: http://irrlicht.sourceforge.net/phpBB2/ ... hp?t=18121


2d array is used to alove acces to tiles based on their position. However since 2d array is square and terrain round some pointers iside arrays would be NULL ...there are no tiles on that positions to be pointed to. Thats why I use array of pointers to tiles not array of tiles.

All this mean that if I want to acces tile at some position I need to check if tile on that position exist ...if() statement.

[kh_]

Hi Arras,
Not sure if it would save time, but another possibility is to use a kind of imposter object that would call the method without doing anything. (They would need to share a common interface for that function.)
I've never tested it but, something else (I have heard of) that might make it faster, other than asm, is to use pointer arithmetic instead of indexing.

check your messages.

[arras]

hmm ...I am not cathing with you ...excuse me. Howe would object that would call the method without doing anything help me?

"to use pointer arithmetic instead of indexing" ...not that I am great programer, so I might be wrong ...but array indexing is not in fact pointer aritmethic?

[kh_]

Howe would object that would call the method without doing anything help me?

You wanted a way to avoid using "if" to test for a null pointer. I was suggesting having no null objects. It's probably not faster though, could even be slower:

Code: Select all

class IMyTerrain
{
      public virtual void update()=0;

};

class MyTerrain : public IMyTerrain
{

public virtual void update(){do_stuff();return;}
//other stuff

};

class MyTerrainDummy : public IMyTerrain
{
//do nothing
public virtual void  update(){return;}

};



IMyTerrain* array1[100][100];
//load dummies where the empty spaces are
array1[0][0] = new MyTerrainDummy();
.....
array1[0][n] = new MyTerrain();
...
...
for(int j=0; j<100; j++)
   for(int i=0; i<100; i++)
        array1[i][j]->update();
  //no ifs needed    

"to use pointer arithmetic instead of indexing" ...not that I am great programer, so I might be wrong ...but array indexing is not in fact pointer aritmethic?

not that I am great programer either,
I might have used the wrong terms. I mean using:
array1[j]
as indexing.

and this as pointer arithmetic:

Code: Select all

IMyTerrain* array1[100][100];
//load dummies where the empty spaces are
array1[0][0] = new MyTerrainDummy();
.....
array1[0][n] = new MyTerrain();
...

//not %100 sure if it must be this:
IMyTerrain** p_array1;
//or if this will also work since its the base type
//IMyTerrain* p_array1;

 p_array1 =  array1;
...
for(int j=0; j<100; j++)
   for(int i=0; i<100; i++)
{
//haven't done this in a long time so it's probably wrong
           p_array1->update();
           p_array1++;
}

anyhow this is what I meant. I have definitely read (somewhere) it is faster than the other way in C++. You may not notice a difference , but then again......
Hopefully some of the more experienced programmers here will have some opinions on this (and clean up my code)

[arras]

OK now I am catching on

-the firsth code ...I'll think about it and make some tests.

-the second: what I know about arrays is that in fact they are working in similar fasion as pointers and vice versa. Thats why you can use indexing with pointers like:

Code: Select all

IMyTerrain* p;
p[2] = whatever;

of course code above is not correct since you reach somevere in to memory. Just example. Also as I understand arrays using for example somearray[0] is in fact using pointer. At last I was reading something like that in Thinking in C++ book.

And finaly I don't use static arrays instead I use dinamic C like arrays which look like:

Code: Select all

IMyTerrain** p;
p = new IMyTerrain*[100];
for(int i=0; i<100; i++) p[i] = new IMyTerrain[100];

As you can see I am using pointers in fact. I dont think second method you sugested is much diferent ...but again I might be wrong and I would welcome anything improving my knoweledgr about subject