000205070 001__ 205070
000205070 005__ 20190317000108.0
000205070 037__ $$aSTUDENT
000205070 245__ $$aTurning Relaxed Radix Balanced Vector from Theory into Practice for Scala Collections (Master Thesis)
000205070 269__ $$a2015
000205070 260__ $$c2015
000205070 336__ $$aStudent Projects
000205070 520__ $$aThe immutable Vector collection in the Scala library offers nearly constant-time random access reads thanks to its underlying wide tree data structure. Furthermore, it provides amortized constant time sequential read, update, append and prepend operations by efficiently sharing parts of the tree between different immutable vectors. However, the performance of parallel operations is hindered by the overhead of re-combining the results obtained from parallel workers. Recent research has shown that parallel performance can be improved by relaxing the wide tree invariants and thus improving the performance of the combine operation. Although tree sharing is still used, sequential read, update, append and prepend are no longer amortized constant time. This prevents the new approach from making its way into the Scala Collections library. The main insight of this thesis is that relaxed-invariant vector trees can be seen as a composition of strict and irregular parts. Therefore earlier optimizations can still be applied to strict subtrees, while irregular subtrees bring their own new optimization opportunities. This allows our implementation to provide both amortized constant-time sequential operations and efficient parallel execution at the same time. Our implementation, which is fully compatible with Scala Collections, matches the sequential performance of standard vectors in most cases. At the same time benchmarks show parallel operations execute up to 2.3X faster on 4 threads on a 4 core machine thanks to the relaxed invariants allowing fast re-combination of results from different parallel executions.
000205070 6531_ $$avector
000205070 6531_ $$aimmutable
000205070 6531_ $$atrees
000205070 6531_ $$arelaxed radix balanced
000205070 6531_ $$aoptimization
000205070 700__ $$aStucki, Nicolas
000205070 720_2 $$aOdersky, Martin$$edir.$$g126003$$0241835
000205070 8564_ $$uhttps://github.com/nicolasstucki/scala-rrb-vector$$zURL
000205070 8564_ $$uhttps://infoscience.epfl.ch/record/205070/files/main.pdf$$zPreprint$$s1611676$$yPreprint
000205070 909C0 $$xU10409$$0252187$$pLAMP
000205070 909CO $$qGLOBAL_SET$$pIC$$ooai:infoscience.tind.io:205070
000205070 917Z8 $$x200717
000205070 917Z8 $$x200717
000205070 937__ $$aEPFL-STUDENT-205070
000205070 973__ $$aEPFL
000205070 980__ $$bMASTERS$$aSTUDENT