requirements:

• compilation requires C++23 support (provided makefiles use g++-13)
• all tests of CppOrderBook have been performed on x86-64 hardware
• CppOrderBook uses components of the TMP_lib repo, specifically the param_pack::type_pack_t class template and the type checking logic contained in namespace type_pack_check
• the multithreaded implementation for performance measuring uses the SeqLockQueue repo

---

project description:

Limited scope project demonstrating reading an order-message from a socket, constructing a message object, possibly handing it off to another thread through a seqlock-queue and inserting it into an order book. The project employs compile time checks using both classic template metaprogramming and C++20 concepts. Cutting edge C++ features were incorporated if possible, such as monadic operations on std::optional (hence the project requiring C++23 for compilation) and interfacing with heap allocated memory via std::span. Being the de facto industry standard, the byte-layout of messages in the socket buffer complies with the FIX-protocol, more specifically little-endian FIX Simple-Binary-Encoding (SBE) and the FIX Simple-Open-Framing-Header. A precise XML specification of the message types used can be found in the misc folder.
For simplicity reasons (i.e. requiring only a single header file include), doctest was chosen as a unit testing framework.

Special emphasis was put on techniques enabling low-latency. Those include:

• avoiding branches (or, more realistically, keeping them short) even at the expense of some unnecessary computation in each run or a less favorable theoretical algorithmic complexity
• avoiding system calls outside the set-up and tear-down phases of the project, primarily by objects allocating all their required heap memory during construction and holding on to it until destruction and using std::atomic_flag as a lock instead of some flavor of mutex
• memory-aligning objects in accordance with a 64-byte cacheline
• ensuring fast multithreaded access to components that support concurrency, namely the seqlock-queue which enables wait-free enqueueing and lock-free dequeueing and the order book which supports lock-free reads via a seqlock as well (a lock is used required for manipulating book entries though)

major changes compared to previous version:

• seq-lock queue and much of the underlying logic for type checks have been transferred into stand-alone repos (SeqLockQueue and TMP_lib respectively)
• order types are no longer hard coded in the order-book class template, making adding new message types simpler
• every order type must therefore come with its own handling method that obeys some very specific interface requirements

repo structure:

• folder dependencies contains the source files from repos SeqLockQueue and TMP_lib
• src/testing contains, besides unit tests, demo implementations that record empirical latencies in a single- and multithreaded manner (with the option of pinning threads to cores via program arguments) and a single threaded implementation that can be used for profiling purposes
• unit tests employ the doctest framework, which requires including just a single header file which is included in src/tesing
• tests_and_demos/unittests and tests_and_demos/profiling contain makefiles to build unit tests and and the perfromance measuring implementations mentioned above, g++-13 is hard coded as the compiler and has been used validate and test the project
• misc contains an XML-specification of included message types in accordance with the FIX standard and a simple Python implementation to generate sample data for measuring and profiling

instructions on running measuring profiling executables:

• all three binaries require the path to a source of sample data as first argument (RandTestDataRW.csv generated via misc/generate_test_data.py is recommended)
• all three binaries will, before completing, print the volume at a random price in the order book to keep the compiler from optimizing away the order executions
• Record_latencies_single_threaded and Record_latencies_multithreaded accept one and two optional additional arguments respectively to specifiy the indices of the cores their are supposed to run on
• Record_latencies_multithreaded will generate a csv file with total time every single order took to be processed (in nanoseconds), the csv file generated by Record_latencies_single_threaded breaks those total latencies down further into how long it took to extract the message from the FIXSocketHandler object and generate an order and how long it to the OrderBook object to process the order

---

empirical latencies:

• generated on Intel Core i5-12450H
• generated running pinned to isolated performance cores with hyperthreading disabled
• findings:
  • generally low fluctuation, spikes in latency are rare and appear to occur randomly
• results for single-threaded run (in nanoseconds, n = 1000000 after excluding the initial 1000 runs):
  • mean: 111.42
  • standard deviation: 21.35
  • max: 1613
  • 0.99 quantile: 154
  • number of outcomes > 1 microsecond: 21
• results for multithreaded run (in nanoseconds, n = 1000000 after excluding the initial 1000 runs):
  • mean: 196.9
  • standard deviation: 56.0
  • max: 9553
  • 0.99 quantile: 307
  • number of outcomes > 1 microsecond: 166

---

unit-tests and profiling:

dedicated components:

the components listed below have the sole purpose of enabling unit testing and/or profiling

FIXMockSocket::FIXMockSocket

• mimics the behaviour of a user-space networking stack with a POSIX-socket like interface
• dispenses FIX messages as they might come in via network
• std::int32_t fixMockSocket::recv(void* dest, std::uint32_t len) represents a blocking call of recv on a POSIX socket, copying len bytes to dest
• FIXMockSocket is constructed from std::vector<std::tuple<std::uint8_t, std::int32_t, std::uint32_t>>
• each std::tuple represents a single FIX message with its entries representing the message's type, volume and price respectively

