[RFC/ANN] FLoops.jl: fast generic for loops (foldl for humans™)

[tkf]

@Datseris Yeah, my ambition is to put this in julia itself. I think it is possible to do this in a backward compatible manner so this might even be possible to do within 1.x. But, as @tim.holy says, they might be some edge cases or even some fatal flaw at the moment. So I think it’s a good idea to explore this as an external package.

@tim.holy Before writing this, I (naively) thought the analysis of the user code would be much simpler. So, initially, I thought I’d automatically figure out the state variables. It then turned out that it was a rather hard problem so I had to backoff a bit in terms of the UI and let the user manually specify the states by listing them after @floop begin. So, yeah, hooking into the compiler become more appealing while writing FLoops.jl. Thanks a lot for preparing the plugable compiler path infrastructure!

@c42f

So as I understand it, foldl-based lowering allows the iteration source to own part of the program stack which is very natural and efficient, rather than forcing the compiler to reconstruct something efficient from the iterator state machine.

@c42f Exactly! The basic idea is that collection authors know much more about their collection types than the compiler. foldl-based iteration is a way to let them express their knowledge more naturally.

@c42f

the usual optimization difficulties with lexical scoping of captured variables

Are you referring to that it’s hard to efficiently mutate variables of the outer scope? I think this is why it is important to use foldl rather than foreach as the lowering target. Since foldl takes the function of the form (state, input) -> state′, there is no need to mutate the variables of outer scope via the boxing used by the usual lowering of closure. All the changes during the loop can stay in state (a named tuple) and assigned back to the original variables after the loop is finished. OTOH, using foreach would have this problem.

@c42f

I’m impressed you got goto to work inside @floop , very neat.

Haha, thanks It was kind of a fun moment when I figured out how to do it.

@oschulz Thanks! Good to know you like it. I need JuliaVariables.jl and MLStyle.jl during macro expansion time so I can’t make them optional. I’m using JuliaVariables.jl as I just didn’t want to implement scope analysis myself (as it sounds like a hairy problem). I use MLStyle.jl as it is already a dependency of JuliaVariables.jl and I’ve been wanting to try it out in a non-trivial package. Regarding the concern of the dependencies, it looks like MLStyle.jl has no dependencies and uses DataFrames.jl only during test.