• Advertisement
Sign in to follow this  

STL Saves or Enslaves?

This topic is 4326 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

How wise is using STL containers (lists) in a fast-paced game instead of creating the sturctures form scratch? Hurts efficiency? More overhead which is noticeable to the player? Or slight drop in frame per second counter like q couple of frames? Thanks.

Share this post


Link to post
Share on other sites
Advertisement
Depends on what you're doing. An STL list is a linked list and shares the same basic performance properties.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Lets put it this way: You're probably not gonna be able to write a faster doubly linked list yourself ;)

Share this post


Link to post
Share on other sites
I'd say that STL will give better performance than pretty much any home-brewn container, if used correctly. I highly recommend STL.

Share this post


Link to post
Share on other sites
STL containers are extremely efficient when used properly.

Share this post


Link to post
Share on other sites
Quote:
Original post by Mushu
I'd say that STL will give better performance than pretty much any home-brewn container, if used correctly. I highly recommend STL.


Ditto. And even if your linked list is somehow faster, it's not going to be more robust or cleaner than the STL implementation, which has been banged on for years by people much smarter than yourself. [grin]

Share this post


Link to post
Share on other sites
And since some ppl here offend my intellignece "smarter than yourself," and "You're probably not gonna be able to write a faster..."

I say yup I can write much much faster close to the speed of photons and much faster and efficient doubly linked list with random access facility and sorting capabilities and memory management to beat up the hell out of the CPU and guess what, it runs on GPU using a shader language. Just kidding!

Anyway thanks for ur replies, I will go with STL.

Share this post


Link to post
Share on other sites
If there's one STL container you CAN beat though, it would be the set, but only by caching or preallocating nodes for a binary search tree which I believe most implementations of set use.

Share this post


Link to post
Share on other sites
Quote:
Original post by quaker
And since some ppl here offend my intellignece "smarter than yourself," and "You're probably not gonna be able to write a faster..."


They're much smarter than the rest of us too. Some of the people working on the STL are the same people working on the C++ language itself -- people way smarter than you, or I, or probably anyone on this site are working on this stuff every day and making it more robust and solid.

Regardless of their intelligence, spending weeks re-writing most of the STL is just stupid. That time could be better spent writing game code, and I'm pretty sure you must have bigger performance sinks in there than the STL.

Share this post


Link to post
Share on other sites
If you find a problem with speed, it probably will have little to do with WHICH linked list you use(STL or your own). Instead, your speed problems will probably stem from the typical use of a list, where you dynamically allocate objects and add them to the list.

If you need to speed things up you should consider if there's a strategy that would allow you to allocate some/most/all of your objects all at once. Even if objects are created and destroyed frequently you could still use a pooling scheme. With this in hand, it probably doesn't matter all that much if you put the active ones at the front of a sorted array, point to them in a linked list, etc.

Hope that helps!

-John

Share this post


Link to post
Share on other sites
Some posters mentioned here, that STL could be very effective, when used properly. But main problem, IMHO, is in this proper usage, you should spend weeks (or even months) of time to begin understand right usage of stl, when to use is_empty or when use (count == 0) for example. Why there are so much books written about proper use of STL?
I think, that STL is universal container, when in games we don't need this univesality, so it is neccessary to write your own container. But you should know STL, because there are many good architectural and algorithmical concepts applied.
PS: Assembler, generated from code with stl usually uglier than one generated from your own (But it's also depends on 'how good you are at programming' :) ).

Share this post


Link to post
Share on other sites
@const (cool nickname, BTW). I feel that could mislead into thinking that the STL's generality somehow compromises its efficiency. It does not in all but the most extreme and contrived cases. That is one of the best things about it.

Assembly can be as ugly as it wants as long as we don't have to look at it. Find me an example of an STL container or algorthim being outperformed by a user-created equivalent in a way that ACTUALLY IMPACTS UPON AN APPLICATION IN A MEANINGFUL WAY and I'll shut up.

Share this post


Link to post
Share on other sites
Quote:
Original post by EasilyConfused
I feel that could mislead into thinking that the STL's generality somehow compromises its efficiency. It does not in all but the most extreme and contrived cases. That is one of the best things about it.

Is not game development extreme and contrived case? :)
You must get from processor as much, as possible, and every excess tick on operation, performed in main loop gives you fps loss.

