Making a linked list with mutable elements in a contiguous block of memory

user_4132144 0
Viewed 142

I was reading about the use of memory pools in real-time contexts, and I wanted to implement the code in the article Making a Pool Allocator. I'm already stuck at square one: making a circular singly-linked list of fixed-size chunks that all reside in a contiguous block. Further down the line, the linked list is used to track the next free memory chunk; allocated chunks are popped off the list; deallocated chunks are prepended back onto the list.

For a contiguous block of fixed-size elements, I obviously considered a Vector of immutable elements. Rather than making a circular linked list with mutable nodes, I could use the array index as an address:

struct Chunk{T}
    next::Int
    data::T
end

function Pool(T, size)
    pool = Chunk.(2:size+1, zero(T))
    pool[size] = Chunk(1, zero(T))
    return pool
end

intpool = Pool(Int, 5)

The line pool[size] = Chunk(1, zero(T)) gave me pause: a downside of immutable Chunks is that I need to access and edit the pool every time I did something with the data, and I didn't want to be restricted to immutable data anyway. Unfortunately, elements generally exist independently and can outlive containers e.g. return pool[1], so mutable elements are allocated on the heap separately from a containing struct or array. However, in this use case, the elements only exist in the array.

This may be a long shot, but is there a way to make a linked list of mutable elements that are allocated in a contiguous block of memory?

julia allocation linked-list
1 Answers

After some time, I figured that I was asking for something weird: a so-called "mutable" object that isn't allocated independently on the heap and thus doesn't have an address in the usual sense. What I actually needed is the syntax of mutability; mutating pool is just fine, and the indices can serve as addresses. I could do that for assignment-mutation by overloading getproperty and setproperty! for a type that represents pool[index]. This is hardly a final draft but it gets around the problem posed in my question:

# include the original post's code here

struct PoolRef{T}
    pool::Vector{Chunk{T}}
    index::Int64
end
# points to heap-allocated Vector, but not heap allocated in Julia >=1.5

function Base.getproperty(p::PoolRef{T}, name::Symbol) where T
    if name == :data
        getfield(p.pool[p.index], name)
    else # :pool, :index
        getfield(p, name)
    end
end

function Base.setproperty!(p::PoolRef{T}, name::Symbol, newdata::T) where T
    if name == :data
        oldvalue = p.pool[p.index]
        newvalue = Chunk(oldvalue.next, newdata)
        p.pool[p.index] = newvalue
    end
end

# intended usage
x = PoolRef(3, intpool)
x.data += 33
x.data

For a Chunk with multiple data fields, creating a new instance to only edit a select field is complicated and wasteful, so in that case I could keep separate pools for each field. I'm also not sure of the exact "size limit" for allocating immutable structs on the stack or inline in arrays instead of the heap, as mentioned in the Julia 1.5 Highlights, but splitting the fields into pools would help with that too.

Of course, the alternative to such workarounds is to manage memory in C and wrapping it in Julia, but I'll learn that another day.

user_41321440
Related