@ericphanson many thanks for preparing the PR in the `#hashing`

branch of Convex.jl;

Iâ€™ve given it a try and unfortunately it seems not to solve the problem but likely just shift it around. Please let me know if you would like this conversation to continue in the PR or here.

I have again profiled my code (full tree dump below); this time the â€śhotâ€ť code path seems to be the following:

```
81108 ...vex/qMsri/src/atoms/affine/add_subtract.jl:117; +
...
79090 ...ex/qMsri/src/atoms/affine/add_subtract.jl:79; Convex.AdditionAtom(::Convex.AdditionAtom, ::Convex.MultiplyAtom)
78922 ./hashing.jl:18; hash
...
35415 ./abstractarray.jl:2204; hash(::Array{Convex.AbstractExpr,1}, ::UInt64)
...
39863 ./abstractarray.jl:2223; hash(::Array{Convex.AbstractExpr,1}, ::UInt64)
```

Looking at `add_subtract.jl:79`

, I see this:

```
return new(:+, hash(children), children, sz)
```

which might be causing recursion over the entire tree of operations?

Now: if `id_hash`

is going to be used as a â€śfingerprintâ€ť to quickly test if two subexpressions are different, then Convex.jl needs to compute it for every subexpression; because of the way addition (and multiplication, etc.) atoms are built, the hash has to be derived from all children and there seems to be no better general solution than `hash(::Array{AbstractExpr})`

. But then, when large and deep expressions are built, this just seems to be slowâ€¦

According to @abulakâ€™s remark I have tried:

```
Base.hash(a::AbstractExpr, h::UInt) = h
```

In my understanding, this would speed up the hashing but then make equality comparisons much slower; however this makes my code die in `solve!()`

with *KeyError: key 0xf4f7cf55a81fe6ca not found*

Now I am trying by re-adding the old definition for `hash(::Array{AbstractExpr}, ::UInt64)`

to see if *combined with the new simpler definition of *`hash()`

for single AbstractExprâ€™s it gives some better speed-up:

```
const hashaa_seed = UInt === UInt64 ? 0x7f53e68ceb575e76 : 0xeb575e7
Base.hash(a::AbstractExpr, h::UInt) = hash((a.id_hash, a.head), h)
function Base.hash(a::Array{AbstractExpr}, h::UInt)
h += hashaa_seed
h += hash(size(a))
for x in a
h = hash(x, h)
end
return h
end
```

Unfortunately, I do not see any speed-up with this eitherâ€¦

Anyway, hereâ€™s the full profile dump; itâ€™s entirely possible that I picked out the wrong section as the culprit for slowness:

```
julia> Profile.print(mincount=100)
81809 ./task.jl:268; (::getfield(Revise, Symbol("##80#82")){REPL.REPLBackend})()
81809 /home/rmurri/.julia/packages/Revise/439di/src/Revise.jl:975; run_backend(::REPL.REPLBackend)
81809 ...4/build/usr/share/julia/stdlib/v1.2/REPL/src/REPL.jl:86; eval_user_input(::Any, ::REPL.REPLBackend)
81809 ./boot.jl:330; eval(::Module, ::Any)
81809 /home/rmurri/w/BEAM.jl/src/BEAM.jl:59; beam(::Int64, ::Array{Float64,3}, ::Array{Float64,2}, ::Array{Float64,2}, ::Ar...
81809 /home/rmurri/w/BEAM.jl/src/BEAM.jl:110; beam(::Int64, ::Array{Float64,3}, ::Array{Float64,2}, ::Array{Float64,2}, ::A...
81809 ./abstractarray.jl:2073; map
81809 ./array.jl:548; collect_similar
81809 ./array.jl:619; _collect(::UnitRange{Int64}, ::Base.Generator{UnitRange{Int64},getfield(BEA...
81809 /home/rmurri/w/BEAM.jl/src/BEAM.jl:115; iterate
81809 /home/rmurri/w/BEAM.jl/src/BEAM.jl:386; make_constraint_A(::Array{Convex.Variable,1}, ::Int64, ::Array{Float64,2},...
81770 /home/rmurri/w/BEAM.jl/src/BEAM.jl:421; conv2d(::Array{Float64,2}, ::Convex.Variable)
81761 ./array.jl:611; collect(::Base.Generator{Base.Iterators.ProductIterator{Tuple{UnitRange{I...
81760 ./array.jl:630; collect_to_with_first!
81760 ./array.jl:651; collect_to!(::Array{Convex.AdditionAtom,2}, ::Base.Generator{Base.Iterat...
81760 ./generator.jl:47; iterate
81760 ./none:0; #15
81760 ./reduce.jl:420; sum
81760 ./reduce.jl:403; sum
81760 ./reduce.jl:208; mapreduce
81760 ./reduce.jl:208; #mapreduce#192
81760 ./reduce.jl:72; mapfoldl
81760 ./reduce.jl:72; #mapfoldl#188
81758 ./reduce.jl:61; mapfoldl_impl
649 ./reduce.jl:47; mapfoldl_impl(::typeof(identity), ::typeof(Base.add_sum), ::NamedT...
648 ./generator.jl:47; iterate
640 ./none:0; (::getfield(BEAM, Symbol("##16#18")){Int64,Int64,Array{Float64,2}...
202 ...ges/Convex/qMsri/src/atoms/affine/index.jl:83; getindex
202 ...ges/Convex/qMsri/src/atoms/affine/index.jl:80; getindex
199 ...ges/Convex/qMsri/src/atoms/affine/index.jl:17; Type
173 ./hashing.jl:18; hash
173 ./tuple.jl:303; hash
115 ./tuple.jl:303; hash(::Tuple{UnitRange{Int64},UnitRange{Int64},Nothing}, ::UIn...
342 .../qMsri/src/atoms/affine/multiply_divide.jl:102; *(::Float64, ::Convex.IndexAtom)
325 .../qMsri/src/atoms/affine/multiply_divide.jl:30; Type
254 ./hashing.jl:18; hash
254 ./tuple.jl:303; hash
190 .../packages/Convex/qMsri/src/expressions.jl:38; hash
81108 ./reduce.jl:49; mapfoldl_impl(::typeof(identity), ::typeof(Base.add_sum), ::NamedT...
81108 ./reduce.jl:21; add_sum
81108 ...vex/qMsri/src/atoms/affine/add_subtract.jl:117; +
499 ...ex/qMsri/src/atoms/affine/add_subtract.jl:70; Convex.AdditionAtom(::Convex.AdditionAtom, ::Convex.MultiplyAtom)
497 ./array.jl:811; append!
1410 ...ex/qMsri/src/atoms/affine/add_subtract.jl:77; Convex.AdditionAtom(::Convex.AdditionAtom, ::Convex.MultiplyAtom)
1408 ./array.jl:853; push!
1408 ./array.jl:811; _growend!
79090 ...ex/qMsri/src/atoms/affine/add_subtract.jl:79; Convex.AdditionAtom(::Convex.AdditionAtom, ::Convex.MultiplyAtom)
78922 ./hashing.jl:18; hash
2477 ./abstractarray.jl:2197; hash(::Array{Convex.AbstractExpr,1}, ::UInt64)
2477 ./indices.jl:446; getindex
158 ./abstractarray.jl:2203; hash(::Array{Convex.AbstractExpr,1}, ::UInt64)
117 ./array.jl:728; getindex
35415 ./abstractarray.jl:2204; hash(::Array{Convex.AbstractExpr,1}, ::UInt64)
7722 ./pair.jl:15; Pair(::Int64, ::Convex.MultiplyAtom)
7594 ./pair.jl:12; Type
8443 ./pair.jl:52; hash(::Pair{Int64,Convex.MultiplyAtom}, ::UInt64)
323 ./float.jl:565; hash
262 ./float.jl:561; hx
223 ./hashing.jl:62; hash_uint64
7800 ...packages/Convex/qMsri/src/expressions.jl:38; hash
1192 ./tuple.jl:303; hash(::Tuple{UInt64,Symbol}, ::UInt64)
585 ./float.jl:564; hash
187 ./float.jl:66; Type
372 ./float.jl:561; hx
281 ./hashing.jl:62; hash_uint64
583 ./tuple.jl:303; hash
245 ./hashing.jl:23; hash
189 ./hashing.jl:63; hash_uint
311 ./reflection.jl:312; hash
39863 ./abstractarray.jl:2223; hash(::Array{Convex.AbstractExpr,1}, ::UInt64)
149 ./array.jl:0; findprev(::getfield(Base, Symbol("##60#61")){Base.Fix2{typeof...
173 ./array.jl:1876; findprev(::getfield(Base, Symbol("##60#61")){Base.Fix2{typeof...
225 ./array.jl:1878; findprev(::getfield(Base, Symbol("##60#61")){Base.Fix2{typeof...
100 ./int.jl:49; <
2817 ./array.jl:1880; findprev(::getfield(Base, Symbol("##60#61")){Base.Fix2{typeof...
123 ./array.jl:728; getindex
26959 ./operators.jl:894; !
3259 ./operators.jl:939; isequal(::Convex.MultiplyAtom)
3178 ./operators.jl:924; Type
575332 ./task.jl:327; task_done_hook(::Task)
575332 ./task.jl:591; wait()
575332 ./task.jl:564; poptaskref(::Base.InvasiveLinkedListSynchronized{Task})
```