Quote:

Assembly can be as ugly as it wants as long as we don't have to look at it.


Checking assembly is a neccessary case because sometimes compiler goes crazy on absolutely simple cases. For example some days ago we found that usage of unsigned int and float created VERY bad code - compiler generated tons of absolutely unneeded instructions (This is only example of need to check assembly).

Quote:

Find me an example of an STL container or algorthim being outperformed by a user-created equivalent in a way that ACTUALLY IMPACTS UPON AN APPLICATION IN A MEANINGFUL WAY and I'll shut up.


I think this algorithm could be sorting one :)

Well, I don't want to say, that own-made bicycle is a better one, however my point is, that usually I don't need all that complexity, that brings STL. I must think about memory allocation strategy, when my task is simple iteration over list members for example.

Share this post


Link to post
Share on other sites
Just use it.

Get the code done, make it work, profile, AND THEN optimize. Things change as your code base grows, requirements change, designs change. Why waste time rolling your own tightly optimized linked-list if you might just toss it out in the end because a straight array turned out to be faster? What you spend time optimizing may end up inconsequential due to a bottleneck.

When you do optimize, remember to optimize the algorithm first. Use a list if you need fast inserts/deletes at any location. Use a vector if you need fast traversals. Write a custom allocator if memory allocation is an issue. If all else fails, then roll your own.


What is it with C++? No one using C# seems to question using the .Net Standard Library... no wonder people find themselves more productive... they aren't reinventing the wheel all the time.

Share this post


Link to post
Share on other sites
Quote:
Original post by const
I think, that STL is universal container, when in games we don't need this univesality, so it is neccessary to write your own container.


Whoa whoa whoa, where'd we jump from "don't need feature X" to "we need to rewrite this"?

Yes, there will be some 10, 1, or 0.1% of cases where, gosh darn it, your container usage is a bottleneck and no STL container can quite do the job you need done, at the speed you need it done. By using the STL in the 90, 99, or 99.9% remaining cases, you can focus on spending your time optimizing where it counts, instead of repeatedly reinventing the wheel every few seconds for no good reason. Given how good optimizers are these days, it's going to be damn hard to beat the compiler in a lot of circumstances, especially when it boils down to repeating exactly what the STL version would do.

While some parts of game programming are extreme, contived cases, there are a lot of parts where it is not. If you spend 10 hours optimizing a game, you're going to get better results by focusing on where it matters rather than spreading it paper thin everywhere. This is common sense!!

Quote:
Original post by const
Well, I don't want to say, that own-made bicycle is a better one, however my point is, that usually I don't need all that complexity, that brings STL. I must think about memory allocation strategy, when my task is simple iteration over list members for example.


for ( container_type::iterator i = container.begin() ; i != container.end() ; ++i ) {
//use i
}


Could you please point out where I worried about memory allocation strategy? I can't find it.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Admit it, it's fun to rewrite the obvious to fool yourself into thinking you are doing something productive.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by EasilyConfused
@const (cool nickname, BTW). I feel that could mislead into thinking that the STL's generality somehow compromises its efficiency. It does not in all but the most extreme and contrived cases. That is one of the best things about it.

Assembly can be as ugly as it wants as long as we don't have to look at it. Find me an example of an STL container or algorthim being outperformed by a user-created equivalent in a way that ACTUALLY IMPACTS UPON AN APPLICATION IN A MEANINGFUL WAY and I'll shut up.


A good example is where many allocations/deallocations happen in a short time frame and the system's malloc implementation is not the best. Of course there is a way to work around this by making an object cache out of stl templates and using that, but it requires as much effort as making your own array based object pool. So the best example is the memory and speed contrained application where allocating objects from the heap would be too slow. Also a custom container can wrap the control info and the actual data into one large malloc()-ed or mmap()-ed block.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I don't really buy the argument that "smarter people have worked on it, therefore you don't need to write one".

One of the very basic parts of a language is it's memory manager. new and malloc SUCK. They fragment memory and are unusable on a platform with a fixed memory footprint.