template <typename LineTuple> std::vector<LineTuple> file_to_tuples(const std::string& file_path, char delimiter = ',')

• reads lines from a file (comma seperated by default) to create a vector of tuples
• mock socket can then be constructed from the resulting vector

unit tests:

• build using CppOrderBook/tests_and_demos/unittests/makefile
• must be run from CppOrderBook/tests_and_demos/unittests directory as that's where the CSVs with test data located
• RandTestDataErratic.csv can be reproduced by running CppOrderBook/misc/generate_test_data.py

profiling:

• build using CppOrderBook/tests_and_demos/profiling/makefile
• builds executables profiling_single_threaded and profiling_multithreaded
• both executables read FIX messages from a mock socket, construct message objects and insert messages into an order book
• profiling_multithreaded hands message off to be inserted by a second thread via SeqLockQueue::seqLockQueue
• both executables require the path to a CSV file with test data as first command line argument
• to achieve CPU-affinity, give index of the core (or indices of two cores for profiling_multithreaded) you wish the executable to run on as additonal command line arguments
• both executables print out the volume contained in the order book at a random index to prevent the compiler from optimizing away the logic
• both executables generate a CSV containing the latency (time between starting read from socket and completing processing by order book) for every single message that was processed

---

components:

OrderBookBucket::OrderBookBucket:

template <std::uint32_t alignment, typename EntryType_>
requires std::signed_integral<EntryType_>
struct alignas(alignment) OrderBookBucket

template parameters:

• alignment: determines the aligment of a single bucket in the order-book and enables a cache optimal outline of the entire order-book memory
• EntryType_: type of the integer that holds the volume of liquidity in a bucket. Needs to be a signed integer as a negative value signifies demand liquidity and a positive value signifies demand

description:

• class template for a type that holds the liquidity at a specific price in an order book includding functionality to add and consume liquidity

interfaces:

• void add_liquidity(const EntryType): adds to the liquidity in the bucket
• EntryType consume_liquidity(const EntryType fill_volume): withdraws liquidity from the bucket and, given there is a liquidity match, reduces the absolute value of liquidity. Returns the liquidity withdrawn

MsgTypeChecks:

• defines checks to ensure that any new message type provides all interfaces and functionality necessary to be constructed by FIXSocketHandler and to be handled within OrderBook
• uses type_pack_check::monoid_check_t from the TMP_lib repo to conduct checks

specific checks:

template <typename FixMsgClass, typename BucketType, std::uint32_t book_length>
concept FixMsgHandlingInterface

• message type needs to provide a member function template that with the book's bucket type and book length as template parameters
• has to accept an order object, the book's base price, a std::span to access the order book's memory and a std::span of four std::optional<std::uint32_t> to access the book's stats as function arguments
• has to return a std::tuple containing the response returned when the order is processed

template <typename FixMsgClass>
concept FixMsgClassGeneral

• necessary for FIXSocketHandler to be able to construct instances of the message type class
• ensures that the following constexpr std::uint32_t members are present: msg_length, header_length, length_offset, length_offset, delimiter_value and volume_offset
• ensures that an instance of the class can be constructed from a std::span of std::uint8_t

struct MsgConsistencyCheck

• template metafunction that ensures consistency of constexpr members across all message types
• the follwing members must be equal: header_length, length_offset, length_offset, delimiter_value and volume_offset
• additionally msg_length must not be equal for any two message types as it is the only message type identifier withing the Single-Open-Framing-Header of the FIX-protocol

template <typename MsgClassPack>
requires param_pack::type_pack_convertible_v<MsgClassPack>
constexpr inline std::uint32_t determine_max_msg_len

• variable template to determine the length of the longest message type
• necessary for a FIXSocketHandler type to determine the required size of its buffer at compile time

template <typename MsgClassPack>
requires param_pack::type_pack_convertible_v<MsgClassPack>
constexpr inline std::uint32_t determine_min_msg_len

• variable template to determine the length of the shortest message type
• required by FIXSocketHandler types

template<typename MsgClassPack>
requires param_pack::type_pack_convertible_v<MsgClassPack>
constexpr inline bool AlternativesDefaultConstructible

• variable template that ensures all message types can be default-constructed
• necessary because OrderBook constructs dummy order objects to avoid braches when handling an order

FIXMsgClasses:

• defines different types of FIX messages
• need to comply with all the requirements outlined in MsgTypeChecks
• the logic for processing a message in the order book is contained solely within the message type's handle_order method to provide maximum modularity and making it easy to add a new message type
• types of messages currently contained in namespace FIXMsgClasses:
  • AddLimitOrder: adds bid or ask liquidity to the order book at a specific price
  • WithdrawLimitOrder: withdraws bid or ask liquidity at a specific price from the order book that has previously been entered
  • MarketOrder: buys or sells some amout of stock without specifying a transaction price, thereby consuming liquidity previously present in the order book
• class template OrderBookHelpers (with the type of the order book bucket and the length of the book as template parameters) encapsulates some functionality that is used across multiple order type handling methods

FIXSocketHandler::FIXSocketHandler:

template <typename MsgClassPack, typename SocketType_>
struct FIXSocketHandler

template parameters:

• MsgClassPack: collection of supported message class types. Needs to either specialize class template param_pack::type_pack_t from repo TMP_lib or of a type that can be used to generate such a specialization
• SocketType_: class of socket that messages will be read from, needs to satisfy concept Auxil::ReadableAsSocket (such as a specialization of std::variant or std::tuple)

description:

• constructs FIX message objects from bytes read from the buffer of an object of a type providing a socket like interface
• reads FIX messages in little-endian Simple Binary Encoding(SBE) and the Simple Open Framing Header(SOFH)
• holds pointer to a socket-type object

interfaces:

• MsgClassVariant: member type, specialization of std::variant with all the types contained in MsgClassPack
• std::optional<MsgClassVariant> read_next_message(): returns a std::optional type including the a message object within a variant when a message of a type contained in MSGClassVar is read an validated via checksum or an empty std::optional if message with a valid header of a type not included in MsgClassPack or a message is invalidated via checksum

limitations:

• not able to correctly handle an incoming message with valid header and checksum if the message is shorter than the shortest message contained in MsgClassPack

Guards::AtomicFlagGuard:

description:

• roughly analogous to std::lock_guard for std::atomic_flag instead of mutex
• holds pointer to std::atomic_flag given as argument to constructor (can be nullptr)
• has to be locked and can be unlocked by calls to member instead construction and destruction
• supports moving but not copying

interfaces:

• bool lock(): returns false if pointer to flag is nullptr or flag is already set by object, sets flag and returns true otherwise, will block/spin until flag is released by other thread
• bool unlock(): clears flag and returns true, returns false if pointer to flag is nullptr or flag wasn't set in the first place
• void rebind(std::atomic_flag* otherflag_ptr): calls unlock() and sets pointer to otherflag_ptr

OrderBook::OrderBook:

template <typename MsgClassPack, typename EntryType_, std::uint32_t book_length_, bool exclusive_cacheline_>
struct OrderBook

template parameters:

• MsgClassPack: collection of supported message class types. Needs to either specialize class template param_pack::type_pack_t from repo TMP_lib or of a type that can be used to generate such a specialization
• EntryType_: same as in orderBookBucket
• book_length_: number of price buckets contained in order book
• exclusive_cacheline_: if true, each bucket will be aligned to a full cacheline (64 bytes)

description:

• contains the bid/ask volume for some asset in a range of price buckets relative to some base price
• provides functionality for querying volume for specific price and adusting volume by processing order objects
• negative volume represents demand, positive volume represents supply
• price is represented by an unsigned integer and must therefore always be positive
• contained price range is determined by base price (argument of constructor) book length
• keeps track of best bid, lowest bid, best offer and highest offer at all times
• supports lock-free queries for volume, relies on std::atomic_flag as lock when processing orders
• all message types come with their own message handling methods, the order book class itself calls those methods when processing orders

invariants:

• represent conditions that need to hold to avoid a crossed book and maintain the integrity of stats kept
• if there is a best bid, there is a lowest bid and vice versa
• if there is a best offer, there is a highest offer and vice versa
• best offer > best bid, highest offer >= best offer, lowest bid <= best bid
• no positive volume below best offer, no negative volume above best bid
• no non-zero volume above highest offer or below lowest bid

interfaces:

• MsgClassVariant: member type, specialization of std::variant with all the types contained in MsgClassPack
• EntryType_ volume_at_price(std::uint32_t price): returns volume contained in order book at price specified by argument
• std::tuple<std::optional<std::uint32_t>, std::optional<std::uint32_t>>best_bid_ask(): returns tuple of two std::optionals containing the prices of best bid and best offer if book contains demand and supply respectively and empty std:optionals otherwise
• bool shift_book(std::int32_t shift_by): changes base price of book by shift_by and shifts all volume within memory. Not possible if shifting would turn base price negative or result in non-zero volume buckets falling out of bounds. Returns true if successful, false otherwise
• std::tuple<std::uint32_t, EntryType_, EntryType_, std::uint8_t> process_order(MsgClassVariant order): processes order contained in argument, returns tuple containing:
  • marginal executions price/ last price at which any volume contained in order was filled
  • filled volume: volume filled right when order was processed
  • order revenue: price * volume for any volume contained in order that was filled while processing
  • 0 if order price was within bounds, 1 if it wasn't (other three entries must be 0 in this case)
  • to avoid branches, dummy instances of all the message types other than the one contained in order are constructed and all handling methods are called
• std::uint64_t __invariants_check(int n_it): intended for debugging purposes, checks invariants layed out above aren't violated, prints an error message containing argument n_it (most likely an iteration index) for any violation and returns a sum of error codes of all violations