How to improve yout STL performance?

Started by
12 comments, last by Washu 19 years, 6 months ago
Quote:Original post by Mawr
Made a reference to the end of the list, and tested against that instead of calling dustlist.end(); every loop.


I'm not sure what your saying, you can't test an iterator with a reference, certainly if your not modifying the list you can cache a copy of the end iterator e.g.

for(std::list<dust>::const_iterator itr = dustlist.begin(),    end = dustlist.end();    itr != end;    ++itr) { /*...*/ }


but we mean't to use a reference type at the beginning of the loop.

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?


list iterator will typically encapsulate a list node that refers to a node in the list, list iterator is a user-defined type with overloaded operators that mick schematics of a pointer, your really calling a member function so to avoid the overhead of the function call you cache a reference or constant reference (even better) and in all intents a reference is the object presto no more function calls.

By the way did you get a performance increase?
Advertisement
The cache and TLB misses on all those items in the list are killing you. Also, print the size of the list every so often, to make sure you're not leaving lots of zombie items in the list.

I would keep the actual elements (not pointers) in a vector, so walking the vector is linear memory access, which dramatically reduces cache miss penalties. I'd consider using a "zombie" bit on elements in the vector, so I don't have to move the entire vector each time a particle is purged. Keep a counter of the number of zombie items, and when it's bigger than some number (30 ?) then I'd compact the vector and resize in one go.
enum Bool { True, False, FileNotFound };
Guess my nomenclature is a bit bad. Here is the code I used to replace my old code.

//Old versionfor(it;it!=dustlist.end();it++){...}//New versionstd::list<dust>::const_iterator end_it=list.end();for(it;it!=end_it;++it){...}


I did get a signifigant boost to performance. While my program wasn't really that slow before on my machine, I wanted to know if there was any easy optimizations I could do, for the simple fact I'd know them.

I shifted the most time intensive calls from the ones I mentioned in my orignal post to void Draw(), void Update(), and float TransulatePoint(). And because some of my other functions were made in the same style, I improved them also with what you guys suggested.

Though I still have some questions, I think I understand moving away from it->member to const dust& d=*it, I'll try that next. But now zombie items inside the list? I thought the statement it=dustlist.erase(it); removed the item at position it, preventing any zombie items from being inside the list. Also, while watching the amount of memory my program uses, it stabilizes fairly quickly at a reasonable number (7 megabytes or so).
Quote:Original post by Mawr
Though I still have some questions, I think I understand moving away from it->member to const dust& d=*it, I'll try that next. But now zombie items inside the list? I thought the statement it=dustlist.erase(it); removed the item at position it, preventing any zombie items from being inside the list. Also, while watching the amount of memory my program uses, it stabilizes fairly quickly at a reasonable number (7 megabytes or so).

think of it this way, if you store a vector of things, then the cache can load up a bunch of those "things" however a list of things tends to result in the actual things residing all over in memory, very hard to cache.

Now, the reason you don't use the erase with the vector is that all elements after the erased item have to up one to fill in the space. Instead you have two options. 1) swap with the last living element (thus the first "dead" item you hit is where you would stop looping or 2) mark the element as 'dead' and then collect it at a later time when performance doesn't matter as much. (so you would have a condition here, if(!isDead) { do } else { skip })

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.

This topic is closed to new replies.

Advertisement