在连续的内存块中制作具有可变元素的链表

Question

我正在阅读有关在实时上下文中使用内存池的内容，我想实现文章 Making a Pool Allocator 中的代码。我已经停留在第一个方块上：制作一个固定大小块的循环单链表，所有这些都位于一个连续的块中。再往下，链表用于跟踪下一个空闲内存块；分配的块从列表中弹出；释放的块被重新添加到列表中。

对于固定大小元素的连续块，我显然考虑了 Vector 不可变元素。我可以使用数组索引作为地址，而不是制作一个带有可变节点的循环链表：

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)

行 pool[size] = Chunk(1, zero(T)) 让我停顿了一下：不可变 Chunks 的一个缺点是每次我对 [=15] 做某事时我都需要访问和编辑 pool =]，而且我不想被限制在不可变的 data 中。不幸的是，元素通常是独立存在的，并且比容器长寿。 return pool[1]，因此可变元素在堆上与包含的结构或数组分开分配。然而，在这个用例中，元素只存在于数组中。

这可能是一个远景，但有没有办法制作一个可变元素的链表，这些元素分配在连续的内存块中？

Answer 1

一段时间后，我发现我在要求一些奇怪的东西：一个所谓的“可变”对象，它不是在堆上独立分配的，因此没有通常意义上的地址。我真正需要的是 syntax 的可变性；改变 pool 就好了，索引可以作为地址。我可以通过为表示 pool[index] 的类型重载 getproperty 和 setproperty! 来实现赋值突变。这几乎不是最终草案，但它解决了我的问题中提出的问题：

# 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

对于具有多个数据字段的 Chunk，创建一个仅编辑 select 字段的新实例既复杂又浪费资源，因此在这种情况下，我可以为每个字段保留单独的池。我也不确定在堆栈上分配不可变结构或在数组中内联而不是在堆上分配不可变结构的确切“大小限制”，如 Julia 1.5 Highlights 中所述，但将字段拆分到池中也有帮助。

当然，这种解决方法的替代方法是在 C 中管理内存并将其包装在 Julia 中，但我改天再学习。

在连续的内存块中制作具有可变元素的链表

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

linked-list

julia

allocation