Bumper.jl

Every task has its own independent default buffer. A task's buffer is only created if it is used, so this does not slow down the spawning of Julia tasks in general. Here's a demo showing that the default buffers are different:

using Bumper
let b = default_buffer() # The default buffer on the main task
    t = @async default_buffer() # Get the default buffer on an asychronous task
    fetch(t) === b
end

false

Whereas if we don't spawn any tasks, there is no unnecessary buffer creation:

let b = default_buffer()
    b2 = default_buffer() 
    b2 === b
end

true

Because of this, we don't have to worry about @no_escape begin ... @alloc() ... end blocks on different threads or tasks interfering with each other, so long as they are only operating on buffers local to that task or the default_buffer().

SlabBuffer is a slab-based bump allocator which can dynamically grow to hold an arbitrary amount of memory. Small allocations from a SlabBuffer will live within a specific slab of memory, and if that slab fills up, a new slab is allocated and future allocations will then happen on that slab. Small allocations are stored in slabs of size SlabSize bytes (default 1 megabyte), and the list of live slabs are tracked in a field called slabs. Allocations which are too large to fit into one slab are stored and tracked in a field called custom_slabs.

SlabBuffers are nearly as fast as stack allocation (typically up to within a couple of nanoseconds) for typical use. One potential performance pitfall is if that SlabBuffer's current position is at the end of a slab, then the next allocation will be slow because it requires a new slab to be created. This means that if you do something like

buf = SlabBuffer{N}()
@no_escape buf begin
    @alloc(Int8, N÷2 - 1) # Take up just under half the first slab
    @alloc(Int8, N÷2 - 1) # Take up another half of the first slab
    # Now buf should be practically out of room. 
    for i in 1:1000
        @no_escape buf begin
            y = @alloc(Int8, 10) # This will allocate a new slab because there's no room
            f(y)
        end # At the end of this block, we delete the new slab because it's not needed.
    end
end

then the inner loop will run slower than normal because at each iteration, a new slab of size N bytes must be freshly allocated. This should be a rare occurance, but is possible to encounter.

Do not manipulate the fields of a SlabBuffer that is in use.

AllocBuffer{StorageType} is a very simple bump allocator that could be used to store a fixed amount of memory of type StorageType, so long as ::StoreageType supports pointer, and sizeof. If it runs out of memory to allocate, an error will be thrown. By default, AllocBuffer stores a Vector{UInt8} of 1 megabyte.

Allocations using AllocBuffers should be just as fast as stack allocation.

Do not manually manipulate the fields of an AllocBuffer that is in use.

Bumper.jl's SlabBuffer type is very flexible and fast, and so should almost always be preferred, but you may have specific use-cases where you want to use a different design or make different tradeoffs, but want to be able to interoperate with Bumper.jl's other features. Hence, Bumper.jl provides an API for you to hook custom allocator types into it.

When someone writes

@no_escape buf begin
    y = @alloc(T, n, m, o)
    f(y)
end 

this turns into the equivalent of

begin
    local cp = Bumper.checkpoint_save(buf)
    local result = begin 
        y = Bumper.alloc!(buf, T, n, m, o)
        f(y)
    end
    Bumper.checkpoint_restore!(cp)
    result
end

checkpoint_save should save the state of buf, alloc! should create an array using memory from buf, and checkpoint_restor! needs to reset buf to the state it was in when the checkpoint was created.

Hence, in order to use your custom allocator with Bumper.jl, all you need to write is the following methods:

• Bumper.alloc_ptr!(::YourAllocator, n::Int)::Ptr{Nothing} which returns a pointer that can hold up to n bytes, and should be created from memory supplied with your allocator type however you see fit.
  • Alternatively, you could implement Bumper.alloc!(::YourAllocator, ::Type{T}, s::Vararg{Integer}) which should return a multidimensional array whose sizes are determined by s..., created from memory supplied by your custom allocator. The default implementation of this method calls Bumper.alloc_ptr!.
• Bumper.checkpoint_save(::YourAllocator)::YourAllocatorCheckpoint which saves whatever information your allocator needs to save in order to later on deallocate all objects which were created after checkpoint_save was called.
• checkpoint_restore!(::YourAllocatorCheckpoint) which resets the allocator back to the state it was in when the checkpoint was created.

Let's look at a concrete example where we make our own simple copy of AllocBuffer:

mutable struct MyAllocBuffer
    buf::Vector{UInt8} # The memory chunk we'll use for allocations
    offset::UInt       # A simple offset saying where the current position of the allocator is.
	
    #Default constructor
    MyAllocBuffer(n::Int) = new(Vector{UInt8}(undef, n), UInt(0))
end

struct MyCheckpoint
    buf::MyAllocBuffer # The buffer we want to store
    offset::UInt       # The buffer's offset when the checkpoint was created
end

function Bumper.alloc_ptr!(b::MyAllocBuffer, sz::Int)::Ptr{Cvoid}
    ptr = pointer(b.buf) + b.offset
    b.offset += sz
    b.offset > sizeof(b.buf) && error("alloc: Buffer out of memory.")
    ptr
end

function Bumper.checkpoint_save(buf::MyAllocBuffer)
    MyCheckpoint(buf, buf.offset)
end
function Bumper.checkpoint_restore!(cp::MyCheckpoint)
    cp.buf.offset = cp.offset
    nothing
end

that's it!

julia> let x = [1, 2, 3], buf = MyAllocBuffer(100)
           @btime f($x, $buf)
       end
  9.918 ns (0 allocations: 0 bytes)
9

As a bonus, this isn't required, but if you want to have functionality like default_buffer, it can be simply implemented as follows:

#Some default size, say 16kb
MyAllocBuffer() = MyAllocBuffer(16_000)

const default_buffer_key = gensym(:my_buffer)
function Bumper.default_buffer(::Type{MyAllocBuffer})
    get!(() -> MyAllocBuffer(), task_local_storage(), default_buffer_key)::MyAllocBuffer
end

You may also want to implemet Bumper.reset_buffer! for refreshing you allocator to a freshly initialized state.

Bumper.jl is in the process of becoming a dependancy of StaticTools.jl (and thus StaticCompiler.jl), which extends Bumper.jl with a new buffer type, MallocSlabBuffer which is like SlabBuffer but designed to work without needing Julia's runtime at all. This allows for code like the following

using Bumper, StaticTools
function times_table(argc::Int, argv::Ptr{Ptr{UInt8}})
    argc == 3 || return printf(c"Incorrect number of command-line arguments\n")
    rows = argparse(Int64, argv, 2)            # First command-line argument
    cols = argparse(Int64, argv, 3)            # Second command-line argument

    buf = MallocSlabBuffer()
    @no_escape buf begin
        M = @alloc(Int, rows, cols)
        for i=1:rows
            for j=1:cols
                M[i,j] = i*j
            end
        end
        printf(M)
    end
    free(buf)
end

using StaticCompiler
filepath = compile_executable(times_table, (Int64, Ptr{Ptr{UInt8}}), "./")

giving

shell> ./times_table 12, 7
1   2   3   4   5   6   7
2   4   6   8   10  12  14
3   6   9   12  15  18  21
4   8   12  16  20  24  28
5   10  15  20  25  30  35
6   12  18  24  30  36  42
7   14  21  28  35  42  49
8   16  24  32  40  48  56
9   18  27  36  45  54  63
10  20  30  40  50  60  70
11  22  33  44  55  66  77
12  24  36  48  60  72  84