Help with binary trees benchmark games example

[jzr]

@Sukera

The reason your annotation didn’t help as much as you’d hoped (and other versions that still interpolate the integer get) is because Array{String} is an abstract type - it does not have the second type parameter (specifying the dimensionality). You were probably looking for Array{String, 1} , or equivalently (and what other people here used), Vector{String} .

I agree that Vector{String} is what I should have used, but I don’t think it actually helps in this case?

julia> function stupidloop(num_iterations)
                  str_list::Array{String} = []
                  for i in 0:num_iterations-1
                      push!(str_list, "str_list, test_$(i + 3)_somethingsomething")
                  end

                  total_length::Int = 0

                  for line in str_list
                      total_length += length(line)
                  end

              total_length
              end
stupidloop (generic function with 1 method)

julia> 

julia> using BenchmarkTools

julia> stupidloop(1234567)
49506155

julia> @benchmark stupidloop(1234567)
BenchmarkTools.Trial: 
  memory estimate:  374.92 MiB
  allocs estimate:  7406915
  --------------
  minimum time:     969.548 ms (37.52% GC)
  median time:      997.991 ms (40.08% GC)
  mean time:        1.016 s (41.16% GC)
  maximum time:     1.111 s (46.10% GC)
  --------------
  samples:          5
  evals/sample:     1

julia> function stupidloop(num_iterations)
                  str_list::Vector{String} = []
                  for i in 0:num_iterations-1
                      push!(str_list, "str_list, test_$(i + 3)_somethingsomething")
                  end

                  total_length::Int = 0

                  for line in str_list
                      total_length += length(line)
                  end

              total_length
              end
stupidloop (generic function with 1 method)

julia> stupidloop(1234567)
49506155

julia> @benchmark stupidloop(1234567)
BenchmarkTools.Trial: 
  memory estimate:  374.92 MiB
  allocs estimate:  7406915
  --------------
  minimum time:     986.241 ms (37.14% GC)
  median time:      1.095 s (44.64% GC)
  mean time:        1.072 s (42.75% GC)
  maximum time:     1.131 s (46.05% GC)
  --------------
  samples:          5
  evals/sample:     1

@Sukera

Deeper investigation (regarding why string construction here is slow) was not more than basic @code_warntype and @time (wondering why allocations went up with larger inputs, seeing that it calculated them and noticing that the calculation wasn’t accurate in a large amount of cases).

I’m not sure what I’m supposed to get from @code_warntype here?

julia> function stupidloop(num_iterations)
                  str_list::Vector{String} = []
                  for i in 0:num_iterations-1
                      push!(str_list, "str_list, test_$(i + 3)_somethingsomething")
                  end

                  total_length::Int = 0

                  for line in str_list
                      total_length += length(line)
                  end

              total_length
              end
stupidloop (generic function with 1 method)

julia> @code_warntype stupidloop(1234567)
Variables
  #self#::Core.Compiler.Const(stupidloop, false)
  num_iterations::Int64
  str_list::Array{String,1}
  @_4::Union{Nothing, Tuple{Int64,Int64}}
  total_length::Int64
  @_6::Union{Nothing, Tuple{String,Int64}}
  i::Int64
  line::String

Body::Int64
1 ─       Core.NewvarNode(:(total_length))
│         Core.NewvarNode(:(@_6))
│   %3  = Base.vect()::Array{Any,1}
│   %4  = Core.apply_type(Main.Vector, Main.String)::Core.Compiler.Const(Array{String,1}, false)
│   %5  = Base.convert(%4, %3)::Array{String,1}
│         (str_list = Core.typeassert(%5, %4))
│   %7  = (num_iterations - 1)::Int64
│   %8  = (0:%7)::Core.Compiler.PartialStruct(UnitRange{Int64}, Any[Core.Compiler.Const(0, false), Int64])
│         (@_4 = Base.iterate(%8))
│   %10 = (@_4 === nothing)::Bool
│   %11 = Base.not_int(%10)::Bool
└──       goto #4 if not %11
2 ┄ %13 = @_4::Tuple{Int64,Int64}::Tuple{Int64,Int64}
│         (i = Core.getfield(%13, 1))
│   %15 = Core.getfield(%13, 2)::Int64
│   %16 = str_list::Array{String,1}
│   %17 = (i + 3)::Int64
│   %18 = Base.string("str_list, test_", %17, "_somethingsomething")::String
│         Main.push!(%16, %18)
│         (@_4 = Base.iterate(%8, %15))
│   %21 = (@_4 === nothing)::Bool
│   %22 = Base.not_int(%21)::Bool
└──       goto #4 if not %22
3 ─       goto #2
4 ┄ %25 = Base.convert(Main.Int, 0)::Core.Compiler.Const(0, false)
│         (total_length = Core.typeassert(%25, Main.Int))
│   %27 = str_list::Array{String,1}
│         (@_6 = Base.iterate(%27))
│   %29 = (@_6 === nothing)::Bool
│   %30 = Base.not_int(%29)::Bool
└──       goto #7 if not %30
5 ┄ %32 = @_6::Tuple{String,Int64}::Tuple{String,Int64}
│         (line = Core.getfield(%32, 1))
│   %34 = Core.getfield(%32, 2)::Int64
│   %35 = total_length::Int64
│   %36 = Main.length(line)::Int64
│   %37 = (%35 + %36)::Int64
│   %38 = Base.convert(Main.Int, %37)::Int64
│         (total_length = Core.typeassert(%38, Main.Int))
│         (@_6 = Base.iterate(%27, %34))
│   %41 = (@_6 === nothing)::Bool
│   %42 = Base.not_int(%41)::Bool
└──       goto #7 if not %42
6 ─       goto #5
7 ┄       return total_length



