Sign in to follow this  
VprMatrix89

C++ STL -- how important?

Recommended Posts

So I'm reading this book calling "The C++ Programming Language" to help reinforce what I have already learned. Stroustrup emphasizes the use of the STL over integral arrays. My guess is that the stl's string, vector, and map are just dressed up arrays with functions to help out. He warns against trying to write your own, but never really says why. Besides things like "the stl is fast". He uses words like "ought" and "proper" to further demote other philosophies. I really want to know how important is the stl in REAL games? Especially things like cin and cout , are they even used?

Share this post


Link to post
Share on other sites
Depends heavily on your definition of "Real Games". Many game development studios eschew the STL in favor of more focused data structures, sometimes to work around compiler constraints (Compilers for consoles are notoriously bad), other times to work around memory / efficiency constraints.

However, the STL will almost always be superior to the raw versions of what they abstract. std::vector, for example, will perform equally well as a raw array, with the benefit of optional bounds checking and automatically resizing (which takes up extra memory). Using raw arrays is prone to error, and indeed, using std::vector is almost always superior to using a normal array.

Stroustrup's advocacy of the STL is really just denunciation of the more unsafe portions of C++, such as raw pointers (vector and boost's smart pointers will cover most of these) and C style strings (std::string offers huge benefits over null terminated character arrays).

Do take note that std::map is not simply a 'dressed up array'. A map is an associative container, allowing you to relate one set of data to another, often internaly implemented as a red-black tree. This data structure is rather non-trivial, and writing your own would almost certainly result in errors and segfaults.

More specifically, std::cin and std::cout are rarely used in graphical games, since they imply the use of a console. Loggers, however, prominently feature the use of std::ofstream and the like.

The STL is very important, and even if game studios do not use them, it is no excuse for you not to use them. If you ever find that the STL is a bottleneck in your applications (In release mode, after you have disabled safe iterators and the like and profiling), then you can refactor them out.

Share this post


Link to post
Share on other sites
The STL is part of C++. Thus if you don't know the STL then you don't know C++.

It's a bad idea to write your own versions of vector etc, because the STL's version of vector is:
1) Well defined. There is a standard that guarantees how it will behave, and the big-oh complexity of different operations.
2) Implemented by the same people who wrote your compiler. They're probably smarter than most of us ;)
3) Well tested. Everyone with your compiler has tested these classes, so you can safely assume they are free of bugs.


In the past however, some platforms have had pretty crappy C++ compilers, with pretty crappy implementations of the STL. If you're on one of these platforms then it is often worth your while avoiding "normal practices" when it comes to the STL...

Share this post


Link to post
Share on other sites
Quote:
Original post by VprMatrix89
My guess is that the stl's string,

Probably.
Quote:
vector,

Yes, by intentional design. The C++ standard mandates that a non-empty vector can be passed ala &v[0] to a function expecting a C style array of the same type and work, by guaranteeing that elements are contiguous. (An exception: std::vector<bool> makes no such guarantees)
Quote:
and map

No, impossible by design. Typically a red black tree, although other trees are at least legal.

Quote:
are just dressed up arrays with functions to help out. He warns against trying to write your own, but never really says why. Besides things like "the stl is fast".


"The SC++L is fast" is 1 reason why, but it admittedly doesn't go into the details. Aside from strict algorithmic performance requirements set forth by the standard, modern implementations use a huge bag of tricks to perform at their best -- empty base optimization, return value optimization, tag based dispatch to optimized versions, and general tailoring to the compiler they're targeted for. It's very intentionally designed to be damn hard to beat for the tasks they're designed to solve.

On top of this, it's already written, debugged, and usually has another spitload of extra features for debugging pre written, thus reducing the amount of code you usually have to consider as being possibly at blame for various bugs that creep up in your projects as they inevitably do.

Quote:
He uses words like "ought" and "proper" to further demote other philosophies.


