# Type instability in Treap

Hi,

I have done an implementation of a treap in Julia. I could not be satisfied with Treap.jl because I need the `split` operation and I wanted to keep the `maximum` element.

Hence, every time I insert a new element, I save the max of the Treap in type `Treap{K}`.

Some part of my treap implementation is here

``````type NodeImpl{K}
heap_key::PriorityT
tree_key::K
left::NodeImpl{K}
right::NodeImpl{K}
NodeImpl(key, priority, left, right) = new(priority, key, left, right)
NodeImpl(key) = new(rand(PriorityT),key,NodeImpl{K}(),NodeImpl{K}())
NodeImpl() = new(PriorityT(-Inf))
end

typealias Node{K} NodeImpl{K}
isempty(t::Node) = t.heap_key == PriorityT(-Inf)
copy{K}(t::Node{K}) = Node{K}(t.tree_key::K,t.heap_key,t.left,t.right)

type Treap{K}
root::Node{K}
max::Nullable{K} #minimum of the treap
Treap() = new(Node{K}(), Nullable{K}())
Treap(key::K) = new(Node{K}(key),Nullable(key))
end

function insert!{K}(t::Treap{K},k::Node{K})
insert!(t.root,k) # call another insert function
if isnull(t.max)
t.max = Nullable{K}(k.tree_key,true)
return
end

if k.tree_key > get(t.max)
t.max = Nullable{K}(k.tree_key,true)
end
end
``````

My problem comes from the insert function which seems to be type unstable, for example:

``````t = TreaP.Treap{Int64}()#Node{Int64}()
a = [Node{Int64}(abs(rand(Int8))) for ii=1:3]
insert!(t,a[1])
@code_warntype insert!(t,a[2])
``````

gives

``````@code_warntype insert!(t,a[2])
Variables:
#self#::Base.#insert!
t::TreaP.Treap{Int64}
k::TreaP.NodeImpl{Int64}
#temp#::Int64

Body:
begin
\$(Expr(:invoke, MethodInstance for insert!(::TreaP.NodeImpl{Int64}, ::TreaP.NodeImpl{Int64}), :(TreaP.insert!), :((Core.getfield)(t, :root)::TreaP.NodeImpl{Int64}), :(k))) # line 179:
unless (Base.not_int)((Core.getfield)((Core.getfield)(t::TreaP.Treap{Int64}, :max)::Nullable{Int64}, :hasvalue)::Bool)::Bool goto 9 # line 180:
SSAValue(0) = \$(Expr(:new, Nullable{Int64}, true, :((Core.getfield)(k, :tree_key)::Int64)))
(Core.setfield!)(t::TreaP.Treap{Int64}, :max, SSAValue(0))::Nullable{Int64} # line 181:
return
9:  # line 184:
SSAValue(3) = (Core.getfield)(k::TreaP.NodeImpl{Int64}, :tree_key)::Int64
SSAValue(2) = (Core.getfield)(t::TreaP.Treap{Int64}, :max)::Nullable{Int64}
\$(Expr(:inbounds, false))
# meta: location nullable.jl get 92
unless (Base.not_int)((Core.getfield)(SSAValue(2), :hasvalue)::Bool)::Bool goto 18
#temp#::Int64 = (Base.throw)(\$(QuoteNode(NullException())))::Union{}
goto 20
18:
#temp#::Int64 = (Core.getfield)(SSAValue(2), :value)::Int64
20:
# meta: pop location
\$(Expr(:inbounds, :pop))
unless (Base.slt_int)(#temp#::Int64, SSAValue(3))::Bool goto 28 # line 185:
SSAValue(1) = \$(Expr(:new, Nullable{Int64}, true, :((Core.getfield)(k, :tree_key)::Int64)))
(Core.setfield!)(t::TreaP.Treap{Int64}, :max, SSAValue(1))::Nullable{Int64}
return SSAValue(1)
28:
return
end::Union{Nullable{Int64}, Void}
``````

Any idea why this is the case?

`insert!` will return `Nullable{K}(k.tree_key,true)` if the last conditional is true since Julia implictly returns the value of the last code block/expression. Just add a `return` statement on the last line and the type instability should go away.

1 Like

change to

``````function insert!{K}(t::Treap{K},k::Node{K})
insert!(t.root,k)
if isnull(t.max)
t.max = Nullable{K}(k.tree_key,true)
return nothing
end

if k.tree_key > get(t.max)
t.max = Nullable{K}(k.tree_key,true)
return nothing
end
return nothing
end
``````

removed one the two instabilities (i.e. Union()), thank you.

``````@code_warntype insert!(t,a[2])
Variables:
#self#::Base.#insert!
t::TreaP.Treap{Int64}
k::TreaP.NodeImpl{Int64}
#temp#::Int64

Body:
begin
\$(Expr(:invoke, MethodInstance for insert!(::TreaP.NodeImpl{Int64}, ::TreaP.NodeImpl{Int64}), :(TreaP.insert!), :((Core.getfield)(t, :root)::TreaP.NodeImpl{Int64}), :(k))) # line 179:
unless (Base.not_int)((Core.getfield)((Core.getfield)(t::TreaP.Treap{Int64}, :max)::Nullable{Int64}, :hasvalue)::Bool)::Bool goto 9 # line 180:
SSAValue(0) = \$(Expr(:new, Nullable{Int64}, true, :((Core.getfield)(k, :tree_key)::Int64)))
(Core.setfield!)(t::TreaP.Treap{Int64}, :max, SSAValue(0))::Nullable{Int64} # line 181:
return TreaP.nothing
9:  # line 184:
SSAValue(3) = (Core.getfield)(k::TreaP.NodeImpl{Int64}, :tree_key)::Int64
SSAValue(2) = (Core.getfield)(t::TreaP.Treap{Int64}, :max)::Nullable{Int64}
\$(Expr(:inbounds, false))
# meta: location nullable.jl get 92
unless (Base.not_int)((Core.getfield)(SSAValue(2), :hasvalue)::Bool)::Bool goto 18
#temp#::Int64 = (Base.throw)(\$(QuoteNode(NullException())))::Union{}
goto 20
18:
#temp#::Int64 = (Core.getfield)(SSAValue(2), :value)::Int64
20:
# meta: pop location
\$(Expr(:inbounds, :pop))
unless (Base.slt_int)(#temp#::Int64, SSAValue(3))::Bool goto 29 # line 185:
SSAValue(1) = \$(Expr(:new, Nullable{Int64}, true, :((Core.getfield)(k, :tree_key)::Int64)))
(Core.setfield!)(t::TreaP.Treap{Int64}, :max, SSAValue(1))::Nullable{Int64} # line 186:
return TreaP.nothing
29:  # line 188:
return TreaP.nothing
end::Void
``````

It seems the `get` method for `Nullable` return a `Union()`. Is it good?

``````a=Nullable(1)
@code_warntype(get(a))
Variables:
#self#::Base.#get
x::Nullable{Int64}

Body:
begin
unless (Base.not_int)((Core.getfield)(x::Nullable{Int64}, :hasvalue)::Bool)::Bool goto 3
return (Base.throw)(\$(QuoteNode(NullException())))::Union{}
3:
return (Core.getfield)(x::Nullable{Int64}, :value)::Int64
end::Int64
``````

No, `get` is guaranteed to return an `Int64` in that case, as shown by the `end::Int64` part. If the Nullable in question doesnâ€™t have a value then a `NullException()` is thrown, and the â€śreturn typeâ€ť of that is a `Union{}` â€“ which is irrelevant, because the function doesnâ€™t return anything anyways.