000213452 001__ 213452
000213452 005__ 20190415235357.0
000213452 020__ $$a978-1-4503-3669-7
000213452 0247_ $$2doi$$a10.1145/2784731.2784739
000213452 037__ $$aCONF
000213452 245__ $$aRRB Vector: A Practical General Purpose Immutable Sequence
000213452 269__ $$a2015
000213452 260__ $$aNew York, NY, USA$$bACM$$c2015
000213452 336__ $$aConference Papers
000213452 520__ $$aState-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.
000213452 6531_ $$aArrays
000213452 6531_ $$aData Structures
000213452 6531_ $$aImmutable
000213452 6531_ $$aRadix-Balanced
000213452 6531_ $$aSequences
000213452 6531_ $$aTrees
000213452 6531_ $$aVectors
000213452 700__ $$0249091$$aStucki, Nicolas Alexander$$g226421
000213452 700__ $$0243345$$aRompf, Tiark$$g185682
000213452 700__ $$aBagwell, Phil
000213452 700__ $$0245399$$aUreche, Vlad$$g200717
000213452 700__ $$0241835$$aOdersky, Martin$$g126003
000213452 7112_ $$aInternational Conference on Functional Programming (ICFP)$$cVancouver, BC, Canada$$dAugust 31 – September 2, 2015
000213452 773__ $$q342--354$$tProceedings of the 20th ACM SIGPLAN International Conference on Functional Programming
000213452 8564_ $$uhttp://dl.acm.org/citation.cfm?id=2784739$$zURL
000213452 8564_ $$s1756736$$uhttps://infoscience.epfl.ch/record/213452/files/rrbvector.pdf$$yPublisher's version$$zPublisher's version
000213452 909C0 $$0252187$$pLAMP$$xU10409
000213452 909CO $$ooai:infoscience.tind.io:213452$$pconf$$pIC$$pGLOBAL_SET
000213452 917Z8 $$x200717
000213452 937__ $$aEPFL-CONF-213452
000213452 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000213452 980__ $$aCONF