julia> function stupidloop(num_iterations)
                  str_list::Array{String} = []
                  for i in 0:num_iterations-1
                      push!(str_list, "str_list, test_$(i + 3)_somethingsomething")
                  end

                  total_length::Int = 0

                  for line in str_list
                      total_length += length(line)
                  end

              total_length
              end
stupidloop (generic function with 1 method)

julia> @code_warntype stupidloop(1234567)
Variables
  #self#::Core.Compiler.Const(stupidloop, false)
  num_iterations::Int64
  str_list::Array{String,1}
  @_4::Union{Nothing, Tuple{Int64,Int64}}
  total_length::Int64
  @_6::Union{Nothing, Tuple{String,Int64}}
  i::Int64
  line::String

Body::Int64
1 ─       Core.NewvarNode(:(total_length))
│         Core.NewvarNode(:(@_6))
│   %3  = Base.vect()::Array{Any,1}
│   %4  = Core.apply_type(Main.Array, Main.String)::Core.Compiler.Const(Array{String,N} where N, false)
│   %5  = Base.convert(%4, %3)::Array{String,1}
│         (str_list = Core.typeassert(%5, %4))
│   %7  = (num_iterations - 1)::Int64
│   %8  = (0:%7)::Core.Compiler.PartialStruct(UnitRange{Int64}, Any[Core.Compiler.Const(0, false), Int64])
│         (@_4 = Base.iterate(%8))
│   %10 = (@_4 === nothing)::Bool
│   %11 = Base.not_int(%10)::Bool
└──       goto #4 if not %11
2 ┄ %13 = @_4::Tuple{Int64,Int64}::Tuple{Int64,Int64}
│         (i = Core.getfield(%13, 1))
│   %15 = Core.getfield(%13, 2)::Int64
│   %16 = str_list::Array{String,1}
│   %17 = (i + 3)::Int64
│   %18 = Base.string("str_list, test_", %17, "_somethingsomething")::String
│         Main.push!(%16, %18)
│         (@_4 = Base.iterate(%8, %15))
│   %21 = (@_4 === nothing)::Bool
│   %22 = Base.not_int(%21)::Bool
└──       goto #4 if not %22
3 ─       goto #2
4 ┄ %25 = Base.convert(Main.Int, 0)::Core.Compiler.Const(0, false)
│         (total_length = Core.typeassert(%25, Main.Int))
│   %27 = str_list::Array{String,1}
│         (@_6 = Base.iterate(%27))
│   %29 = (@_6 === nothing)::Bool
│   %30 = Base.not_int(%29)::Bool
└──       goto #7 if not %30
5 ┄ %32 = @_6::Tuple{String,Int64}::Tuple{String,Int64}
│         (line = Core.getfield(%32, 1))
│   %34 = Core.getfield(%32, 2)::Int64
│   %35 = total_length::Int64
│   %36 = Main.length(line)::Int64
│   %37 = (%35 + %36)::Int64
│   %38 = Base.convert(Main.Int, %37)::Int64
│         (total_length = Core.typeassert(%38, Main.Int))
│         (@_6 = Base.iterate(%27, %34))
│   %41 = (@_6 === nothing)::Bool
│   %42 = Base.not_int(%41)::Bool
└──       goto #7 if not %42
6 ─       goto #5
7 ┄       return total_length

@Sukera

Lastly, just because some people argue for why a change hasn’t been made doesn’t mean that change isn’t wanted at all - it’s just that there are not enough people “taking the leap”

I don’t think so. People see benchmarks that look irrelevant to them and argue against focusing on those benchmarks. This is fine and good, since performance optimization takes time away from other priorities and complicates the language implementation. So it’s useful for users with different needs to communicate about which parts of the language they need to be fast.