Flexible Data Views: Design and Implementation
In this paper, we present a library-based framework of data views over chunks of memory segments. Such views not only enable a uniform treatment of references and arrays, but they provide a more general abstraction in the sense that parts of arrays, references, or even views, can be combined into hierarchies to form new logical data structures. To provide efficient implementations in widely used industrial languages such as C++ and Scala, we employ static and dynamic multi-staging techniques, respectively. Through staging and code specialization, the overhead of traversal and tracking of such view hierarchies is mostly eliminated. Thus, our data views can be used as building blocks for creating data structures for which programmers need not pick a specific representation but can rely on code generation and specialization to provide the right implementation that meets asymptotic running time and space guarantees. We apply our approach in case studies in which two-dimensional array views are used to efficiently encode real-world matrices, showing performance on par with specialized data structures such as sparse matrices from popular linear algebra libraries (Armadillo and Eigen), or hand-tuned dense representations. We also show the practicality of specializing data views at run-time on the JVM via Lightweight Modular Staging, a Scala framework for dynamic multi-stage programming, by designing a user-friendly API that hides the underlying compilation through lazy evaluation and a uniform access principle.
Slides (ARRAY17- Flexible Data Views.pdf) | 697KiB |
Sun 18 JunDisplayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change
11:00 - 12:30 | Morning talks 2ARRAY at Vertex WS218 Chair(s): Martin Elsman Department of Computer Science, University of Copenhagen | ||
11:00 30mTalk | An ELI-to-C Compiler: Design, Implementation and Performance ARRAY DOI File Attached | ||
11:30 30mTalk | Array Programming in Whiley ARRAY David J. Pearce Victoria University of Wellington DOI File Attached | ||
12:00 30mTalk | Flexible Data Views: Design and Implementation ARRAY DOI File Attached |