In just about every programming language, using the standard library provided by it is widely encouraged and considered proper, in part because it's what everybody is used to and expecting you to use. Similar applies to the Standard C++ Library which absorbed what continues to be labeled "the STL". Even when custom containers are required, they usually implement the standard idioms -- naming for various members, iterators, range based operations, etc.

These help reduce the costs of getting a new programmer up to speed on existing code -- if you're using the same patterns they're used to, that's one less thing they have to learn before they're caught up to where the rest of the team is at. Nonstandard interfaces to the same concepts should only be considered with caution and good reason.

Quote:
I really want to know how important is the stl in REAL games? Especially things like cin and cout , are they even used?


cin is probably almost never used in "real" games, on account of most games not needing console io. cout or ofstream might be -- while iostreams are better than their C stdlib equivalents, both have enough deficiencies that a custom solution is often required for anything beyond fairly basic logging. The boost library collection has a bunch of libraries trying to help target some of those deficiencies -- and provide alternatives (e.g. boost::serialization for general data saving)

And, while game development has been a field notoriously slow in picking up new tools, I'm under the impression that many studios are using C++ standard containers, even if their end product ends up needing customized containers for large portions of their code e.g. on oddball consoles such as the PS3 where SC++L support has been traditionally sorely lacking (as far as I know).

[Edited by - MaulingMonkey on July 7, 2008 1:19:02 AM]

Share this post


Link to post
Share on other sites
Yes, I've heard that on the PS3, you'll get massive amounts of cache misses with STL. The main reason Stroustrup advocates STL is probably because of the familiarity. It's too bad he uses words like "ought" and "proper" instead of delving into the real reason. In software even more than games the code will be kept and reworked many many times by different developers. Using STL will allow these developers to understand the code right off the get go. Books such as Code Complete, and most of Effective C++, describe techniques to write code that will be easy to read and delve into these kind topics (Effective C++ gets more into efficiency than Code Complete, which is almost all organization).

Share this post


Link to post
Share on other sites
The STL is one of those things, it's quite difficult to write good quality, idiomatic C++ code without proper usage of the STL.

STL is also pretty useful in that it caters for extension by design. Adding your own algorithms, functions and containers isn't too difficult assuming fairly good familiarity with the library.

The real problem with STL is that for console development it's just completely inappropriate. That might sound like a sweeping statement and it is, but it's the conclusion most developers might draw after reading about the EASTL, which EA effectively wrote from the start to address the major design flaws in STL preventing good performance on consoles, which often have unusual memory or cpu constraints.

If you're writing a game for the PC, Mac or Linux then you can probably get away with using STL, and in fact it's an extremely important tool. However, you should be aware that it is not perfect.

Share this post


Link to post
Share on other sites
IMO it's as simple as this:
If you don't utilise the STL, you'll end up reinventing the wheel.

As some have already mentioned, in some cases it's necessary to do so (ie consoles), but for the large part failure to use it just means frustration when you have memory management problems, which can be extremely difficult to find and fix.

cheers,
metal

Share this post


Link to post
Share on other sites
Well I don't know what C++ you read before Stroustroup's but the way he shows in his book is the modern and according to the creator of the language the way you should be using C++ in your programs.
If you read one of the highly recommended C++ books like "Accelerated C++" or C++ Primer they also rarely resort to using old C style arrays if at all and also emphasis using the STL.
Anyways I don't remember if he mentions specifically why in the book since it's been a while since I read it but he says why on his webpage here:

What's wrong with arrays?

In terms of time and space, an array is just about the optimal construct for accessing a sequence of objects in memory. It is, however, also a very low level data structure with a vast potential for misuse and errors and in essentially all cases there are better alternatives. By "better" I mean easier to write, easier to read, less error prone, and as fast.

