Super Fast List

Inspired by HFT order book implementations, I wanted to create a basic version of a container in c++ that supports super fast operations for adding and removal to test the concepts used in those order books. This list supports an average of up 41 million ops/s, including FIFO ops + remove access/removal.

Performance

Google Benchmark

As seen, the fast list outperforms std::list on every benchmark by a non-trivial factor.
Randomed mixed operations (first test) is the probably most realistic test. Slowdown is probably due to a collapse in branch prediction support, simulating real hot path conditions.

However, fast list supports both random access and removal while std::list doesnt

List Design

It is a memory contiguous doubly linked linkedlist. List structs are 16 bytes each, which is cache friendly.
An array map is used, with indices as ids to prevent hash overhead:

• The $$ith$$ index of the array = $$ith$$ memory slot

Illustration of Fast List

Features

• Add to back O(1)
• Remove from front & back O(1)
• Access and remove at random O(1)

In theory: Could support adding to front O(1), Adding to random O(1)

Key Optimizations:

1. Memory Continguity. Preallocates enough buffer for up to 1 million nodes contiguously leveraging cache locality in cpu access.
2. Cache Friendliness. List node structs are designed to be 16 bytes, so each cache line fetches 4 structs
3. Memory Alignment. Aligned alloc is used to ensure the buffer is 64 byte aligned, perfect for cache fetch
4. Prefaulted Pages. Pages are prefaulted upon allocation, ensure even faster access time as we can leverage TLB.
5. Doubly Linked list. Allows O(1) insertion and delete
6. Node ID Array. Uses an array of booleans, each index points to an ith slot using only pointer math, no hashing
7. Free list. Dynamically append remove nodes to a free vector, allowing to memory reuse while keeping FIFO order.

Metric Analysis

Hardware - Apple M2 Pro, Sonoma 14.6.1, 16GB Ram

Randomized — Number of operations / s

Operation	std::list	fast_list	Speedup
Add	57.7M	451.4M	7.82x
Remove	20.3M	238.7M	11.76x
Consume	29.9M	279.7M	9.35x
Mixed	34.3M	41.8M	1.22x

std::list does not support O(1) random access removal — requires O(n) walk to find order by ID.
fast_list supports O(1) removal by order_id via orderMap[] direct lookup.

Randomized — Time / operation (fast_list)

Operation	N	Time	ns/op
Add	1000000	2.22 ms	2 ns
Remove (every other)	500000	2.09 ms	4 ns
Consume	500000	1.79 ms	4 ns
Mixed	1000000	23.92 ms	24 ns

Run It Yourself

Running benchmark.cpp
Clone the repo and navigate to root dir

make

This will compile benchmark.cpp along with fast_list.cpp, you can run ./benchmark to print out the results from the benchmakr.

Running google_benchmark.cpp
To run the google benchmark, you will need to compile it with std=c++17 and link the google benchmark libraries manually.