# Type stability on Arrays of Arrays in nested for loops?

**URL:** <https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619>\
**Category:** Performance\
**Tags:** question, arrays, type-stability\
**Created:** [February 19, 2021, 2:31pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619 "2021-02-19T14:31:02Z")\
**Posts on this page:** 17\
**Page:** 1

<div class="post-metadata">

**Author:** ![swishmas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/swishmas/32/8803_2.png) [@swishmas](https://discourse.julialang.org/u/swishmas)\
**Post date:** [February 19, 2021, 2:31pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/1 "2021-02-19T14:31:02Z")

</div>

I was writing a function that would ideally be written as

```julia
  function ideal(supervec::Array{Array{Int64,1},1}, vec::Array{Int64,1})
    return vcat(supervec[vec])
  end

```

But this takes a bit more time than I think is unnecessary

```julia
julia> using BenchmarkTools

julia> @btime ideal([[1],[2]],[1,2])
  232.497 ns (6 allocations: 576 bytes)
2-element Array{Array{Int64,1},1}:
 [1]
 [2]

```

So, I tried to write a longer version

```julia
  function simplecount(supervec::Array{Array{Int64,1},1}, vec::Array{Int64,1})
    consize = sum(a->length(supervec[a]),vec)
    con = Array{Int64,1}(undef,consize)
    counter = 0
  
    for j = 1:length(vec)
      b = vec[j]
      altvec = supervec[b]
      for r = 1:length(supervec[b])
        p = altvec[r]
        counter += 1
        con[counter] = p
      end
    end
    return con
  end

```

This performs better

```julia
julia> @btime simplecount([[1],[2]],[1,2])
  177.572 ns (5 allocations: 480 bytes)
2-element Array{Int64,1}:
 1
 2

```

But it has a type instability when I use `@code_warntype`

```julia
julia> @code_warntype simplecount([[1],[2]],[1,2])
Variables
  #self#::Core.Compiler.Const(simplecount, false)
  supervec::Array{Array{Int64,1},1}
  vec::Array{Int64,1}
  #97::var"#97#98"{Array{Array{Int64,1},1}}
  val::Nothing
  consize::Int64
  con::Array{Int64,1}
  counter::Int64
  @_9::Union{Nothing, Tuple{Int64,Int64}}
  j::Int64
  b::Int64
  altvec::Array{Int64,1}
  @_13::Union{Nothing, Tuple{Int64,Int64}}
  r::Int64
  p::Int64

Body::Array{Int64,1}
1 ─ Core.NewvarNode(:(val))
│ %2 = Main.:(var"#97#98")::Core.Compiler.Const(var"#97#98", false)
│ %3 = Core.typeof(supervec)::Core.Compiler.Const(Array{Array{Int64,1},1}, false)
│ %4 = Core.apply_type(%2, %3)::Core.Compiler.Const(var"#97#98"{Array{Array{Int64,1},1}}, false)
│ (#97 = %new(%4, supervec))
│ %6 = #97::var"#97#98"{Array{Array{Int64,1},1}}
│ (consize = Main.sum(%6, vec))
│ %8 = Core.apply_type(Main.Array, Main.intType, 1)::Core.Compiler.Const(Array{Int64,1}, false)
│ (con = (%8)(Main.undef, consize))
│ (counter = 0)
│ $(Expr(:inbounds, true))
│ %12 = Main.length(vec)::Int64
│ %13 = (1:%12)::Core.Compiler.PartialStruct(UnitRange{Int64}, Any[Core.Compiler.Const(1, false), Int64])
│ (@_9 = Base.iterate(%13))
│ %15 = (@_9 === nothing)::Bool
│ %16 = Base.not_int(%15)::Bool
└── goto #7 if not %16
2 ┄ %18 = @_9::Tuple{Int64,Int64}::Tuple{Int64,Int64}
│ (j = Core.getfield(%18, 1))
│ %20 = Core.getfield(%18, 2)::Int64
│ (b = Base.getindex(vec, j))
│ (altvec = Base.getindex(supervec, b))
│ %23 = Base.getindex(supervec, b)::Array{Int64,1}
│ %24 = Main.length(%23)::Int64
│ %25 = (1:%24)::Core.Compiler.PartialStruct(UnitRange{Int64}, Any[Core.Compiler.Const(1, false), Int64])
│ (@_13 = Base.iterate(%25))
│ %27 = (@_13 === nothing)::Bool
│ %28 = Base.not_int(%27)::Bool
└── goto #5 if not %28
3 ┄ %30 = @_13::Tuple{Int64,Int64}::Tuple{Int64,Int64}
│ (r = Core.getfield(%30, 1))
│ %32 = Core.getfield(%30, 2)::Int64
│ (p = Base.getindex(altvec, r))
│ (counter = counter + 1)
│ Base.setindex!(con, p, counter)
│ (@_13 = Base.iterate(%25, %32))
│ %37 = (@_13 === nothing)::Bool
│ %38 = Base.not_int(%37)::Bool
└── goto #5 if not %38
4 ─ goto #3
5 ┄ (@_9 = Base.iterate(%13, %20))
│ %42 = (@_9 === nothing)::Bool
│ %43 = Base.not_int(%42)::Bool
└── goto #7 if not %43
6 ─ goto #2
7 ┄ (val = nothing)
│ $(Expr(:inbounds, :pop))
│ val
└── return con

```

Why is the iterator in the innermost for-loop unable to distinguish between `Nothing` and `Tuple` (the line `@_9::Union{Nothing, Tuple{Int64,Int64}}` is yellow)? Is there a way to force the compiler to know which one it should be? Is there is a simpler way to write something like this? Thanks a lot!

---

<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:** [February 19, 2021, 2:57pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/2 "2021-02-19T14:57:41Z")

</div>

> [@How to prevent type instability in for loops?](https://discourse.julialang.org/t/how-to-prevent-type-instability-in-for-loops/30508/2):
>
> AFAIU, this “type instability” is harmless. It is a consequence of the [iterator interface](https://docs.julialang.org/en/latest/manual/interfaces/#) which returns nothing when the end of the iterator is reached. Note that the line you cited from the @code\_warntype output is colored in yellow (not red, which indicates “true” type instabilities).

---

<div class="post-metadata">

**Author:** ![swishmas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/swishmas/32/8803_2.png) [@swishmas](https://discourse.julialang.org/u/swishmas)\
**Post date:** [February 19, 2021, 3:20pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/3 "2021-02-19T15:20:48Z")

</div>

Ok, I’ll assume it is ok then. The reason that I asked was when I run `ProfileView`, this is the only function in the whole code that shows up as red on the resulting graph. So, I guess I should ignore the red bar there and trust this comment and `@code_warntype`. Thank you!

---

<div class="post-metadata">

**Author:** ![pixel27](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pixel27/32/8902_2.png) [@pixel27](https://discourse.julialang.org/u/pixel27)\
**Post date:** [February 19, 2021, 4:17pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/4 "2021-02-19T16:17:13Z")

</div>

You could change it (both) to a while loop, then there is no yellow.

---

<div class="post-metadata">

**Author:** ![swishmas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/swishmas/32/8803_2.png) [@swishmas](https://discourse.julialang.org/u/swishmas)\
**Post date:** [February 19, 2021, 4:25pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/5 "2021-02-19T16:25:58Z")

</div>

Interesting, that seems to work, @pixel27:

```julia
  function whilesimplecount(supervec::Array{Array{Int64,1},1}, vec::Array{Int64,1})
    consize = sum(a->length(supervec[a]),vec)
    con = Array{Int64,1}(undef,consize)
    counter = 0
  
    j = 0
    while j < length(vec)
      j += 1
      b = vec[j]
      altvec = supervec[b]
      r = 0
      while r < length(supervec[b])
        r += 1
        p = altvec[r]
        counter += 1
        con[counter] = p
      end
    end
    return con
  end

```

with no loss in efficiency when tested with `@btime`

```julia
@btime whilesimplecount([[1],[2]],[1,2])
  179.348 ns (5 allocations: 480 bytes)

```

Thank you!

---

<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:** [February 19, 2021, 4:34pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/6 "2021-02-19T16:34:49Z")

</div>

> [@swishmas](#):
>
> with no loss in efficiency when tested with `@btime`

but no gain either, I expect

---

<div class="post-metadata">

**Author:** ![pixel27](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/pixel27/32/8902_2.png) [@pixel27](https://discourse.julialang.org/u/pixel27)\
**Post date:** [February 19, 2021, 5:16pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/7 "2021-02-19T17:16:37Z")

</div>

I was seeing differences of about 6ns but that was really just fluctuation based on other activity on the computer. However it sounds like ProfileView is giving false positives, and unfortunately false positives have a habit of hiding true positives.

---

<div class="post-metadata">

**Author:** ![swishmas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/swishmas/32/8803_2.png) [@swishmas](https://discourse.julialang.org/u/swishmas)\
**Post date:** [February 19, 2021, 5:18pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/8 "2021-02-19T17:18:45Z")

</div>

With the new improved “while” version, the troublesome spots in ProfileView are now gone, so good news there.

I think for an individual function call, there is no difference that I can see. For larger inputs and repeated calls to this function, I can see a bit of a difference. Thank you both so much for your help! I really appreciate your input!

---

<div class="post-metadata">

**Author:** ![Jeff\_Emanuel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jeff_emanuel/32/15440_2.png) [@Jeff\_Emanuel](https://discourse.julialang.org/u/Jeff_Emanuel)\
**Post date:** [February 19, 2021, 6:29pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/9 "2021-02-19T18:29:37Z")

</div>

I think this is a really bad idiom, especially since it has no advantage other than removing an inconsequential warning. It spreads the loop control logic over three lines and makes it harder for the reader to parse than the clear, concise, and much less error prone `for j=1:length(vec)`. It screams “maintenance land mine” to me.

> [@swishmas](#):
>
> ```julia
> j = 0
> while j < length(vec)
> j += 1
> 
> ```

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [February 19, 2021, 6:33pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/10 "2021-02-19T18:33:51Z")

</div>

Yeah, agreed–the compiler turns you `for` loop into a `while` loop internally anyway, obeying the iteration protocol discussed here: [Writing Iterators in Julia 0.7](https://julialang.org/blog/2018/07/iterators-in-julia-0.7/#iteration_in_julia_06)

If you find the `while` loop easier to write or read, then by all means go for it, but there should be no efficiency advantage in turning all your `for` loops into `while` loops just to make `@code_warntype` less colorful.

---

<div class="post-metadata">

**Author:** ![Seif\_Shebl](https://avatars.discourse-cdn.com/v4/letter/s/eada6e/32.png) [@Seif\_Shebl](https://discourse.julialang.org/u/Seif_Shebl)\
**Post date:** [February 19, 2021, 8:34pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/11 "2021-02-19T20:34:54Z")

</div>

I’m not sure if it’s a good idea, but if you change the function signature as below, you get rid of all warnings. Performance is unchanged, of course. BTW, what is `intType`?

```julia
function simplecount(supervec::Array{Array{Int64,1},1}, 
                     vec::Array{Int64,1},
                     L=length(vec))
    ...
    for j = 1:L
    ...

```

---

<div class="post-metadata">

**Author:** ![swishmas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/swishmas/32/8803_2.png) [@swishmas](https://discourse.julialang.org/u/swishmas)\
**Post date:** [February 19, 2021, 9:23pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/12 "2021-02-19T21:23:54Z")

</div>

`intType` was just trying to copy an HDF5 variable name…it’s just `Int64` here

---

<div class="post-metadata">

**Author:** ![swishmas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/swishmas/32/8803_2.png) [@swishmas](https://discourse.julialang.org/u/swishmas)\
**Post date:** [February 19, 2021, 9:25pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/13 "2021-02-19T21:25:04Z")

</div>

My main reason for this is that the code might be used by other people, so if they notice that there is potentially a type stability issue, I will hear about it. They may or may not know about this non-issue.

It’s a bit of a shame that the major focus of debugging in Julia is to get rid of type stability and that phantom issues can appear…but it’s a relief that I didn’t do anything wrong!

---

<div class="post-metadata">

**Author:** ![Nosferican](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nosferican/32/9275_2.png) [@Nosferican](https://discourse.julialang.org/u/Nosferican)\
**Post date:** [February 19, 2021, 9:50pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/14 "2021-02-19T21:50:06Z")

</div>

Maybe try

```julia
using BenchmarkTools
ideal(x::AbstractVector{<:AbstractVector}, y::AbstractVector{<:Integer}) =
    reduce(vcat, x[elem] for elem in y)
x = [[1], [2]]
y = [1, 2]

```

```julia
julia> @code_warntype ideal(x, y) # Seems to be gucci
Variables
  #self#::Core.Compiler.Const(ideal, false)
  x::Array{Array{Int64,1},1}
  y::Array{Int64,1}
  #15::var"#15#16"{Array{Array{Int64,1},1}}

Body::Array{Int64,1}
1 ─ %1 = Main.:(var"#15#16")::Core.Compiler.Const(var"#15#16", false)
│ %2 = Core.typeof(x)::Core.Compiler.Const(Array{Array{Int64,1},1}, false)
│ %3 = Core.apply_type(%1, %2)::Core.Compiler.Const(var"#15#16"{Array{Array{Int64,1},1}}, false)
│ (#15 = %new(%3, x))
│ %5 = #15::var"#15#16"{Array{Array{Int64,1},1}}
│ %6 = Base.Generator(%5, y)::Base.Generator{Array{Int64,1},var"#15#16"{Array{Array{Int64,1},1}}}
│ %7 = Main.reduce(Main.vcat, %6)::Array{Int64,1}
└── return %7

```

```julia
julia> @btime ideal($x, $y)
  49.821 ns (1 allocation: 96 bytes)
2-element Array{Int64,1}:
 1
 2

```

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [February 19, 2021, 10:41pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/15 "2021-02-19T22:41:21Z")

</div>

> [@swishmas](#):
>
> My main reason for this is that the code might be used by other people, so if they notice that there is potentially a type stability issue, I will hear about it. They may or may not know about this non-issue.

That’s certainly your choice to make. But note that if you go down this road, you won’t be able to use _any_ iterators of any kind (not just for loops). That’s a huge price to pay to avoid false positive issue reports from users. particularly when you can just point those users to the excellent explanations which have already been written, e.g. [Union-splitting: what it is, and why you should care](https://julialang.org/blog/2018/08/union-splitting/)

---

<div class="post-metadata">

**Author:** ![swishmas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/swishmas/32/8803_2.png) [@swishmas](https://discourse.julialang.org/u/swishmas)\
**Post date:** [February 19, 2021, 11:55pm UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/16 "2021-02-19T23:55:30Z")

</div>

That is very slick code. Thank you. Just for anyone stumbling onto this code in the future, had I initialize the inputs outside of the function call like they are here, then the results essentially match. Thank you! Very clever!

---

<div class="post-metadata">

**Author:** ![swishmas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/swishmas/32/8803_2.png) [@swishmas](https://discourse.julialang.org/u/swishmas)\
**Post date:** [February 20, 2021, 12:01am UTC](https://discourse.julialang.org/t/type-stability-on-arrays-of-arrays-in-nested-for-loops/55619/17 "2021-02-20T00:01:52Z")

</div>

I very much agree here. You are correct that people should know. Had this been an issue that extended to more than one function, I would leave it alone, but for some reason some similar functions in the code don’t have this issue. I might change it to the very clever implementation with `reduce` above.

Thanks again for your input, I very much appreciate it!