Performance of nested named tuples

[GunnarFarneback]

Deeply nested named tuples run into bad complexity somewhere.

julia> x = (a = 0, b = 0)
(a = 0, b = 0)

julia> y = Any[x]
1-element Array{Any,1}:
 (a = 0, b = 0)

julia> for k = 1:20
           push!(y, (a = 0, b = y[end]))
       end

julia> for k = 10:20
           @time println(k, " ", y[k])
       end
10 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0))))))))))
  0.651738 seconds (855.35 k allocations: 48.457 MiB, 1.52% gc time)
11 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0)))))))))))
  0.159373 seconds (88.89 k allocations: 5.065 MiB, 3.15% gc time)
12 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0))))))))))))
  0.332907 seconds (88.98 k allocations: 5.072 MiB)
13 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0)))))))))))))
  0.866842 seconds (88.92 k allocations: 5.218 MiB)
14 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0))))))))))))))
  2.468387 seconds (88.95 k allocations: 5.085 MiB)
15 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0)))))))))))))))
  8.583492 seconds (89.07 k allocations: 5.097 MiB, 0.06% gc time)
16 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0))))))))))))))))
 21.715772 seconds (88.97 k allocations: 5.080 MiB)
17 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0)))))))))))))))))
 64.891510 seconds (88.99 k allocations: 5.099 MiB)
18 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0))))))))))))))))))
260.981331 seconds (89.01 k allocations: 5.075 MiB)
19 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0)))))))))))))))))))
936.665742 seconds (89.00 k allocations: 5.064 MiB, 0.00% gc time)
20 (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = (a = 0, b = 0))))))))))))))))))))
2365.115879 seconds (89.02 k allocations: 5.077 MiB)

On second run everything is fast. The corresponding example for unnamed tuples does not have this problem.

[GunnarFarneback]

I see somewhat smaller numbers with current Julia master, but the problem remains.

[JeffreySarnoff]

This has been resolved with (if not before) current stable release.

[GunnarFarneback]

Confirmed.