Welcome to Ethan’s Air Garden. This is dedicated to creating a computer technology column that can be read during commutes, meals, or before bed, which is both accessible and in-depth.
At CppCon 2017, Carl Cook delivered a talk titled “When a Microsecond Is an Eternity: High Performance Trading Systems in C++”. This article records the key points of his presentation and expands on related knowledge.
Keywords: high performance C++ cache optimization assembly
During the presentation, Carl Cook proposed several practical techniques and optimization strategies aimed at achieving ultra-low latency. These techniques mainly focus on optimizing the execution efficiency of the hot path code, improving cache utilization, and avoiding unpredictable delays (Jitter).
According to the order of the presentation, the content is recorded as follows.
1. Hot Path Code Optimization
Hot Path refers to the most critical code in the system that has the highest latency requirements. Although it only accounts for 1% to 5% of the total code, it needs to execute at extremely high speeds, and its execution frequency is not high.
Minimizing branches and conditional checks:
By replacing complex error handling code (e.g., containing the handle_error function) with simple integer flag checks (checking whether the integer is zero or non-zero), the burden on the branch predictor can be reduced, alleviating pressure on the instruction cache.
The principle of Branch Prediction: For a code with branches, it guesses and selects a path and loads instructions into the pipeline. Pipeline execution is a crucial support for high performance in modern CPUs; not guessing will significantly reduce execution speed at branches. The branch predictor may use specialized hardware to record the context and path history at branches, allowing it to utilize historical information to improve the accuracy of its guesses. Therefore, simplifying the conditional check context at branches is very important.
In the hot path, branches are expensive. If all possible conditions can be determined at compile time (e.g., only buying or selling), template specialization should be used to completely eliminate branches, generating fully deterministic non-branching code. This essentially locks in the compiler’s optimization behavior.
In short, template specialization is separating branching code into independent non-branching code at compile time through function templates. At runtime, the branching code for decision-making has a clean context, making it easy to predict. Meanwhile, the independent non-branching code can fully utilize pipeline characteristics to improve performance.
Avoiding virtual functions:
If the complete set of all possible instantiated classes can be known at compile time, template-based configurations should be used instead of virtual functions.
Using templates allows for calling non-virtual, concrete types (e.g., instantiating the correct type using factory functions), which can generate more compact code, provide more opportunities for the optimizer, and alleviate pressure on the instruction cache.
How do virtual functions affect runtime performance? The call to a virtual function relies on vtable and vptr, requiring a table lookup to obtain the address of the target function, which is an indirect jump. Moreover, because the jump target is uncertain, instruction prefetch cannot be used to optimize performance.
In contrast, static polymorphism determines the function address at compile time, using direct jumps, which is faster. Additionally, the compiler can optimize code layout to store functions consecutively. This fully utilizes locality for prefetching.
Using Lambdas to enhance expressiveness while maintaining speed:
Lambda functions themselves may not provide direct acceleration, but they allow for the use of relatively advanced language features while still achieving extremely fast speeds.
For example, when sending messages, Lambdas can be fully inlined, and low-level operations (such as preparing or sending messages) can be optimized to the bare minimum (e.g., simply flipping a bit on the network card to trigger sending).
Controlling inline behavior:
The C++ inline keyword is primarily for the linker and does not enforce inlining.
Attributes from GCC or Clang (e.g., always_inline or noinline) should be used to enforce control over inlining.
Do not inline non-hot path code (such as logging) into the hot path, as this will pollute the instruction cache. Using noinline can convert this code into a function call, avoiding instruction cache pollution.
Creating stack frames, passing parameters, and instruction jumps during function calls consume CPU cycles.Inlining embeds the function body directly at the call site, avoiding these overheads, which is particularly effective for small functions that are called frequently.
Excessive inlining can lead to an increase in the size of the executable file (code bloat). This may trigger an increase in instruction cache miss frequency, which in turn can lead to higher memory access costs.
2. Data and Cache Optimization
Training hardware branch predictors and maintaining cache warmth (virtual orders):
Since the fast path is executed very rarely, the hardware (branch predictors, caches) is usually “cold”.
Solution: Simulate sending orders continuously through the system (virtual orders), but must stop before sending to the exchange.
By simulating sending orders at a frequency of 1,000 to 10,000 times per second, the instruction cache and data cache can be kept “warm”, and the hardware branch predictor can be trained to correctly predict the fast path. This method can bring a speedup of 5 microseconds.
Cache line optimization for data lookup (denormalization):
When reading data (e.g., instrument prices), the machine reads a complete 64-byte cache line.
Therefore, the associated data that is needed and changes infrequently in the hot path (e.g., multipliers of market data) should be placed directly into the object being read (e.g., tool objects). Although this may violate some software engineering principles, it can yield faster code because this data is “prefetched” for free.
Using cache-friendly custom hash tables:
The linked lists in the standard std::unordered_map may not be located in contiguous memory, leading to cache misses.
The speaker recommends using a cache-friendly hash table implementation, where the hash table itself stores metadata: precomputed hash values (8 bytes) and pointers to objects (8 bytes), with each pair occupying 16 bytes.
Since a cache line can accommodate four pairs of such metadata, reading one entry will typically prefetch the other three, helping to resolve conflicts. This custom implementation is twice as fast as std::unordered_map.
The core of CPU data prefetching is: to load “likely to be used data” from memory in advance, avoiding the CPU waiting for memory reads, thus improving data access efficiency. This can be achieved through hardware detection of data access patterns
or proactive preloading. It is suitable for continuous, predictable data access (such as array traversal), significantly reducing memory latency; if predictions fail (prefetching useless data), it will occupy cache space and bandwidth, potentially degrading performance.
3. Memory and System Management
Avoiding memory allocation and deallocation:
Memory allocation is slow, so object pools should be used to reuse and recycle objects.
Deleting or destructing objects can also be relatively expensive, as it involves a call to free.
Using multithreading cautiously:
If multithreading must be used, keep the amount of data shared with other threads in the hot path to an absolute minimum.
Consider not sharing data, but instead passing copies of data between producers and consumers through locked single-writer single-reader queues.
Utilizing dedicated cores and caches:
To maximize the availability of L3 cache and eliminate interference from other processes, all cores except one on a multi-core CPU can be turned off, allowing that core to exclusively use the cache.
Alternatively, processes that generate “noise” can be moved to different CPUs.
Avoiding system calls:
Any system call that involves calling kernel space (e.g., select or kernel space TCP) will severely impact latency. All interrupts should be removed from the core running the hot path, ensuring that only C++ code runs on that core.
Regarding exceptions:
As long as exceptions are not thrown, the cost of exceptions can be ignored (zero cost).
However, if exceptions are thrown, measurements indicate a cost of one to two microseconds, so they should absolutely not be used to control program flow.
Conclusion: The core of optimizing high-frequency trading systems lies in ensuring that the execution path of the code is as simple and deterministic as possible while maximizing CPU cache utilization, guided by precise measurements to direct optimization efforts.