Katkat
Back

Design Stack Evaluators and Low-Latency Memory Primitives

Jump TradingSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

This question tests your understanding of low-latency systems programming, focusing on thread-safe memory management, cache locality, and efficient expression parsing.

Part 1: RPN Evaluator with Macros

Design an evaluator for Reverse Polish Notation (RPN) that supports integer arithmetic (+, -, *, /) and a macro system. A macro allows users to define a new symbol (e.g., SQR x := x x *) that replaces the symbol with its definition during evaluation. Explain how you would store these macros to ensure O(1) or O(log N) lookup and how you would handle potential recursion in macros.

Part 2: Low-Latency SPSC Queue

Implement a Single-Producer Single-Consumer (SPSC) lock-free queue using a ring buffer. Your implementation must use C++11 memory order semantics. Define the enqueue and dequeue functions with appropriate barriers.

Requirements:

  • The queue must be fixed-size (power of 2).
  • Explain why memory_order_release is necessary for the producer and memory_order_acquire for the consumer.

Part 3: Cache Locality & Alignment

In a multi-threaded trading system, explain the concept of "false sharing" in the context of your SPSC queue. How would you modify your structure (using alignas or padding) to ensure the head and tail pointers reside on different cache lines?

Part 4: Memory Allocation

Describe how you would design a cross-thread pool allocator to avoid the overhead of malloc. Consider a scenario where one thread allocates objects of size T and another thread deallocates them. How do you prevent thread contention and fragmentation?

Hints

Hint 1

For the macro system, consider a hash map of token sequences and expand the string before tokenization or during the parsing stack process.

Hint 2

For the SPSC queue, ensure the producer only updates the 'tail' after writing the data, and the consumer only updates the 'head' after reading.

Hint 3

Use cache line size constants (typically 64 bytes) combined with compiler-specific directives to force alignment and avoid false sharing.

Follow-up questions

  • How does your SPSC queue handle the 'full' versus 'empty' state ambiguity, and what are the trade-offs of using an extra 'dummy' slot?
  • If your macro system allowed recursive calls, what memory safety risks would you introduce, and how would you cap the recursion depth?
  • In a high-frequency trading context, why is dynamic memory allocation considered a performance anti-pattern, and what is your strategy for pre-allocation?