But yeah if you read the whole book you'll notice Stroustroup pretty much tries to get you to code the new improved C++ as he imagines people will use it and restricts old legacy C to the appendix-LOL! It is a C++ book after all!
Anyways, the only problem I have with this approach is that I see way too much legacy C code and C++ used as a better C in most of the professional game source I've seen like Quake,HomeWorld,etc to try to banish arrays to the dustbin. So I'd say STL hasn't caught on as much as was hoped by Stroustroup at least for game programming since I've only seen maybe 2 out of my like 20+ game programming books in C/C++ actually make use of it. My Frank Luna DirectX book and Programming an RTS Game with Direct3D book.
But if you are starting a new game in C++ I'd do myself a favor and use it as much as possible since there should be no noticeable peformance penalty in using it. At least that's what Stroustroup's been saying as long as I can remember but I'm sure there are people still using outdated C++ compilers or being forced to use one that will show there is a difference in some instances?
Plus, you'll save yourself some headaches and grief;)


[Edited by - daviangel on July 7, 2008 7:49:32 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by daviangel
Anyways, the only problem I have with this is personally I see way too much legacy C code and C++ used as a better C in most of the professional game source I've seen like Quake,HomeWorld,etc. So I'd say STL hasn't caught on as much as was hoped by Stroustroup at least for game programming since I've only seen maybe 2 out of my like 20+ game programming books in C/C++ actually make use of it. The Frank Luna DirectX books come to mind.


You have to consider timeframe and legacy.

When Quake was written the C++ Standard hadn't even been finished and it hasn't been until recent years that we've had compilers and Standard libraries which have been optimised well enough to use.

The classic example of this, which I wish I could point you to the post for but I can't, is Doom3 and iD's custom containers. I would guess iD used custom containers due to legacy code from older games, however when tested against the Std. C++ Lib containers the latter outperformed them by a significant factor.

Granted, as already pointed out, on consoles the Std. Lib containers probably aren't going to be your best bet due to other contraints, but for the average PC based C++ coder if you arent' using them then chances are you are doing it wrong.

Share this post


Link to post
Share on other sites
I'm a big CSL advocate, so I'm not going to tell you to not use it. But I also admit that the CSL has many game development related issues - even on PC.

The biggest problem is about how it handles memory. Consider a typical std::vector<T>, with its typical std::allocator<T>. Unless you carefully design your program to know how many units you want to push_back() in your vector, you end up with a few problems:

1) you don't know when memory allocation occurs
2) you don't know when your objects are copied
3) you don't know how many times your objects are copied

Unfortunately, these problems can prove to be quite awfull to deal with, especially when you want to optimize memory handling. Even if you write your own allocator, you're still not responsible for calling it, so the major problems remains.

The CSL is quite a good piece of software, and - as I said - I advocate its use. Nevertheless, you shall remember that it's not a silver bullet. I fyou have very specific needs that are nut fulfilled by the CSL, you'll have to write your own containers/algorithm/...

So here is what everyone shall do:

1) code your project using the CLS
2) measure
3) if you found problems that cannot be handled correctly with the CSL, consider going another route.

Share this post


Link to post
Share on other sites
STL is very important for almost any C++ programmer. I'd hate to write ten lines of C++ without having access to STL, and I'd take STL over inheritance and virtual methods any day.

That beeing said, just a couple of years ago many compilers gave som pretty useless error feedback when using STL. And the initial decision of not having hash-map in the first version was an annoying dissapointment.

Stroustrup is correct. STL is one of the rare libraries which is both robust, flexible, and efficcient.

Share this post


Link to post
Share on other sites
Quote:
Original post by VprMatrix89

I really want to know how important is the stl in REAL games?


A carpenter comes to fix your ceiling. You see they don't use a hammer, but take off their shoe, and use that instead.

Upon asking them, they say they don't care about hammer, because they are overhyped. He then proceeds to show you the double reinforced heel of the shoe, along with padding on the sole, supposedly to improve the grip.

Quote:
Especially things like cin and cout , are they even used?


The difference between std::c* approach and *print*(...) approach exists. There are trade-offs, and in some cases, the later may be preferred. But this again is a matter of case-by-case requirements evaluation. Knowing both approaches well, and being able to recognize the most suitable one is well recommended.


