JuliaLang / julia

The Julia Programming Language
https://julialang.org/
MIT License
45.68k stars 5.48k forks source link

lowering of typed comprehension unnecessarily complex #40373

Open simeonschaub opened 3 years ago

simeonschaub commented 3 years ago

Is there any reason we implement pretty much the whole functionality for typed comprehensions in lowering? Compare:

julia> Meta.@lower Int[i for i in 1:3]
:($(Expr(:thunk, CodeInfo(
     @ none within `top-level scope'
1 ──       Core.NewvarNode(:(#s45))
│          Core.NewvarNode(:(@_2))
│          Core.NewvarNode(:(@_3))
│    %4  = 1:3
│    %5  = Base.IteratorSize(%4)
│    %6  = %5 isa Base.SizeUnknown
└───       goto #3 if not %6
2 ── %8  = Core.apply_type(Core.Array, Int, 1)
│          @_3 = (%8)(Core.undef, 0)
└───       goto #4
3 ──       @_3 = Base._array_for(Int, %4, %5)
4 ┄─ %12 = Base.LinearIndices(@_3)
│          @_2 = Base.first(%12)
│          #s45 = Base.iterate(%4)
│    %15 = #s45 === nothing
│    %16 = Base.not_int(%15)
└───       goto #10 if not %16
5 ┄─ %18 = #s45
│          i = Core.getfield(%18, 1)
│    %20 = Core.getfield(%18, 2)
│    %21 = i
│          $(Expr(:inbounds, true))
└───       goto #7 if not %6
6 ──       Base.push!(@_3, %21)
└───       goto #8
7 ──       Base.setindex!(@_3, %21, @_2)
8 ┄─       $(Expr(:inbounds, :pop))
│          @_2 = Base.add_int(@_2, 1)
│          #s45 = Base.iterate(%4, %20)
│    %30 = #s45 === nothing
│    %31 = Base.not_int(%30)
└───       goto #10 if not %31
9 ──       goto #5
10 ┄       return @_3
))))

to the way untyped comprehensions are lowered:

julia> Meta.@lower [i for i in 1:3]
:($(Expr(:thunk, CodeInfo(
    @ none within `top-level scope'
1 ─ %1 = 1:3
│   %2 = Base.Generator(Base.identity, %1)
│   %3 = Base.collect(%2)
└──      return %3
))))

This makes this syntax hard to extend for other array types and also prevents AD from making use of higher-level adjoints here. Is there a reason we do it this way or is it just historical baggage? Otherwise, I would propose lowering this just like untyped comprehensions, but using collect(Int, %2), which is what I initially expected this to do.

JeffBezanson commented 3 years ago

This was probably to reduce the number of closures and make it easier on the compiler. Otherwise it has to re-analyze a significant amount of code for each comprehension.

simeonschaub commented 3 years ago

Would you say that is something that's still as relevant nowadays, or would the additional consistency and extendability be worth it? A much more speculative proposal would be to lower comprehensions to opaque closures, since IIUC they would avoid recompiling the same code over and over again, but not sure if the slight semantic differences might lead to some odd edge cases.

JeffBezanson commented 3 years ago

It's probably still relevant now. If we still wanted everything inlined, I'm not sure opaque closures would be much better.

KristofferC commented 3 years ago

Here is an example where it seems relevant https://github.com/JuliaLang/julia/issues/40302#issuecomment-812525555

simeonschaub commented 3 years ago

40302 seems mostly due to the return_type calculation, if I read that correctly. Since that shouldn't get called in the typed case, that might not be affected by this change.