x.*x not customizable #22053

malmaud · 2017-05-24T22:07:39Z

There doesn't seem to be a way to get x.*x to do something different than x*x, as the following perhaps naive example shows:

import Base: *

type T
    t
end

Base.broadcast(::typeof(*), t1::T, t2::T) = 1
*(t1::T, t2::T) = 2
x = T(1)
x*x # Prints 2

x.*x # Also prints 2

If there really isn't a way, this is a non-trivial breaking regression in functionality compared to .5 that some packages depended upon.

The text was updated successfully, but these errors were encountered:

KristofferC · 2017-05-24T22:10:08Z

julia> import Base: *

julia> type T
           t
       end

julia> Base.broadcast(::typeof(*), t1::T, t2::T) = 1

julia> *(t1::T, t2::T) = 2
* (generic function with 182 methods)

julia> T(1)*T(2) # Prints 2
2

julia> T(1).*T(2) # Also prints 2
1

?

malmaud · 2017-05-24T22:13:50Z

What version are you on?

KristofferC · 2017-05-24T22:21:26Z

0.6-rc2

mbauman · 2017-05-24T22:24:55Z

Right, the problem is when you use a repeated symbol:

julia> x = T(1)
T(1)

julia> x .* x
2

Because:

julia> expand(:(T(1).*T(2)))
:((Base.broadcast)(*, T(1), T(2)))

