Cache-Friendly Search Trees; or, In Which Everything Beats std::set
While a lot of work in theoretical computer science has gone into optimizing the runtime and space usage of data structures, such work very often neglects a very important component of modern computers: the cache. In doing so, very often, data structures are developed that achieve theoretically-good runtimes but are slow in practice due to a large number of cache misses. In 1999, Frigo et al. introduced the notion of a cache-oblivious algorithm: an algorithm that uses the cache to its advantage, regardless of the size or structure of said cache. Since then, various authors have designed cache-oblivious algorithms and data structures for problems from matrix multiplication to array sorting. We focus in this work on cache-oblivious search trees; i.e. implementing an ordered dictionary in a cache-friendly manner. We will start by presenting an overview of cache-oblivious data structures, especially cache-oblivious search trees. We then give practical results using these cache-oblivious structures on modern-day machinery, comparing them to the standard std::set and other cache-friendly dictionaries such as B-trees.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
FastBDT: A speed-optimized and cache-friendly implementation of stochastic gradient-boosted decision trees for multivariate classification
Stochastic gradient-boosted decision trees are widely employed for multivariate classification and regression tasks. This paper presents a speed-optimized and cache-friendly implementation for multivariate classification…
ClassificationGeneral ClassificationGet More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference
Many computational factors limit broader deployment of large language models. In this paper, we focus on a memory bottleneck imposed by the key-value (KV) cache, a computational shortcut that requires storing previous KV…
KVTuner: Sensitivity-Aware Layer-wise Mixed Precision KV Cache Quantization for Efficient and Nearly Lossless LLM Inference
KV cache quantization can improve Large Language Models (LLMs) inference throughput and latency in long contexts and large batch-size scenarios while preserving LLMs effectiveness. However, current methods have three uns…
Mathematical ReasoningQuantizationSensitivityPrefixing Attention Sinks can Mitigate Activation Outliers for Large Language Model Quantization
Despite recent advances in LLM quantization, activation quantization remains to be challenging due to the activation outliers. Conventional remedies, e.g., mixing precisions for different channels, introduce extra overhe…
Language ModelingLanguage ModellingLarge Language ModelQuantizationError Certificates for KV-Cache Eviction via Randomized Design
Deterministic KV-cache eviction keeps the top-$k$ tokens under an importance score and deletes the rest. We prove that this design cannot know what it destroyed: evicted values can be altered so that everything the servi…