Home » C++ » The Embedded Template Library

The Embedded Template Library

By John Wellbelove in C++, Embedded Template Library, Frameworks on 20th November 2017.

Why did I start it?

I wrote the Embedded Template Library (ETL), and all the others I have written over the years, because I’m lazy.

Yes, lazy! But in a good way I believe. See here.

Don’t Re-invent The Wheel

I hate having to code yet another variation of the same thing in a slightly different way time and and time again.

Reinventing the wheel every time is daft for many reasons.

Code bloat

Multiple instances of slight variations of a theme results in an increase in code size due to no commonality of functionality.

Testing, more testing or no testing

Are all the variants tested to the same degree? Are some even tested at all?

Variable functionality

Not all the variants are going to have the same level of functionality, or the same API. Ad-hoc solutions are invariably only going to solve the little bit of the problem that was needed at the time.

No collective knowledge base

Without commonality every new variant has to be learned. The underlying principles may be understood (i.e. Linked list), but each implementation has to be understood separately, along with its particular caveats and foibles. Documentation is likely to be patchy.

Octopus code

The application is liable to have a close coupling with the solution. For example, I’ve often seen code using linked lists directly accessing the node pointers. Ad-hoc solutions are liable to have lazy (the bad kind) implementations.

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

All storage is allocated either at compile time or on the stack. The library should not use the heap at all.

No RTTI required

Lowers the overhead.

Very little use of virtual functions

I’m not one of those that thinks virtual functions are the root of all evil in embedded software. Sometimes they are extremely useful and the alternative would be clunky and awkward and sometimes just C++ virtuals in another form. At other times a slightly different technique can eliminate a lot of them with little pain. They should be used only when they are absolutely necessary for the required functionality.

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

A technique sometimes known as ‘hoisting’. There is a top level class that knows type and size. This inherits from a class that contains functionality that is only interested in the type. This may also inherit from a base class that is both type and size agnostic.

Templated compile time constants

Helper templates that calculate constants at compile time. Sometimes useful when included inside another template.
i.e. When an internal constant is Log2 of a non-type template parameter constant.

Templated design pattern base classes

I say, let the templated boiler plate code do the work.

Frameworks for message routing, finite state machines and task scheduling

When have you not needed something like this for any non-trivial application, especially for bare bones systems? Don’t reinvent the wheel every time.

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

See above.

8, 16, 32 & 64 bit CRC, checksums & hash functions

We’ve written them, so you don’t have to.

Variants (a type-safe union)

No more messing with unions and/or void*

Choice of asserts, exceptions, error handler or no checks on errors

How you repond to errors is up to you. The ETL does not dictate.

Many utilities for template support

Allowing you the ability to set types and constants according to the template parameters, allowing static asserts to perform concept checks.

Unit tested

So we can avoid accidently breaking anything.

Easy to read and documented source

But we all do this anyway don’t we?

Free email support

That’s what I would want, so that’s what you get.

Continuous integration testing

Every push is automatically unit tested, just in case we messed up and didn’t do our job properly (Perish the thought!)

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.

Tags: C++, Embedded, Templates

Recent Posts

Recent Comments

Archives

Categories

Meta