Order book

Overview

price level = (price, sum of quantities from all orders of the price)

need to maintain the 2 lists:

• bid price level: people buying → need to prioritize high price
• ask price level: people selling → prioritize low price
• there are roughly 100 price levels in each side

operations:

• add_order(uint64_t order_id, side, price, qty)
• modify_order(order_id, new_qty)
• delete_order(order_id)

C++ lessons

• in most cases you don’t want node containers (e.g. std::map)

  • due to excessive memory allocation…

• understand your problem by looking at the data…

  • Optiver: when building the order book using flat map, initial idea is to maintain a sorted vector, putting the most prioritized price level at front (index 0)
    • upon observation, they saw the best prices vary a lot! → putting at index 0 causes a lot of reshuffling!
    • better: reverse vector: put the most prioritized prices at back → less reshuffling!

• specialized algos are key to perf

  • should not run perf command on the whole binary due to long init steps (negligible!)
    • within the program fork a child process at a good point and run perf on the parent!
  • first perf measurements should not be too specific:
    • run perf stat -I 10000 -M Frontend_Bound,Backend_Bound,Bad_Speculation,Retiring -p [pid]
      • this gathers perf counter stat…????
    • Optiver: got 25% bad spec!
      • then run perf record -g -p [pid]
        • this is sampling profiler…
      • found that 30% time is spent on 2 jump instructions in binary search → use branchless binary search instead!
    • can also use hardware countesr with libpapi…

• simplicity is the ultimate sophistication

  • linear search is faster (on average) than binary search, as measured!

  

• mechanical sympathy: algo needs to work in harmony with hardware

  • avoid i-cache misses!
    • use likely/unlikely attribute
    • sometimes inlining is bad!
      • for example, if a condition is likely to the false, then its nested block code should be kept far away from the common execution → make a separate function/lambda/IIFE!
    • careful with lambda and functor…
      • std::function uses type erasure → lose type info → generated code might not be optimal!

Network lessons

• order book needs to send/recv data!