# glass: ordered set data structure for client-side order books

**Authors:** Viktor Krapivensky  
**arXiv:** [2506.13991](https://arxiv.org/abs/2506.13991)  
**Date:** 2025-06-16  
**Summary page:** https://www.summarizepaper.com/en/paper/2506.13991v1/

## Key points

- The "ordered set" abstract data type in computer science includes operations such as "insert", "erase", "find", "min", "max", "next" and "prev"
- Traditional implementations of the ordered set use red-black trees, $B$-trees, or $B^+$-trees
- A novel approach has been introduced with an ordered set based on a trie specifically designed for integer keys and optimized for market data applications
- Features of the trie-based ordered set include leveraging a cached path for rapid truncation during erase operations, utilizing a hash table for O(1) time complexity key lookup up to a pre-leaf node, and hardware-accelerated operations using BMI2 instruction set extension on x86-64
- Order book-specific functionalities like the preemption principle and tree restructure operation are incorporated to prevent excessive memory consumption
- Performance benchmarks show significant speedups compared to C++'s standard std::map container across various operations: 6x-20x improvement on modifying operations, 30x faster lookup operations, 9x-15x enhancement on real market data scenarios, and 2x-3x boost in iteration speed

## Summary

, , , , 

In the realm of computer science, the "ordered set" abstract data type is a fundamental concept with operations such as "insert", "erase", "find", "min", "max", "next" and "prev". Traditionally, this data structure is implemented using red-black trees, $B$-trees, or $B^+$-trees. However, a novel approach has been introduced in the form of an ordered set based on a trie. This implementation specifically caters to integer keys and is finely tuned for market data applications, focusing on what is known as sequential locality. Several innovative features distinguish this trie-based ordered set from traditional implementations. Firstly, it leverages a cached path to exploit sequential locality and enables rapid truncation during erase operations. Additionally, a hash table (or cache table) guarantees O(1) time complexity for key lookup operations up to a pre-leaf node. Furthermore, hardware-accelerated operations utilizing the BMI2 instruction set extension on x86-64 enhance performance in finding next/previous set bits. Moreover, this ordered set incorporates order book-specific functionalities such as the preemption principle and tree restructure operation to prevent excessive memory consumption. The performance benchmarks showcase significant speedups compared to C++'s standard std::map container across various operations – 6x-20x improvement on modifying operations, 30x faster lookup operations, 9x-15x enhancement on real market data scenarios, and a more modest 2x-3x boost in iteration speed. The detailed analysis presented in this paper delves into the intricacies of the trie-based ordered set implementation and highlights its efficiency in handling market data workloads. By combining cutting-edge techniques with tailored optimizations for specific use cases, this innovative approach sets a new benchmark for performance in managing ordered sets within computer science applications.