Type instability in Treap

New to Julia
1

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?

2

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
3

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
4

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
5

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.