C and C++ Arrays on Stack and Heap

Simple table lists choices for different arrays in C and C++ regarding array length and allocation cost on storage. In this context, array means a linear sequential container of element objects of the same type that are next to its neighbors in memory. The array may or may not be resized. The colors are assigned based on the flexibility of array length, speed of allocation on storage, and extra benefits and pitfalls in features.

Array

Array Length

Storage (auto variable)

Notes

C/C++ array fixed at compile-time stack example: int a[10];
boost::array fixed at compile-time stack container-like support
C99 Variable Length Array fixed after created at run-time stack unspecified behavior on error
C++ Variable Length Array on stack with alloca() fixed after created at run-time stack See previous post. non-portable alloca().
std::vector with fixed_block_allocator<T,N> Dynamic at run-time, but no larger than N stack STL compliant
stlsoft::auto_buffer Dynamic at run-time stack if size within a static length; heap otherwise covered in Imperfect C++ (book)
boost::auto_buffer Dynamic at run-time stack if size within a static length; heap otherwise more versatile than  stlsoft::auto_buffer. Still in boost review process.
eastl::fixed_vector Dynamic at run-time stack if size within a static length; heap otherwise EASTL replaces STL for high performance game development mostly on memory allocation. Download
rde::fixed_vector Dynamic at run-time stack if size within a static length; heap otherwise RDESTL is similar to EASTL.
std::vector (plain) Dynamic at run-time heap explicit elements construction (slow)
TR2 dynarray fixed after created at run-time heap, but compiler may use stack for auto variable optimization in fact a std::vector but run-time size is fixed when vector’s variable length is unnecessary.
std::valarray Dynamic at run-time heap mostly for mathematic use; no iterator
C++0x std::array fixed at compile-time stack see boost::array

It is quite clear that when high performance is needed, auto_buffers and fixed_vectors are winners, because it provides a fast stack allocation/deallocation when array length is less than the static template parameter, and falls back to heap storage in the worst case.

In fact, the same problem exists on other containers (and string as a special container). EASTL and RDESTL provide fixed_xxxx containers and fixed_string primarily based on stack. STLSOFT has basic_simple_string and basic_static_string for strings.

Leveraging Allocator of STL Containers

Other than std::vector with fixed_block_allocator<T,N> and std::vector, all approaches above are exactly STL containers. Given all the benefits of STL, it would be great to have a STL compliant approach.

STL containers have an allocator template argument for customizing memory allocation for the container. So other than creating new array classes, it is interesting to use the STL container types by using a custom allocator class to get the stack memory for container, for example, for vector.

The C++ allocator for containers is still quite limited with a lot of restrictions (see Effective STL Item 10: Be aware of allocator conventions and restrictions, and Improving Performance with Custom Pool Allocators for STL). For example, an allocator should be able to deallocate memory allocated by another instance of the same allocator class; this is important to implement swap() and list::splice correctly. This would require all allocator types to not have instance data members, but have only class-static data or access global variables. This requirement would make allocator customization a real pain. One can imagine such an allocator is really very restricted.

Fortunately, one can make the operator == of the allocator class to return false when one has instance data in the class. Most STL implementation would know that free swapping is not available for containers with this allocator, and would copy elements one by one. Therefore, by signifying an always unequal allocator, one can get much freedom in designing an allocator.

Even though the standard does not explicitly require the container to have an allocator member variable, it implies so in Allocator requirements. Especially, C++0x enhanced the the allocator model; unlike C++98/03, C++0x explicitly allows one to use an allocator with state (scoped allocator). The container can use meta-programming to take out the allocator member completely if an allocator does not have any data and compact the container’s footprint. If the allocator has state, however, the container has to store it as a data member.

This basically means that it is possible to create upfront an allocator with a big size, for example a fixed length array of T as reserved for container elements. When an instance of the container with a data member of such an allocator type is created on stack, it has that reserved array on stack too.

C++ Programming: Stack Allocators for STL Containers is an example. The fixed_block_allocator<T,N> would house up to N elements. It simply uses max_size() to indicate that fixed length as its memory limit, and trying to size over that would result in std::length_error in container. Because the array member in the allocator is obviously non-static, the allocator uses a false-returning operator ==. Currently it works fine with Visual C++ 10.0 in Release build, but with Debug build the vector has run-time error in the default Visual C++ setting, probably because VC adds debugging bells and rings out-run the buffer.

I think it is possible to extend fixed_block_allocator to use heap as a fall back when more memory is required, such that it does not have the severe limitation of capacity N. This will bring it on par with the auto_buffers and fixed_vectors, but still remain STL compliant.

About these ads

3 Comments to “C and C++ Arrays on Stack and Heap”

  1. Good comparison of containers. I often wondered why the STL didn’t provide a container which allowed memory to be allocated on the stack. As you didn’t include it on your list, I don’t know if you are aware of std::dynarray which is a container proposed for C++ Technical Report 2. It’s size is fixed at run-time on construction and memory is allocated on the stack, if possible, and heap otherwise. Standard proposal is located here:
    http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2648.html

    This would fill an important gap in the STL containers I feel

  2. Can you please explain what is meant by “when array length is less than the static template parameter”? What is the “static template parameter”? Is that a compiler constant? Where does it come from?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: