Very long compile time for recursive function of dynamic tuple type

[IainNZ]

Here is the code, it has been whittled down extensively from the original version but is still a little unwieldy. On Julia HEAD it reports

Executing now
elapsed time: 21.684431147 seconds (2064014320 bytes allocated)

type MyType
    innerArray
    indexsets
end

function print_values(dict::MyType, depth::Int, 
                        parent_index::Any, parent_str::String)
    indexset = dict.indexsets[depth]  
    depth == length(dict.indexsets) && return
    for i = 1:length(indexset)
        index = indexset[i]
        print_values(dict,depth+1,
             parent_index == nothing ? (index,) : tuple(parent_index...,index,),
            (parent_index == nothing ? "" : parent_str) * "$index,")
    end
end

println("Executing now")
mydict = MyType([8.0,9.0,10.0,11.0,12.0], (8:12,))
@time print_values(mydict, 1, nothing, "")

[IainNZ]

(this isn't actually a problem for me, as I changed parent_index to be a vector that grows, but I was worried this might point to something more troublesome)

[vtjnash]

julia> function print_values2(dict::MyType, depth::Int, 
                               parent_index::ANY, parent_str::String)
           indexset = dict.indexsets[depth]  
           depth == length(dict.indexsets) && return
           for i = 1:length(indexset)
               index = indexset[i]
               print_values(dict,depth+1,
                    parent_index == nothing ? (index,) : tuple(parent_index...,index,),
                   (parent_index == nothing ? "" : parent_str) * "$index,")
           end
       end
print_values2 (generic function with 1 method)

julia> @time code_typed(print_values2,typeof((mydict, 1, nothing, "")))
elapsed time: 0.000976887 seconds (78104 bytes allocated)

Tuple is a special internal type. Since it is changes type on every function call, it appears that julia tries to generate many unique functions for each possible tuple type. There are some limits to that, but they are pretty high. Using ::ANY instead of ::Any is another special internal type which prohibits julia from generating specialized versions of the function for that parameter (and is therefore very fast).

[IainNZ]

I figured it might be something like that, but I thought there might be something pathological going on - after all, the function, as called, doesn't even recurse.

If you change the fourth argument from (parent_index == nothing ? "" : parent_str) * "$index,") to just "$index" it also doesn't have this compile time, and alternatively if you change parent_index == nothing ? (index,) : tuple(parent_index...,index,), to just (index,) it also is OK.

[simonster]

@vtjnash I think you have a typo: print_values2 is calling print_values instead of itself. The original function still seems to compile slowly with the type annotation changed to ANY.

[vtjnash]

oh, that would explain it more. oops

[vtjnash]

@JeffBezanson the following patch has no impact on the perf or regular test, but improves the compile time for this from 23 seconds to 0.03 seconds. thoughts?

diff --git a/base/inference.jl b/base/inference.jl
index d08f6e0..0675c0d 100644
--- a/base/inference.jl
+++ b/base/inference.jl
@@ -1123,6 +1123,9 @@ function tmerge(typea::ANY, typeb::ANY)
     if is(typeb,NF)
         return typea
     end
+    if typea <: Tuple && typeb <: Tuple && !(typea <: typeb || typeb <: typea)
+        typea = Union(typea,Tuple)
+    end
     if typea <: typeb
         return typeb
     end

[JeffBezanson]

Eh, that's only a 766x speedup :)
Something like this is probably what we need. Isn't this change equivalent to just returning Tuple?

[vtjnash]

as written, yes. i was trying to take into existing account type unions. in pseudo-code:

if hastuples(typea) && hastuples(typeb) && !all_tuples_same(typea, typeb)
  typea = Union(Tuple, typea, typeb); typeb = None
end

where all_tuples_same is the elementwise typea <: typeb || typeb <: typea

[JeffBezanson]

I see. Well, if it doesn't cause any perf regressions let's just put in the return Tuple version and fix this.