Wednesday 

Room 3 

13:40 - 14:40 

(UTC+02

Talk (60 min)

Template Meta-State Machines, Madness and Shannon.

Investigating the limits of extreme micro-optimisation in C++. After years indulging in the temptations of micro-optimisations, I shall present a definitive, micro-optimiser's guide to implementing template meta-state machines!

C++
Design

This was motivated by the cut-throat arena of High-Frequency Trading (HFT) and my own experiments. Extensive effort has been made to see just how far one can get using extensive template meta-programming to optimise the performance.

Following on from my previous talks regarding optimisations in C++, I undertook a multi-year investigation into extreme micro-optimisation of template meta-state machines. This Herculean effort eventually hit a "hard limit": due to Shannon's Information Theory... The meta-state machine described was a cut-down variant of the renown Boost.MetaStateMachine (mine lacks guards and other such flexibility). Each transition has been instantiated in a custom-container I termed "unordered_tuple", it provides extremely fast run-time access to each element. The input state has been encoded, using template meta-programming, in the enum tag-value to try to ensure that fastest possible instruction-encoding. The hashing of the state to identify the correct transition in the table uses a custom-designed, data-parallel algorithm that attempts to generate via brute-force an extremely fast, perfect (possibly minimal) hash: this might fail due to inadequate entropy. All this to generate a ... computed-`! (Forgive me Dijkstra...) So having erased all type information via the generated computed-GOTO, type-safety was restored via some further template meta-programming: the "constrained_override_type" that generates a specified override-set of functions and suitable abstract base-class. An analysis of the generated assembler that should demonstrate the efficacy of the techniques shall be given, followed by a performance comparison versus the much more simple "if-else" chain one may have used to implement the lookup of the transition in the meta state-machine.

Jason McGuiness

Jason has a long-standing love/hate affair with C++ and vastly prefers *nix-like O/S. With over 20 years experience, including programming prototype super-computers and automated program-verifiers, but mainly in finance, now focusing on low-latency and HFT software and architectures and the issues arising from them. I am also actively involved with the ISO C++ Standards Committee (UK Panel) and try to present regularly to maintain my skill-set.