One thing that always boggles my mind, is for engineers to deliberately refusing to learn as many tools at their disposal as possible. Script kiddes - fine. But anyone aiming above that should:
- Look at (in this case very fundamental) technology
- Evaluate it in context (open source, articles, books, case studies)
- Apply it or dismiss it, based on requirements of a project

And hopefully, nobody attempting to work on "real games" will find a tiny little set of classes that are STL intimidating. That in itself is a much bigger problem.

Quote:
My guess is that the stl's string, vector, and map are just dressed up arrays with functions to help out.


No, they're not. Guessing here is somewhat pointless, STL is very precisely defined, and it's not about dressing up. It tackles some crucial issues that deal with the difference between C and C++ way of doing things, as well as addressing some big issues that C++ is known to have.

Share this post


Link to post
Share on other sites
Quote:
Original post by MaulingMonkey
"The SC++L is fast" is 1 reason why, but it admittedly doesn't go into the details. Aside from strict algorithmic performance requirements set forth by the standard, modern implementations use a huge bag of tricks to perform at their best -- empty base optimization, return value optimization, tag based dispatch to optimized versions, and general tailoring to the compiler they're targeted for. It's very intentionally designed to be damn hard to beat for the tasks they're designed to solve.


Actually, they are not. At least on my GCC 4.3, that's it. My own std :: vector implementation is a whooping 70% faster than the STL one. But remember, unless you use a given STL container very heavily in your code there is absolutely no reason to reimplement it, since, as MaulingMonkey said, the STL containers are already debuged and basically bug-free. It's silly to introduce new bugs in your code when there will be no benefit performance-wise.

Share this post


Link to post
Share on other sites
So there we are again, the same old question keeps rotating around the same point viciously.

Well STL is, as a standard, certainly well defined and has a very concrete goal. But to be honest, when someone says "STL containers and algorithms will be as optimum as possible", I'm sorry to note but this isn't always the case. And I wonder to which STL implementation iD's code is compared? Because, there are many implementations, one can run faster or slower than the other. So, saying that STL will be always optimum and at least as fast as custom code, is pointless... You can say "libstdc++' STL implementation will be..." but it would be one huge mistake if one generalizes all of the STL implementations out there.

Also have you checked Dinkumware's implementation? One big pile of pointless indirections. Though, according to the ASM output, the compiler is somewhat successful at handling it.

STL sure provides a very nice fundamental for building on top. But in my opinion a good coder should also know what he/she is using. It's true that coding more complex applications became very easy with the adoption of STL use in the projects, though we also started to end up with "coders" who doesn't even know why they are calling certain functions or why they are using a certain container X for the task Y.

I'm not advocating STL nor doing the contrary. Yes trying to code something similar would certainly be re-inventing the wheel. But why not, if I can? Please note that what I say applies mostly to the indies or amateurs like us. Most of us have nothing to lose but time while doing so, unlike big companies with millions of dollars to sink, thus in the end you would learn what you're calling when you call array.clear(); Also it's a very nice practice to code such things.

So, to use STL or not, it depends on your intentions as a coder. I, personally, would love to take the challenge and write something similar just for my personal use to see how far my abilities and skills can carry me in a race with all those big sharks in the ocean.

Share this post


Link to post
Share on other sites
Quote:
Original post by desudesu
Quote:
Original post by MaulingMonkey
"The SC++L is fast" is 1 reason why, but it admittedly doesn't go into the details. Aside from strict algorithmic performance requirements set forth by the standard, modern implementations use a huge bag of tricks to perform at their best -- empty base optimization, return value optimization, tag based dispatch to optimized versions, and general tailoring to the compiler they're targeted for. It's very intentionally designed to be damn hard to beat for the tasks they're designed to solve.


