Strymonas Streams: stream fusion, to completeness

Strymonas is a streaming library for fast, bulk, single-thread in-memory processing -- of the sort epitomized by Software Defined Radio or Java Streams. It attains the speed and memory efficiency of hand-written state machines, yet provides the familiar declarative interface for finite and infinite streams, supporting any combination of map, filter, take(while), drop(while), zip, flatmap combinators and tupling. Experienced users may use the lower-level interface of stateful streams and implement accumulating maps, compression and windowing.

The library is based on assured code generation (at present, OCaml, C and Scala/Java) and guarantees in all cases complete fusion: if each operation in a pipeline individually runs without any function calls and memory allocations, the entire streaming pipeline runs without calls and allocations. Thus strymonas per se introduces not even constant-size intermediary data structures. The main processing loop thus may run in constant memory and stack space.

In essence, strymonas is a DSL that generates high-performance single-core stream processing code from declarative descriptions of stream pipelines and user actions -- something like Yacc. Unlike Yacc, strymonas is an embedded DSL. There are two flavors of the library, with the host language being OCaml and Scala 3. The C generation back-end needs no other dependencies, the OCaml back-end relies on BER MetaOCaml, and Scala backend uses Scala 3 native metaprogramming facilities.

News

• Published a part of version 2.1 and SDR examples (October 2023): link containing the documentations for the each example

• Version 2.1 (September 2023): greatly expanded back-end (with C99 code-generation, more numeric data types, including complex numbers, and operations on them), static arrays, more general FFI, and provisions for Wasm

• OCaml 22 workshop paper link

• Complete Stream Fusion for Software-Defined Radio Tomoaki Kobayashi and Oleg Kiselyov http://arxiv.org/abs/2208.08732 https://doi.org/10.48550/arXiv.2208.08732

• Even Better Stream Fusion Oleg Kiselyov University of Oxford Department of Computer Science. Seminar on Tensor Computation. Feb 18, 2022. http://www.cs.ox.ac.uk/seminars/2447.html

• Stream Fusion, to Completeness (describes the previous version of the library) POPL 2017. (paper with appendicies, arXiv POPL 17 talk)

Getting Started

git clone https://github.com/strymonas/strymonas-ocaml
git clone https://github.com/strymonas/strymonas-C
git clone https://github.com/strymonas/strymonas-scala

(For the latest manuals, please visit the each repository.)

Prerequisites

• For strymonas-ocaml and strymonas-C:
  1. OCaml: from your system's package manager
  2. OPAM: after you install OPAM you will need to initialize it with opam init and resolve any dependencies with:
     • either the opam depext command
     • or your system's package manager (e.g., OML's dependencies)
• For Scala: (work in progress...)

Benchmarks

How to compile and run the benchmarks:

• For strymonas-ocaml: see

  strymonas-ocaml/benchmarks/README.md

  Benchmarks require MetaOCaml

• For strymonas-C: see

  strymonas-C/bench/README.md

  (to generate the C code for the benchmark, see the end of strymonas-ocaml/benchmarks/README.md)

• For strymonas-scala: (work in progress...)

Bugs and Feedback

To discuss bugs and improvements please use our Github Issues for each corresponding flavor, for discussions and recommendations please use our gitter pages.

Team

• Oleg Kiselyov
• Tomoaki Kobayashi
• Aggelos Biboudis
• Nick Palladinos
• Yannis Smaragdakis

Old Design (POPL17)

You can find and experiment with the implementations of the old design please follow the guidelines here:

https://github.com/strymonas/strymonas.github.io/blob/master/index-old.md