Vectorization Roadmap

[stevengj]

Now that #15032 is merged, here are the main remaining steps discussed in #8450, roughly in order that they should be implemented:

• Improve output type-computation in broadcast to be at least as good as map (broadcast picking incorrect result type #4883). The trickest part is the ongoing discussion of what to do in the empty-array case (see Coherent map and comprehension, the imminent death of type_goto #11034).
• Deprecate @vectorized functions like sin(x) in favor of sin.(x). Deprecate functions vectorized via @vectorize_(1|2)arg in favor of compact broadcast syntax #17302
• Parse operators like a .+ b as broadcast(+, a, b). (See also support many more Unicode infix operators #6929 (comment), Allow users to define "dot" vectorized operators. #14544, and parse more dot operators, parse .= with assignment precedence #17393.) Existing overloaded functions .+(a, b) = ... can be deprecated in favor of overloading broadcast(::typeof(+), a, b). make "dot" operations (.+ etc) fusing broadcasts #17623

More speculative proposals probably for the 0.6 timeframe (suggested by @yuyichao):

• Define nested f.(args...) calls as "fusing" broadcast operations at the syntax level. For example, sin.(x .+ cos.(x .^ sum(x.^2))) would turn (in julia-syntax.scm) into broadcast((x, _s_) -> sin(x + cos(x^_s_)), x, sum(broacast(^, x, 2))). Notice that the sum function (or any non-dot call) would be a "fusion boundary." The caller would be responsible for not using f.(args...) in cases where fusion would screw up side effects. fusion of nested f.(args) calls into a single broadcast call #17300
• Define x .= ... as "fusing" calls to broadcast!, e.g. x .= sin.(x .+ y) would act in-place with a single loop. Again, this would occur at the syntax level, so the caller would be responsible for avoiding function calls with problematic side effects. (See make .+= et al. mutating LinearAlgebra.jl#119, but the lack of loop fusion at that time made .+= much less attractive.) treat .= as syntactic sugar for broadcast! #17510

[andyferris]

Regarding the third point, can we do .= as broadcast! without worrying overly about loop fusion?

As in A .= B as broadcast!(x->x, A, B) as an element-wise copy. Of course, more complex expressions would require more complex loop fusion, but this gives some moderate gain. .+= and so-on are very low-hanging fruit for at least removing one layer of allocation very simply.

(Hmm... that last one makes me think if .sin= is good syntax? As in A .sin= B being like Julia 0.4 A[:] = sin(B[:]) I'm being more than a bit silly here, but it works similarly to the . prefix version like .sin(x) rather than suffix sin.(x). It even kinda nests: A .exp.sin= x. Quite ugly though, and messes with scoping/field syntax)

[stevengj]

@andyferris, without loop fusion, an in-place .= is pretty useless. An expression like x .= 4y .+ 5y.^2 .- sin.(y) will still allocate lots of temporary arrays. If you just want element-wise copy, you can already do A[:] = B.

[andyferris]

@stevengj I agree that it is (almost) useless, except for an alternative copy syntax. It's just "step zero" - it's dirt simple and provides the precedence for "step one" as doing similarly for .+= and all the other op= with a prefix ., which then starts to be useful, for things like x .+= 1 or something to be non-allocating where x is an Array. In fact, the number of op= operators currently defined is relatively small... so it shouldn't be too hard to define them all.

"Step 2" would be the more complex loop fusion or similar, and perhaps generalizations to generic functions.

On the whole, I do have to support what Jeff said in #14544 (comment). Perhaps the cleaner approach is to have some neat syntax for map/broadcast (and hopefully where loop fusion is clear to the user or compiler). I dunno.

[stevengj]

@andyferris, that discussion is out of date. We now do have a neat syntax for broadcast, and the possibility for loop fusion is now exposed to the compiler at the syntax level. And the since that syntax is ., generalized dot operators now make a lot more sense.

[andyferris]

@stevengj Sorry, I missed the last week or so of #8450 (it's really hard to keep up with all the threads!).

In any case, the progress seems very cool! The parser-based loop fusion (e.g. your #8450 (comment) seems like a great option to me. Any more complex things can still be done with loops, comprehensions, map and broadcast explicitly.

[diegozea]

A @fuse macro can be more safe than making the loop fusion at parser level, can't it?

[yuyichao]

What's the advantage? We already have that Devectorize.jl and I don't think It will be more flexible or give you more control.

[diegozea]

I'm only worry about making loop fusion everywhere. "The caller would be responsible for avoiding function calls with problematic side effects" but... How can the user use the point notation and avoid the fusion at the same time? Also I think that @fuse will be more explicit to write and to read in the code. @fuse can do the same proposed loop fusion, but It can also check the functions to be called (i.e. annotated pure functions). The last isn't possible at syntax level.

[yuyichao]

The caller would be responsible for avoiding function calls with problematic side effects

I think this is not an issue for the majority of cases.

How can the user use the point notation and avoid the fusion at the same time?

Split the line

but It can also check the functions to be called (i.e. annotated pure functions).

This is impossible. Or at least it won't be better at doing that.

[stevengj]

@diegozea, macros operate at the syntax level, without knowing types, so they can't check pureness. Same for the proposed f.(args...) fusing. (In practice, though, vectorized operations are virtually never used in cases with side effects, much less side effects that would be effected by fusion. And if f.(args...) is defined as always fusing, then you can reliably know what to expect.)

Think of f.(args...) as a much more compact and discoverable syntax for @fuse. (Once we deprecate e.g. sin(x) in favor of sin.(x) etcetera, people doing Matlab-like computations will end up using fused loops automatically in many case due to the deprecation warning, whereas they might never learn about @fuse.)