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: ``` julia 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: ``` julia 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 `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`. `SlabBuffer`s 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 ``` julia 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 `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 `AllocBuffer`s 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 ``` julia @no_escape buf begin y = @alloc(T, n, m, o) f(y) end ``` this turns into the equivalent of ``` julia 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`: ``` julia 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 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: ``` julia #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](https://github.com/brenhinkeller/StaticTools.jl) (and thus [StaticCompiler.jl](https://github.com/tshort/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 ``` julia 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 ```