Paper Info
Title
Conc-Trees for Functional and Parallel Programming
Abstract
Parallel algorithms can be expressed more concisely in a functional programming style. This task is made easier through the use of proper sequence data structures, which allow splitting the data structure between the processors as easily as concatenating several data structures together. Efficient update, split and concatenation operations are essential for declarative-style parallel programs. This paper shows a functional data structure that can improve the efficiency of parallel programs. The paper introduces two Conc-Tree variants: the Conc-Tree list, which provides worst-case $$O\\log n$$ time lookup, update, split and concatenation operations, and the Conc-Tree rope, which additionally provides amortized O1 time append and prepend operations. The paper demonstrates how Conc-Trees implement efficient mutable sequences, evaluates them against similar persistent and mutable data structures, and shows up﾿to $$3 \\times $$ performance improvements when applying Conc-Trees to data-parallel operations.
Year
DOI
Venue
2015
10.1007/978-3-319-29778-1_16
LCPC 2015 Revised Selected Papers of the 28th International Workshop on Languages and Compilers for Parallel Computing - Volume 9519
Field
DocType
Citations 
Data structure,Functional programming,Computer science,Parallel algorithm,Parallel computing,Theoretical computer science,Append,Data sequences,Concatenation,Rope
Conference
5
PageRank 
References 
Authors
0.41
5
2
Name
Order
Citations
PageRank
Aleksandar Prokopec116313.56
Martin Odersky22261170.39