STL within embedded system with very limited memory

Question

I'm currently in the process of building an embedded system, using an ARM Cortex M3 processor, with 64 KB of SRAM. At the moment, I'm looking for a way to ensure deterministic performance with STL containers, which includes ensuring that I cannot end up running out of memory at run-time.

I'm primarily concerned with how STL containers perform dynamic memory allocation. Although I can utilize a custom allocator to have these structures get memory from a pool which I set aside, I would need to setup a separate pool for each structure in order to ensure one instance of a structure cannot take up another instance's space.

I'm working with other individuals on this project who do not want to be concerned with raw allocation of memory and would prefer to be able to utilize the "well known" data structures (stack, queue, deque, etc). Therefore, I'm currently considering building wrappers around C-arrays to provide these structures. This would enable static allocation of the memory required to support these containers and allow the other developers to know the size of the container they have instantiated prior to run time, based on the code-size information provided by the compiler. In my opinion, this guarantees that memory outage issues cannot occur at runtime, and simplifies system design considerably.

The other option would involve allocation of STL containers at system initialization. After the initialization period, no additional dynamic memory allocation could occur. However, to my knowledge, the standard C++ STL data structures do not support this -- it would require that containers such as a stack be capable of being pre-allocated (similar to a vector).

I would appreciate any comments regarding my proposal to build classes around standard C-arrays? In addition, is there a simpler way to allocate a static size STL container, such as a static size stack or queue, at compile time? (I know this is possible with vector, but the others I'm not sure)

Note: I've read through another question (Embedded C++ to use STL or not), but the author of this question didn't make clear how much memory they had (other then how they were using an ARM7 process) or appear to be considering a solution similar to mine.

Second Note: I'm aware that to some developers, 64 KB of SRAM may look like a lot of memory. In fact, I've done development on AVR processors with significantly less memory, so I understand this perspective. However, from my current (perhaps uninformed) view, 64 KB of memory isn't much when talking about STL containers.

Inviolable

At the end of the day, I went with EASTL. Was easy to use and worked well. – Inviolable

Answer 1

This question is sort of confused and weird. First, let's clear up some misconceptions.

You mention "stack, queue, deque" by name. Well, two of these are not containers. stack and queue are container adapters. See, they don't actually directly store the elements; they simply mediate the interface to them. stack ensures that you can only push, pop, and get the top element. queue ensures that you can only push-back, pop-front, and get the front element (thought it also lets you get the back element).

The container adapters actually take as one of their template parameters the actual container type to use. So you could use a stack with a std::list if you want. I wouldn't necessarily suggest it (depending on your use case), but you could.

The container adapters don't care about memory; it's the containers that they use that allocate memory.

If you're running in such a tightly memory limited system, you're not going to find the standard containers to be terribly friendly. Even if you use allocators to give them fixed-size memory buffers, the only thing those allocators can do to stop the actual container from allocating more memory is to throw an exception.

For example, if you have a vector that needs to work within 2KB of memory, if it has a size of 1KB, and tries to allocate 2.5KB more, the allocator cannot simply return 2KB. It can either return 2.5KB as requested or throw std::bad_alloc. Those are your only two options. There is no way for the allocator to tell the vector that it can get more memory than what it has, but not as much as it wants.

Similarly, the allocator is required to provide new memory, freshly allocated memory that can be copied into. It is not supposed to provide the same spot of memory only with more of it available. Doing so will likely cause problems in some implementations.

Allocators are intended to provide different regions of memory for access; they're not well designed for limiting the size of the container itself.

My suggesting is to track down a copy of EASTL. It's really designed for this sort of thing. The Github repo I linked you to has some bug fixes and so forth, but it's still mostly the same. It's not a bad bit of code. Their STL-like containers provide most of the interface, so they can be mostly drop-in replacements. But they provide special functionality to specifically control memory allocations.

Rationality

Thanks for the pointer to EASTL source - I didn't know that source had ever been released. Last time I looked into the EASTL (a long time ago), it looked like only the n2271 document was available (open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html). Hopefully I'll have some time to look at the source released so far. – Premonitory

This is perhaps another example of where cplusplus.com has hurt me, as I have learned to associated "STL Containers" with stack/queue/etc. from them (cplusplus.com/reference/stl). I'm aware of how a list could be used as a stack, etc (I've taken a data structures course where I've had to build these container adapters). I was aware of EASTL -- although there seems to be a bit of controversy regarding it in other answers (see the one I linked to in my original question). – Inviolable

stack, queue, dequeue are data structures in the generic sense, that STL has decided to implement them as adapters is merely an implementation detail. So I don't think there's anything particular wrong with how the OP formulated his question. Still very solid advice! – Jeuz

@Ylisar: First, deque is a container, not an adapter; it implements a specific memory model. Second, it's not an implementation detail that stack and queue are adapters. The fact that you can swap out different containers for them means that the memory model for them comes for which actual container you use, not the stack and queue classes themselves. So if you want fixed-size stacks, looking at the stack class itself is the wrong place to look. – Rationality

@BSchlinker: CPlusPlus.com specifically says that those are container adapters. It says quite clearly, "Container adaptors are not full container classes." – Rationality

@NicolBolas -- But they are listed under "STL Containers" on the left side. Over the years, I've used that little menu box to chose "queue", "stack", etc. and have always seen "STL Containers" above -- never anything about "STL Container Adapters". I'm likely at fault for not reading the container page to see the clarification -- but you can see how I would become confused. – Inviolable

@NicolBolas The other problem is that I've developed implementations of queues / stacks / etc. in (FPGA) hardware. My use of the word container is likely also the result of me using it when describing those implementations. – Inviolable

@MichaelBurr Note that the EASTL implementation (as released) does not include a deque, although there appears to be an attempt at an implementation here based on EASTL documentation: mpgh.net/forum/174-battlefield-3-bf3-hacks/… – Inviolable

@NicolBolas This may just be due to this being an old topic, but your link to "a copy of EASTL" points at an outdated fork. You can find the mainline (and actively developed) version at github.com/electronicarts/EASTL – Outcry

Answer 2

I know this is an old thread, but for anyone that's interested, I maintain an STL-like template library for embedded applications. No heap usage at all.

Embedded Template Library (MIT licence) https://www.etlcpp.com

Ribbing

Answer 3

Besides EASTL, you can also use static_vector from boost. It shares most of the API with std::vector and it can be used with container adapters (queue, stack). Instead of throwing std::bad_alloc it can call throw_bad_alloc(), so it can be used in an embedded environment without exceptions too.

Shashaban