   Reinventing the wheel or not?
  Hi, I'm in mood of writing the game engine/game framework, so I got myself a copy of "3D Game Engine Architecture" by David H. Eberly.Almost in the beginning he start with description of basic data structure one may need. He gives an example where he uses STL's set<T> versus his own so called SmallSet<T>. STL's set uses about 980MB and his own SmallSet uses 50% less or about 503MB.Then I would like to quote:Quote:Real-time applications are of such a nature that the designer/architect of thesystem has a lot of knowledge about memory usage patterns, but a generic set oftemplate containers do not have the benefit of this knowledge. In this setting, there issome justification for reinventing the wheel! Section 2.1.1 discusses the basic datastructures that replicate some of the functionality of STL, but just the minimumnecessary to support the engine.Keep in mind that new hardware (such as game consoles) might not immediatelyhave libraries that support STL. Since consoles tend to have much less memory thandesktop computers, the presence of STL might actually be a curse because of thememory overhead.Now I'm a fan of reinventing the wheel, but people yelled at me, and in the last time I tend to use language built-in functionality even tough I barely use 50% of all the features that some data structure or class gives me (simply because I don't need more).I pretty agree with David in his quote about the knowledge of memory management of the data structure and for me will be probably easier to write my own than digg's STL's (or other library) code to understand how it manages the memory.What is your opinion?   
Quote:for me will be probably easier to write my own than digg's STL's (or other library) code to understand how it manages the memory.How are you going to fix something, when you don't know what is broken?This is the very definition of why not to roll your own. Your reasoning:- A book published in 2004 (probably before MVS2003, so perhaps based on VC6, and probably in time of gcc 2.x) claims std::set implementation uses too much memory- Same book provides alternate implementation SmallSetYour conclusion:- I will roll my own (logic folks would say: Does not follow)There are many good reasons to use custom structures, and memory use is definitely one of them. But not in your case, unless you know *why* existing implementations are invalid, and also how to fix them.If you feel that existing implementations use too much memory for your needs, analyze why that is so, then fix the cause of the problem.In theory, a set doesn't need any overhead at all, so its total committed memory will be the sum of sizes of objects it stores. But since this is often not practical, some overhead is usually allowed, either on per-set basis, sometimes even on per-element basis. But the final choice will depend on performance characteristics of user, as well as elements.   ;  My opinion would be to use built-in container types. In the first iteration of the game/engine/whatever there's no need to waste your time on such things as writing your own.You do need to be cognizant of the memory you're using but perhaps this early in the development process it's not warranted.You can always specify your own allocator for certain containers in the future if you find that memory allocation is a bottleneck.I typically typedef (c++) any container that I use that I can foresee changing in some way in the future to reduce the amount of code changes.   ;Quote:Original post by s.kweeI pretty agree with David in his quote about the knowledge of memory management of the data structure and for me will be probably easier to write my own than digg's STL's (or other library) code to understand how it manages the memory.What exactly do you mean by "how it manages memory"?  You can provide custom allocators if you want that will allocate memory in whatever way you want.  If you're curious as to when your allocator will be called or what will be done with the memory... well then that depends on each container.   ;  First of all thanks for the fast comments :)AntheusAs I said, I used to fix things that are not broken (or I don't know where they are broken), but not anymore (at least I try not to), so no I'm not going to roll my own while there is a ready one, I just noticed that this book is the most popular among book in this topic at gamedev.net and for me book are holy (as people how knows the topic and can help/assist) and I tend to take good advices from books and people with knowledge and to use them, and I just want to clarify how good is this advice, cause many people convinced me to do the opposite from what is written here.AAAAs the book "Code Complete" that I read says: "You can not know what will cause overhead without you try it" (quotes in my words, cause the book is in Russian and I'm lazy to search it) so I totally agree with you :)MikeTacularI mean that you don't know what happens behind the lines "std::some_container S = new std::some_container()" How it will allocate memory? How Insert() function works (will it reallocate the memory for a new place with +1 item or some other way)?I'm pretty sure answer could be found in the Internet its just a matter of "do I really need this?".   ;Quote:As the book "Code Complete" that I read says: "You can not know what will cause overhead without you try it"As with all rules, this one has exception:- You cannot know what will cause overhead, unless you *know* what will cause the overheadAs with everything, the basic problem here boils down to this:- Do you have memory issues? Is your working set 1GB when you only have 500MB working memory?- If so, can it be reduced?- If so, how?The 1GB vs 500MB comparison you state in OP - is this your application, and this memory usage causes excessive paging, making the application unusable? Or is this just some example from the book which might not even apply in your case?What you should right now is the following:- sum up the sizes of objects in set. That is your baseline metric.- Is this size too big for target platform (500MB non-paged memory, where your size comes out at 600Mb)?- If yes, then consider a different algorithm- If no, you are done, use the fastest, simplest solution which turns out to be std::set... later ...- When profiling, you may find out that std::set uses more memory than you calculated in step one. Determine if this is due to some overhead in implementation, and see if it can be fixed.   ;Quote:Original post by s.kweeI mean that you don't know what happens behind the lines "std::some_container S = new std::some_container()" How it will allocate memory?Just like any other heap allocation.  Usually you don't allocate containers on the heap though.Quote:Original post by s.kweeHow Insert() function works (will it reallocate the memory for a new place with +1 item or some other way)?That depends on each type of container.  If you're using a std::vector and its capacity is full, it usually increases its storage by a factor of 1.5 or 2, otherwise it doesn't need to allocate any new memory if its capacity isn't full.  AFAIK, other containers like set, list, map, etc. usually only allocate storage for each element and not in large blocks (though I suppose this depends on implementation details).  But this is where you can use your custom allocators if you want.   