Allocate and forget with cyclical allocation

[Aniki]

Suppose we have a fixed size set of N objects from which we want to allocate on demand.

On the first allocation we get the 1st object.
On the next we get the 2nd object.
...
On the Nth we get the Nth and last object.

At this point if we try to allocate again, some other allocator might stop the execution or simply return null, but a "cyclical allocator" would just wrap-around and return the 1st object.


The thesis of this post is that this wrap-around behavior is useful because it saves one from having to deallocate the objects explicitly.

Not having to deallocate objects simplifies the usage of a data type and increases its "expressive power".
One of the benefits of high level languages compared to very low level ones (e.g assembly) is the freedom to arbitrary nest expressions. Unfortunately one cannot use compound types (structs in vJass) in such a way (they could try but at some point they would run out of instances).

Cyclical allocation is not magic, it can only be safely applied when the lifetime of an object is shorter than the time it would take for the cyclical allocator to wrap-around and stomp on it. Objects that are only used (passed as arguments, returned) inside functions are good candidates. Objects that are stored in arrays/structs/hashtables are probably not.

A simple example might be a struct that implements a vector (mathematical vector) type. A vector type would implement functions that take 2 vectors (or vector and a scalar) and return a temporary vector. As a result of that, the functions can easily be nested.

Another example might be a struct/tuple that is used as the return value of a function which needs to return more than 1 thing.

Spells that make use of structs, need to allocate them, and after the duration of the spell (usually just moments after), need to deallocate them. Here a cyclical allocator can be used, but the benefit would be small because spells usually have to do other cleanup, so they might as well call deallocate on the struct.


Ot_Alloc is a hybrid allocator for structs, it has two alloc[ate] functions, one for instances whose lifetime is unknown or very long (these instances are allocated using the good old free list allocator), and one for instances whose lifetime is short (these instances are allocated using a cyclic allocator).

Ot_Alloc demo:

library otallocdemo initializer init

struct v3 extends array
    //! runtextmacro Ot_Alloc("4", "6")

    // Ot_Alloc implements the methods 'talloc', 'oalloc', 'dealloc' and 'otowned'

    real x
    real y
    real z

    static method tnew takes real x, real y, real z returns v3
        local v3 v = v3.talloc()
        set v.x = x
        set v.y = y
        set v.z = z
        return v
    endmethod

    static method onew takes real x, real y, real z returns v3
        local v3 v = v3.oalloc()
        set v.x = x
        set v.y = y
        set v.z = z
        return v
    endmethod

    method to_owned takes nothing returns v3
        if this.otowned() then
            // we are already an owned 'v3'
            return this
        else
            return onew(this.x, this.y, this.z)
        endif
    endmethod

    method free takes nothing returns nothing
        set this.x = 0.0
        set this.y = 0.0
        set this.z = 0.0

        // if 'this' was allocated by 'talloc' then 'dealloc' does nothing
        call this.dealloc()
    endmethod
endstruct

function v3a takes v3 a, v3 b returns v3
    return v3.tnew(a.x + b.x, a.y + b.y, a.z + b.z)
endfunction

function v3s takes v3 a, v3 b returns v3
    return v3.tnew(a.x - b.x, a.y - b.y, a.z - b.z)
endfunction

function v3m takes v3 a, v3 b returns v3
    return v3.tnew(a.x * b.x, a.y * b.y, a.z * b.z) // ignore bad math
endfunction

function v3d takes v3 a, v3 b returns v3
    return v3.tnew(a.x / b.x, a.y / b.y, a.z / b.z) // ignore bad math
endfunction

private function print_v3 takes v3 v returns nothing
    call BJDebugMsg(s)("v3(" + I2S(v) + ")(" + R2SW(v.x, 1, 2) + ", " + R2SW(v.y, 1, 2) + ", " + R2SW(v.z, 1, 2) + ")")
endfunction

private function delayed_init takes nothing returns nothing
    local v3 a
    local v3 b
    local v3 c
    local v3 d

    set a = v3.onew(1.0, 1.0, 1.0)
    set b = v3.onew(2.0, 2.0, 2.0)

    call print_v3(a)
    call print_v3(b)

    set c = v3a(a, b)
    call print_v3(c)

    set c = v3s(a, b)
    call print_v3(c)

    set c = v3m(a, b)
    call print_v3(c)

    set c = v3d(a, b)
    call print_v3(c)

    set d = v3a(c, v3.tnew(5.0, 5.0, 5.0)).to_owned()
    call print_v3(d)

    // if we uncomment we would get an error because
    // we only have 3 owned 'v3's to work with (//! runtextmacro Ot_Alloc("4", "6"))
    // and 2 temporary 'v3's
    // the owned 'v3's are 1, 2 and 3
    // the owned 'v3's start from 1 and go up to but not including 4
    // the temporary 'v3's are 4 and 5
    // the temporary 'v3' start from 4 and go up to but not including 6
    //
    // set d = v3.onew(6.0, 6.0, 6.0)

    // 'a', 'b' and 'd' are all owned 'v3's, so we need to free them, otherwise we would leak them
    call a.free()
    call b.free()
    call d.free()

    // 'c' is a temporary 'v3', we don't have to free it
endfunction

private function init takes nothing returns nothing
    call TimerStart(CreateTimer(), 0.0, false, function delayed_init)
endfunction

endlibrary // otallocdemo

Ot_Alloc:

library otalloc

//! textmacro Ot_Alloc takes Ta, Tb
    private static integer ot__tnext = $Ta$
    private static method talloc takes nothing returns thistype
        local thistype x = ot__tnext
        set ot__tnext = ot__tnext + 1
        if ot__tnext == $Tb$ then
            set ot__tnext = $Ta$
        endif
        return x
    endmethod

    private static thistype ot__ohead = 0
    private thistype ot__onext
    static method oalloc takes nothing returns thistype
        local thistype x
        if ot__ohead.ot__onext != 0 then
            set x = ot__ohead
            set ot__ohead = ot__ohead.ot__onext
        else
            set ot__ohead = ot__ohead + 1
            debug if ot__ohead == $Ta$ then
            debug    call DisplayTimedTextToPlayer(GetLocalPlayer(), 0.0, 0.0, 1000.0, "Unable to allocate id for an object of type: thistype")
            debug    return 0
            debug endif
            set x = ot__ohead
        endif
        set x.ot__onext = 0
        return x
    endmethod

    private method dealloc takes nothing returns nothing
        if integer(this) < $Ta$ then
            debug if this.ot__onext != 0 then
            debug    call DisplayTimedTextToPlayer(GetLocalPlayer(), 0.0, 0.0, 1000.0, "Double free of type: thistype")
            debug    return
            debug endif
            set this.ot__onext = ot__ohead
            set ot__ohead = this
        endif
    endmethod

    private method otowned takes nothing returns boolean
        return integer(this) < $Ta$
    endmethod
//! endtextmacro

endlibrary // otalloc

 

[Aniki]

Another example where cyclical allocation comes in handy:

function interface Foo_Fn takes integer n returns integer

function square1 takes integer x returns integer
    return x*x
endfunction

function factorial1 takes integer n returns integer
    if n == 1 then
        return 1
    else
        return n * factorial1(n - 1)
    endif
endfunction

function fibonacci1 takes integer n returns integer
    if n == 0 then
        return 0
    elseif n == 1 then
        return 1
    else
        return fibonacci1(n - 2) + fibonacci1(n - 1)
    endif
endfunction

function function_pointers_vjass takes nothing returns nothing
    local Foo_Fn array fns
    local integer array fn_args
    local integer a

    set fns[0] = Foo_Fn.square1
    set fn_args[0] = 3

    set fns[1] = Foo_Fn.factorial1
    set fn_args[1] = 5

    set fns[2] = Foo_Fn.fibonacci1
    set fn_args[2] = 11

    set a = 0
    loop
        exitwhen a == 3
        call writeln("(" + I2S(fn_args[a]) + ") = " + I2S(fns[a].evaluate(fn_args[a])))
        set a = a + 1
    endloop
endfunction

struct Bar_Fn extends array
    //! runtextmacro Ot_Alloc("1", "8191")
    integer n
    integer r
    static Bar_Fn args = 0
    static method scall takes string fn, integer n returns Bar_Fn
        local Bar_Fn x = talloc()
        set x.n = n
        set Bar_Fn.args = x
        call ExecuteFunc(fn)
        return x
    endmethod
endstruct

function square2 takes nothing returns nothing
    local Bar_Fn x = Bar_Fn.args
    set x.r = x.n*x.n
endfunction

function factorial2 takes nothing returns nothing
    local Bar_Fn x = Bar_Fn.args
    if x.n == 1 then
        set x.r = 1
    else
        set x.r = x.n * Bar_Fn.scall("factorial2", x.n - 1).r
    endif
endfunction

function fibonacci2 takes nothing returns nothing
    local Bar_Fn x = Bar_Fn.args
    if x.n == 0 then
        set x.r = 0
    elseif x.n == 1 then
        set x.r = 1
    else
        set x.r = Bar_Fn.scall("fibonacci2", x.n - 2).r + Bar_Fn.scall("fibonacci2", x.n - 1).r
    endif
endfunction

function function_pointers_approximation takes nothing returns nothing
    local string array fn_names
    local integer array fn_args
    local string fn
    local integer a

    set fn_names[0] = "square2"
    set fn_args[0] = 3

    set fn_names[1] = "factorial2"
    set fn_args[1] = 5

    set fn_names[2] = "fibonacci2"
    set fn_args[2] = 11

    set a = 0
    loop
        exitwhen a == 3

        call writeln(fn_names[a] + "(" + I2S(fn_args[a]) + ") = " + I2S(Bar_Fn.scall(fn_names[a], fn_args[a]).r))

        set a = a + 1
    endloop
endfunction