patmorin/arraylayout

Experiments with array layouts for comparison-based searching

arraylayout

Experiments with memory layouts for binary search.

These are the sources (LaTeX, C++, and Python) for the paper

ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING

by Paul-Virak Khuong and Pat Morin

About

This project is about trying different memory layouts for searching in an array, with a focus on improving performance for the most common-case: When the input fits entirely in RAM. The layouts we try are:

1. sorted: The usual sorted array on which we apply binary search
2. eytzinger: The Eytzinger (or BFS) layout most commonly used implicit binary heaps
3. btree: A (B+1)-ary variant of the Eytzinger layout
4. veb: The van Emde Boas layout from the cache-oblivious literature

Quick start

To run an experiment on your own (linux) machine (with g++ installed):

cd src
make main
./main uint32 uint32 100000000 10000000

This will test the cost of performing ten million searches in an array of one hundred million integers. You'd better have at least 800MB of free RAM, which you can check with

free -h

Replicated Computational Results

This work is in the process of earning a Replicated Computational Result certificate from the ACM Journal of Experimental Algorithmics. To achieve this, we have developed scripts that allow anyone with a suitable system to reproduce the computational results (in this case, figures) in the paper.

If you want to try and reproduce our results, execute

./rcr

For this to work, you will need (at least) the following software installed

• g++
• lscpu
• free
• numactl
• python with matplotlib
• pdflatex

To fully replicate the experiments in the paper, you will need at least 15GB of free RAM. The experiments will scale down to use at most 2/3 of your available RAM otherwise.

Using the preceding script will generate PDF and SVG figures in the scripts/figs-rcr directory. You can view the resulting SVG files in a browser by opening scripts/figs-rcr/index.html

Results

A webpage describing this work and with some collected results is being maintained here:

http://cglab.ca/~morin/misc/arraylayout-v2/

arraylayout's Issues

Some pointers for which variants to use

Following a discussion over at gimli-rs/addr2line#61 (comment), I'm thinking of implementing the Eytzinger array-based search in Rust. But, looking through https://github.com/patmorin/arraylayout/blob/master/src/eytzinger_array.h, it's not immediately clear to me which of the variants would be the appropriate one to implement.

If I'm reading the paper correctly:

arraylayout/src/eytzinger_array.h

Line 128 in 3f20174

I __attribute__ ((noinline)) eytzinger_array_deeppf<T,I,C,aligned>::search(T x) const {

should be used when the size of T is small (roughly < 8 bytes), and

arraylayout/src/eytzinger_array.h

Line 253 in 3f20174

I __attribute__ ((noinline)) eytzinger_array_bfpm<T,I,aligned>::search(T x) const {

should be used as the general implementation for all T.

Are those conclusions mostly correct? Which would suggest that I should implement the latter of the two first, and then possibly add a variant for small T using the former.

I also noticed there's an "unrolled" version of the algorithm:

arraylayout/src/eytzinger_array.h

Line 266 in 3f20174

I __attribute__ ((noinline)) eytzinger_array_unrolled<T, I, aligned>::search(T x) const {

which is not evaluated in the paper? Is that something worth paying attention to?