Sign in to follow this  
obhi

The Myth About STL

Recommended Posts

Can anybody clear a myth that surrounds me about STL. Is STL fast enough for games ?? I know I might get kicked for asking this question given the debate that surrounds the usage of STL. But I have looked around and into a lot of open source engines. Most dont use STL. Can anybody explain that ??

Share this post


Link to post
Share on other sites
There are certain problems with the Standard Library. If and when those problems become actual, pressing problems for you (they probably won't), you'll know, and you'll know what to do about them. Until that happens, you don't need to worry. Seriously. If you have pressing, unmasterable curiosity about it, though, google EASTL.

Share this post


Link to post
Share on other sites
It's not the STL anymore, that's an old library most of which was adopted into the C++ Standard Library (SC++L) and this is what we use today.

The SC++L is a part of the C++ specification. Asking whether it's fast enough games is like asking whether for-loops are fast enough games, and the answer is the same: Most of the time, yes.

As a person who isn't sure about whether they're fast enough in the first place and possibly considering rolling their own, it's always worth considering the hyperthetical situation of finding out they are slow. For example, would you actually know how to write a faster for-loop/SC++L than the one provided by the language itself and incrementally optimised over the decades by the experts? Sometimes you just have to accept speed limitations for what they are... limiting.

Share this post


Link to post
Share on other sites
Quote:
Original post by obhi
But I have looked around and into a lot of open source engines.


Such as?

First one that comes to mind: Ogre. Makes abundant use of the SC++L. Discussion of involving boost is going on.

Share this post


Link to post
Share on other sites
Quote:
Original post by dmatter
Asking whether it's fast enough games is like asking whether for-loops are fast enough games, and the answer is the same: Most of the time, yes.

As someone who isn't sure about whether they're fast enough in the first place it's always worth considering the hyperthetical situation of finding out they are slow. Would you actually know how to write a faster for-loop/SC++L? Sometimes you just have to accept speed limitations for what they are... limiting.


I strongly disagree. SC++L objects donot translate to simple looping instructions so the comparison is irrelevant.
On a second thought if you mean that SC++L implements every possible algorithm (which seems impossible) or at least the most optimum codes for container management then it eventually will contain the most optimum code for every container. That might be a good motivation for using SC++L instead.

Share this post


Link to post
Share on other sites
Quote:
Original post by nullsquared
Quote:
Original post by obhi
But I have looked around and into a lot of open source engines.


Such as?

First one that comes to mind: Ogre. Makes abundant use of the SC++L. Discussion of involving boost is going on.


CrystalSpace. Irrlitch. Ogre does use SC++L and that is why I said most.

Share this post


Link to post
Share on other sites
Quote:
Original post by obhi
I strongly disagree. SC++L objects donot translate to simple looping instructions so the comparison is irrelevant.
That's not what I meant.
The SC++L is an actual part of the C++ language; for-loops are a part of the C++ language. Why does it make sense to pick on the SC++L? Why not pick on for-loops? Both of them have implementations, both of them could be reimplemented by a user concerned about speed.

Another way to look at it is, why pick on C++'s standard library? Nobody ever starts these discussions asking about whether C#'s or Java's collection frameworks are fast enough for games.

Quote:
On a second thought if you mean that SC++L implements <...> the most optimum codes for container management then it eventually will contain the most optimum code for every container. That might be a good motivation for using SC++L instead.
That's somewhat true. If you took the specification of a std::vector for example, it's increasingly difficult to imagine a (portable) implementation that can be any more optimal than the popular implememtations around today. The only way to do better is to change the specification and allow domain knowledge in, this in effect is how the EASTL works (although there are improvements in that which don't compromise the generality).

Share this post


Link to post
Share on other sites
For what most games do - which in terms of non-graphical computation and data management, isn't generally very much - STL is going to be fine. And if you write something STL_like, in terms of providing general containers, you probably won't get much in the way of improvement, at least if you design for the basic capabilities.

But keep in mind that in the modern world, everyone's got a dual core 2Ghz processor or better, at least if they want to play games. There was a time people wrote games for machines 50 times slower, and you can believe that a great deal of squeezing went on to get speed any way they could. You used fixed arrays because that was the only thing fast enough. You hand optimized things like hash functions. You unrolled loops and you used assembler. Some of that tradition still survives.

I'd say this: use things like STL to get started. If you find you're writing something so ambitious that the costs of STL are in the way, then you can fade the use of STL out in the critical areas, and go back to the old methods.

Share this post


Link to post
Share on other sites
if i'm working on my 286 just playing around i use every speed trick i know, but for the most part, i use what works now and if it too slow i either find something that fixes it or figure out some other way to achieve what i want

Share this post


Link to post
Share on other sites
Quote:
Original post by obhi
Can anybody clear a myth that surrounds me about STL. Is STL fast enough for games ??

I know I might get kicked for asking this question given the debate that surrounds the usage of STL. But I have looked around and into a lot of open source engines. Most dont use STL. Can anybody explain that ??


depends. for what you are likely to do, yes

for consoles, and platforms with limited memory, its nice to have some fixed size containers which dont call allocators, fixed element size containers (which also dont hit constructors), and other non-resizing containers.

such things arent found in the STL.

it comes down to that, in certain situations, you can make decisions based on the data you have, and the memory budgets you need to fit within and the resulting solution will be better(sic) than using a generic container.

this also only applies to runtime situations. for tools, we use everything we can lay our hands on.

but back to the original point, if your a hobby programmer, or writing smallish games, and not trying to eek every last cycle out of the hardware (and at a guess, your not) and would rather spend the time writing code and using good, tested, fast containers then use STL, and dont feel bad about it.

Share this post


Link to post
Share on other sites
Newbies don't want to use SC++L for so many reasons: Because the pros roll their own, because they want to learn as much as possible, because they don't know how it's working internally, because misusage produces strange error messages, because good online help is hard to come by.

Pros roll their own after they've been through all this.

Alas I know of some pros who never really used SC++L... I guess they are just too busy writing code to really learn C++. [smile]

Share this post


Link to post
Share on other sites
Thanks for the reply's. You see I asked this question because I am using my own containers that I implemented a long time back. Most of them basically cuts down to what SC++L has inbuilt, specializing in certain areas. Memory management for example. But when I started posting here I noticed people talk about SC++L a lot. And since I neglected SC++L from the day I was learning C++, I had to know what makes it tick in the gaming world. Or does it really carry its fame that I noticed here to the commercial engines.

And
Quote:

Crystal Space is an ancient piece of shit, and there's some evidence that Irrlicht was written by people who didn't know what they were doing at all.

Thats for sure! But they are open source and available for study.

Share this post


Link to post
Share on other sites
Quote:
Original post by loufoque
Contrary to popular nonsense, basic operations on vectors don't have to be slower than equivalent operations on arrays/pointers, see http://www.xs4all.nl/~weegen/eelis/vector-speed.cpp.


You left out the fact that vectors have to be created and destroyed. The memory for the storage of elements has to come from somewhere, and if you add to the vector often enough, it's going to mean more trips to that special somewhere. Ultimately, these are heap operations. Heap allocations are searches; they are not free. An array creation takes 0 time (but see below) and, as it can't grow, it can't cost more time at a later point.

At heart,

class Foo {
std::vector<MyData> list;

and

class Foo {
MyData list[256];

may perform (and should perform) identically when indexing into list[], but they are not identical as regards what it costs Foo to be created, list[] to be added to, and Foo to be destroyed. Of course, vector has all sorts of advantages, starting with the fact that you don't have to know in advance how many elements you need. It's there to free you from the substantial restrictions of arrays. But such freedom isn't free.

All bets are off, of course, if MyData is a class with a slow, complex default constructor, in which case the array case is going to expensively construct 256 objects, which is annoying if you only needed 3. The vector init doesn't have to create any. But if you are worried about performance to this degree, you are already looking at these issues and know when array is not going to win. (caveat: the same argument can affect the vector case when a class has an extremely expensive copy constructor. Array elements can be built in place, they don't have to be loaded by a copy operator.)

STL is great for many things. Some people will never need more. But anyone who codes long enough and pushes machine limits as part of his work, is always going to find a case, sooner or later, where the latest panacea, be it STL or anything else, has some unacceptable cost. If that day comes, it is important to know what the alternatives are and how they behave.

Share this post


Link to post
Share on other sites
At my company we use both STL and Boost extensively in our console game.

Pretty generally, if just use some common sense and don't pack a ton of this into very tight loops, you'll be all set.

We HAVE encounter some bottle necks with STL, but nothing that wasn't able to be remedied with some careful evaluation.

Share this post


Link to post
Share on other sites
Quote:
Original post by obhi
And
Quote:

Crystal Space is an ancient piece of shit, and there's some evidence that Irrlicht was written by people who didn't know what they were doing at all.

Thats for sure! But they are open source and available for study.


Here's you situation made clearer:

"Don't eat this mushroom, it's poisonous!"
"But it's free and right there on the floor!"
"..."

Share this post


Link to post
Share on other sites
The biggest myth about STL is that it's to slow for serious development.

Another huge problem is people being absolutely obsessive about "slow" and making dubious micro-optimizations without looking at algorithmic changes or even bothering to measure performance and understand what exactly it is that's slow. Or in some cases, even defining what "slow" is.

Yet another problem is people thinking that the demands of a AAA title that is pushing the technology envelope are somehow relevant to thier small-medium title that will run just fine on 3 year old hardware without going to heroic optimization efforts.

Share this post


Link to post
Share on other sites
As far as I noticed there are certain features in SC++L that I really liked. Apart from portability and robustness (after all it is a standard!), things like Construct when required (which can be done using an overriding new operator that is passed a already allocated memory pointer and the operator returns that address only, apart from calling the constructor), consistency in the way objects can be accessed.
But given that I've reinvented the wheel I might stick to my library for a while. Thankfully most functions I implemented has similar names as a SC++L class of similar functionality would. So converting to SC++L wont be trouble. But I think I will do some profiling first.
Thanks again.

Share this post


Link to post
Share on other sites
Quote:
Original post by ScottMayo
You left out the fact that vectors have to be created and destroyed. The memory for the storage of elements has to come from somewhere, and if you add to the vector often enough, it's going to mean more trips to that special somewhere. Ultimately, these are heap operations. Heap allocations are searches; they are not free. An array creation takes 0 time (but see below) and, as it can't grow, it can't cost more time at a later point.

....

may perform (and should perform) identically when indexing into list[], but they are not identical as regards what it costs Foo to be created, list[] to be added to, and Foo to be destroyed. Of course, vector has all sorts of advantages, starting with the fact that you don't have to know in advance how many elements you need. It's there to free you from the substantial restrictions of arrays. But such freedom isn't free.


Wait.. did you honestly just use the point that 'an array can't cause you problems when it resizes' as an advantage?

You do realise that you can size a Vector upfront if you know the resources you require, yes?
At which point the Vector has the memory reserved (0 time as you seem to think) but hasn't constructed anything. You can then add data to this array as before with no resize cost AND with all the normal vector safety and access methods for ensuring length etc for data and it can adapt if you change the size of something and 'forget' to update your code somewhere.

On the flip side with an array if, for some reason, the data is no longer that expected size but longer you start suffering memory corruption, buffer over runs and ultimately crashes and maybe even exploites.

So, yes, a Vector CAN resize itself however this slow operation can be allowed for an even removed if you have enough information up front in much the same way as you can with a staticaly sized array, the vector is just safer.

So; what was the point of your post again?

Share this post


Link to post
Share on other sites
Quote:
Original post by obhi
But I think I will do some profiling first.
You know the second largest barrier to STL adoption (after the 'slow' myth)? Newbies with profilers [smile]

I can tell you right now, that your profiling will tell you something along the lines of: "A is faster than B for such-and-such a synthetic benchmark with such-and-such compiler optimisation flags, on such-and-such a platform". The truth is that nobody really cares whether library 'X' is 10% faster than the STL - if that is the case, switch it out once you finish with real optimisations (algorithmic improvements, caching, parallelisation, ...).

Share this post


Link to post
Share on other sites
Quote:
Original post by swiftcoder
Quote:
Original post by obhi
But I think I will do some profiling first.
You know the second largest barrier to STL adoption (after the 'slow' myth)? Newbies with profilers [smile]

I can tell you right now, that your profiling will tell you something along the lines of: "A is faster than B for such-and-such a synthetic benchmark with such-and-such compiler optimisation flags, on such-and-such a platform". The truth is that nobody really cares whether library 'X' is 10% faster than the STL - if that is the case, switch it out once you finish with real optimisations (algorithmic improvements, caching, parallelisation, ...).


You know I agree with you. That optimizing data structure code will not greatly improve a game engine performance. At some point it might though, for example when I created a physics simulation (which used LCP) last year one of the major optimization I made was in managing the active and inactive objects. All objects belonged to a single linked list, only a simple pointer or a separator in that list separated the active objects from the inactive ones. This greatly reduced my search for constrain connected objects as I simply dumped the active objects to the iterator to process. The list was thus a specialization.
Making the long story short, it is sometimes worth it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this