# Very slow loop

**URL:** <https://discourse.julialang.org/t/very-slow-loop/53608>\
**Category:** Performance\
**Tags:** loops\
**Created:** [January 19, 2021, 2:07pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608 "2021-01-19T14:07:25Z")\
**Posts on this page:** 14\
**Page:** 2

<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:** [January 19, 2021, 8:58pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/21 "2021-01-19T20:58:45Z")

</div>

> [@lmiq](#):
>
> Yet, using `x=x` does not really make sense.

I have to disagree here.

Keyword arguments may be completely independent from the positional arguments of the same function/method. There is no special reason to make them dependent of the remaining positional arguments if this is not the case.

Many times the default of a keyword argument is just an instance of some object representing a safe default, and if this (often immutable) object is used in other places, then it is common for it to be stored in a global constant (for both the “no magical numbers” pattern and ease of change of the value in all contexts with a new release version).

---

<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:** [January 19, 2021, 9:08pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/22 "2021-01-19T21:08:44Z")

</div>

> [@Henrique\_Becker](#):
>
> (often immutable) object is used in other places, then it is common for it to be stored in a global constant

Ok, if there was a global constant `x` yes, although probably I would choose a better name, like `x0`. Yet it was not the case here.

---

<div class="post-metadata">

**Author:** ![jmcastro2109](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jmcastro2109/32/38427_2.png) [@jmcastro2109](https://discourse.julialang.org/u/jmcastro2109)\
**Post date:** [January 21, 2021, 11:58am UTC](https://discourse.julialang.org/t/very-slow-loop/53608/23 "2021-01-21T11:58:49Z")

</div>

Leandro, one last question. Do you mind explaining me why is the fragment

```julia
if N>NF
        A= vcat(A,A,A)
        H = cat(H ,H ,H ,dims=2)
        P= cat(P,P,P,dims=2)
    end

```

so detrimental for performance even in we were working on a case in which N==NF, so we should not be entering that loop?

---

<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:** [January 21, 2021, 12:46pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/24 "2021-01-21T12:46:52Z")

</div>

As far as I understand, the problem is in `cat(...,dims=2)`. That can return an array of different kind, depending on the input. For example:

```julia
julia> B = [1,2,3]
3-element Array{Int64,1}:
 1
 2
 3

julia> cat(B,B,dims=2)
3×2 Array{Int64,2}:
 1 1
 2 2
 3 3

```

In this case, the input is a vector and the output is a two-dimensional array. In the code that contains that conditional clause, there is no way for the compiler to know in advance if that change in dimensions will occur or not, because it is dependent on an input parameter of the function. Thus, the code does not become specialized for the type of array that you are operating on. That is independent on entering or not the conditional, the problem is the possibility of entering and changing the meaning of the foregoing operations.

If you put that in an `outer` function, as I suggested, the `inner` function will get specialized for the type of array received every time. Consider the following minimal example:

```julia
julia> function f(A,N)
         if N == 0
           println("got here")
           A = cat(A,A,dims=2)
         end
         s = 0.
         for a in A
           s += a
         end
         s
       end
f (generic function with 1 method)

julia> function outer(A,N)
         if N == 0
           println("got here")
           A = cat(A,A,dims=2)
         end
         g(A)
       end
       function g(A)
         s = 0.
         for a in A
           s += a
         end
         s
       end
g (generic function with 1 method)

julia> A = rand(3,3);

julia> using BenchmarkTools

julia> @btime f($A,1)
  269.185 ns (18 allocations: 288 bytes)
4.425721907655399

julia> @btime outer($A,1)
  17.008 ns (1 allocation: 16 bytes)
4.425721907655399

```

Note that it also has the same problem, and the same solution. If you do `@code_warntype` on `f(A,1)` or on `outer(A,1)`, you will see that both are type-unstable. Yet, no matter which is the input of `g(A)`, it is always type-stable. Since `g` is the function doing the expensive computations, that specialization is absolutely determinant to performance.

Sometimes, depending on the conditional involved, the compiler figures out that it can split the function in two branches, and that does not happen. But here it cannot do it.

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [January 21, 2021, 12:54pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/25 "2021-01-21T12:54:32Z")

</div>

You can make `cat` type-stable, like so:

```julia
julia> @code_warntype cat(B, B, dims=2)
...
Body::Any

julia> @code_warntype hcat(B, B)
...
Body::Matrix{Int64}

julia> @code_warntype cat(B, B, dims=Val(2))
...
Body::Matrix{Int64}

```

The issue with the first one is that `cat(B, B; dims=1) isa Vector` – same input types, but different output.

---

<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:** [January 21, 2021, 1:11pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/26 "2021-01-21T13:11:14Z")

</div>

> [@mcabbott](#):
>
> `dims=Val(2)`

Why does this make any difference? What is less constant in the number `2` than in `Val(2)`?

---

<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:** [January 21, 2021, 1:24pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/27 "2021-01-21T13:24:34Z")

</div>

`2` is a value of type `Int`  
`Val(2)` is a value of type `Val{2}`

Therefore, the dimension is mapped to type-space.

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [January 21, 2021, 1:25pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/28 "2021-01-21T13:25:04Z")

</div>

One answer is that `@code_warntype` only looks one layer deep. For example, it tells us `map` is type-stable here, because it evaluates the inputs before getting to work:

```julia
julia> @code_warntype map(exp, cat(B,B, dims=rand(1:3)))
Body::Vector{Float64}

julia> @code_warntype map(exp, cat(B,B, dims=rand(1:3))) # another run of the same
Body::Array{Float64, 3}

```

But another answer is that if you literally write `dims = Val(2)` in the source code, Julia is usually smart enough to propagate that constant literal `2` outwards, to `Val{2}()` which has it in the type domain. Writing `d = 2; cat(B, B, dims=Val(d))` would in general work less well (even though `@code_warntype` acting on `cat` won’t tell you this), but sometimes it will still manage:

```julia
julia> mycat(B) = begin d=1; cat(B,B, dims=Val(d+1)) end;

julia> @code_warntype mycat(B)
Body::Matrix{Int64}

julia> mycat2(B, d=2) = cat(B,B, dims=Val(d));

julia> @code_warntype mycat2(B) # seems easier but fails
Body::Any

```

---

<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:** [January 21, 2021, 1:31pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/29 "2021-01-21T13:31:33Z")

</div>

Thanks @Henrique_Becker and @mcabbott , but in that case I think I have to go to the books to understand that… or maybe not even that. It is very unclear to me how the compiler will have more information in case than in the other. The compiler won’t as effectively propagate the type information of a `Int` value than a value of type `Val{2}`? Seems something very specific about the way that the type-inference is implemented rather than a fundamental principle, isn’t it?

---

<div class="post-metadata">

**Author:** ![dmolina](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dmolina/32/5246_2.png) [@dmolina](https://discourse.julialang.org/u/dmolina)\
**Post date:** [January 21, 2021, 1:36pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/30 "2021-01-21T13:36:43Z")

</div>

Yes, it is an interesting topic but a little advanced, the use of Val.

From my point of view, consider comments from @mcabbott, I get the conclusion that it is usually better to use `vcat` or `hcat` when it is possible than general `cat`, because the most general function like that could return generic types.

---

<div class="post-metadata">

**Author:** ![mcabbott](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mcabbott/32/6603_2.png) [@mcabbott](https://discourse.julialang.org/u/mcabbott)\
**Post date:** [January 21, 2021, 1:37pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/31 "2021-01-21T13:37:08Z")

</div>

Yes, I don’t think these follow logically from the definition of the type system. In older Julia code you will see much more `Val{2}()` or types `Val{2}` used instead of `Val(2)`, as it used to be less smart about propagating things. The precise details of when this will & won’t happen are above my pay grade, I just learn by poking it & seeing what happens.

@dmolina yes, I think writing `hcat` is usually best & clearest when you know in advance. There is no special name for `cat(A, B, dims=Val(3))` so that’s when it’s worth knowing that it accepts `Val`.

---

<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:** [January 21, 2021, 3:40pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/32 "2021-01-21T15:40:59Z")

</div>

> [@lmiq](#):
>
> The compiler won’t as effectively propagate the type information of a `Int` value than a value of type `Val{2}` ?

Not obligatorily. The compiler could, of course, if sufficient smart propagate the _value_ `2` of type `Int` and obtain the same results. But at the moment `2` is encoded in the type `Val{2}` then the function receiving it will (probably) be specialized for that type what leads to easier analysis (at cost of compiling one more specialization of `cat`). It seems to me that it follows from the concept of function barrier, but I may be wrong. Anyway, considering that type-instability always takes inference in account, and inference is not entirely defined by the language (i.e., versions of Julia may change what they are able to infer without this being considered breaking), then it is somewhat type-inference specific.

---

<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:** [January 24, 2021, 1:49pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/33 "2021-01-24T13:49:06Z")

</div>

I just noticed that if you annotate the output of `cat`, the instability is solved in this case as well (at least in the MWE). The result is as good as using `dims=Val(2)`, and probably more intuitive:

```julia
julia> function g(A,N)
         if N == 0
           println("got here")
           A = cat(A,A,dims=2)::Array{Float64,2}
         end
         s = 0.
         for a in A
           s += a
         end
         s
       end
g (generic function with 1 method)

julia> A = rand(3,3);

julia> @btime g($A,1)
  5.923 ns (0 allocations: 0 bytes)
5.379437443399205

```

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [January 24, 2021, 7:26pm UTC](https://discourse.julialang.org/t/very-slow-loop/53608/34 "2021-01-24T19:26:26Z")

</div>

It’s slightly less general than `hcat` et al, though, since it will fail for N-d arrays for N\>2.

[Previous page](https://discourse.julialang.org/t/very-slow-loop/53608.md?page=1)