Skip to content

Rewrite of sum()*constant is suboptimal #169

@odow

Description

@odow

Consider:

julia> import MutableArithmetics

julia> @macroexpand MutableArithmetics.@rewrite(sum(i for i in 1:2) * 2)
quote
    #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:293 =#
    let
        #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:294 =#
        begin
            var"#892###928" = (MutableArithmetics.MutableArithmetics).Zero()
            begin
                for i = 1:2
                    var"#892###928" = (MutableArithmetics.MutableArithmetics).operate!!((MutableArithmetics.MutableArithmetics).add_mul, var"#892###928", i, 2)
                end
                var"#893###927" = var"#892###928"
            end
        end
        #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:295 =#
        var"#893###927"
    end
end

julia> @macroexpand MutableArithmetics.@rewrite(sum(i for i in 1:2) / 2)
quote
    #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:293 =#
    let
        #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:294 =#
        begin
            var"#896###930" = (MutableArithmetics.MutableArithmetics).Zero()
            begin
                for i = 1:2
                    var"#896###930" = (MutableArithmetics.MutableArithmetics).operate!!((MutableArithmetics.MutableArithmetics).add_mul, var"#896###930", i, 1 / 2)
                end
                var"#897###929" = var"#896###930"
            end
        end
        #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:295 =#
        var"#897###929"
    end
end

julia> @macroexpand MutableArithmetics.@rewrite(2 * sum(i for i in 1:2))
quote
    #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:293 =#
    let
        #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:294 =#
        begin
            var"#908###936" = (MutableArithmetics.MutableArithmetics).Zero()
            begin
                for i = 1:2
                    var"#908###936" = (MutableArithmetics.MutableArithmetics).operate!!((MutableArithmetics.MutableArithmetics).add_mul, var"#908###936", 2, i)
                end
                var"#909###935" = var"#908###936"
            end
        end
        #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:295 =#
        var"#909###935"
    end
end

julia> @macroexpand MutableArithmetics.@rewrite(2 / sum(i for i in 1:2))
quote
    #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:293 =#
    let
        #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:294 =#
        begin
            var"#912###938" = (MutableArithmetics.MutableArithmetics).Zero()
            var"#913###937" = (MutableArithmetics.MutableArithmetics).operate!!((MutableArithmetics.MutableArithmetics).add_mul, var"#912###938", 2, 1 / sum((i for i = 1:2)))
        end
        #= /Users/oscar/.julia/packages/MutableArithmetics/maUDe/src/rewrite.jl:295 =#
        var"#913###937"
    end
end

All cases are troubling:

  • The 1st and 3rd examples leads to n additional * operations
  • The 2nd example leads to n additional / operations
  • The 4th doesn't even use mutation.

This came up digging into this example in jump-dev/JuMP.jl#3106:

@objective(
    model,
    Max,
    n / 2 * log(1 / (2 * π * σ^2)) -
    sum((data[i] - μ)^2 for i in 1:n) / (2 * σ^2)
)

The first step brigs the denominator into the loop:

@objective(
    model,
    Max,
    n / 2 * log(1 / (2 * π * σ^2)) -
    sum((data[i] - μ)^2 * (1 / (2 * σ^2)) for i in 1:n)
)

but then, even worse, it brings the - into the loop:

term = n / 2 * log(1 / (2 * π * σ^2))
for i in 1:n
    sub_mul(term, (data[i] - μ)^2, 1 / (2 * σ^2))
end
@objective(model, Max, term)

a better outcome would be something along the lines of

term = n / 2 * log(1 / (2 * π * σ^2))
sum_term = 0
for i in 1:n
    add_mul(term, (data[i] - μ)^2)
end
obj = operate(-, term, operate(/, sub_term, 2 * σ^2))
@objective(model, Max, obj)

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions