![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
http://www.cs.kuleuven.ac.be/publicaties/rapporten/cw/CW715.pdf
Faster Coroutine Pipelines:A Reconstruction (Extended Version)
Ruben P. Pieters, Tom Schrijvers
Report CW 715, November 2018
Department of Computer Science, KU Leuven
Spivey has recently presented a novel functional representation that supports the efficient composition, or merging, of coroutine pipelines for processing streams of data. This representation was inspired by Shivers and Might’s three-continuation approach and is shown to be equivalent to a simple yet inefficient executable specification. Unfortunately, neither Shivers and Might’s original work nor the equivalence proof sheds much light on the underlying principles allowing the derivation of this efficient representation from its specification.This paper gives the missing insight by reconstructing a systematic derivation in terms of known transformation steps from the simple specification to the efficient representation. This derivation sheds light on the limitations of the representation and on its applicability to other settings. In particular, it has enabled us to obtain a similar representation for pipes featuring two-way communication,similar to the Haskell pipes library. Our benchmarks confirm that this two-way representation retains the same improved performance characteristics
Faster Coroutine Pipelines:A Reconstruction (Extended Version)
Ruben P. Pieters, Tom Schrijvers
Report CW 715, November 2018
Department of Computer Science, KU Leuven
Spivey has recently presented a novel functional representation that supports the efficient composition, or merging, of coroutine pipelines for processing streams of data. This representation was inspired by Shivers and Might’s three-continuation approach and is shown to be equivalent to a simple yet inefficient executable specification. Unfortunately, neither Shivers and Might’s original work nor the equivalence proof sheds much light on the underlying principles allowing the derivation of this efficient representation from its specification.This paper gives the missing insight by reconstructing a systematic derivation in terms of known transformation steps from the simple specification to the efficient representation. This derivation sheds light on the limitations of the representation and on its applicability to other settings. In particular, it has enabled us to obtain a similar representation for pipes featuring two-way communication,similar to the Haskell pipes library. Our benchmarks confirm that this two-way representation retains the same improved performance characteristics
Faster coroutine pipelines
Apr. 10th, 2019 03:15 pmhttps://dl.acm.org/citation.cfm?id=3110249
Faster coroutine pipelines
Michael Spivey University of Oxford, UK, 2017
Coroutine pipelines provide an attractive structuring mechanism for complex programs that process streams of data, with the advantage over lazy streams that both ends of a pipeline may interact with the I/O system, as may processes in the middle. Two popular Haskell libraries, Pipes and Conduit, support such pipelines. In both libraries, pipelines are implemented in a direct style by combining a free monad of communication events with an interpreter for (pseudo-)parallel composition that interleaves the events of its argument processes. These implementations both suffer from a slow-down when processes are deeply nested in sequence or in parallel. We propose an alternative implementation of pipelines based on continuations that does not suffer from this slow-down. What is more, the implementation is significantly faster on small, communication-intensive examples even where they do not suffer from the slow-down, and comparable in speed with similar programs based on lazy streams. We also show that the continuation-based implementation may be derived from the direct-style implementation by algebraic reasoning.
Faster coroutine pipelines
Michael Spivey University of Oxford, UK, 2017
Coroutine pipelines provide an attractive structuring mechanism for complex programs that process streams of data, with the advantage over lazy streams that both ends of a pipeline may interact with the I/O system, as may processes in the middle. Two popular Haskell libraries, Pipes and Conduit, support such pipelines. In both libraries, pipelines are implemented in a direct style by combining a free monad of communication events with an interpreter for (pseudo-)parallel composition that interleaves the events of its argument processes. These implementations both suffer from a slow-down when processes are deeply nested in sequence or in parallel. We propose an alternative implementation of pipelines based on continuations that does not suffer from this slow-down. What is more, the implementation is significantly faster on small, communication-intensive examples even where they do not suffer from the slow-down, and comparable in speed with similar programs based on lazy streams. We also show that the continuation-based implementation may be derived from the direct-style implementation by algebraic reasoning.
Coroutine pipes
Apr. 9th, 2019 12:34 am/*
https://github.com/rizo/streams/blob/master/src/coroutine.ml
https://pusher.com/sessions/meetup/the-realtime-guild/realtime-stream-processing-with-coroutines
*/
https://github.com/rizo/streams/blob/master/src/coroutine.ml
https://pusher.com/sessions/meetup/the-realtime-guild/realtime-stream-processing-with-coroutines
*/
object Pipes {
sealed trait Pipe[I, O, R] {
final def flatMap[T](f: R => Pipe[I, O, T]): Pipe[I, O, T] = this match {
case Yield(b, p) => Yield(b, () => p() flatMap f)
case Await(k) => Await(a => k(a) flatMap f)
case Ready(r) => f(r)
}
( Read more... )
