Re: Benchmarking srfi-41, srfi-121 and srfi-158
Amirouche Boubekki 02 Aug 2020 08:10 UTC
I few months back before proposing SRFI-167 and SRFI-168, I
benchmarked using Guile three kinds of generators:
- srfi-41
- srfi-158
And another kind of generator that is not standard that look like the following:
(define (traversi-range count)
(let loop ((index 0))
(lambda ()
(if (= index count)
(values #f #f) ;; This is the end of the traversi generator
(values index (loop (+ index 1)))))))
So it looks somewhat like SRFI-121 / SRFI-158 generators, but with
different calling conventions, and in particular it works without any
set!. SRFI-41 and traversi generators were slower than R7RS
generators.
I think SRFI-41 and traversi generators are more difficult to understand.
Outside the performance differences between SRFI-41 and SRFI-158,
there is also a semantic difference, both offering different
"guarantees". I describe the difference between SRFI-41 and SRFI-158
in terms of state. SRFI-41 are stateless or to say it otherwise,
SRFI-41 streams can be replayed. Whereas SRFI-158 and SRFI-121 are
stateful, once the code consumes a generator, it is gone, you can not
re-iterate over the generator without re-creating the whole generator
which is not necessarily easy when working e.g. with ports. Otherwise
said, SRFI-41 supports backtracking, whereas plain generators do not.
Traversi generators are faster than SRFI-41, and support some limited
form of backtracking. I remember using traversi generators in a parser
combinator that requires backtracking.
Mind the fact that at least the SRFI-158 sample implementation could
use some performance optimization by avoiding the use of
make-coroutine-generator. E.g. [1]
make-coroutine-generator is very handy to build a generator quickly,
but it is not performant.
I am working on a finger-tree implementation that used to rely on
make-coroutine-generator, when translating to
Continuation-Passing-Style, it is much faster. It is faster than
make-coroutine-generator implemented with call/1cc [0]. Similarly,
SRFI JSON could use make-coroutine-generator but would be much slower
(but also much more readable).
While I am at it, when implementing generators, you should properly
take care of end-of-file, I think once eof was produced, the generator
should always produce eof...
[0] https://www.scheme.com/csug8/control.html#./control:s6
[1] https://github.com/amirouche/guile-arew/commit/01dbf6353d6ad55759221ede823a33d311516234#diff-fca38fa8286c100b4e5f5180ed87e58e