Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. RRB Vector: A Practical General Purpose Immutable Sequence
 
conference paper

RRB Vector: A Practical General Purpose Immutable Sequence

Stucki, Nicolas Alexander  
•
Rompf, Tiark  
•
Bagwell, Phil
Show more
2015
Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming
International Conference on Functional Programming (ICFP)

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.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1145/2784731.2784739
Author(s)
Stucki, Nicolas Alexander  
Rompf, Tiark  
Bagwell, Phil
Ureche, Vlad  
Odersky, Martin  
Date Issued

2015

Publisher

ACM

Publisher place

New York, NY, USA

Published in
Proceedings of the 20th ACM SIGPLAN International Conference on Functional Programming
ISBN of the book

978-1-4503-3669-7

Start page

342

Subjects

Arrays

•

Data Structures

•

Immutable

•

Radix-Balanced

•

Sequences

•

Trees

•

Vectors

URL

URL

http://dl.acm.org/citation.cfm?id=2784739
Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LAMP1  
Event nameEvent placeEvent date
International Conference on Functional Programming (ICFP)

Vancouver, BC, Canada

August 31 – September 2, 2015

Available on Infoscience
November 2, 2015
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/120382
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés