Typed memory pool for julia.

binarytrees-MemoryArena.jl

using MemoryArena
using Printf
struct Node
  left::RefCell{Node}
  right::RefCell{Node}
end
function make(pool, d)
  d == 0 && return RefCell{Node}(nothing)
  alloc(pool, Node(make(pool, d - 1), make(pool, d - 1)))
end
check(t::Node) = 1 + check(t.left[]) + check(t.right[])
check(n::Nothing) = 1
function check(node::RefCell{Node})
  node[] == nothing && return 1
  return check(node[])
end
function threads_inner(pool, d, min_depth, max_depth)
    niter = 1 << (max_depth - d + min_depth)
    c = 0
    for j = 1:niter
        c += check(make(pool, d))
    end
    @sprintf("%i\t trees of depth %i\t check: %i\n", niter, d, c)
end
function loop_depths(io, d, min_depth, max_depth)
    output = ntuple(x-> String[], Threads.nthreads())
    Threads.@threads for d in min_depth:2:max_depth
        pool = TypedArena{Node}()
        push!(output[Threads.threadid()], threads_inner(pool, d, min_depth, max_depth))
        destroy(pool)
    end
    foreach(s->foreach(x->print(io, x), s), output)
end
function perf_binary_trees(io, N::Int=10)
    min_depth = 4
    max_depth = N
    stretch_depth = max_depth + 1
    pool = TypedArena{Node}()
    # create and check stretch tree
    let c = check(make(pool, stretch_depth))
        @printf(io, "stretch tree of depth %i\t check: %i\n", stretch_depth, c)
    end

    destroy(pool)
    pool = TypedArena{Node}()
    long_lived_tree = make(pool, max_depth)

    loop_depths(io, min_depth, min_depth, max_depth)
    @printf(io, "long lived tree of depth %i\t check: %i\n", max_depth, check(long_lived_tree))
    destroy(pool)

end
 @time perf_binary_trees(stdout, 5)
 @time perf_binary_trees(stdout, 21)

binarytrees.jl

using Printf
using TypedPools

struct Node
    left::Int
    right::Int
end
function make(pool, d)
    d == 0 && return 0
    alloc!(pool, Node(make(pool, d - 1), make(pool, d - 1)))
end
check(pool, t::Node) = 1 + check(pool, t.left) + check(pool, t.right)
function check(pool, node::Int)
    node == 0 && return 1
    @inbounds return check(pool, pool[node])
end
function delete_tree(pool, node::Node)
  delete_tree(pool,node.left) 
  delete_tree(pool,node.right) 
end
function delete_tree(pool, node::Int)
    node == 0 && return 1
    delete_tree(pool,pool[node])
    free!(pool,node)
end

function threads_inner(pool, d, min_depth, max_depth)
    niter = 1 << (max_depth - d + min_depth)
    c = 0
    for j = 1:niter
        tree = make(pool, d)
        c += check(pool, tree)
        # much faster to just empty the pool, but feels a bit like a cheat
        #empty!(pool)
        delete_tree(pool,tree)
    end
    @sprintf("%i\t trees of depth %i\t check: %i\n", niter, d, c)
end
function loop_depths(io, d, min_depth, max_depth)
    output = ntuple(x-> String[], Threads.nthreads())
    pools = ntuple(x->StructPool{Node}(4), Threads.nthreads())
    Threads.@threads for d in min_depth:2:max_depth
      pool = pools[Threads.threadid()]
      push!(output[Threads.threadid()], threads_inner(pool, d, min_depth, max_depth))
    end
    foreach(s->foreach(x->print(io, x), s), output)
end
function perf_binary_trees(io, N::Int=10)
    min_depth = 4
    max_depth = N
    stretch_depth = max_depth + 1
    pool = StructPool{Node}(4)
    # create and check stretch tree
    stretch = make(pool, stretch_depth)
    let c = check(pool, stretch)
        @printf(io, "stretch tree of depth %i\t check: %i\n", stretch_depth, c)
    end

    # much faster to just empty the pool, but feels a bit like a cheat
    #empty!(pool)
    delete_tree(pool,stretch)

    long_lived_tree = make(pool, max_depth)

    loop_depths(io, min_depth, min_depth, max_depth)
    @printf(io, "long lived tree of depth %i\t check: %i\n", max_depth, check(pool, long_lived_tree))

end
println("Thread count: ", Threads.nthreads())
 @time perf_binary_trees(stdout, 5)
 @time perf_binary_trees(stdout, 21)

TypedPools.jl

module TypedPools

  export
  Handle,
  TypedPool,
  StructPool,
  MutableStructPool,
  alloc!,
  alloc_args!,
  alloc_inplace!,
  free!,
  @with

  import Base: @propagate_inbounds
  import Base: getindex, resize!, empty!

  function args_with( args, obj )
    fun = first(args)
    argsobj = vcat([fun,obj], args[2:end])
    argsobj
  end

  function with1(obj, funex)
    if funex.head == :call
      funex.args = args_with(funex.args,obj)
    elseif funex.head == :(=) && typeof(funex.args[2]) == Expr && funex.args[2].head == :call
      funex.args[2].args = args_with(funex.args[2].args,obj)
    end
    funex
  end
 
  """
  macro to place the @with argument into first position of all non-nested function calls 

      v = Int[]
      @with v begin
        push!(5)
        push!(6)
        push!(length(v))
        a = length()
        doublecat = l->vcat(l,l) 
        aa = doublecat() 
        push!(length(aa))
      end
  """
  macro with(obj, bod)
    if bod.head == :block
      for funex in filter(y->
                            y.head == :call || y.head == :(=),
                          filter(x->typeof(x) != LineNumberNode, bod.args))
        with1(obj, funex)
      end
    else
      with1(obj,bod)
    end
    bod
  end



  const Handle = Int
  abstract type TypedPool{T} end

  struct StructPool{T} <: TypedPool{T}
    free_list::Vector{Handle}
    pool::Vector{T}
    function StructPool{T}( size::Int ) where T 
      tp = new(Handle[], T[])
      resize!(tp.pool, size)
      empty!(tp.pool)
      tp
    end
    StructPool{T}() where T = new(Handle[], T[])
  end

  struct MutableStructPool{T} <: TypedPool{T}
    free_list::Vector{Handle}
    pool::Vector{T}
    function MutableStructPool{T}( size::Int ) where T 
      tp = new(Handle[], T[])
      resize!(tp.pool, size)
      empty!(tp.pool)
      tp
    end
  end

  pool(tp::StructPool{T}) where T = tp.pool
  free_list(tp::StructPool{T}) where T = tp.free_list
  pool(tp::MutableStructPool{T}) where T = tp.pool
  free_list(tp::MutableStructPool{T}) where T = tp.free_list

  @propagate_inbounds function getindex(tp::StructPool{T}, h::Handle) where T
    @inbounds tp.pool[h] 
  end
  @propagate_inbounds function getindex(tp::MutableStructPool{T}, h::Handle) where T
    @inbounds tp.pool[h] 
  end

  function alloc!(tp::TP, el::T) where {T,TP<:TypedPool{T}}
    if isempty(free_list(tp))
      push!(pool(tp),el)
      Handle(length(pool(tp)))
    else
      h = pop!(free_list(tp))
      pool(tp)[h] = el
      h
    end
  end

  alloc!(tp::TypedPool{T}) where T = alloc!(tp, T())

  @generated function inplace!(xy, a...)
    farg = fieldnames(xy)
    ex = Expr(:block)
    ex.args = reduce(vcat, map(
                               (f,i)->:(setproperty!(xy, $(QuoteNode(f)), a[$i])),
                               farg, 1:length(a) ))
    ex
  end

  function alloc_inplace!(tp::MutableStructPool{T}, a...) where T 
    if isempty(free_list(tp))
      alloc!(tp, T(a...))
    else
      h = pop!(free_list(tp))
      @inbounds inplace!(pool(tp)[h], a...)
      h
    end
  end

  alloc_args!(tp::MutableStructPool{T}, a...) where T = alloc_inplace!(tp, a...)

  alloc_args!(tp::StructPool{T}, a...) where T = alloc!(tp, T(a...))

  free!(tp::TypedPool{T}, h::Handle) where T = push!(free_list(tp), h)

  function empty!(tp::TypedPool{T}) where T
    empty!(pool(tp))
    empty!(free_list(tp))
  end

end