# Strange performance issue on 1.9.0-rc3

**URL:** <https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427>\
**Category:** Performance\
**Tags:** question, package\
**Created:** [May 7, 2023, 1:50am UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427 "2023-05-07T01:50:59Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![MilesCranmer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/milescranmer/32/21070_2.png) [@MilesCranmer](https://discourse.julialang.org/u/MilesCranmer)\
**Post date:** [May 7, 2023, 1:50am UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427/1 "2023-05-07T01:50:59Z")

</div>

I’m seeing a weird performance issue related to the presence of an if-statement in my function, _regardless of the if-statement being triggered or not_. I can only reproduce this in `1.9.0`, not earlier Julia versions.

I have a function called [`tree_mapreduce`](https://github.com/SymbolicML/DynamicExpressions.jl/blob/8b97f362f33b8357b116c9d87287469b5aa50814/src/tree_map.jl#L92) which has two different modes of behavior configured by the `preserve_sharing` flag:

```julia
function tree_mapreduce(
    args...;
    preserve_sharing::Bool=false,
    result_type::Type{RT}=Nothing,
)
    if preserve_sharing && result_type != Nothing
        return _tree_mapreduce(args..., IdDict{Node,RT}())
    else
        return _tree_mapreduce(args...)
    end
end

```

(simplified version; here is the [full implementation](https://github.com/SymbolicML/DynamicExpressions.jl/blob/8b97f362f33b8357b116c9d87287469b5aa50814/src/tree_map.jl#L92))

This function is used for copies of my `Node{T}` type in the [`copy_node`](https://github.com/SymbolicML/DynamicExpressions.jl/blob/8b97f362f33b8357b116c9d87287469b5aa50814/src/tree_map.jl#L331-L340) function. When it has an extra argument, it has slightly different behavior. With this implementation, I get the following benchmark times:

```julia
using DynamicExpressions

# Create expression tree
operators = OperatorEnum(; binary_operators=[+, -, *, /], unary_operators=[cos, sin])
x1, x2, x3 = (i -> Node(Float64; feature=i).(1:3)
tree = cos(x1 * 3.2 - 5.8) * 0.2 - 0.5 * x2 * x3 * x3 + 0.9 / (x1 * x1 + 1)

# Benchmark:
@btime copy_node(tree; preserve_sharing=false)

```

This gives me **682.752 ns (26 allocations: 2.02 KiB)**.

Note that `preserve_sharing` is set to false.

However, when I simply change the function to be

```julia
function tree_mapreduce(
    f_leaf::F1,
    f_branch::F2,
    op::G,
    tree::N;
    preserve_sharing::Bool=false,
    result_type::Type{RT}=Nothing,
) where {T,N<:Node{T},F1<:Function,F2<:Function,G<:Function,RT}
    #if preserve_sharing
    # return _tree_mapreduce(f_leaf, f_branch, op, tree, IdDict{N,RT}())
    #else
    return _tree_mapreduce(f_leaf, f_branch, op, tree)
    #end
end

```

and re-run the benchmark, I obtain the result **285.015 ns (24 allocations: 1.88 KiB)**

Why is the simple presence of that if-statement harming performance so dramatically? I note that for `preserve_sharing=true`, the performance is significantly higher, so I don’t think that branch is actually being executed.

* * *

Additional notes:

- I ran the above benchmarks with `-O3`. But running _without_ seems to make the second benchmark slightly worse, and thus the times slightly closer together in performance.
- I ran the benchmarks with the return type annotated on `tree_mapreduce`, which didn’t seem to change the performance.
- **On Julia 1.8.5, the timings are nearly identical.**
- Another weird thing I noticed is that if I am using Revise.jl, and make this edit, and then go back, the time of about ~700 ns will go down to ~460 ns, even though it’s the identical function. Even if I call the function many many times in between. It’s almost like the compilation is improved by Revising the function multiple times.

* * *

Edit: added the full function signature as it appears relevant

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [May 7, 2023, 4:17am UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427/2 "2023-05-07T04:17:24Z")

</div>

> [@MilesCranmer](#):
>
> `@btime copy_node(tree`

Probably not related, but shouldn’t `tree` be interpolated here for the benchmark?

---

<div class="post-metadata">

**Author:** ![MilesCranmer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/milescranmer/32/21070_2.png) [@MilesCranmer](https://discourse.julialang.org/u/MilesCranmer)\
**Post date:** [May 7, 2023, 5:04am UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427/3 "2023-05-07T05:04:55Z")

</div>

You are correct. Sadly it doesn’t fix the weird results though.

---

<div class="post-metadata">

**Author:** ![MilesCranmer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/milescranmer/32/21070_2.png) [@MilesCranmer](https://discourse.julialang.org/u/MilesCranmer)\
**Post date:** [May 7, 2023, 5:17am UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427/4 "2023-05-07T05:17:37Z")

</div>

More weirdness (/clues). If I manually expand the contents of `copy_node`, the performance gap goes away:

```julia
@btime(
  tree_mapreduce(
    t -> t.constant ? Node(; val=t.val::Float64) : Node(Float64; feature=t.feature),
    identity,
    (p, c...) -> Node(p.op, c...),
    ctree;
    preserve_sharing=false
  ),
  setup=(ctree=copy_node($tree))
)
# ~ 282 ns

```

**BUT** if I also manually pass the `result_type`, the performance gap comes back:

```julia
@btime(
  tree_mapreduce(
    t -> t.constant ? Node(; val=t.val::Float64) : Node(Float64; feature=t.feature),
    identity,
    (p, c...) -> Node(p.op, c...),
    ctree;
    preserve_sharing=false,
    result_type=Nothing
  ),
  setup=(ctree=copy_node($tree))
)
# ~474 ns

```

which is very strange because `result_type=Nothing` is the default value!!

---

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [May 7, 2023, 1:14pm UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427/5 "2023-05-07T13:14:40Z")

</div>

I only glanced, but the implementation is clearly recursive. If types can change, inference hates recursion. Anything that hoists the final type into a caller will suddenly make inference much happier.

Try running Cthulhu over this and fix any inferrability problems you see. I think @jishnub has been doing the exact same task over the ApproxFun ecosystem with excellent results (and who has been a faithful bug reporter in the Cthulhu repository, he’s a real hero for it).

---

<div class="post-metadata">

**Author:** ![MilesCranmer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/milescranmer/32/21070_2.png) [@MilesCranmer](https://discourse.julialang.org/u/MilesCranmer)\
**Post date:** [May 7, 2023, 8:58pm UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427/6 "2023-05-07T20:58:13Z")

</div>

Thanks @tim.holy, I will try it out. The return type is (should be) constant throughout the recursion, but perhaps there is a part I need to annotate to help the compiler.

---

<div class="post-metadata">

**Author:** ![MilesCranmer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/milescranmer/32/21070_2.png) [@MilesCranmer](https://discourse.julialang.org/u/MilesCranmer)\
**Post date:** [May 7, 2023, 10:20pm UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427/7 "2023-05-07T22:20:31Z")

</div>

Okay I think I might have figured out the issue thanks to Cthulhu:

 ![image](https://global.discourse-cdn.com/julialang/original/3X/2/4/2493e1248bd1f6ef572d34c68cadfb57ad37d2d5.png)

I did not realize this, but apparently Julia does not perform multiple dispatch on keyword arguments? Is that (still) true?

> [@Force specialization on kwargs](https://discourse.julialang.org/t/force-specialization-on-kwargs/34789):
>
> If I have a function like this: f\_vararg(varargs::Int...) = tuple(varargs...) I can force specialization on varargs with either of the following: g\_vararg(varargs::Vararg{Int, N}) where {N} = tuple(varargs...) h\_vararg(varargs::Vararg{\<:Any, N}) where {N} = tuple(varargs...) Now suppose instead that I have a function like this: f\_kwarg(; kwargs...) = (; kwargs...) How can I force specialization on the keyword arguments?

If so then I suppose I need to specify this `result_type` as a normal argument, rather than a kwarg. Otherwise it thinks the return type is `Any`, because `result_type` could be anything.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [May 7, 2023, 10:30pm UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427/8 "2023-05-07T22:30:04Z")

</div>

Yes, this is true, and I do not believe it will ever change, even in Julia 2.0 (which may never come). However, you can annotate the type of a keyword parameter, so to say to Julia that, in that method body, no other type could be passed.

---

<div class="post-metadata">

**Author:** ![tim.holy](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tim.holy/32/52_2.png) [@tim.holy](https://discourse.julialang.org/u/tim.holy)\
**Post date:** [May 7, 2023, 10:38pm UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427/9 "2023-05-07T22:38:00Z")

</div>

It does specialize on kwargs, in the sense that supplying `kwarg=1` and `kwarg=1.0` will generate different compiled code. Likewise, as Henrique says you can constrain the types of kwargs. But you can’t dispatch on them (dispatch=control which method gets called) because you can’t have two Methods with identical positional arguments but different sets of kwargs—and when there’s only one method, there’s nothing to dispatch on.

In this case you’re probably encountering weird issues with specialization heuristics. Julia specializes on `x` by compiling a version for `typeof(x)`, but when `x` is a `Type` then `typeof(x)` is `DataType` which seems not to be what you want to happen here. The `Type{RT}` is the escape-hatch, but in this case things are confusing because `return_type` and `RT` are nominally identical yet may be subject to different specialization heuristics and behavior with respect to this escape hatch. In this case, indeed it seems that the requirement to pass kwargs by name is causing the issue.

---

<div class="post-metadata">

**Author:** ![MilesCranmer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/milescranmer/32/21070_2.png) [@MilesCranmer](https://discourse.julialang.org/u/MilesCranmer)\
**Post date:** [May 7, 2023, 10:44pm UTC](https://discourse.julialang.org/t/strange-performance-issue-on-1-9-0-rc3/98427/10 "2023-05-07T22:44:34Z")

</div>

Thanks @Henrique_Becker and @tim.holy, that is helpful to know. That is indeed more complex of an issue than I was expecting. I’m glad we figured it out though.

For posterity, I see the speeds go back to normal with the following modification:

```diff
 function tree_mapreduce(
     args...,
+ result_type::Type{RT}=Nothing,
     ;
     preserve_sharing::Bool=false,
- result_type::Type{RT}=Nothing,
 )
     if preserve_sharing && result_type != Nothing
         return _tree_mapreduce(args..., IdDict{Node,RT}())
     else
         return _tree_mapreduce(args...)
     end
 end

```

which gives me the same speeds as if the branching code was commented out.