Actually, they are not. At least on my GCC 4.3, that's it. My own std :: vector implementation is a whooping 70% faster than the STL one. But remember, unless you use a given STL container very heavily in your code there is absolutely no reason to reimplement it, since, as MaulingMonkey said, the STL containers are already debuged and basically bug-free. It's silly to introduce new bugs in your code when there will be no benefit performance-wise.


I'm very skeptic to your numbers without source and compiler settings for your benchmark. And 70% faster at doing what? Access? Insertion? Deletion? You are being extremely vague.

Share this post


Link to post
Share on other sites
Quote:
Original post by desudesu

Actually, they are not. At least on my GCC 4.3, that's it. My own std :: vector implementation is a whooping 70% faster than the STL one.


So it can do Kessel run in 12 parsecs?

What does 70% faster mean in terms of vector?

And a very important point that is missed by previous sentence: On GCC 4.3. STL containers guarantee behavior on STL-compliant implementations. Regardless of compiler, regardless of platform.

It's a fact that sequential storage can be implemented in a different way, one which has lower constant factor costs. That is not why STL came to be.

Quote:
It's true that coding more complex applications became very easy with the adoption of STL use in the projects,


It's the very big projects which may, if possible, justify creating your own containers.

But what is the purpose of writing 5000-line implementation of your own standard library for a 2000 line project?

I'd be very wary of someone implementing STL equivalents in under 40 man-hours that even approaches the quality of current STL implementations. And that is a lot of money for mere constant factor improvement. Some do that because they really need to, or because they don't have a choice.

And besides, 70% improvement is mostly moot point, when simply using the facilities provided by STL can provide 50x (fifty times) faster usage.

Share this post


Link to post
Share on other sites
Quote:
Original post by Omid Ghavami
I'm very skeptic to your numbers without source and compiler settings for your benchmark. And 70% faster at doing what? Access? Insertion? Deletion? You are being extremely vague.


Sorry for being vague. Insertion. Access is obviously irrelevant here (constant time). Deletion (of the first element) is about 800 thousand % faster, since I managed to get away without memory reallocation every delete. My std :: vector probably doesn't exhibit *exactly* the same behaviour as STL one, but, I don't care. That wasn't my design goal. I wanted a vector that, speed-wise, can be used in a place of massive raw array manipulations without (or with very negligible) performance loss.

Quote:
Original post by Antheus
It's the very big projects which may, if possible, justify creating your own containers.

But what is the purpose of writing 5000-line implementation of your own standard library for a 2000 line project?

I'd be very wary of someone implementing STL equivalents in under 40 man-hours that even approaches the quality of current STL implementations. And that is a lot of money for mere constant factor improvement. Some do that because they really need to, or because they don't have a choice.

That's what I was saying in my previous post, unless you really need the speed (or have too much time on your hands), there is no point in doing the reimplementation. On other hand, when you need it you don't have to reimplement the whole STL - one can always rewrite a given container, or even rewrite it only partially, excluding the features that will not be used.

Share this post


Link to post
Share on other sites
With a few corrections....

Quote:
Deletion (of the first element) is about 800 thousand % faster, since I managed to get away without memory reallocation copy every delete.


I'm wondering if you haven't just reinvented std::deque [smile]

Quote:
My std :: vector container probably doesn't exhibit *exactly* the same behaviour as STL one, but, I don't care. That wasn't my design goal. I wanted a vector that, speed-wise, can be used in a place of massive raw array manipulations without (or with very negligible) performance loss.


It's been a long-known fact that some containers will outperform a vector on some operations. For instance, std::deque and std::list generally outperform a vector when removing or inserting elements at the front. This is less a case of "the SC++L is slow" than a case of "using the wrong container is stupid".

Share this post


Link to post
Share on other sites
Quote:
Original post by desudesu

Sorry for being vague. Insertion. Access is obviously irrelevant here (constant time). Deletion (of the first element) is about 800 thousand % faster, since I managed to get away without memory reallocation every delete.


So you have ultra-special case which you optimized. That doesn't make it faster.