Why am I to believe that this nebulous standard template library (which implementations change from compiler to compiler) would be better suited than something I can write.

I write for consoles. Certain current generation consoles have small L1 caches, and no L2 cache. Cache coherency is CRITICAL. How can I be sure that the STL will respect that and write code with good data and code locality in mind?

I can't, and most of the time, it doesn't.

STL is easier, but doesn't nessecarily mean it's BETTER.

I know this is a bit of a religeous topic, and I certainly can see how STL is very useful. Especially for PCs, in which software is written mostly to libraries and an operating system, and doesn't have such an intimate correlation with the hardware. But there is a huge games market in which it is critical that the developers have full control over the libraries that they use.

I just hate to see people act as if someone would be crazy not to use STL. STL has it's place, but is certainly not the be-all end-all

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
Admit it, it's fun to rewrite the obvious to fool yourself into thinking you are doing something productive.


Lol

Actually, I accept that it may be a different kettle of fish in the world of console programming and, having never written my own allocator, I can't really comment on how much effort it is compared to writing your own code.

I just felt that the point about STL compromising efficiency for generality demanded refuting. Let's not fight for 14 pages about this as it's been done so many times on this site.

Share this post


Link to post
Share on other sites
Well...
All I want to say, is that STL has no place in production in-game code (especially main loop), just because this is a place, where we need to optimize almost everything to get maximum fps.
There is absolutely no problem of stl-usage in tools-development or level-loading-code.
And one more issue, I'm console developer, and there is not too much resources to spend on template instances (generated code grows too large, therefore consuming more memory) and other things.

Share this post


Link to post
Share on other sites
Don't be rediculous, STL is perfectly fine in a game loop, provided you aren't doing something stupid with it, like thousands of map lookups, clearing and re-populating a large list container, etc.

Share this post


Link to post
Share on other sites
Quote:
Original post by const
Is not game development extreme and contrived case? :)
You must get from processor as much, as possible, and every excess tick on operation, performed in main loop gives you fps loss.
Does it now? Even in operations that aren't bottlenecks? Even when the bottleneck is the GPU?

And even when it is a bottleneck, one has to weigh the potential improvement vs. other improvements they could make with that time. What are players going to prefer, a couple more FPS, or some extra features, or maybe a few less bugs?

As a programmer, you not only have to optimize your program, but your own time as well. Professionally, it's extremely important to balance your time; no one, especially your boss, is going to give a flying %#^$ if the game is 5fps faster if you missed your milestone. Even if it's just a hobby, most of us only have a few hours a day to spend coding, and maybe only a couple computers to test on. It could turn out that the extra month you spent optimizing was wasted because most people who download your game have fast computers, or are complete novices and still have their monitors at 60Hz, negating most of the improvement. An entire month gone that you could have spent implementing their excellent suggestions.


Consoles of course, are an entirely different story, where templates in general must be used very carefully. But if you're working on a console, you most likely know this already.

Share this post


Link to post
Share on other sites
omg, stop! stop right now!

"console this", "console that", news flash!
99.9% of people on this message board ARENT going to be writing for constricted consoles/devices.
They will be writing for PCs which DONT suffer the memory, cache or other console based problems.
I'd also argue that with the newer breed of consoles this is becoming less and less a problem.

But, regardless, mentioning all that here just muddies the waters something terrible; newbies and 'not made here' addicts alike will take what you guys say and around we go with another cycle of 'the STL is slow' game, which is rubbish and doesnt apply to most people here.

Oh, and on the memory issue, the STL's containers have allocators, these allocators can be used to provide pool memory, avoiding repeated calls to new/delete AND allowing entities held in containers to be contigous in memory (be they pointers to real object or the objects themselves).

In short, for practically everyone on this message board the STL is what they should be using.
End.
Of.
Story.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:

What is it with C++? No one using C# seems to question using the .Net Standard Library... no wonder people find themselves more productive... they aren't reinventing the wheel all the time.


Most of the ppl writing C# aren't overly concerned with speed of the code as much as development times or ease of use that is provided by C#; its a mentality issue. STL may help in certain circumstances, but it is definately not perfect for every condition.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement