1
2
3
4
TEMPLATE METAPROGRAMMING
A tribute to Andrei Alexandrescu and his book 'Modern C++ Design', his templated design pattern ideas and implemention in his 'Loki' template library
Template Metaprogramming
John Ince
When you Stretch the Compiler Great Things Happen!
We've always had an interest in software design patterns. Like all good programmers we've read and understood the great coding solutions in the GoF (Gang of Four) 'Design Patterns' book. Why keep reinventing new software solutions when a bag full of tried and trusted techniques solves a world of software design and implementation problems. Back in the 2009 we stumbled across a gem of a book from 'Modern C++ Design' by Andrei Alexandrescu who was building a template library, called Loki, containing template implementations of some design patterns, using the compiler to write code and a lot more too in the detail. It stimulated our interest. We like the idea of doing work at compile time. If the compiler can write some of our replicated classes on the fly then we don't need to, less code to maintain. Before reading 'Modern C++ Design' we've always used templates quite heavily in our C++ code since we love generic programming. We don't just love generic programming because it sounds cool, we love anything that saves us writing more lines of code and makes it easier for us to extend our software easily. So we thought it was well worth a read and it was! Today, Loki is one of the few libraries of code/template code that we trust in our source code base. So what's it all about?
So What's so Cool about 'Modern C++ Design'
We see 'C++' as having 4 distinct or rather interrelated technologies. Firstly the core 'C' language, that's quite brief, relatively easy to learn but quite difficult to master. Secondly the object orientated part, which makes the 'C++', which allows better structured code to be written through inheritance, encapsulation, derivation, polymorphism, interfaces and so on. Thirdly is the STL, the Standard Template Library which extends 'C' where it is somewhat lacking with higher level concepts such as collections, strings, containers, algorithms, functions, iterators and so on. And fourthly, related to the STL, is the raw templating, where 'Modern C++ Design' builds upon. Most programmers use the first three elements of the language extensively, and in our experience, use basic templating concepts from the forth category. But what if you push c++ templates much more. We could force the compiler to do much more work. Using templates we can simulate programming paradigms like iteration (through recursion) and conditionals (through partial template instantiation), in effect the compiler contains it's own programming environment. This is what the 'Loki' library exploits. Some of the advanced templating concepts in 'Modern C++ Design' workaround lack of C++ language features to manipulate variable 'types' in terms of collections, these aren't value collections like in runtime programming but simply collections of types at compile time, TypeLists. For example, {int, string, MyWidget} is a list of three types. Turns out at compile time we can add functionality to support our TypeLists just like a regular array of values things like IndexOf, Length, Add, Remove, etc. Remember the key element here is that these TypeLists are NOT designed to be instantiated BUT consumed by the compiler to aid writing code. An example here could be the Length generated by the compiler at compile time, using template recursion and and enum value, is used to initialise an array length used at runtime. The compiler expands templates and is in effect running compile time code. If this has made you think "Damn, I thought I could code..," then read the book. Variable length TypeLists are very useful. Imagine the code you don't need to write. Imagine the editor copy/paste/modify blocks of code that is essentially replicated just for a different type. When you combine compile time TypeLists and runtime virtual functions then you could potentially implement Design Pattern's 'Abstract Factory' in a generic way, without replication of code. Powerful and we both seen it and exploited it. But it's bigger than these lower level coding hacks.

'Modern C++ Design' is also a great attempt at plug and play code using policy based design. What's that mean? The idea is that you define your object's customisation in terms of small, useful elements of behaviour that are inherited via C++ multiple inheritance. If you want to change the behaviour or extend the behaviour then the generic core stays the same and you write or enhance a small component which affects the behaviour of the generic core. It matches what we do with generic coding so well we bought the book to support Andrei. If you're thinking 'Yuk' at multiple inheritance then remember it's the compiler that will be writing this code, via template metaprogramming. You don't need to like it since you never see it in your source code.

So we've TypeLists to iterate and the compiler writing C++ classes on the fly, that's classes with inheritance. What if we could traverse a TypeList, create a class hierarchy and pass in our own class containing virtual functions, member variables, etc? It exists in the 'Loki' library as a scatter hierarchy. If there are setter and getter functions to access the data and functions contained then bingo the compiler writes the generic code and we simply provide implementations of our runtime derived objects of our own class. Wow. Twiddled our buttons.

That's just the start of 'Modern C++ Design' but generic code helps us maintain our source code base much more effectively. Enhancing is easier. The software we write is more discrete and loosely coupled. It simply works. Our software improves over time.
Variable Argument Lists with Scatter Hierarchies
So all this talk about compile time coding, TypeLists and Scatter Hierarchies. Do we have a concrete example in our coding where we have benefited from compiler generated coding. Sure have. Lots in fact BUT one springs to mind. Variable argument lists implemented as a scatter hierarchy that is passed to a template function implementation for handling a specific application message type. Type safe, the compiler generates the parameter class hierarchy and coding is simplified to a couple of MACRO additions for a new message type. It simplifies the application programmers world via some hefty. low level macros and templating. Before we delve into this a little recap of our application message architecture follows. Then we will describe the actual benefits of this model of programming.
Application Messages, Abstract Factory, Variable Arguments and RTTI
A little background before we put some flesh on the bones.