julia> expand(:(x.*x))
:($(Expr(:thunk, CodeInfo(:(begin
        $(Expr(:thunk, CodeInfo(:(begin
… # effectively broadcast(y->y*y, x)

malmaud · 2017-05-24T22:30:05Z

Ah woops, I wrote my example wrong. I'll edit it.

andyferris · 2017-05-24T23:06:41Z

Function-based implementations of broadcast seem rather fragile. I think it's only suitable as an optimization to get the same result, and even then it's bad to have users rely upon the optimization...

oxinabox · 2017-05-25T06:11:18Z

Function-based implementations of broadcast seem rather fragile.

They are rather common.
Eg @SimonDanisch wrt: https://github.com/JuliaGPU/GPUArrays.jl/blob/master/src/abstractarray.jl#L182-L224

cf: FluxML/Flux.jl#31
cf: malmaud/TensorFlow.jl#135

andyferris · 2017-05-25T06:33:43Z

Yes, they are common and they are really useful!

But if they are fragile, then they will always feel like a bit of a hack. The fundamental problem of equating functions which "do the same thing", e.g. so that (x...) -> f(x...) == f, will probably never be solved. I don't know how to progress beyond that, but it would be nice to find a way to do this kind of thing.

nalimilan · 2017-05-25T08:59:06Z

I think the current design assumes that function-based implementations are optimizations, but should implement the same behavior as the default broadcast version. I guess @stevengj can confirm.

stevengj · 2017-05-25T15:42:19Z

Yes, @nalimilan. Overriding broadcast for particular functions should ordinarily not be done, and at most should be done as an optimization only.

Because of fusion, it will never be possible to guarantee that broadcast(::typeof(f), ...) is called for a particular f. For example, consider x .* y .* z — this will get lowered to broadcast((x,y,z) -> x*y*z, x,y,z), meaning that a specialized broadcast(::typeof(*), ...) method will not be called.

(In addition to that, there are some internal optimizations to the lowering for repeated symbols, numeric literals, etcetera, aimed at expressions like @. (3x+4x^2-6)/(x^2 + 1). That's what @malmaud noticed above. But even if we removed these optimizations, the fusion would still remain.)

stevengj · 2017-05-25T15:44:44Z

Note that broadcast methods in GPUArrays are entirely different, because they are for broadcast(f::Function, ...) on any f — this is entirely appropriate to define for custom container types.

(GPUArrays probably should have used a generated function to handle arbitrary mixtures of scalars and numbers, and in general we should make broadcast easier to overload for custom container types, but that is a separate issue.)

mlubin · 2017-05-25T17:01:01Z

CC @madeleineudell jump-dev/Convex.jl#192 (comment)

ghost · 2017-05-25T23:40:59Z

There's a workaround in ArrayFire.jl: https://github.com/gaika/ArrayFire.jl/blob/master/src/array.jl#L130

By overriding broadcast() and saving the state in a global variable it is possible to do something different.

ExpandingMan · 2017-05-30T15:59:48Z

+1 to this being a serious issue that breaks lots of things

One of the underlying issues here is that Hadamard products and "loop over multiplication" (or other operations) aren't necessarily the same thing, at least from a software perspective. Users override broadcast(*,...) to mean Hadamard products even in cases where this doesn't imply a loop over *, however the emerging semantics of Julia are that .* necessarily implies such a loop. The solution is probably for users to switch to ⊙ in such cases, but I don't see that happening any time soon.

…ed syntax for .*, ./, and .^ to dot(*), dot(/), and dot(^) in the file broadcast.jl

fix #21094 fix #22060 fix #22053 replaces #22063

Among other things, this supports returning AbstractRanges for appropriate inputs. Fixes #21094, fixes #22053

@lower

This patch represents the combined efforts of four individuals, over 60 commits, and an iterated design over (at least) three pull requests that spanned nearly an entire year (closes #22063, #23692, #25377 by superceding them). This introduces a pure Julia data structure that represents a fused broadcast expression. For example, the expression `2 .* (x .+ 1)` lowers to: ```julia julia> Meta.@lower 2 .* (x .+ 1) :($(Expr(:thunk, CodeInfo(:(begin Core.SSAValue(0) = (Base.getproperty)(Base.Broadcast, :materialize) Core.SSAValue(1) = (Base.getproperty)(Base.Broadcast, :make) Core.SSAValue(2) = (Base.getproperty)(Base.Broadcast, :make) Core.SSAValue(3) = (Core.SSAValue(2))(+, x, 1) Core.SSAValue(4) = (Core.SSAValue(1))(*, 2, Core.SSAValue(3)) Core.SSAValue(5) = (Core.SSAValue(0))(Core.SSAValue(4)) return Core.SSAValue(5) end))))) ``` Or, slightly more readably as: ```julia using .Broadcast: materialize, make materialize(make(*, 2, make(+, x, 1))) ``` The `Broadcast.make` function serves two purposes. Its primary purpose is to construct the `Broadcast.Broadcasted` objects that hold onto the function, the tuple of arguments (potentially including nested `Broadcasted` arguments), and sometimes a set of `axes` to include knowledge of the outer shape. The secondary purpose, however, is to allow an "out" for objects that _don't_ want to participate in fusion. For example, if `x` is a range in the above `2 .* (x .+ 1)` expression, it needn't allocate an array and operate elementwise — it can just compute and return a new range. Thus custom structures are able to specialize `Broadcast.make(f, args...)` just as they'd specialize on `f` normally to return an immediate result. `Broadcast.materialize` is identity for everything _except_ `Broadcasted` objects for which it allocates an appropriate result and computes the broadcast. It does two things: it `initialize`s the outermost `Broadcasted` object to compute its axes and then `copy`s it. Similarly, an in-place fused broadcast like `y .= 2 .* (x .+ 1)` uses the exact same expression tree to compute the right-hand side of the expression as above, and then uses `materialize!(y, make(*, 2, make(+, x, 1)))` to `instantiate` the `Broadcasted` expression tree and then `copyto!` it into the given destination. All-together, this forms a complete API for custom types to extend and customize the behavior of broadcast (fixes #22060). It uses the existing `BroadcastStyle`s throughout to simplify dispatch on many arguments: * Custom types can opt-out of broadcast fusion by specializing `Broadcast.make(f, args...)` or `Broadcast.make(::BroadcastStyle, f, args...)`. * The `Broadcasted` object computes and stores the type of the combined `BroadcastStyle` of its arguments as its first type parameter, allowing for easy dispatch and specialization. * Custom Broadcast storage is still allocated via `broadcast_similar`, however instead of passing just a function as a first argument, the entire `Broadcasted` object is passed as a final argument. This potentially allows for much more runtime specialization dependent upon the exact expression given. * Custom broadcast implmentations for a `CustomStyle` are defined by specializing `copy(bc::Broadcasted{CustomStyle})` or `copyto!(dest::AbstractArray, bc::Broadcasted{CustomStyle})`. * Fallback broadcast specializations for a given output object of type `Dest` (for the `DefaultArrayStyle` or another such style that hasn't implemented assignments into such an object) are defined by specializing `copyto(dest::Dest, bc::Broadcasted{Nothing})`. As it fully supports range broadcasting, this now deprecates `(1:5) + 2` to `.+`, just as had been done for all `AbstractArray`s in general. As a first-mover proof of concept, LinearAlgebra uses this new system to improve broadcasting over structured arrays. Before, broadcasting over a structured matrix would result in a sparse array. Now, broadcasting over a structured matrix will _either_ return an appropriately structured matrix _or_ a dense array. This does incur a type instability (in the form of a discriminated union) in some situations, but thanks to type-based introspection of the `Broadcasted` wrapper commonly used functions can be special cased to be type stable. For example: ```julia julia> f(d) = round.(Int, d) f (generic function with 1 method) julia> @inferred f(Diagonal(rand(3))) 3×3 Diagonal{Int64,Array{Int64,1}}: 0 ⋅ ⋅ ⋅ 0 ⋅ ⋅ ⋅ 1 julia> @inferred Diagonal(rand(3)) .* 3 ERROR: return type Diagonal{Float64,Array{Float64,1}} does not match inferred return type Union{Array{Float64,2}, Diagonal{Float64,Array{Float64,1}}} Stacktrace: [1] error(::String) at ./error.jl:33 [2] top-level scope julia> @inferred Diagonal(1:4) .+ Bidiagonal(rand(4), rand(3), 'U') .* Tridiagonal(1:3, 1:4, 1:3) 4×4 Tridiagonal{Float64,Array{Float64,1}}: 1.30771 0.838589 ⋅ ⋅ 0.0 3.89109 0.0459757 ⋅ ⋅ 0.0 4.48033 2.51508 ⋅ ⋅ 0.0 6.23739 ``` In addition to the issues referenced above, it fixes: * Fixes #19313, #22053, #23445, and #24586: Literals are no longer treated specially in a fused broadcast; they're just arguments in a `Broadcasted` object like everything else. * Fixes #21094: Since broadcasting is now represented by a pure Julia datastructure it can be created within `@generated` functions and serialized. * Fixes #26097: The fallback destination-array specialization method of `copyto!` is specifically implemented as `Broadcasted{Nothing}` and will not be confused by `nothing` arguments. * Fixes the broadcast-specific element of #25499: The default base broadcast implementation no longer depends upon `Base._return_type` to allocate its array (except in the empty or concretely-type cases). Note that the sparse implementation (#19595) is still dependent upon inference and is _not_ fixed. * Fixes #25340: Functions are treated like normal values just like arguments and only evaluated once. * Fixes #22255, and is performant with 12+ fused broadcasts. Okay, that one was fixed on master already, but this fixes it now, too. * Fixes #25521. * The performance of this patch has been thoroughly tested through its iterative development process in #25377. There remain [two classes of performance regressions](#25377) that Nanosoldier flagged. * #25691: Propagation of constant literals sill lose their constant-ness upon going through the broadcast machinery. I believe quite a large number of functions would need to be marked as `@pure` to support this -- including functions that are intended to be specialized. (For bookkeeping, this is the squashed version of the [teh-jn/lazydotfuse](#25377) branch as of a1d4e7e. Squashed and separated out to make it easier to review and commit) Co-authored-by: Tim Holy <[email protected]> Co-authored-by: Jameson Nash <[email protected]> Co-authored-by: Andrew Keller <[email protected]>

@lower

This patch represents the combined efforts of four individuals, over 60 commits, and an iterated design over (at least) three pull requests that spanned nearly an entire year (closes #22063, #23692, #25377 by superceding them). This introduces a pure Julia data structure that represents a fused broadcast expression. For example, the expression `2 .* (x .+ 1)` lowers to: ```julia julia> Meta.@lower 2 .* (x .+ 1) :($(Expr(:thunk, CodeInfo(:(begin Core.SSAValue(0) = (Base.getproperty)(Base.Broadcast, :materialize) Core.SSAValue(1) = (Base.getproperty)(Base.Broadcast, :make) Core.SSAValue(2) = (Base.getproperty)(Base.Broadcast, :make) Core.SSAValue(3) = (Core.SSAValue(2))(+, x, 1) Core.SSAValue(4) = (Core.SSAValue(1))(*, 2, Core.SSAValue(3)) Core.SSAValue(5) = (Core.SSAValue(0))(Core.SSAValue(4)) return Core.SSAValue(5) end))))) ``` Or, slightly more readably as: ```julia using .Broadcast: materialize, make materialize(make(*, 2, make(+, x, 1))) ``` The `Broadcast.make` function serves two purposes. Its primary purpose is to construct the `Broadcast.Broadcasted` objects that hold onto the function, the tuple of arguments (potentially including nested `Broadcasted` arguments), and sometimes a set of `axes` to include knowledge of the outer shape. The secondary purpose, however, is to allow an "out" for objects that _don't_ want to participate in fusion. For example, if `x` is a range in the above `2 .* (x .+ 1)` expression, it needn't allocate an array and operate elementwise — it can just compute and return a new range. Thus custom structures are able to specialize `Broadcast.make(f, args...)` just as they'd specialize on `f` normally to return an immediate result. `Broadcast.materialize` is identity for everything _except_ `Broadcasted` objects for which it allocates an appropriate result and computes the broadcast. It does two things: it `initialize`s the outermost `Broadcasted` object to compute its axes and then `copy`s it. Similarly, an in-place fused broadcast like `y .= 2 .* (x .+ 1)` uses the exact same expression tree to compute the right-hand side of the expression as above, and then uses `materialize!(y, make(*, 2, make(+, x, 1)))` to `instantiate` the `Broadcasted` expression tree and then `copyto!` it into the given destination. All-together, this forms a complete API for custom types to extend and customize the behavior of broadcast (fixes #22060). It uses the existing `BroadcastStyle`s throughout to simplify dispatch on many arguments: * Custom types can opt-out of broadcast fusion by specializing `Broadcast.make(f, args...)` or `Broadcast.make(::BroadcastStyle, f, args...)`. * The `Broadcasted` object computes and stores the type of the combined `BroadcastStyle` of its arguments as its first type parameter, allowing for easy dispatch and specialization. * Custom Broadcast storage is still allocated via `broadcast_similar`, however instead of passing just a function as a first argument, the entire `Broadcasted` object is passed as a final argument. This potentially allows for much more runtime specialization dependent upon the exact expression given. * Custom broadcast implmentations for a `CustomStyle` are defined by specializing `copy(bc::Broadcasted{CustomStyle})` or `copyto!(dest::AbstractArray, bc::Broadcasted{CustomStyle})`. * Fallback broadcast specializations for a given output object of type `Dest` (for the `DefaultArrayStyle` or another such style that hasn't implemented assignments into such an object) are defined by specializing `copyto(dest::Dest, bc::Broadcasted{Nothing})`. As it fully supports range broadcasting, this now deprecates `(1:5) + 2` to `.+`, just as had been done for all `AbstractArray`s in general. As a first-mover proof of concept, LinearAlgebra uses this new system to improve broadcasting over structured arrays. Before, broadcasting over a structured matrix would result in a sparse array. Now, broadcasting over a structured matrix will _either_ return an appropriately structured matrix _or_ a dense array. This does incur a type instability (in the form of a discriminated union) in some situations, but thanks to type-based introspection of the `Broadcasted` wrapper commonly used functions can be special cased to be type stable. For example: ```julia julia> f(d) = round.(Int, d) f (generic function with 1 method) julia> @inferred f(Diagonal(rand(3))) 3×3 Diagonal{Int64,Array{Int64,1}}: 0 ⋅ ⋅ ⋅ 0 ⋅ ⋅ ⋅ 1 julia> @inferred Diagonal(rand(3)) .* 3 ERROR: return type Diagonal{Float64,Array{Float64,1}} does not match inferred return type Union{Array{Float64,2}, Diagonal{Float64,Array{Float64,1}}} Stacktrace: [1] error(::String) at ./error.jl:33 [2] top-level scope julia> @inferred Diagonal(1:4) .+ Bidiagonal(rand(4), rand(3), 'U') .* Tridiagonal(1:3, 1:4, 1:3) 4×4 Tridiagonal{Float64,Array{Float64,1}}: 1.30771 0.838589 ⋅ ⋅ 0.0 3.89109 0.0459757 ⋅ ⋅ 0.0 4.48033 2.51508 ⋅ ⋅ 0.0 6.23739 ``` In addition to the issues referenced above, it fixes: * Fixes #19313, #22053, #23445, and #24586: Literals are no longer treated specially in a fused broadcast; they're just arguments in a `Broadcasted` object like everything else. * Fixes #21094: Since broadcasting is now represented by a pure Julia datastructure it can be created within `@generated` functions and serialized. * Fixes #26097: The fallback destination-array specialization method of `copyto!` is specifically implemented as `Broadcasted{Nothing}` and will not be confused by `nothing` arguments. * Fixes the broadcast-specific element of #25499: The default base broadcast implementation no longer depends upon `Base._return_type` to allocate its array (except in the empty or concretely-type cases). Note that the sparse implementation (#19595) is still dependent upon inference and is _not_ fixed. * Fixes #25340: Functions are treated like normal values just like arguments and only evaluated once. * Fixes #22255, and is performant with 12+ fused broadcasts. Okay, that one was fixed on master already, but this fixes it now, too. * Fixes #25521. * The performance of this patch has been thoroughly tested through its iterative development process in #25377. There remain [two classes of performance regressions](#25377) that Nanosoldier flagged. * #25691: Propagation of constant literals sill lose their constant-ness upon going through the broadcast machinery. I believe quite a large number of functions would need to be marked as `@pure` to support this -- including functions that are intended to be specialized. (For bookkeeping, this is the squashed version of the [teh-jn/lazydotfuse](#25377) branch as of a1d4e7e. Squashed and separated out to make it easier to review and commit) Co-authored-by: Tim Holy <[email protected]> Co-authored-by: Jameson Nash <[email protected]> Co-authored-by: Andrew Keller <[email protected]>

nalimilan added the domain:broadcast Applying a function over a collection label May 25, 2017

stevengj mentioned this issue May 25, 2017

better internal interface for extending broadcast #22060

Closed

This was referenced May 30, 2017

update for Julia v0.6 dmlc/MXNet.jl#248

Merged

method error when using .* between identical symbols on 0.6 dmlc/MXNet.jl#253

Closed

mlubin referenced this issue in jump-dev/Convex.jl Jun 21, 2017

compatibility with v0.6: mostly, added .s for broadcasting, and chang…

ba00f76

…ed syntax for .*, ./, and .^ to dot(*), dot(/), and dot(^) in the file broadcast.jl

This was referenced Jul 3, 2017

No method matching for overloaded dot operator #22662

Closed

Use dot operators for broadcasting elementwise operations in AD probcomp/GenExperimental.jl#46

Open

mlubin mentioned this issue Jul 24, 2017

performance hints jump-dev/MathOptInterface.jl#63

Closed

stevengj mentioned this issue Aug 25, 2017

Fix docs explaining broadcasting, or change behaviour of min.(1,f) #23445

Closed

vtjnash self-assigned this Sep 9, 2017

vtjnash added a commit that referenced this issue Sep 12, 2017

introduce runtime representation of broadcast fusion

a13aacd

fix #21094 fix #22060 fix #22053 replaces #22063

vtjnash added a commit that referenced this issue Sep 12, 2017

introduce runtime representation of broadcast fusion

bfd0a3e

fix #21094 fix #22060 fix #22053 replaces #22063

vtjnash added a commit that referenced this issue Sep 13, 2017

introduce runtime representation of broadcast fusion

535fefa

fix #21094 fix #22060 fix #22053 replaces #22063

vtjnash mentioned this issue Sep 13, 2017

RFC: introduce runtime representation of broadcast fusion #23692

Closed

timholy added a commit that referenced this issue Jan 3, 2018

Test fixes to #21094, #22053

53b3d14

timholy added a commit that referenced this issue Jan 3, 2018

Integrate lazy broadcast representation into new broadcast machinery

a049a70

Among other things, this supports returning AbstractRanges for appropriate inputs. Fixes #21094, fixes #22053

timholy mentioned this issue Jan 3, 2018

RFC: Customizable lazy broadcasting with options for pure-Julia fusion and eager evaluation #25377

Closed

timholy added a commit that referenced this issue Jan 7, 2018

Integrate lazy broadcast representation into new broadcast machinery

9115e1f

Among other things, this supports returning AbstractRanges for appropriate inputs. Fixes #21094, fixes #22053

timholy added a commit that referenced this issue Jan 7, 2018

Integrate lazy broadcast representation into new broadcast machinery

0698edc

Among other things, this supports returning AbstractRanges for appropriate inputs. Fixes #21094, fixes #22053

mbauman mentioned this issue Apr 24, 2018

Customizable lazy fused broadcasting in pure Julia #26891

Merged

mbauman closed this as completed in #26891 Apr 26, 2018

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

x.*x not customizable #22053

x.*x not customizable #22053

malmaud commented May 24, 2017 •

edited

Loading

KristofferC commented May 24, 2017 •

edited

Loading

malmaud commented May 24, 2017

KristofferC commented May 24, 2017

mbauman commented May 24, 2017

malmaud commented May 24, 2017

andyferris commented May 24, 2017

oxinabox commented May 25, 2017

andyferris commented May 25, 2017

nalimilan commented May 25, 2017

stevengj commented May 25, 2017

stevengj commented May 25, 2017 •

edited

Loading

mlubin commented May 25, 2017

ghost commented May 25, 2017 •

edited by ghost

Loading

ExpandingMan commented May 30, 2017 •

edited

Loading

x.*x not customizable #22053

x.*x not customizable #22053

Comments

malmaud commented May 24, 2017 • edited Loading

KristofferC commented May 24, 2017 • edited Loading

malmaud commented May 24, 2017

KristofferC commented May 24, 2017

mbauman commented May 24, 2017

malmaud commented May 24, 2017

andyferris commented May 24, 2017

oxinabox commented May 25, 2017

andyferris commented May 25, 2017

nalimilan commented May 25, 2017

stevengj commented May 25, 2017

stevengj commented May 25, 2017 • edited Loading

mlubin commented May 25, 2017

ghost commented May 25, 2017 • edited by ghost Loading

ExpandingMan commented May 30, 2017 • edited Loading

malmaud commented May 24, 2017 •

edited

Loading

KristofferC commented May 24, 2017 •

edited

Loading

stevengj commented May 25, 2017 •

edited

Loading

ghost commented May 25, 2017 •

edited by ghost

Loading

ExpandingMan commented May 30, 2017 •

edited

Loading