Quad Ropes: Immutable, Declarative Arrays with Parallelizable Operations

Florian Biermann, Peter Sestoft

    Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

    Abstract

    We describe the quad rope data structure, a representation of immutable two-dimensional arrays that avoids many of the performance pitfalls of plain C-style two-dimensional arrays. Our motivation is that, for end-user development in high-level declarative programming languages, it is impractical to let users choose between different array-like data structures. Instead, one should use the same, somewhat performance-robust, representation for every programming task. Quad ropes roughly retain array efficiency, as long as programmers express their programs using high-level constructs. Moreover, they allow for fast concatenation and dynamic task-based parallelism and are well suited to represent sparse arrays. We describe their operational semantics and evaluate the performance of individual functions on quad ropes as well as declarative algorithms that use our quad rope implementation.
    OriginalsprogEngelsk
    TitelProceedings of the 4th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming : ARRAY 2017
    Antal sider8
    ForlagAssociation for Computing Machinery
    Publikationsdato18 jun. 2017
    Sider1-8
    ISBN (Trykt)978-1-4503-5069-3
    DOI
    StatusUdgivet - 18 jun. 2017
    BegivenhedACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming - Barcelona, Spanien
    Varighed: 18 jun. 201723 jun. 2017
    Konferencens nummer: 4
    http://pldi17.sigplan.org/track/array-2017

    Workshop

    WorkshopACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming
    Nummer4
    Land/OmrådeSpanien
    ByBarcelona
    Periode18/06/201723/06/2017
    Internetadresse

    Emneord

    • Quad Rope Data Structure
    • Immutable Arrays
    • High-Level Declarative Programming
    • Sparse Arrays
    • Dynamic Parallelism

    Fingeraftryk

    Dyk ned i forskningsemnerne om 'Quad Ropes: Immutable, Declarative Arrays with Parallelizable Operations'. Sammen danner de et unikt fingeraftryk.

    Citationsformater