HFT_PROJECT

Group Members: Rowan Hennessy (rh3322)

Discussion Questions:

Phase 1:

1. Explain the key differences between pointers and references in C++. When would you choose to use a pointer over a reference, and vice versa, in the context of implementing numerical algorithms?
   • Pointers can be null, references must refer to valid objects
   • Pointers can point to different objects, references are bound at initialization
   • Pointers support pointer arithmetic
   • Pointers store addresses, references alias
   • Pointers explicitly dereference via *ptr, references are directly accessed
2. How does the row-major and column-major storage order of matrices affect memory access patterns and cache locality during matrix-vector and matrix-matrix multiplication? Provide specific examples from your implementations and benchmarking results.
   • The row-major storage order is ~2-10x better, due to sequential memory access
   • The row-major cache miss ratio is about 1-5%, while column major is 20-50%
   • Row-major uses the full cache line, column-major wastes most of the line
3. Describe how CPU caches work (L1, L2, L3) and explain the concepts of temporal and spatial locality. How did you try to exploit these concepts in your optimizations?
   • L1 caches are the smallest, about 32-64 KB, with L2 being 256-1MB, and L3 being 8-32 MB.
   • L1 and L2 caches are per-core, while the L3 is shared across cores
   • Temporal Locality is the concept that recently accessed data is more likely to be accessed again than data accessed a longer time ago
   • Spatial Locality is the concept that memory "nearby" each other in the address space is likely to be accessed together
   • We exploit these in the row-major matrix format by accessing all of a row at once, which is stored near each other and therefore quickly accessed
4. What is memory alignment, and why is it important for performance? Did you observe a significant performance difference between aligned and unaligned memory in your experiments? Explain your findings.
   • Memory alignment is the idea that, when addressing something in C++, the address is always accessed in aligned form, i.e. at the beginning of the (for example) 8 bits it takes up total
   • It ensures that data starts at addresses that are multiples of the data size or cache line size
   • It allows faster access, and easier access from a human perspective
5. Discuss the role of compiler optimizations (like inlining) in achieving high performance. How did the optimization level affect the performance of your baseline and optimized implementations? What are the potential drawbacks of aggressive optimization?
   • There are -O1, ..., -O3 compiler flags, from least compiler optimization to the most
   • These sped up the performance from ~1.33x in -O1 to ~7x in -O3
   • The benefits are less cycles and overhead, while compiler optimization may lead to a higher binary size of the code
   • Optimized code can also be difficult to understand, since the compiler may make decisions that a human would not
6. Based on your profiling experience, what were the main performance bottlenecks in your initial implementations? How did your profiling results guide your optimization efforts?
   • The obvious performance bottlenecks were cache misses in the column-major oriented matrix operations
   • While profiling, the flat graph showed that the majority of the time was spent looping due to cache misses, so I changed the order of the loops to try and optimize
7. Reflect on the teamwork aspect of this assignment. How did dividing the initial implementation tasks and then collaborating on analysis and optimization work? What were the challenges and benefits of this approach?
   • NA, I worked alone.

Phase 3:

Build and Run Instructions:

cd Phase3
g++ -std=c++17 -Wall -Wextra -O2 -o trading_system main.cpp market_snapshot.cpp order_manager.cpp
./trading_system

Architecture

1. MarketSnapshot
   • Maintains real-time bid/ask price levels
   • Uses std::map with std::unique_ptr<PriceLeve> for automatic memory management
   • Removes price levels when quantity reaches 0
2. Ordermanager
   • Tracks placed orders with unique IDs
   • Manages order lifecycle
   • Uses std::unique_ptr<MyOrder> for memory managemeny
3. Feedparses
   • Parses simulated market feed from sample_feed.txt
   • Supports BID, ASK, and EXECUTION events
   • Header-only utility
4. Strategy (main.cpp)
   • Simple example trading logic, to allow integration with sample_feed.txt

Phase 4:

Build and Run Instructions:

Run

g++ -std=c++17 -O3 -I./include \
    src/main.cpp src/MarketData.cpp \
    -o build/hft_system

./build/hft_system

to see the different levels of testing the system allows.

With the modularity allowing a run-then-exit approach, we don't need to run and exit and change parameters and run again, rather we utilize std::iostream to allow the user to run multiple levels of tests with a single executed command.

Phase 5:

Run

g++ -std=c++17 -g main.cpp -o main 

./main 

python3 plotting.py

To see results:

Phase 6:

Building and running:

cd Phase6/Client;

g++ -std=c++17 main.cpp -o client