# This should be documented in performance tips if not a temporary bug

**URL:** <https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894>\
**Category:** Performance\
**Created:** [June 23, 2018, 9:10am UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894 "2018-06-23T09:10:36Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [June 23, 2018, 9:10am UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/1 "2018-06-23T09:10:36Z")

</div>

Here is a drastically simplified and self-contained fragment of code dealing with permutation groups. The point of my post is that without the line `let s=s, i=i, e=i^s` the compiler cannot infer the type of either s, i or e, as @code\_warntype shows. I spent literally days on this kind of problem, almost giving up on Julia along the way, before I stumbled on a similar problem/solution in a post on this (very useful) forum, and discovered that this kind of bug is all over my code and can invariably be fixed in a similar way. So my questions are:

- What is going on here exactly?
- Is this a temporary bug which is going to be fixed? (it is on 0.6.3 and on 0.7alpha)
- If not, why is this not mentioned in the section “Performance tips”?

```julia
# a permutation is defined by the list d holding the images of 1:length(d)
struct Perm 
   d::Vector{Int}
end

degree(a::Perm)= length(a.d)

# i^p : apply permutation p to integer i
import Base.^
^(n::Int, a::Perm)=if n>degree(a) n else a.d[n] end

import Base.*
function *(b::Perm, a::Perm)
  if degree(b)<=degree(a)
    d=copy(a.d)
    for i in 1:degree(b) d[i]=a.d[b.d[i]] end
  else
    d=[i^a for i in b.d]
  end
  Perm(d)
end

struct PermGroup # Permutation group with generators gens
  gens::Vector{Perm}
end

G=PermGroup([Perm([2,1,3]),Perm([1,3,2])])

# for each q in the orbit of point p under g, record
# in d[p] an element of G sending p to q
function orbit_and_representative(G::PermGroup,p)
  new=[p]
  d=Dict(p=>Perm(collect(1:degree(G.gens[1]))))
  while !isempty(new)
    old=copy(new)
    resize!(new,0)
    for s in G.gens, i in old
      let s=s, i=i, e=i^s
        get!(d,e) do
          push!(new,e)
          s*d[i]
        end
      end
    end
  end
  d
end

@code_warntype orbit_and_representative(G,1)
```

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [June 23, 2018, 9:26am UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/2 "2018-06-23T09:26:44Z")

</div>

This is the infamous closure bug:  
[https://github.com/JuliaLang/julia/issues/15276](https://github.com/JuliaLang/julia/issues/15276)

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [June 23, 2018, 9:31am UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/3 "2018-06-23T09:31:20Z")

</div>

I am not sure what you mean here. Is it because the variables s,i and e appear in the function argument to `get!`  
that they are “captured in a closure”? If so it seems a dramatic restriction on allowed code in Julia!!

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [June 23, 2018, 9:33am UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/4 "2018-06-23T09:33:23Z")

</div>

You’re defining an anonymous function:

```julia
do
    push!(new,e)
    s*d[i]
end

```

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [June 23, 2018, 9:36am UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/5 "2018-06-23T09:36:32Z")

</div>

OK. You did not answer my questions except perhaps the first one. Here are two more:

- Is there a better way to code this?
- Is my workaround the best one?

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [June 23, 2018, 9:56am UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/6 "2018-06-23T09:56:48Z")

</div>

A closure is when you create a function, and it “captures” variables in the scope in which it is defined. The bug is that the compiler has a hard time confirming types are stable when that happens.

Using variables as arguments to functions is fine, but capturing them in functions you define risks the bug.  
Note that in Julia 0.6 broadcasts actually define an anonymous function, but I’ve not heard of the bug rearing it’s head in a broadcast. It is definitely a problem, but it doesn’t happen most of the time. (Perhaps someone knows what makes it more likely?) It’s also definitely getting better – a lot of the examples from the issue linked above are now inferred correctly.

And yes, your approach is probably the best when it works, because it’s a lot less cumbersome than something like this:

```julia
struct close <: Function
    new::Vector{Int}
    e::Int
    s::Perm
    d::Dict{Int,Perm}
    i::Int
end
function (c::close)()
    push!(c.new, c.e)
    c.s*c.d[c.i]
end
function orbit_and_representative_manual_closure(G::PermGroup,p)
  new=[p]
  d=Dict(p=>Perm(collect(1:degree(G.gens[1]))))
  while !isempty(new)
    old=copy(new)
    resize!(new,0)
    for s in G.gens, i in old
        e = i^s
        get!(close(new, e, s, d, i), d,e)
    end
  end
  d
end

```

or than creating global constant `RefValue`s or arrays to hold the variables you’re passing in a closure.

---

<div class="post-metadata">

**Author:** ![hustf](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hustf/32/2374_2.png) [@hustf](https://discourse.julialang.org/u/hustf)\
**Post date:** [June 23, 2018, 10:10am UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/7 "2018-06-23T10:10:49Z")

</div>

So is there some general way one could phrase the “let” hint to compiler? Even if it is most often not necessary?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [June 23, 2018, 11:52am UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/8 "2018-06-23T11:52:15Z")

</div>

AFAIK using `let` is the simplest option at the moment.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [June 23, 2018, 12:07pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/9 "2018-06-23T12:07:35Z")

</div>

> [@Jean\_Michel](#):
>
> I spent literally days on this kind of problem, almost giving up on Julia along the way

Before giving up on the language, it may be better to ask for help first. You can always give up on Julia later 😉

> [@Jean\_Michel](#):
>
> Is this a temporary bug which is going to be fixed? (it is on 0.6.3 and on 0.7alpha)

Hopefully, yes. The issue linked by @Elrod has a 1.x milestone, so you may have to wait a bit.

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [June 23, 2018, 12:18pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/10 "2018-06-23T12:18:43Z")

</div>

**Before giving up on the language, it may be better to ask for help first. You can always give up on Julia later**

I thought the problem was with me, that I had not grasped something in the language. This should definitely be  
in the section “Performance tips” of the manual: I can tell you it is not easy to find the origin of the problem and the solution when you are a new user of the language, with the resources available in the manual.

I took some time to make a simplified example and was going to post for help when I stumbled on a solution. I  
still posted, hoping my plight will help others.

---

<div class="post-metadata">

**Author:** ![cstjean](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cstjean/32/1444_2.png) [@cstjean](https://discourse.julialang.org/u/cstjean)\
**Post date:** [June 23, 2018, 12:43pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/11 "2018-06-23T12:43:37Z")

</div>

It’s a pretty subtle problem to explain to the average user. Maybe someone should compile a list of “Performance gotchas for advanced julia usage”. There’s a lot of them, but that’s also true in the other high-level high-performance languages I’ve looked at. You have to know and understand your compiler’s mental-blocks.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [June 23, 2018, 1:13pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/12 "2018-06-23T13:13:29Z")

</div>

> [@Jean\_Michel](#):
>
> This should definitely be in the section “Performance tips” of the manual

I am not sure I agree with this; this is not something inherent to Julia’s design, but a bug that should be fixed in due time. There are [about 150 open bugs with the performance label](https://github.com/JuliaLang/julia/issues?q=is%3Aissue+is%3Aopen+label%3Aperformance) at the moment, they come and go.

---

<div class="post-metadata">

**Author:** ![antoine-levitt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/antoine-levitt/32/4008_2.png) [@antoine-levitt](https://discourse.julialang.org/u/antoine-levitt)\
**Post date:** [June 23, 2018, 1:33pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/13 "2018-06-23T13:33:26Z")

</div>

> I am not sure I agree with this; this is not something inherent to Julia’s design, but a bug that should be fixed in due time.

Technically other gotchas are also “performance bugs” (eg globals, whose performance could be optimized). It makes sense to document the current state of the language, not the ideal implementation allowed by the design (kind of how release notes usually include a “known bugs” section). This issue in particular is very easy to run into and non-trivial to figure out.

---

<div class="post-metadata">

**Author:** ![abulak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abulak/32/28314_2.png) [@abulak](https://discourse.julialang.org/u/abulak)\
**Post date:** [June 23, 2018, 3:03pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/14 "2018-06-23T15:03:38Z")

</div>

I know that this is probably not the answer You seek, but does this work for You?

```julia
using AbstractAlgebra

G = PermGroup(3)

function orbit_and_representative(G::Generic.PermGroup, p)
  new = [p]
  orbit = Dict(p=>G())
  for g in elements(G)
    if !(g[p] in keys(orbit))
      orbit[g[p]] = g
    end
  end
  return orbit
end
  
orbit_and_representative(G, 1)

```

Of course you could break the loop when orbit is complete

---

<div class="post-metadata">

**Author:** ![Jean\_Michel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jean_michel/32/8282_2.png) [@Jean\_Michel](https://discourse.julialang.org/u/Jean_Michel)\
**Post date:** [June 23, 2018, 3:13pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/15 "2018-06-23T15:13:41Z")

</div>

I am porting thousands of lines of GAP code, including a much more complete implementation of permutations groups, as part of a much larger port, so I did not even look at other Julia implementations.  
As a detail, in your implementation is `x in keys(d)` implemented efficiently for a Dict? I used `get!` since  
it seems to me that it minimizes the number of hashes/accesses. Also, you assume `elements(G)` is known,  
while I am porting basic code like Schreier-Sims base and strong generating set, a preliminary to construct  
`elements`.

---

<div class="post-metadata">

**Author:** ![abulak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/abulak/32/28314_2.png) [@abulak](https://discourse.julialang.org/u/abulak)\
**Post date:** [June 23, 2018, 3:16pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/16 "2018-06-23T15:16:42Z")

</div>

I implemented all of this in `AbstractAlgebra`, would be great if You contribute Schreier-Sims to this project!

EDIT: answering Your question about accessing the `keys`: I didn’t look into this, but this seems a premature optimisation.

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [June 23, 2018, 6:29pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/17 "2018-06-23T18:29:27Z")

</div>

[https://github.com/JuliaLang/julia/pull/27282](https://github.com/JuliaLang/julia/pull/27282)

---

<div class="post-metadata">

**Author:** ![ScottPJones](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scottpjones/32/146_2.png) [@ScottPJones](https://discourse.julialang.org/u/ScottPJones)\
**Post date:** [June 23, 2018, 7:43pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/18 "2018-06-23T19:43:51Z")

</div>

Yes, I agree.  
A “known performance issues” section, with the best workarounds for each case, if possible, would be great.

---

<div class="post-metadata">

**Author:** ![louisponet](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/louisponet/32/2070_2.png) [@louisponet](https://discourse.julialang.org/u/louisponet)\
**Post date:** [June 26, 2018, 1:12pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/19 "2018-06-26T13:12:49Z")

</div>

If it’s decided to compile such a chapter in the manual, it might be useful to point people to the same bug if their multithreaded loop does not perform as expected. Happened to me a couple of times that I had to unmacro the macro to get to at least some kind of type stability. Maybe that’s fixed though, I didn’t really follow the development

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [June 26, 2018, 4:42pm UTC](https://discourse.julialang.org/t/this-should-be-documented-in-performance-tips-if-not-a-temporary-bug/11894/20 "2018-06-26T16:42:38Z")

</div>

The advanced pitfalls chapter should also contain a link to the function specialization heuristics and workaround, with the warning that `@code_warntype` up to `@code_native` show the fully realized code instead of the really existing code.

(solution is `some_fun(F::FT, x) where F<:Function` instead of `some_fun(F::Function, x)` if you want any kind of type-stability and `F` does not appear in head-position of the AST; this is properly documented in the developer-section, but imho deserves a cross-ref because it is initially quite surprising to see all the allocations that are not present in `@code_native`)