Oberon_Command, as the old phrase goes: "you can lead a horse to water, but you can't make it drink"
...even if you repeatedly splash it's nose with enticing cool stl goodness :lol:
Linked list adventure
...even if you repeatedly splash it's nose with enticing cool stl goodness :lol:
Thats NOTHING to do with STL though. placement new is the correct way of constructing class-instances in custom memory regions - even if you ban STL from your entire codebase, you still want the classes (default) ctor to execute, and not just set the entire memory region (all members including vptr-tables!) to 0.
Clearly micro-seconds CPU time are more precious than hours programmer time to the OP.
Personally, I tend to optimize much more on programmer time, but fair enough.
Personally, I tend to optimize much more on programmer time, but fair enough.
I like Mike Acton and he has a lot of good points, but more so for consoles. Even a Blizzard (engine) developer at CppCon2016 hinted now that they're using C++11 internally they are looking at the standard library for common usage in their games. I also agree with Mike on optimizing if you know from past experience something will be slow, or using tricks to help the compiler to generate more optimized code when possible. But spending quite a few number of hours writing back end code instead of a game seems to be a waste other than as experience gaining (or a profiler identifies it as a serious bottleneck). The amount of testing needed to verify every iteration of the code is not simple nor trivial if you want to rely on it. But that's just me at least.
I like Mike Acton and he has a lot of good points, but more so for consoles. Even a Blizzard developer at CppCon2016 hinted now that they're using C++11 internally they are looking at the standard library for common usage in their games. I also agree with Mike on optimizing if you know from past experience something will be slow, or using tricks to help the compiler to generate more optimized code when possible.
That's not true. I saw production code where people happily used STL containers. They might have rolled out their own allocators, but the flexibility of STL allows you to do that. STL containers are fast in most cases if you use them properly.Its the opposite: When you dont care about peformance or memory, you use std library however you like, like for example in some tools, debug stuff, business applications, you name it etc. but i would never use the std library in any realtime production code ever.
For example, I'm using std::vector often, and it works perfectly. There are slowdowns in debug mode (of course), but that doesn't concern me.
Also, there are many cases where STL or C++ templated approach is faster than C. In other cases, it'll be as fast as C as long as you are doing the same thing. Many comparisons are usually incorrect, because the C++ implementation is doing more than the C does.
The behaviors of the containers are well documented and are deterministic. There might be small differences between compilers, but nothing you have to worry about too much.- I have no idea how the memory is allocated, how much it allocates, what it allocates, where it allocates the memory etc.
Yes, you can have total control by creating your own allocator.- I have no control over the allocated memory at all
STL errors can be hard to read at first glance, but after a while you'll easily understand them. Clang even improves this further on. (MSVC will move to a clang based backend in the future btw)- Debugging any std library errors is just horror
It potentially breaks any non trivial class / struct, not just STL containers. You should never zero initialize anything but the simplest structs.- Zero initialization totally breaks the containers:
Personally, I tend to optimize much more on programmer time, but fair enough.
Well, in this case you're in luck because he's implying that STL doesn't have anything better for performance than his linked list, which is a pipe dream at best, so you can spend 1/10th of the programming time and get 10x the performance from std::vector.
Author
You should investigate placement new if you have not already done so - which I would hope you have, if you're intending to use non-POD types with a custom allocator.// is there a reason you can't just do this? GameState *gameState = reinterpret_cast<GameState*>(myGameMemoryAddress); *gameState = GameState(); // or even this GameState *gameState = new (myGameMemoryAddress) GameState();
Placement new is "new" for me, never heard about that before, Thanks - will look into that, may safe me some trouble at work.
But for the rest of it: This entire discussion boils down to the fact that i rather use C for game development instead of C++ and here are the reasons why:
- I have no idea what internally happens in the implementation of the std library and after a look at the source: i seriously do not wanna know.
- I always do programming in a object oriented fashion and wanted to do it differently now: Seeing the other side too
- I want to have full control over memory and all systems in my game -> Nothing should be a blackbox
- I do not want to be forced to any programmings patterns whatsoever (Ctor, RAII, Singleton, Templates, Interfaces, Classes, New/Delete etc.)
- Zero initialization is great, even though its a c++ feature
- static_cast is nice, but i still prefer the C way for game development
- I want to be not afraid of pointers and memory anymore, which i was 5 years ago
- I am not afraid to write complex code
- I do not want to just write less code by the cost of abstraction, making it harder to read, less understable
- You think much more about memory, performance and the hardware when doing low level programming -> You learn a ton
That saying with 25+ years of programming experience in all kinds of fields and languages but still like doing programming in C++/C#/Java with full OOP.
This entire discussion boils down to the fact that i rather use C for game development instead of C++
So you came from a higher level language? I can see how C offered you new things in that case.
For me, it's the opposite, mostly because of my age, I was already programming before OOP was a thing :)
As a result, I already knew what assembly language and C offered, and getting rid of all that additional standard boilerplate was welcome.
My background of compiler construction probably also counts, I always loved the magic of code generation (although it's not so magic once you understand it), and love being able to express myself at a higher level of abstraction, as long as it is well-defined.
First off, wanting to use C over C++ is perfectly acceptable, just don't confuse the reasons why. Don't also confuse C over STL; C++ is not STL, STL is a standardized library to aid in development, but it's built on top of C++ itself. You can develop in C++ without ever needing to use STL.
- I have no idea what internally happens in the implementation of the std library and after a look at the source: i seriously do not wanna know.
Why do you need to know what happens internally? Playing the devils advocate a little here, but the fact that it's pure headers means you can understand it, it's just a (very) complex beast. Wanting to use C over C++ doesn't magically make your code cleaner or the implementations more accessible/readable either, neither does C over STL.
- I always do programming in a object oriented fashion and wanted to do it differently now: Seeing the other side too
Is your original example really an example of the other side? Composition over inheritance are two pretty distinct paths and separate, but using STL over reinventing the wheel doesn't really seem productive unless you're a beginner wanting to learn the how. Even C over C++ isn't really seeing the other side, C++ offer numerous features over C, but that doesn't mean you are forced to use those features.
- I want to have full control over memory and all systems in my game -> Nothing should be a blackbox
Again, allocators, they're actually not overly complicated and let you have (admittedly mostly) full control over memory. I will note that because of potential performance impacts, allocators are not as fully customizable as originally envisioned, but they do allow creating pools for allocating from, just like your examples.
- I do not want to be forced to any programmings patterns whatsoever (Ctor, RAII, Singleton, Templates, Interfaces, Classes, New/Delete etc.)
Note that singletons are the only real pattern in that list, the rest are either idioms or features of the language. While you are forced to use some of those features when using STL, you're not forced to use all of them (singletons, new/delete, interfaces, raii). Again, STL is a tool to help replace common code that (invariably) gets used anyways, you accept that you're using templatized classes when using STL. Those classes themselves do have constructors, but you don't have to create constructors for your own types when using STL. STL also doesn't require or prevent usage of raii, singletons, interfaces, new/delete, etc. That's entirely up to you on how to want to use what STL provides.
- Zero initialization is great, even though its a c++ feature
Zero initialization only makes sense when things need to be zero. I only have a handful of classes that actually need to be all zero, and even then I still prefer member initialization because it makes the code a lot cleaner and more readable. You don't even need to search for the constructor body, you just see the initial value right at declaration.
- static_cast is nice, but i still prefer the C way for game development
The C way of casting is ambiguous, which I can imagine is a big reason why they added different casts in C++. I actually wish there were a compiler option to error on C style casts (is there?), since I still tend to use them without noticing, especially for simple data types. They're quicker to write and quicker to crash, I like the explicit and single purpose nature of C++ casts so that I can prevent issues. I actually don't see why you'd want to use C style casts in game development, when typically you do want every little bit of performance games that you can get. Someone please correct me if I'm wrong, but using explicit casts and type conversions is going to offer greater gains than relying on the ambiguous C style cast. At the very least, the compiler will choose the correct cast and do the same thing, but then that's entirely up to the compiler (and may change between compilers?).
- I want to be not afraid of pointers and memory anymore, which i was 5 years ago
What does fear/lack of fear of pointers and memory have to do with it? You don't use STL because you're afraid of pointers or memory, you use STL because you don't want to reinvent the wheel. You can write your own code to handle allocation/traversal/release of everything (or use other existing code), or you can use STL, or even a multitude of other libraries. STL is just a tool to aid in development, same as your own code samples, same as EASTL.
- I am not afraid to write complex code
Then you shouldn't be afraid of using STL, which doesn't really decrease the complexity of code if you're already using boilerplate helpers. It's just a tried and tested alternative to your own ad hoc code. I'd say that adding macros and an array of independent functions ends up leading to more complex code, but honestly to each their own on that point.
- I do not want to just write less code by the cost of abstraction, making it harder to read, less understable
What do you mean abstraction though. You're already trying to abstract out the linked list implementation into a set of independent functions, which is the same thing that stl::list does. Using STL has the advantage of making everything self contained, accessing a list works on the list itself, no casts, no independent functions, etc. Unifying the containers also has a huge advantage, everything has a begin/end/size/clear/etc, you can iterate over the container the same way regardless of what type of container you are using. If you want to switch to using a vector instead of a list, you just change the type, as long as you're not using list specific operations then everything down river works exactly the same.
- You think much more about memory, performance and the hardware when doing low level programming -> You learn a ton
STL doesn't prevent you from learning about memory, performance, or hardware. I don't think STL does anything in terms of hardware actually, that's still entirely up to you. I was recently looking more into SIMD, that requires learning about the hardware, the compiler, etc. It also required learning about allocators in STL to support proper alignment to store the data. Thinking about performance still applies when using STL too, using STL doesn't instantly bottom out your performance. STL has wide range of functionality, but the most common still seems to be the containers, using STL containers over your own implementation doesn't change anything else in your application, you still have to look into performance issues, bottlenecks, etc all the same.
Sadly this has become a this-versus-that debate.
Personally, I'd dump the whole thing. Over the decades of performance tuning I've learned to GENERALLY avoid linked lists. A regular array with a 'dead' flag is very often faster than a linked list thanks to cache effects.
If you're going to progress serially through the container then a linked list is absolutely terrible in terms of access patterns, jumping from here to there with every step, with potentially a full cache miss on every link. Storing with an array directly you're going to leverage the cache for every read, unless your types are so huge they barely fit in cache.
The cost of a cache miss is enormous. If it is in your cache and you need to test if it is dead, the cost is about a half nanosecond. Since the prefetcher can see the linear access it will have all the data available as you race through it. The prefetcher is very good at its job and stalls are rare. But following linked lists if you aren't fortunate to have it already in L1 cache, following a link in L2 cache takes about 15x-20x the time, around 7-10 nanoseconds. If it happens to jump out to main memory, that's about 200x the cost at around 100 nanoseconds.
The same is true for tree structures as well. Over the years I've seen an enormous about of code rewritten so that trees are stored in contiguous arrays as a binary heap. That is, the binary tree is stored breadth-first as an array. Algorithms using the tree get restructured into breadth-first work where possible to enable all the wonderful cache effects.
If you have so much data that a flat array is unreasonable (which is extremely rare in games), a structure of arrays can generally be built, and if that still isn't good you can link together arrays in a linked-list fashion.
Wrapping up the loose end of insertions at the beginning, the deque style operations work well for this by leveraging the collection of arrays, linking an array to before the beginning and allowing it to grow in front as well as in back.
The performance of such a system tends to work well until the ratio hits about 10 dead nodes for every 1 live node. Then it needs to be compacted, which is a single linear pass over the array, typically a very small price to pay for the speedup achieved during most typical cases.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
