Anzeige
Erschienen in:
2016 | OriginalPaper | Buchkapitel
Conc-Trees for Functional and Parallel Programming
verfasst von : Aleksandar Prokopec, Martin Odersky
Erschienen in: Languages and Compilers for Parallel Computing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 O(1) 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.