Jump to content
  • Advertisement
Sign in to follow this  
maximAL

boost::array style fixed-size template data containers

This topic is 3682 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

so, i'll be doing some console development again and one thing that puzzles me is the use of the STL. unfortunalty, using the STL is mostly considered evil in this area, since it constant memory (de-)allocations fragment the heap quickly. a possible solutions came to my mind, when i saw the boost::array container. it uses a template argument to control the size and doesn't need any dynamic heap allocations. i could imagine extending this approach to more sophisticated containers like strings, lists or maps with a template parameter controlling the maximum number of objects (who are internally stored in an fixed-size array). but one thing puzzles me: won't this introduce a massive template overhead? boost::array claims to introduce zero overhead over plain arrays, but after all the compiler has to make a new specialization not only for every type the container is used with (like with the STL containers), but also for every size used. while this may be not so dramatic for the rather small boost::array class, i could imagine a massive code bloat for more complex containers - maybe too much for smaller systems? i could also imagine a page-fault related performance penalty due to increased code size... any ideas on this? i also looked around for libs that implement this, but although embedded developers could make use of something like that (as opposed to plain fixed-size (char) arrays) i couldn't find anything in this direction.

Share this post


Link to post
Share on other sites
Advertisement
The solution is to use STL containers but simply implement an efficient allocator rather than using the default allocator. All STL containers (and just about all boost containers) accept a template argument where you can specify an allocator. The default allocator is specified by default.

The problem is that most people don't know how (or even that they could) create custom allocators.

Josuttis explains how to do this in the book titled "The C++ Standard Library"

Share this post


Link to post
Share on other sites
i also looked at implementing custom allocators some time ago.
this approach is a little different as is would mean using memory pools for certain objects.
maybe i don't fully understand them (as they are complex indeed), but i don't see how they really solve the allocation problem.
take a string for example. you might write an allocator to make it use only a specific memory pool, but using the same allocator-type for different strings would introduce the fragmentation problem again as opposed to the boost:array approach, where every instance has it's own memory pool...

Share this post


Link to post
Share on other sites
Quote:
Original post by maximAL
take a string for example. you might write an allocator to make it use only a specific memory pool, but using the same allocator-type for different strings would introduce the fragmentation problem again as opposed to the boost:array approach, where every instance has it's own memory pool...

But where are the individual "pools" for each string in this case? Isn't this fragmentation too, since the instantiation of each string requires creating a new "pool"?

I don't know much about memory pools, but I always thought that fragmentation in a pool was okay. That is, the pool is meant to have many de/allocations (lots of news and deletes). In the end, the pool (and so its contents) exists in a static portion of system memory. In terms of system memory, fragmentation is no longer an issue.

I'd also like to know more about allocators and pools. :-)

Share this post


Link to post
Share on other sites
Or, if you're going to resort to a fixed-size, static allocation anyhow, just use STL vectors and reserve the static size up front. IIRC, STL containers don't down-size unless you tell them to, so they'll stay that size forever.

As a bonus, rather than an immediate problem being caused if you exceed the bounds of the array, the size will simply be increased. As the program ends, you can check whether the final size of the container is larger than the size you initialized it as (and by how much) to expose memory over-use. This would be generally more effective than an assert on overflow, because the program will have the opportunity to keep running and can expose more of such errors.

For other containers, such as lists, a custom, block-based allocator will do great things for fragmentation.

Share this post


Link to post
Share on other sites
Quote:
Original post by GenuineXP
But where are the individual "pools" for each string in this case? Isn't this fragmentation too, since the instantiation of each string requires creating a new "pool"?

yes, but in embedded world one usually clearly defines the point for allocating and deallocating memory. so usually, you'd create all containers with their maximum capacity at one spot, as apposed to "now and then, whenever you need them" in non-embedded world (PC etc.).

Share this post


Link to post
Share on other sites
Quote:
Original post by Ravyne
Or, if you're going to resort to a fixed-size, static allocation anyhow, just use STL containers and reserve the static size up front. IIRC, STL containers don't down-size unless you tell them to, so they'll stay that size forever.

afaik this is only true for vectors, but not for other containers.

Share this post


Link to post
Share on other sites
I appended my above post to speak about other containers. Fragmentation of these other containers will benefit greatly from a custom block-based allocator.

Alternatively, some containers can be made to work with a vector as the back-end storage solution -- though I'm not sure how much control it will give you over setting the reserve size.

Share this post


Link to post
Share on other sites
Quote:
Original post by maximAL
but one thing puzzles me: won't this introduce a massive template overhead? boost::array claims to introduce zero overhead over plain arrays, but after all the compiler has to make a new specialization not only for every type the container is used with (like with the STL containers), but also for every size used.
while this may be not so dramatic for the rather small boost::array class, i could imagine a massive code bloat for more complex containers - maybe too much for smaller systems? i could also imagine a page-fault related performance penalty due to increased code size...


Practically speaking, it would be very unusual to know the size of several containers in the system at compile time, but also have many different sizes. But anyway, template code generation is not quite as dumb as that description suggests.

There aren't templated, static-size equivalents for other types of containers, because it wouldn't make sense: there's almost no reason to put things in a linked list if you know ahead of time how many of them there will be.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Practically speaking, it would be very unusual to know the size of several containers in the system at compile time, but also have many different sizes.

in my experience, it's normal to use some #define/constant to allocate some fixed-size array.
Quote:
Original post by Zahlman
But anyway, template code generation is not quite as dumb as that description suggests.

thats basically the question. could you elaborate on that?
Quote:
Original post by Zahlman
There aren't templated, static-size equivalents for other types of containers, because it wouldn't make sense: there's almost no reason to put things in a linked list if you know ahead of time how many of them there will be.

not how many items, the maximum number of items. when working with tight memory limitations you should know the maximum memory usage beforehand anyways, as you can't afford running out of memory because of a situation that didn't occur in your testing.
and a list still has completely other access characteristics than an array. in my experience, developers resort to plain arrays even if other containers might be faster simply because of allocation issues.

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!