Back to For Beginners

How to improve yout STL performance?

For Beginners

Started by Mawr September 30, 2004 04:14 PM

12 comments, last by Washu 19 years, 6 months ago

Mawr

278

Author

September 30, 2004 04:14 PM

When I was profiling my 2d space game with gprof (mingw is the compiler), the most time taken up was not by my functions (suprised myself!), but by some calls to the STL library. From the STL I'm using a list to keep track of my objects. It's used like this:


void Draw()
{
  std::list<dust>::iterator it= dustlist.begin();
  for(it;it!=dustlist.end();it++)
  {
    glBegin(GL_TRIANGLES);
    glColor3f(.3,.3,.3);
    glVertex2f(TransulatePoint(it->x+(dustWidth/2),true),
               TransulatePoint(it->y,false));

    glVertex2f(TransulatePoint(it->x-(dustWidth/2),true),
               TransulatePoint(it->y,false));

    glVertex2f(TransulatePoint(it->x,true),
               TransulatePoint(it->y-(dustHeight+bonusSpd),false));

    glEnd();
  }
}

And:



void Update()
{
  std::list<dust>::iterator it=dustlist.begin();
  for(it;it!=dustlist.end();it++)
  {
    it->y-=(it->spd+bonusSpd);
    if(it->y<0)
    {
      it=dustlist.erase(it);
    }
  }
}

gprof is reporting that:

std::_List_iterator<dust, dust&, dust*>::operator*() const 

std::_List_iterator<dust, dust&, dust*>::operator->() const

are being called the most. So with this in mind, is there any way to optimize how I use the STL library in those code snippets?

Washu

7,836

September 30, 2004 04:28 PM

Quote:Original post by Mawr
...the most time taken up was not by my functions (suprised myself!), but by some calls to the STL library...

...are being called the most.

Now, which is it? Because if they are being called the most and using up the most time, not surprising. The ratio of time taken to calls performed is fairly linear.

But we really need more information. For instance, did you compile it in release mode? Did you make sure you had optimizations enabled? If so, what level of optimizations? Now for a quick tip, there is no need to call end every iteration of the loop unless you change the contents inside of the loop (which applies to the first loop).

Now, another option would be to keep a pointer to the structure on hand, instead of calling to the iterator each time, but that should be a last resort really, as the compiler should be able to optimize both of those calls out.

In time the project grows, the ignorance of its devs it shows, with many a convoluted function, it plunges into deep compunction, the price of failure is high, Washu's mirth is nigh.

noVum

170

September 30, 2004 04:31 PM

You should use ++it, NOT it++

demonkoryu

980

September 30, 2004 04:34 PM

Because it++ involves making a temporary copy.

Thermo

snk_kid

1,312

September 30, 2004 04:36 PM

First did you try to turn on optimization flags at the highest level? i.e "-O3"

In draw function you should just use const_iterators if your not going modify any elements in the container & you could try doing this instead of using the iterator doing the work cache a reference e.g.

const dust& d= *it;

another thing is with iterators use pre-increment operator instead i.e. instead of it++ do ++it, post-increment cost you.

also you do realize you could probably use STL algorithms instead of writiing explicit loops.

Also something not related to STL, instead of having glBegin/End inside of the loop take it out-side, you can send more than one triangle between glBegin & End, and instead of modifiying indiviual vertices you could probably just do less operations using opengl transform ops.

Fruny

1,658

September 30, 2004 04:37 PM

Quote:
std::_List_iterator<dust, dust&, dust*>::operator*() const
std::_List_iterator<dust, dust&, dust*>::operator->() const

These are the functions that actually access the data so it's not surprising they come at the top. All this says is that you are doing a lot of data accesses.

Here are the definitions for those two functions:

reference operator*() const{ return static_cast<_Node*>(_M_node)->_M_data; }pointer operator->() const { return &(operator*()); }

Considering that they are actually inlined, there's not much (i.e. nothing) you can shave off.

I would suspect that the profiler caused them not to be inlined, possibly artificially inflating their "cost" (i.e. viewing as a function call something that would just be done as a couple of pointer indirections).

Quote:So with this in mind, is there any way to optimize how I use the STL library in those code snippets?

You could do fewer data accesses.

You could grab a reference to the element the iterator points to and use that instead of dereferencing the iterator multiple times. That should placate your profiler (fewer function calls, regardless of inlining), and possibly actually improve performance.

dust& ref = *it;glVertex2f(TransulatePoint(ref.x+(dustWidth/2),true),           TransulatePoint(ref.y,false));

Grabbing a reference to an object whose location is determined by a potentially expensive function is a common trick.

Another option, for those cases where you do not need to refer to the original variable anymore, would be to make local copies of whatever data you need (here, it->x and ref.y) and be done with it. It may improve cache performance.

"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." — Brian W. Kernighan

snk_kid

1,312

September 30, 2004 04:42 PM

Fruny: I beat you to it [smile]

And as it's just a draw function that doesn't seem to modify any elements in the container you'll be better off using const_iterator & a constant reference cache.

Plus take out glBegin/End of the loop!!!

Washu

7,836

September 30, 2004 04:44 PM

Quote:Original post by snk_kid
Fruny: I beat you to it [smile]

And as it's just a draw function that doesn't seem to modify any elements in the container you'll be better off using const_iterator & constant reference cache.

*coughs*
Sure, I said pointer and not reference, but I beat both of you.

In time the project grows, the ignorance of its devs it shows, with many a convoluted function, it plunges into deep compunction, the price of failure is high, Washu's mirth is nigh.

Mawr

278

Author

September 30, 2004 05:35 PM

Thanks for the speedy responses! So far I have done most of the suggested optimizations.
I moved glBegin(GL_TRIANGLES);, glEnd();, and glColor3f(.3,.3,.3); outside of the loop.
I'm using ++it.
Constant iterators when I don't need to modify data.
Made a reference to the end of the list, and tested against that instead of calling dustlist.end(); every loop.

But I don't understand how making a reference to the iterator for my list would improve performance. I thought in this situation 'it' as already a reference?

Clarifing, those functions I mentioned are both called the most, and the most time consuming (1st, and 2nd on the gprof list, for both catagories). I compiled this version with debug information, with optimized turned on to it's highest setting (I'm using dev-cpp, the option is Tools-> Compiler Options-> Settings-> Optimizations ("yes")-> Further Optimizations->Best).

Washu

7,836

September 30, 2004 05:39 PM

Quote:Original post by Mawr
But I don't understand how making a reference to the iterator for my list would improve performance. I thought in this situation 'it' as already a reference?

Not to the iterator, to the structure the iterator points to. The idea is that if your compiler doesn't inline the dereferencing of the iterator, storing a reference to it will avoid that function call each time you need to access a member of the structure.

In time the project grows, the ignorance of its devs it shows, with many a convoluted function, it plunges into deep compunction, the price of failure is high, Washu's mirth is nigh.

How to improve yout STL performance?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

How to improve yout STL performance?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines