deprecated in favor of CppOrderBook2

requirements:

• project has been compiled using g++12.1.0 and tested on Ubuntu 22.04.2 LTS
• compilation requires C++23 support
• CppOrderBook is intended to run on a x86_64 platform

---

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

---

performance:

cachegring:

• the result of a cachegrind run can be found in the misc directory
• results indicate negligible rates of cache misses and branch mispredictions with the possible exception of indirection braches

empirical latencies:

• generated on Intel Core i5-1135G7
• generated running on both one and two threads and dedicated pysical cores (see section on profiling for more details)
• findings:
  • regularly recurring spikes in latency by 1 or 2 orders of magnitude for unknown reasons
  • when using the seq-lock queue, spikes seem to occur at an interval of roughly 2mb
  • this quantity does not appear to coincide with the size of any cache level (or TLB with 4096kb memory pages)
  • context switches seem an unlikely explanation as test runs were assigned isolated physical cores
• results for single-threaded run (in nanoseconds, n = 1000000):
  • mean: 81.4
  • standard deviation: 20.4
  • max: 3684
  • 0.99 quantile: 126
  • number of outcomes > 1 microsecond: 26
• results for multithreaded run (in nanoseconds, n = 1000000):
  • mean: 182.1
  • standard deviation: 65.4
  • max: 12125
  • 0.99 quantile: 340
  • number of outcomes > 1 microsecond: 218

---

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> fileToTuples(const std::string& filePath, 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 Queue::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 cotaining the latency (time between starting read from socket and completing processing by order book) for every single message that was processed
• results of cachegring run can be found in misc directory

---

components:

FIXSocketHandler::fixSocketHandler:

template <typename msgClassVariant_, typename socketType_> struct fixSocketHandler

template parameters:

• msgClassVariant_: std::variant of supported message type classes, subject to compile time checks regarding constructors and static members variables
• socketType_: class of socket that messages will be read from, needs to satisfy concept Auxil::readableAsSocket

description:

• constructs FIX message objects from bytes read out 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:

• std::optional<MsgClassVar> readNextMessage(): returns an optional 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 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 msgClassVar_

FIXmsgClasses:

description:

• three classes representint different types of orders/messages for the order book:
  • adding liquidity
  • withdrawing liquidity added previously
  • filling a market order
• all classes contain static data specifying the byte layout of incoming messages to be used by the socketHandler class
• all classes can be constructed from a std::span of 8-bit integers(for use by socketHandler), default constructed without arguments or constructed from arguments representing their respective non-static members (volume and possibly price)

AtomicGuards::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

OrderBookBucket:orderBookBucket:

template <typename EntryType, std::uint32_t alignment> struct alignas(alignment) orderBookBucket

template parameters:

• EntryType: represents volume in bucket, must be signed integral
• aligment: alignment of bucket in order book, use 0 for default alignment

description:

• encapsulates volume in for single price point in an order book as well as the logic to change and query volume
• negative volume represents supply, positive volume represents demand

interfaces:

• EntryType consumeLiquidity(EntryType fillVolume): removes liquidity of an amount specified by fillVolume and returns the amount of liquidity removed. Always reduces the absolute value of volume contained in bucket. Returns 0 if volume contained does not match the sign of fillVolume
• void addLiquidity(EntryType addVolume): simply adds addVolume to volume already contained in bucket
• EntryType getVolume(): returns volume currently contained in bucket

OrderBook::orderBook:

template <typename msgClassVariant_, typename entryType_, std::uint32_t bookLength_, bool exclusiveCacheline_, size_t newLimitOrderIndex_, size_t withdrawLimitOrderIndex_, size_t marketOrderIndex_> struct orderBook

template parameters:

• msgClassVariant_: variant containing supported message classes (same as in socketHandler class template)
• entryType_: same as in orderBookBucket
• bookLength_: number of price buckets contained in order book
• exclusiveCacheline_: if true, each bucket will be aligned to a full cacheline (64 bytes)
• newLimitOrderIndex_, withdrawLimitOrderIndex_, marketOrderIndex_: indices of respective message class in msgClassVariant_

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
• supports adding volume for specific price, withdrawing/cancelling volume for specific price and filling market orders using volume contained in book
• 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

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:

• entryType volumeAtPrice(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>>bestBidAsk(): 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 shiftBook(std::int32_t shiftBy): changes base price of book by shiftBy 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> processOrder(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)
• std::uint64_t __invariantsCheck(int nIt): intended for debugging purposes, checks invariants layed out above aren't violated, prints an error message containing argument nIt (most likely an iteration index) for any violation and returns a sum of error codes of all violations