Quote:
My std :: vector probably doesn't exhibit *exactly* the same behaviour as STL one, but


Then do not compare it to that. And how did we get from 70% to 800,000% over a single post?

Quote:
That wasn't my design goal. I wanted a vector that, speed-wise, can be used in a place of massive raw array manipulations without (or with very negligible) performance loss.


Then do not claim std::vector is slow, when it's your algorithmic requirements that are the problem. std::vector is storage class, with well-defined characteristics. Using it for a task that it isn't suitable for will make it "slow".

State that you required O(1) deletion of first n elements in combination with contiguous storage, something that std::vector isn't designed to do.

The by far obvious solution for this is what you came to - advance the front pointer rather than delete.

Share this post


Link to post
Share on other sites
Quote:
Original post by ToohrVyk
With a few corrections....

Quote:
Deletion (of the first element) is about 800 thousand % faster, since I managed to get away without memory reallocation copy every delete.


I'm wondering if you haven't just reinvented std::deque [smile]

Quote:
My std :: vector container probably doesn't exhibit *exactly* the same behaviour as STL one, but, I don't care. That wasn't my design goal. I wanted a vector that, speed-wise, can be used in a place of massive raw array manipulations without (or with very negligible) performance loss.


It's been a long-known fact that some containers will outperform a vector on some operations. For instance, std::deque and std::list generally outperform a vector when removing or inserting elements at the front. This is less a case of "the SC++L is slow" than a case of "using the wrong container is stupid".

Not really. I did the research. Insertion in std :: deque is still 49% slower than my implementation. Deletion of the first element is still unbearably slow. (Several thousand %)

Quote:
Original post by Antheus
Then do not claim std::vector is slow, when it's your algorithmic requirements that are the problem. std::vector is storage class, with well-defined characteristics. Using it for a task that it isn't suitable for will make it "slow".

State that you required O(1) deletion of first n elements in combination with contiguous storage, something that std::vector isn't designed to do.

Probably. But it is designed for fast insertions, for which my implementation is still faster. You can treat my constant time first element removal as a 'bonus'.

And, where did I say that std :: vector is slow? I'm just saying that it is not as fast as using a plain C-style array.

Share this post


Link to post
Share on other sites
@desudesu: Any chance that your custom container removes elements by swapping them with the last element and decrementing the size by 1? If so, you can do that with std::vector as well. There's no member function for it (as far as I know), but it's only a few lines of code.

Share this post


Link to post
Share on other sites
Quote:
Original post by desudesu

And, where did I say that std :: vector is slow?


Here: "Actually, they are not."

Quote:
I'm just saying that it is not as fast as using a plain C-style array.


And again - apples to airplanes.

Since when do plain C-style arrays support addition, removal and insertion?


Share this post


Link to post
Share on other sites
Quote:
Original post by Gage64
@desudesu: Any chance that your custom container removes elements by swapping them with the last element and decrementing the size by 1? If so, you can do that with std::vector as well. There's no member function for it (as far as I know), but it's only a few lines of code.

Nope.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
Original post by desudesu

And, where did I say that std :: vector is slow?


Here: "Actually, they are not."

I did not. Read the fragment I quoted. I was mainly referring to the statement that ,,It's very intentionally designed to be damn hard to beat for the tasks they're designed to solve.''.

Quote:
Original post by Antheus
Quote:
I'm just saying that it is not as fast as using a plain C-style array.


And again - apples to airplanes.

Since when do plain C-style arrays support addition, removal and insertion?

They always did, that is, if you do it manually.

Share this post


Link to post
Share on other sites
Quote:
Original post by desudesu
Quote:
Original post by Antheus
Since when do plain C-style arrays support addition, removal and insertion?

They always did, that is, if you do it manually.


They never did. The number of elements in an array is fixed when the array is created, as per the language specification, to be the number between the [] in the array definition (which is a compile-time constant in C89 but can be a run-time value for stack arrays in C99). Perhaps you meant something else?

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