Paper Info
Title
RRB vector: a practical general purpose immutable sequence
Abstract
State-of-the-art immutable collections have wildly differing performance characteristics across their operations, often forcing programmers to choose different collection implementations for each task. Thus, changes to the program can invalidate the choice of collections, making code evolution costly. It would be desirable to have a collection that performs well for a broad range of operations. To this end, we present the RRB-Vector, an immutable sequence collection that offers good performance across a large number of sequential and parallel operations. The underlying innovations are: (1) the Relaxed-Radix-Balanced (RRB) tree structure, which allows efficient structural reorganization, and (2) an optimization that exploits spatio-temporal locality on the RRB data structure in order to offset the cost of traversing the tree. In our benchmarks, the RRB-Vector speedup for parallel operations is lower bounded by 7x when executing on 4 CPUs of 8 cores each. The performance for discrete operations, such as appending on either end, or updating and removing elements, is consistently good and compares favorably to the most important immutable sequence collections in the literature and in use today. The memory footprint of RRB-Vector is on par with arrays and an order of magnitude less than competing collections.
Year
DOI
Venue
2015
10.1145/2784731.2784739
International Conf on Function Programming
Keywords
Field
DocType
Arrays,Data Structures,Immutable,Radix-Balanced,Relaxed-Radix-Balanced,Sequences,Trees,Vectors
Data structure,Locality,Computer science,Parallel computing,Theoretical computer science,Exploit,Tree structure,Memory footprint,Offset (computer science),Speedup,Bounded function
Conference
Volume
Issue
ISSN
50
9
0362-1340
Citations 
PageRank 
References 
7
0.53
22
Authors
4
Name
Order
Citations
PageRank
Nicolas Stucki1113.65
Tiark Rompf274345.86
Vlad Ureche31457.78
Phil Bagwell4814.64