Why did I start it?
Don’t Re-invent The Wheel
Code bloat
Testing, more testing or no testing
Variable functionality
No collective knowledge base
Octopus code
The Beginnings
I’ve been working with software that has had deterministic requirements for most of my programming career. Some of the latest ones involved image processing and feature extraction from objects passing a camera on a conveyor. The objects travelled fast and the gaps between them were small. For example, I once designed software for mail sorting machines where mail items could be travelling of speeds up to 4 metres per second with gaps of around 40mm. Finishing the processing on time was paramount, as a late result would cause the mail item to end up in the ‘hand sort’ bin. For a run of 30,000 mail items you don’t really want that sort of thing happening very often! As we were writing the application in C++ the STL was a very useful library to draw from, but one part of it has issues when used in conjunction with real-time applications.
The containers.
Virtually all of the containers in the STL, by default, get storage from the heap. This is a bit of a no-no for real-time software as the allocation and release of memory from the default heap is somewhat non-deterministic. There are a couple of tricks that can be done to try to alleviate the issues, such as reserving the size of vectors upfront, but it can only get you so far.
There are a few ways in which the programmer can try to get around them.
Create your own replacement for malloc/new
By writing a super optimised global malloc/new replacement you may be able to get the worst case times down to something acceptable for your application. You may have to address issues raised by multiple threads accessing the memory allocator concurrently. But what happens at run-time if the heap becomes too fragmented or you run out of heap space? In my experience it will crash during the demo in front of the customer.
Create your own STL allocator
One solution is to create an allocator similar to the malloc/new replacement, along with its threading, fragmentation and free space issues.
Another is to allow the allocator to contain its own fixed sized storage. This is a solution I used successfully for a while, but there turned out to be issues when porting between compilers, even versions of the same compiler. In the end I abandoned this idea.
Create a new set of STL like containers
Although a lot more work than custom STL allocators, creating a set of custom containers, specifically optimised for operating on internally declared contiguous blocks of memory, can bring great performance advantages. It also has the advantage of being more amenable to static analysis; All of the memory that may be used in a container is declared up front. This is very handy for allowing the application fail on the developer’s desk at compile time, instead in front of the customer at run-time.
Before I started to write the ETL I had built up a collection of ideas, sample code and early versions of containers, but they were not organised in any sort of library. Whenever I looked for the sort of library that met my specifications I could never find anything that really matched. All of the ones that I found were either limited in scope, or would drop back to using the heap when the initial reserved capacity was exceeded. I decided that the best course was to gather together all of my ideas and experiments and build them into the sort of library that I would want to find myself. I assumed that there were others out there that were also searching for the same sort of thing.
At the time, the chance of finding an embedded compiler that supported C++11 or above was fairly remote. I once talked to Keil back in 2014 about C++11 support and at the time the answer was basically “don’t hold your breath”. So I decided that the library must be compatible with C++03. As there were some very useful additions in C++11 I also decided to reverse engineer as many as were practical.
Requirements
MIT licence
Have you ever come across what looks like the perfect library, only to find it’s GPL and therefore unusable in your company? I want anyone to be able to use it, how they like.
Just don’t say you wrote it (unless you did).
Cross platform
I want it to work on all targets and platforms.
C++03 compatibilty
As I said before, C++11 and above was not always an option for embedded compilers back then. For many it still isn’t.
No dynamic memory allocation
No RTTI required
Lowers the overhead.
Very little use of virtual functions
A set of fixed capacity containers
A fixed capacity version of all of the standard containers, plus a few useful extra ones. As the storage for the container types is allocated as a contiguous block, they are extremely cache friendly.
Reduced container code size through use of base classes dependant on type only
Templated compile time constants
i.e. When an internal constant is Log2 of a non-type template parameter constant.
Templated design pattern base classes
Frameworks for message routing, finite state machines and task scheduling
Reverse engineered C++ 0x11 features (type traits, algorithms, containers etc.)
There’s some useful stuff in the later releases of the STL.
Type-safe smart enumerations
A way of reducing many hard to find bugs where a constant from one enum is used where another was expected.
Type-safe typedefs + constants
8, 16, 32 & 64 bit CRC, checksums & hash functions
Variants (a type-safe union)
Choice of asserts, exceptions, error handler or no checks on errors
Many utilities for template support
Unit tested
Easy to read and documented source
Free email support
That’s what I would want, so that’s what you get.
Continuous integration testing
Conclusion
The Embedded Template Library has been available on git for several years now and I’ve had great feedback from users and potential users from around the globe.
The ETL has been improved immeasurably by their input and I can’t thank them enough, especially Ryan Lindeman who did sterling work creating the map and set containers.
The ETL is at a good point at the moment, so I’m taking a little time off from adding any major new features (and I have several ideas in the pipeline) while I work on this blog and try to make a start at writing an ebook. I’ve not decided on a title as yet, but I intend it to be a sort of cook-book of C++ template techniques, especially tailored towards embedded and real-time platforms. A lot of the information in it will draw from the work in the ETL.
[…] Introducing The Embedded Template Library […]