The C++ Standard Template Library (STL) contains many useful template classes, it is the staple diet of any C++ developer and can save some development time in more complex Arduino sketches. When searching for a suitable library to use with the various AVR MCU's as used on the Arduino range of development boards, I found the following:
-
StandardCplusplus Standard C++ for Arduino (port of uClibc++)
-
ArduinoSTL An STL and iostream implementation based on uClibc++
-
avr-stl This one is based on the HP / SGI STL
Memory Usage
I wanted to use a "std::vector" to provide a dynamically sized array in some code I was writing, so I started with the "StandardCplusplus" library but quickly found that was heavy on SRAM and when you only have 2048 Bytes to play with, every Byte matters.
The first issue that I found was that unless the "reserve()" method was used to pre-allocate heap storage for the array, severe heap fragmentation starts to occur as you add more elements using the "push_back()" method.
vector<int16_t> *pulseTrain;
pulseTrain = new vector<int16_t>;
pulseTrain->reserve(size); //this is essential to avoid heap fragmentation
pulseTrain->push_back(number);
......
delete pulseTrain;Analysis
To reduce the number of realloc's that std:vector needs to perform as elements are added, it allocates memory ahead of time in much bigger blocks than is required. During the course of being filled using push_back(), I noticed big jumps in the heap size at various intervals as more elements were added, each jump in heap size also left a large hole in the heap. The hole in the heap was caused by the realloc operation performed by std::vector to claim additional heap space for the extra elements. The allocate-ahead strategy of std:vector appeared to be based on an offset plus a multiple of the current capacity of the vector, this is not sustainable when you only have 2K of SRAM!
I expected the realloc operation to just extend the heap as nothing else was being added to the end of the heap by my code during the course of the loop which added the elements. For some reason realloc was allocating a new segment of free heap space and moving the data, leaving behind a hole. This would be expected if there were other data on the heap after the end of the last heap location used by the vector, as that's the defined behaviour of realloc in those circumstances.
During testing, each time the vector performed a realloc, another hole was left behind, eventually the heap became so fragmented that there was more free space within the heap than it's own size. The eventual conclusion when adding enough elements was a crash due to a heap-stack collision. Due to the fragmentation resulting in many times more heap usage than is actually required to store the elements, the crash occurs much earlier than expected. The only way to solve this is to use the reserve() method to pre-allocate the required heap storage and prevent the realloc operations form occurring. Having to use reserve was not what I intended, I could have just used a simple fixed size C array instead. I tried using std:deque instead of std:vector as it does not require contiguous heap storage to store its elements, but the behaviour was much the same.
For reference, here is a description and representation of the AVR Libc memory model
Conclusion
Out of the libraries that I tested, the best results were obtained with Andy Brown's avr-stl library which is based on the HP / SGI STL implementation from a long time ago, it is also configurable, read his blog post about it for details. I still needed to use reserve() on the std:vector, but the results without using it were less severe when using the more suitable allocate-ahead settings in the avr_config.h file.
Keeping an eye on memory usage and heap fragmentation is very important when using the STL on MCU's with limited RAM. I created my own memory information library based on various example's on the Arduino site and customised for my requirements when testing and debugging.