Application Messages
Our live WebApps use an application messaging system to communicate between our browser hosted UX and our cloud hosted c++ web applications. Basically the browser is only a visual representation of data on the server. To talk between the JavaScript browser world and the c++ server world we use a core websockets implementation of our own which we've extended in functionality. So we've the two worlds and a two way connection between them. To bring our architecture alive we pass application messages between the browser and the server application and visa versa. These messages flow in binary or text, but mostly binary these days depending on the browser implementation. So, flowing from browser to server to browser we have application messages that need to be security validated and handled as fast as possible. These named messages carry variable parameters as a payload depending on message type. So that covers the basic anatomy of an application message.

Abstract Factory
Conceptually we like the idea of Abstract Factory, treating 'new' as an enemy and keeping concrete class names out of the source code. It plays to our generic programming beliefs. Our binary/text based inbound messages are converted to code by instantiating handler objects to deal with the message. Because our inbound messages are named and we've implemented our own RTTI system then we can instruct our abstract factory to create the handler object with an indirection lookup map and call a virtual Perform() function to perform the action. But what about the parameters?

Variable Parameters
As we've said previously different application messages have different payloads. It might be a single parameter, 10 mixed type parameters or blobs or anything. Using our Handler Object build in our abstract factory we need a method of passing variable arguments to the virtual Handle() function. There's quite a few ways to deal with this using OO techniques however we didn't want to write these tedious/erroneous little derivations of a base class cast. So it occurred to us why not use a Loki templating library 'scatter hierarchy' which uses the compiler to generate a class hierarchy containing our parameters. Our virtual Handle() function can then simply extract the strongly typed values using some more Loki magic. One templated, multiple inheritance, class hierarchy that we don't construct. The compiler builds the typelist versions of our parameter list. Genius.

RTTI
We've a full programmers blog on our home rolled RTTI system here. However this little piece of magic helps us create access to our class types at runtime and run the static CreateObject() function to create one of it's own objects, Factory Method. In association with abstract factory we've a great generic way to construct the handler objects from the payload of the application message via RTTI.
Scatter Hierarchies for Variable Arguments Lists
Scatter hierarchies are a brilliant concept created by the compiler using a powerful c++ templates and their ability to mimic running code at compile time. There's no other language we know that has such an amazing ability. There's a C++ template library called 'Loki' that supplements the 'Modern C++ Design' book. This is not sample code. This is an industrial strength template library that is partially documented in the book. So, having absorbed the concepts in this blog so far we can start to describe our implementation of variable argument lists to our message handlers. We're going to simplify our message handling architecture here by omitting the multi-threaded nature and the object caching. Simply put, we use a combination of runtime type information, abstract factory, factory method, RTTI dynamic object creation and a dedicated fast small object allocator (that's for another blog but from the Loki template library too). We want our message handling to be really fast hence the effort. To create any message we have a message HQ. To the enlightened you can see how it works from our list of techniques and design patterns above. We create and pass a specialised message handler object through a single generic creation point and call a virtual 'Process' function. We need a way to pass variable function arguments in a generic way. Hence we inherit the scatter hierarchy containing 'n' arguments and pass our derived variable argument object. Remember the compiler created these parameter classes for free from a simple macro declaration. Since they were created by the compiler at compile time they are stongly typed or early bound which mean with the help of some 'Loki' magic we can extract their values without even a cast. If we get the argument type wrong the compiler lets us know. Pretty safe eh! Sure beats casting down from a base class to a specific class at runtime and letting the error happen there. When we need a new message it's a simple header declaration and the specialised derived message handler class to write and we're done. None of the generic handler code changes, it just works.
A Performance Theme
You may have picked up an underlying theme in this blog. Coding optimisation (both writing and running), compile time generation equal fast message processing, which is our aim. When we were writing and optimising our Message HQ we were also carefully profiling our code. Remember with our Cash Clamber gaming project we were running head to head global gaming across the planet. We've literally processed billions of application messages over the years. Imagine the speed of processing messages to keep a head to head game responsive over the Internet. So every small optimisation mattered hence the profile. When we started our message optimisation we could clock in Milliseconds (1/1000s), from receiving the application message to the point of processing the application message. In the end after we added our caching, small object allocate, compile time code generation we need to profile in Microseconds (1/1000000s) millionths of a second. Our cached messages passed through Message HQ in under 7 Microseconds, a freshly instantiated message took a little under 42 Microseconds. All this message technology is at the core of our mission critical business software framework. Tried and tested 365/24/7 since 2012. Need quality software engineers on your project?
Comments
PROJECT PEACH
Doing it differently since 2012. We're simply 10 years ahead. Our software is designed, coded, maintained, supported & hosted in the United Kingdom.
READING
Blogs
Newfeed
PORTFOLIO
DBD International
The Hawthorn Gallery
ScriptTrack
Knot 2b Missed
Overview
Monero Mine
COMPANY
Home
About Us
Contact Us
Pricing
Pay Us
Copyright 2018 Project Peach