Stream fusion, to completeness

DOI10.1145/3009837.3009880MaRDI QIDQ5370864zbMATH OpenOpenAlexFDO

Authors Oleg Kiselyov, Aggelos Biboudis, Nick Palladinos, Yannis Smaragdakis

Publication date 20 October 2017

Published in Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.06668

zbMATH Keywords

code generationmulti-stage programmingoptimizationstream fusionstreams

Mathematics Subject Classification ID

Theory of programming languages (68N15) Theory of compilers and interpreters (68N20)

Abstract: Stream processing is mainstream (again): Widely-used stream libraries are now available for virtually all modern OO and functional languages, from Java to C# to Scala to OCaml to Haskell. Yet expressivity and performance are still lacking. For instance, the popular, well-optimized Java 8 streams do not support the zip operator and are still an order of magnitude slower than hand-written loops. We present the first approach that represents the full generality of stream processing and eliminates overheads, via the use of staging. It is based on an unusually rich semantic model of stream interaction. We support any combination of zipping, nesting (or flat-mapping), sub-ranging, filtering, mapping-of finite or infinite streams. Our model captures idiosyncrasies that a programmer uses in optimizing stream pipelines, such as rate differences and the choice of a "for" vs. "while" loops. Our approach delivers hand-written-like code, but automatically. It explicitly avoids the reliance on black-box optimizers and sufficiently-smart compilers, offering highest, guaranteed and portable performance. Our approach relies on high-level concepts that are then readily mapped into an implementation. Accordingly, we have two distinct implementations: an OCaml stream library, staged via MetaOCaml, and a Scala library for the JVM, staged via LMS. In both cases, we derive libraries richer and simultaneously many tens of times faster than past work. We greatly exceed in performance the standard stream libraries available in Java, Scala and OCaml, including the well-optimized Java 8 streams.

Recommendations

• Completion for unification
• The Dyadic Stream Merging Algorithm
• On-line stream merging in a general setting.
• scientific article; zbMATH DE number 1798170
• Hybrid completeness
• Comprehensive convergence
• A completion theorem for fusion systems
• scientific article; zbMATH DE number 1759424

Cited in

(8)

• Generating C. System description
• Unified program generation and verification: a case study on number-theoretic transform
• A universal calculus for stream processing languages
• scientific article; zbMATH DE number 3960963 (Why is no real title available?)
• scientific article; zbMATH DE number 2087568 (Why is no real title available?)
• Property-based testing for Spark Streaming
• Extension of Type-Based Approach to Generation of Stream-Processing Programs by Automatic Insertion of Buffering Primitives
• How to mingle streams

Describes a project that uses

Uses Software

• OCaml
• MetaOCaml
• Scala
• Strymonas
• LinqOptimizer
• ScalaBlitz

This page was built for publication: Stream fusion, to completeness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5370864)