While playing around with various ideas about how to approach rendering large (long) tables in uni-table[1], I realized that a lot of the processing work can be done lazily. However that would only postpone the actual work until later. That's why I started experimenting with lazy streams[2] with futures[3].
I've put together a lazy future-mapped stream proof-of-concept[4] which shows the basic idea. The interface is just a stream, but the internal machinery puts everything in futures and therefore the stream might get evaluated in advance. The approach seemed to be very naive at first glance, however (under 8.3 CS), the performance is fairly decent and it keeps ticking two cores at full speed most of the time. The look-ahead feature makes sure some specified number of last elements in the stream get indexed backwards (that is a feature needed for my table rendering - not a general one).
The main idea is to split the rendering into more-or-less independent stages and chain them together using multiple streams constructed in this manner. Basically something like a semi-parallel pipeline. Even without big modifications, my current table rendering algorithm can be put into 3 streams and therefore leverage at least 4 CPU cores when producing the output.
The question here is: am I reinventing the wheel here? Is there some feature/package I overlooked, that would do exactly the same thing?
Because if not, I definitely think that Racket should have a generic library with this functionality. Probably wrapped in something like "lazy opportunistic stream comprehensions". It might be an interesting problem to solve the look-ahead and reverse indexing in general, but it surely looks possible to me.
[1] Unicode Tables
[2] 4.15.2Â Streams
[3] 11.4Â Futures
[4] fm-stream.rkt · master · Dominik Joe PantůÄek / fm-streams · GitLab
4 Likes
If I understand correctly this allows the tail (and its head and tail) to be produced before it is used, without requiring that this happens. (Whereas the #:eager in stream-cons would require it)
So this seems useful.
I had only a brief look at your stream and it has application specific features I might not completely understand so most of what I write are general thoughts and not about your specific implementation.
Maybe another option would be to have a #:opportunistic that wraps the expressions of stream-cons in futures?
Or as a separate form:
(opportunistic-cons head tail) -> (stream-cons #:eager (furture (thunk head)) #:eager (future (thunk tail)))
(opportunistic-first stream) -> (touch (stream-first stream))
(opportunistic-rest stream) -> (touch (stream-rest stream))
;; I don't know whether this is reasonable I would have to actually play with it,
;; for example it might make more sense to have a recursive call as an eager tail that blocks until
;; we actually want the current cell to be processed based on a notion of "demand"
Maybe it also could make sense to have a notion of distance to the furthest stream cell-head that has been touched and use that as a metric to calculate "demand", so as the consumer gets closer to more distant stream cells their demand increases and when it exceeds a threshold the futures could be created with the hope that the calculation is done by the time they are actually needed.
I think especially if you need to download a bunch of image-urls (or something else with lots of latency) to display them in a row, something like this could be useful to have both order and mostly interleaved/parallel processing.
(I imagine if you just create futures for everything right away you could have executions where a lot of futures which are currently not very important are executed before other futures which are needed first,
so some kind of grouping into needed soon vs needed later, may improve general throughput?)
So far I haven't used opportunistic streams and I am not aware of other examples in racket, but I think it might be a nice way to encapsulate the pattern of do a bunch of tasks and give me the results in a ordered way with relatively low latency, especially if the tasks are highly independent just being used in a certain order.
Also another thought: I think there are cases were the simplest thing that can be done is to have a generator function of the stream that has domain specific knowledge about what is slow and what is needed when and write that stream generator in such a way that it starts calculations/tasks in such a way that their results are available close to when they are needed.
For example I may have a picture downloader that always starts some number of downloads going on in parallel and then blocks until another picture is done downloading.
2 Likes