Exponential name blowup in deep computational graphs

[robertsugar]

auto_name! currently concatenates the name of all parents. If one is constructing a deep network with two-operand functions, the size of the name will double at every level. Consider the following code:

using Reactive

s1 = Signal(1)
s2 = Signal(2)

for i in 1:100
    s1 = map(+, s1, s2)
    s2 = map(-, s1, s2)
    println(s1)
    println(s2)
end

this will either take very long, break or run out of memory.

Suggested solution:

#1: limit the size of the name. In core.jl:

const max_name_length = 256 #name size is capped to avoid exponential name explosion
...

function auto_name!(name, parents...)
    parents_str = join(map(s->s.name, parents), ", ")
    isempty(parents_str) || (name *= "($parents_str)")
    if length(name) > max_name_length
        # keep the beginning and the end of the string, and put " ... " in the middle
        size_to_keep = div(max_name_length, 2) - 3 
        name = name[1:size_to_keep] * " ... " * name[end - size_to_keep: end]
    end
    count = get!(node_count, name, 0) + 1
    node_count[name] = count
    countstr = count > 1 ? "-$(node_count[name])" : ""
    "$name$countstr"
end

name: 201: "map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(map(m ... -2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-4)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)-2)" = 8772199286381852747 Int64

#2: use the ID instead of the name. This has the added advantage that it maps to the DAG quite obviously.

function auto_name!(name, parents...)
    parents_str = join(map(s->"$(s.id)", parents), ", ")
    isempty(parents_str) || (name *= "($parents_str)")
    node_count[name] += 1
    countstr = node_count[name] > 1 ? "-$(node_count[name])" : ""
    "$name$countstr"
end

name: 201: "map(199, 200)" = 8772199286381852747 Int64

both of them avoid the name blowup problem.

[SimonDanisch]

I'd say, let's use the id! The map(map(map....))) never carried any usable information for me anyways!

[robertsugar]

And now we are at it we could also add the function name, when calling auto_name! from map, foldp, filter, etc.:

auto_name!("map $(f)", input, inputsrest...)

output:
274: "map +(272, 273)" = 8772199286381852747 Int64

it will look a bit uglier for anonymous functions, but that's life

478: "map #54(476, 477)" = 101 Int64

[TsurHerman]

try using
https://github.com/TsurHerman/Signals.jl
Pkg.add("Signals")
disclaimer:
I am the author of that package