# Co-allocated reference objects **URL:** \ **Category:** Crystal Contrib\ **Created:** [March 3, 2025, 3:10pm UTC](https://forum.crystal-lang.org/t/co-allocated-reference-objects/7820 "2025-03-03T15:10:47Z")\ **Posts on this page:** 6\ **Page:** 1
**Author:** ![HertzDevil](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/hertzdevil/32/1023_2.png) [@HertzDevil](https://forum.crystal-lang.org/u/HertzDevil)\ **Post date:** [March 3, 2025, 3:10pm UTC](https://forum.crystal-lang.org/t/co-allocated-reference-objects/7820/1 "2025-03-03T15:10:47Z")
`ReferenceStorage(T)` exposes the instance representation of a reference type `T`. The original use case of this type and `T.unsafe_construct` is to materialize instances of `T` from memory locations other than the GC heap, such as on the call stack or embedded inside another reference type. However, a different kind of use is also possible where multiple `T` instances are created side by side from a single allocation. Let’s say we want a fixed-size collection of `Foo`s: ```crystal class Foo def initialize(@x : Int32, @y : String) end end foos = Slice.new(10) { |i| Foo.new(i, i.to_s) } foos[0] # => # foos[3] # => # foos[7] # => # ``` Behind the scenes, this will call `GC.malloc(instance_sizeof(Foo))` 10 times. Because `Foo` does not require variable-size allocation like `String` or `Log::Metadata`, we could easily group all the allocations into one call: ```crystal foos = Pointer(ReferenceStorage(Foo)).malloc(10) 10.times { |i| Foo.unsafe_construct(foos + i, i, i.to_s) } foos.as(Foo) # => # (foos + 3).as(Foo) # => # (foos + 7).as(Foo) # => # ``` Notice how the gaps between those `Foo`s’ addresses are now smaller, since those instances are indeed stored contiguously: ```crystal puts foos.as(UInt8*).to_slice(instance_sizeof(Foo) * 10).hexdump ``` ```auto 00000000 b6 00 00 00 00 00 00 00 b8 55 fe 02 01 00 00 00 .........U...... 00000010 b6 00 00 00 01 00 00 00 c8 55 fe 02 01 00 00 00 .........U...... 00000020 b6 00 00 00 02 00 00 00 a0 6f 30 03 01 00 00 00 .........o0..... 00000030 b6 00 00 00 03 00 00 00 90 6f 30 03 01 00 00 00 .........o0..... 00000040 b6 00 00 00 04 00 00 00 80 6f 30 03 01 00 00 00 .........o0..... 00000050 b6 00 00 00 05 00 00 00 70 6f 30 03 01 00 00 00 ........po0..... 00000060 b6 00 00 00 06 00 00 00 60 6f 30 03 01 00 00 00 ........`o0..... 00000070 b6 00 00 00 07 00 00 00 50 6f 30 03 01 00 00 00 ........Po0..... 00000080 b6 00 00 00 08 00 00 00 40 6f 30 03 01 00 00 00 ........@o0..... 00000090 b6 00 00 00 09 00 00 00 30 6f 30 03 01 00 00 00 ........0o0..... ``` On each row, `b6 00 00 00` is `Foo.crystal_instance_type_id`, the next 4 bytes are `@x`, and finally the remaining 8 bytes are `@y.object_id`; there is no extra bookkeeping data for the allocator between the instances. The `foos` raw pointer and the `unsafe_construct` call could be further hidden from the public using a helper type: ```crystal struct ReferenceSlice(T) include Indexable(T) @buf : ReferenceStorage(T)* getter size : Int32 def initialize(@size : Int32, & : Int32 -> {Tuple, NamedTuple}) @buf = Pointer(ReferenceStorage(T)).malloc(size) size.times do |i| args, opts = yield i T.unsafe_construct(@buf + i, *args, **opts) end end def unsafe_fetch(index : Int) : T (@buf + index).as(T) end end foos = ReferenceSlice(Foo).new(10) do |i| args = {i, i.to_s} {args, NamedTuple.new} end foos[0] # => # foos[3] # => # foos[-2] # => # ``` Indexing a `ReferenceSlice(T)` becomes simple pointer arithmetic, and the objects have good spatial locality. In contrast, an `Slice(T)` always requires dereferencing its buffer pointer; both the buffer itself and the `T` instances could also be very far apart, depending on what the GC is doing. The main drawback is that all the objects in a `ReferenceSlice` must share the same lifetime, since there is only one allocation after all. A live reference to any `T` is implicitly a live reference to all other `T`s in that slice, thus extracting just a handful objects and discarding the rest is a bad idea. Additionally, the GC is not primarily designed for large allocations on the order of several MBs, so slice size can be a concern for fat classes (there are plenty of them among the Crystal AST nodes). Finally, this approach does not readily generalize to a resizable array of references, because calling `#realloc` on `@buf` invalidates all the objects immediately; their `object_id`s would change in-place, and all the old `T`s would point to freed memory. I wonder if there are any practical applications for such a `ReferenceSlice` type? ---
**Author:** ![yxhuvud](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/yxhuvud/32/27_2.png) [@yxhuvud](https://forum.crystal-lang.org/u/yxhuvud)\ **Post date:** [March 3, 2025, 7:18pm UTC](https://forum.crystal-lang.org/t/co-allocated-reference-objects/7820/2 "2025-03-03T19:18:38Z")
These look like fantastic additions to the toolbox of available things. I’m sure applications will show up over time for both variants. That said I’m not certain I like the names of either - it is not a storage of references, it is a joint storage of instances, or sets of instances where the backing memory is owned by the collection. And considering references are often stored in slices, that name is no better. I’d suggest something like `OwningStorage`, `OwnerStorage` or `InstanceStorage` or something like that. But that aside, they would both be really nice additions and I really like the deconstruction of the existing initialization into accessible methods all the way down. ---
**Author:** ![bcardiff](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/bcardiff/32/3_2.png) [@bcardiff](https://forum.crystal-lang.org/u/bcardiff)\ **Post date:** [March 3, 2025, 8:14pm UTC](https://forum.crystal-lang.org/t/co-allocated-reference-objects/7820/3 "2025-03-03T20:14:45Z")
This sounds like Buffer or Vector to me. In the past I did some refactors to split Array’s buffer into this kind of structure. But it was never merged and other optimization make it harder. Having this kind of structure make sense to me. But we can start as a shard and then merge it so we can iterate faster. ---
**Author:** ![jgaskins](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/jgaskins/32/2449_2.png) [@jgaskins](https://forum.crystal-lang.org/u/jgaskins)\ **Post date:** [March 4, 2025, 12:05am UTC](https://forum.crystal-lang.org/t/co-allocated-reference-objects/7820/4 "2025-03-04T00:05:54Z")
This sounds like an awesome way write a specialized database. The concept of a `ReferenceSlice` would be similar to a page of tuples in Postgres. ---
**Author:** ![ysbaddaden](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/ysbaddaden/32/2252_2.png) [@ysbaddaden](https://forum.crystal-lang.org/u/ysbaddaden)\ **Post date:** [March 4, 2025, 9:15am UTC](https://forum.crystal-lang.org/t/co-allocated-reference-objects/7820/5 "2025-03-04T09:15:50Z")
It like this `ReferenceSlice(T)`. It would be a nice foundation to write specialized types. > this approach does not readily generalize to a resizable array of references It can still be dynamic by allocating blocks instead of reallocating a contiguous buffer: it can grow and even shrink and the pointers wouldn’t change… until you start to reorder or move things inside the collection. ```crystal def [](index : Int32) : T raise IndexError.new unless index < @size i, j = index.divmod(entries_per_block) @blocks.unsafe_at[i].unsafe_fetch(j) end ``` ---
**Author:** ![HertzDevil](https://yyz2.discourse-cdn.com/flex036/user_avatar/forum.crystal-lang.org/hertzdevil/32/1023_2.png) [@HertzDevil](https://forum.crystal-lang.org/u/HertzDevil)\ **Post date:** [March 4, 2025, 12:38pm UTC](https://forum.crystal-lang.org/t/co-allocated-reference-objects/7820/6 "2025-03-04T12:38:02Z")
A minor spin on this theme is to allocate individual objects on demand, but still share the same buffer. That would of course be a specialized arena allocator: ```crystal class ReferenceArena(T, N) include Indexable(T) getter size : Int32 = 0 @buf = uninitialized ReferenceStorage(T)[N] def new(*args, **opts) : T raise RuntimeError.new "..." if @size >= N obj = T.unsafe_construct(@buf.to_unsafe + @size, *args, **opts) @size &+= 1 obj end def unsafe_fetch(index : Int) : T (@buf.to_unsafe + index).as(T) end end ``` From here you could turn `N` into a `@capacity` instance variable, add multiple “buckets”, etc. One common question is where `T#finalize` should be called; because we used `unsafe_construct` in `ReferenceSlice` and `ReferenceArena`, this is now entirely up to the user.