Open MasonProtter opened 1 year ago
Are you suggesting that IR itself should better represent transducers, or simply that transducers generates better IR as is?
Both actually. At least in theory, if we moved from representing loops with foldl
instead of goto
, it would make some things better / easier, especially when say, trying to interface with MLIR or LoopModels.
In practice, I wouldn't be at all surprised though if it was simply WAY too big a task to change how we internally represent loops, especially given that we've already developed the infrastructure for rediscovering loop flow information inside the compiler with our current goto-based representation.
I just mentioned that as a very far off possible milestone.
The main thing that would potentially improve with a foldl based loop IR is that it might allow us to prove that most loops terminate which would make concrete eval a lot more powerful.
Especially for statically sized objects like Tuples
Fundamentally, the idea with transducers is that you replace iterate as your fundamental operation for traversing data, with foldl
But what if you don't want to do foldl
, e.g. you want to do pairwise mapreduce for accuracy in floating-point reductions (#52397)?
foldl
is how you'd represent a regular sequential loop. What's nice is that if you have only have transducers that are amenable to re-ordering, and your reducing function is associative, you can then freely switch the foldl
out for a parallel_reduce
or whatever
Maybe put another way @stevengj, what's nice about working with this different style is that all the logic and operations of the loop are encoded in the transducer and the reducing operator, and then the details of how it's scheduled and run (i.e. sequential or pairwise, or parallel or whatever) can be changed by simply swapping foldl
for whichever other reduction you may want.
This lets you re-use more code. i.e. in the example I showed above:
foldxl(+, xs |> Map(x -> 2x) |> Filter(iseven))
the reducing operator is +
, the data is xs
and the transducer is Filter(iseven) ∘ Map(x -> 2x)
. These different components are modular and can be re-used, we could swap foldxl
and replace it with foldxt
for a multithreaded reduction, or foldxd
for a distributed reduction, or add custom backend executors like those in FoldsCUDA.jl or FoldsThreads.jl.
Because iterators are inherent sequential, turning the iterator equivalent of this operation into a parallel or pairwise reduction is pretty non-trivial.
I guess I got confused by this description:
Fundamentally, the idea with transducers is that you replace
iterate
as your fundamental operation for traversing data, withfoldl
Because what you are describing is not foldl
, it is reduce
. The foldl
operation specifies an associativity, so it is inherently sequential.
Maybe it could say:
Fundamentally, the idea with transducers is that you replace
iterate
as your fundamental operation for traversing data, with reductions.foldl
provides an ordered sequential reduction analogous to iterate, but the paradigm generalizes better as other reductions (e.g.reduce
) can be used as well.
This has been mentioned in a few scattered places (e.g. here https://github.com/JuliaLang/julia/issues/15648#issuecomment-511048192, https://github.com/JuliaLang/julia/pull/33526, various slack and discourse threads, etc.), but I think it'd be good to have a general tracking issue for this as a large scale goal.
Currently, the majority of our infrastructure is built on the paradigm of iterators. These are essentially state machines that tell you how to progress from one state to the next.
Something @tkf was rightfully a big champion of was the use of transducers instead of iterators where possible, with https://github.com/JuliaFolds/Transducers.jl being his gigantic playground for those ideas.
Fundamentally, the idea with transducers is that you replace
iterate
as your fundamental operation for traversing data, withfoldl
, and this enables a lot of interesting things. To borrow from the docs in Transducers.jl, this is whatis essentially doing:
the Transducers.jl equivalent
does this:
and this is obtained not though clever compiler magic, but just algorithm design. The difference is that with iterators, one writes a loop and pulls values out of the iterator. The loop owns the iterator. With transducers, the transducer owns the loop and pushes out values.
An important practical benefit of transducers is the space of parallelism. Transducers.jl and things built on it like https://github.com/tkf/ThreadsX.jl give really nice APIs for many parallel workflows because whether an algorithm is amenable to parallelism is built into the representation of a transducer. With iterators, many of these things are quite opaque since the fundamental paradigm of iteration is sequential.
Finally, I'll also mention that because our intermediate representations (IR) represent loops in terms of
while
loops (goto
s) on iterators, this makes it a real pain to take lowered julia code and find out what the structure and intent of the original code was, and a lot of IR level transformations on Julia code need to do a lot of work to rediscover what the original loop layout was.When represented in terms of
fold
s though, we could preserve a lot more structured information at the IR level which could make compiler level loop optimizations easier.