# Control where mutables are allocated in a very special case: a large number of mutables of the same type

**URL:** <https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971>\
**Category:** Performance\
**Tags:** memory-allocation, mutable-structure\
**Created:** [July 3, 2021, 3:17am UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971 "2021-07-03T03:17:21Z")\
**Posts on this page:** 12\
**Page:** 1

<div class="post-metadata">

**Author:** ![zsunberg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zsunberg/32/1883_2.png) [@zsunberg](https://discourse.julialang.org/u/zsunberg)\
**Post date:** [July 3, 2021, 3:17am UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/1 "2021-07-03T03:17:21Z")

</div>

In my research, I often find myself incrementally creating large graphs or trees where each node has some properties that might get updated later.

Semantically, it makes the most sense for each node to be represented by a mutable object. But, since mutables are heap-allocated, this is very slow. What I want to do is to set aside a big chunk of memory for these nodes (essentially another stack). Then, when I create a new one, it should be trivial to find space to allocate it at the end of the occupied portion of this chunk (also perhaps there should be special gc behavior).

Is this possible now? Is it a change that could be added? (As far as I can tell, it would not change any semantics, except right where the object is constructed)

Another way of saying this is that I want a single special _source_ vector, where the mutable objects are actually stored contiguously in memory like immutables are, but any other reference to them is just a pointer.

(Currently I use an Int to represent each node and a vector for each of the properties (IIUC what MetaGraphs does), but this results in much harder-to-read code)

---

<div class="post-metadata">

**Author:** ![anon56330260](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@anon56330260](https://discourse.julialang.org/u/anon56330260)\
**Post date:** [July 3, 2021, 4:23am UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/2 "2021-07-03T04:23:47Z")

</div>

> [@zsunberg](#):
>
> Another way of saying this is that I want a single special _source_ vector, where the mutable objects are actually stored contiguously in memory like immutables are, but any other reference to them is just a pointer.

What you request is basically inline-stored mutable struct, which is currently not officially supported by Julia.

> [@zsunberg](#):
>
> Semantically, it makes the most sense for each node to be represented by a mutable object. But, since mutables are heap-allocated, this is very slow. What I want to do is to set aside a big chunk of memory for these nodes (essentially another stack). Then, when I create a new one, it should be trivial to find space to allocate it at the end of the occupied portion of this chunk (also perhaps there should be special gc behavior).

Before you try to design your own memory pool in Julia, note that Julia already has it’s own memory pool, so if you believe that having your own pool might make allocation (much) faster, you might be disappointed, unless your allocation has some special patterns.

But if you just want inline-stored mutable, you can twist pointers in Julia, just like in C++/C (Warning: this is as dangerous as in C++, before you copy the following codes, wall through them carefully). Let’s assume that you will to implement a linked list, which is essentially:

```julia
mutable struct Node
    x::Int
    next::Node
end

```

To store it in a contiguously, try following code:  
Firstly we define a immutable struct `Node`. It will be stored inline in the array. Then we define a `MNode`, which is essentially a pointer to `Node`.

```julia
# wrap Node as a mutable struct
struct MNode
    ptr::Ptr{Nothing}
end

struct Node
    x::Int
    next::MNode
end

```

then define getter and setter to make life easier. So when we mutate or get the field of `MNode`, we are mutating or get the field of the content (that is, `Node`) it points to.

```julia
# delegate the getproperty to underlying Node
function Base.getproperty(p::MNode,i::Symbol) 
    n = Base.unsafe_load(Base.unsafe_convert(Ptr{Node},getfield(p,:ptr)))
    getproperty(n,i)
end

# delegate the setproperty to underlying Node
@generated function _setproperty!(p::MNode,::Val{N},x::V) where {N,V}
    T = Node
    for i = 1:fieldcount(T)
        if fieldname(T,i) == N
            if fieldtype(T,i) != V
                return :(error("Type $T has a field named $N, but type of it is not $V"))
            else
                off = fieldoffset(T,i)
                return :(Base.unsafe_store!(Base.unsafe_convert(Ptr{$V},getfield(p,:ptr)+$off),x,1))
            end
        end
    end
    :(error("Type $T has no field named $N"))
end

function Base.setproperty!(p::MNode,name::Symbol,i) where T
    _setproperty!(p,Val(name),i)
end

```

Finally, build an allocator, which is essentially a stack of `Node`. When we allocate from the allocator, we return a `MNode` which points to the `Node`. Be careful of `deallocate!`, it does nothing more than substrate the stack pointer! (Note, if you deallocate element in arbitrary order, you need to implement your own memory allocator)

```julia
mutable struct NodeFactor
    # don't resize v! since it will cause element reallocating
    v::Vector{Node}
    stackhead::Int
    size::Int
    ptr::Ptr{Node}
    function NodeFactor(c::Int)
        # create a large vector
        v = Vector{Node}(undef,c)
        # get the underlying pointer of vector
        ptr = Base.unsafe_convert(Ptr{Node},v)
        return new(v,0,c,ptr)
    end
end
  
function allocate!(n::NodeFactor)
    if n.stackhead > n.size
        error("run out of space") 
    end
    # return new pointer
    newptr = n.ptr
    # move stack pointer to next place
    n.stackhead += 1
    # update pointer to next place
    n.ptr += sizeof(Node)
    return MNode(newptr)
end

function deallocate!(n::NodeFactor)
    if n.stackhead == 0
        error("double free!") 
    end
    n.stackhead -= 1
    n.ptr -= sizeof(Node)
    return
end

```

Then you can now test the allocator!

```julia
nf = NodeFactor(100)
# allocate three nodes
n1 = allocate!(nf)
n2 = allocate!(nf)
n3 = allocate!(nf)
n1.x = 1
n2.x = 2
n3.x = 18
n1.next = n2
n2.next = n3
println(n1.next.next.x == n3.x)

```

You should get true here.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 3, 2021, 10:34am UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/3 "2021-07-03T10:34:38Z")

</div>

> [@anon56330260](#):
>
> ```julia
> mutable struct Node
> x::Int
> next::Node
> end
> 
> ```

All that is very interesting and instructive, thanks. But maybe it is important to mention to the OP that in this example, an perhaps in his example as well, it is much easier to just let this Node to be immutable, store an array of those and just replace the entire node instead of mutating it.

I would suggest posting more details about the structure of the problem, to obtain more specific suggestions.

An immutable struct containing a mutable-static vector maybe, with overloaded getindex, or getter functions can be practical, maybe.

```julia
struct Node
  index::Int
  properties::MVector{2, Float64}
end
myfirstprop(n::Node) = n.properties[1]
etc

```

Then store an array of those.

---

<div class="post-metadata">

**Author:** ![anon56330260](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@anon56330260](https://discourse.julialang.org/u/anon56330260)\
**Post date:** [July 3, 2021, 3:20pm UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/4 "2021-07-03T15:20:02Z")

</div>

Then `MVetor` is again allocated on heap. This is not working.  
The core problem here is that, each mutable struct has their own identity, so if their lifetime is undetermined, that is, longer than a function call, they must be managed by GC and allocated on heap individually, or you manage memory manually.

---

<div class="post-metadata">

**Author:** ![lmiq](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lmiq/32/18314_2.png) [@lmiq](https://discourse.julialang.org/u/lmiq)\
**Post date:** [July 3, 2021, 3:33pm UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/5 "2021-07-03T15:33:10Z")

</div>

Trying to learn here. What would be the disadvantage of a vector of immutable structs? Only if the number of fields is very large I see a possible problem, otherwise just replacing the “nodes” in the vector by new ones seems good enough, isn’t it?

(There are some packages like StrideArrays.jl that appear to aid the management of large mutable arrays in the heap, but I don’t know much about them)

---

<div class="post-metadata">

**Author:** ![zsunberg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zsunberg/32/1883_2.png) [@zsunberg](https://discourse.julialang.org/u/zsunberg)\
**Post date:** [July 3, 2021, 4:19pm UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/6 "2021-07-03T16:19:22Z")

</div>

@ChenNingCong , @lmiq Thanks! However I am not quite satisfied, and [greed is an important julian value](https://julialang.org/blog/2012/02/why-we-created-julia/) 😉

> [@ChenNingCong](#):
>
> ```julia
> nf = NodeFactor(100)
> # allocate three nodes
> n1 = allocate!(nf)
> n2 = allocate!(nf)
> n3 = allocate!(nf)
> n1.x = 1
> n2.x = 2
> n3.x = 18
> n1.next = n2
> n2.next = n3
> println(n1.next.next.x == n3.x)
> 
> ```

Syntactically, this is very close to what I am looking for - thank you! But I think overloading setproperty is somewhat misleading and there is a lot of overhead for creating new types. If I allow myself to overload setproperty, there are other solutions that don’t involve pointers. What I really want is something to work like this:

```julia
mutable struct MyNode
    x::Int
    next::MyNode
end

p = SpecialPool(MyNode, 1000)

n = @alloc_hint p MyNode(1)

```

> [@ChenNingCong](#):
>
> Before you try to design your own memory pool in Julia, note that Julia already has it’s own memory pool, so if you believe that having your own pool might make allocation (much) faster, you might be disappointed, unless your allocation has some special patterns.

Yeah, you may be right. It seems like a big block of objects of the same type that all get deleted at the same time would be a pattern that could benefit. I do not know enough about garbage collection to know if this would actually help though.

> [@lmiq](#):
>
> Node to be immutable, store an array of those and just replace the entire node instead of mutating it.
> 
> I would suggest posting more details about the structure of the problem, to obtain more specific suggestions.

Thanks! I am aware of this technique 🙂. Again it requires a lot more awkward code than the `@alloc_hint` syntax above. The linked-list is a good enough example for discussion. A real example is here: [GitHub - JuliaPOMDP/ARDESPOT.jl: Implementation of the AR-DESPOT POMDP algorithm](https://github.com/JuliaPOMDP/ARDESPOT.jl)

---

<div class="post-metadata">

**Author:** ![zsunberg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zsunberg/32/1883_2.png) [@zsunberg](https://discourse.julialang.org/u/zsunberg)\
**Post date:** [July 3, 2021, 4:24pm UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/7 "2021-07-03T16:24:21Z")

</div>

> [@lmiq](#):
>
> What would be the disadvantage of a vector of immutable structs?

With SetField.jl it would look something like this:

```julia
nodes[id] = @set nodes[id].a = 3

```

You have to keep track of node id’s. It just results in more convoluted code.

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [July 3, 2021, 6:35pm UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/8 "2021-07-03T18:35:47Z")

</div>

Is this what you’re after?

> **[GitHub - tonyrubak/MemoryArena.jl: Memory Arenas for Julia](https://github.com/tonyrubak/MemoryArena.jl)**
>
> Memory Arenas for Julia. Contribute to tonyrubak/MemoryArena.jl development by creating an account on GitHub.

---

<div class="post-metadata">

**Author:** ![zsunberg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zsunberg/32/1883_2.png) [@zsunberg](https://discourse.julialang.org/u/zsunberg)\
**Post date:** [July 3, 2021, 10:04pm UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/9 "2021-07-03T22:04:17Z")

</div>

@jzr thanks!! that is basically what I’m after! It has a few rough edges, but I think it will work. Time to get down to benchmarking

---

<div class="post-metadata">

**Author:** ![anon56330260](https://avatars.discourse-cdn.com/v4/letter/a/f07891/32.png) [@anon56330260](https://discourse.julialang.org/u/anon56330260)\
**Post date:** [July 4, 2021, 1:28am UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/10 "2021-07-04T01:28:25Z")

</div>

Dose this package actually work for mutable types? I don’t think so. Mutable types have different memory layouts. Use `Ptr{MutableTypes}` won’t work as you might expected…  
Also, `grow` is implemented incorrectly. It doesn’t even try to free the memory. As long as you try to implement your own `grow` function, you can quickly see why mutable types should not be placed inline in array. If they are placed inline, you can’t grow the array by simply replacing the old one by allocating a new one, because you can’t move the mutable types to the new array (unless there is no other values holding the pointer to them, but how can you know that). You can copy immutable values but not mutable ones.  
Instead, you should keep pages of memory. When you grow the allocators, you allocate a new page if all pages are occupied. However this will also cause problems, because you need to scan the pages to determine whether there are free pages. How to implement a fast and correct one allocators is not easy…

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [July 4, 2021, 2:39am UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/11 "2021-07-04T02:39:27Z")

</div>

I haven’t used the package, I only know about it from reading this old benchmark thread [Julia programs now shown on benchmarks game website - #54 by Orbots](https://discourse.julialang.org/t/julia-programs-now-shown-on-benchmarks-game-website/17722/54)

---

<div class="post-metadata">

**Author:** ![jzr](https://avatars.discourse-cdn.com/v4/letter/j/eb9ed0/32.png) [@jzr](https://discourse.julialang.org/u/jzr)\
**Post date:** [July 4, 2021, 5:41am UTC](https://discourse.julialang.org/t/control-where-mutables-are-allocated-in-a-very-special-case-a-large-number-of-mutables-of-the-same-type/63971/12 "2021-07-04T05:41:36Z")

</div>

There is also [GitHub - RelationalAI-oss/Blobs.jl: Binary blobs with on-the-fly pointer patching](https://github.com/RelationalAI-oss/Blobs.jl). I’d be interested to hear if you have an assessment of this one as well.