Array layouts for comparison-based searching

DOI10.1145/3053370zbMATH Open1414.68021arXiv1509.05053OpenAlexW2220328383WikidataQ130961938 ScholiaQ130961938MaRDI QIDQ4577950FDOQ4577950

Authors: Paul-Virak Khuong, Pat Morin 

Publication date: 6 August 2018

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Abstract: We attempt to determine the best order and search algorithm to store $n$ comparable data items in an array, $A$, of length $n$ so that we can, for any query value, $x$, quickly find the smallest value in $A$ that is greater than or equal to $x$. In particular, we consider the important case where there are many such queries to the same array, $A$, which resides entirely in RAM. In addition to the obvious sorted order/binary search combination we consider the Eytzinger (BFS) layout normally used for heaps, an implicit B-tree layout that generalizes the Eytzinger layout, and the van Emde Boas layout commonly used in the cache-oblivious algorithms literature. After extensive testing and tuning on a wide variety of modern hardware, we arrive at the conclusion that, for small values of $n$, sorted order, combined with a good implementation of binary search is best. For larger values of $n$, we arrive at the surprising conclusion that the Eytzinger layout is usually the fastest. The latter conclusion is unexpected and goes counter to earlier experimental work by Brodal, Fagerberg, and Jacob (SODA~2003), who concluded that both the B-tree and van Emde Boas layouts were faster than the Eytzinger layout for large values of $n$. Our fastest C++ implementations, when compiled, use conditional moves to avoid branch mispredictions and prefetching to reduce cache latency.

Full work available at URL: https://arxiv.org/abs/1509.05053

Recommendations

• scientific article; zbMATH DE number 2119642
• Optimal worst-case operations for implicit cache-oblivious search trees.
• scientific article; zbMATH DE number 2090595
• scientific article; zbMATH DE number 1947390
• Skewed Binary Search Trees

zbMATH Keywords

binary searchcachingpipeliningdata layoutsmicroprocessor architecture

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Cites Work

• Title not available (Why is that?)
• Cache-Oblivious Algorithms
• Title not available (Why is that?)
• Algorithms – ESA 2004
• Irredundant intervals

Cited In (3)

• Title not available (Why is that?)
• Languages and Compilers for Parallel Computing
• Title not available (Why is that?)

This page was built for publication: Array layouts for comparison-based searching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4577950)