How can I create a list of owned trait objects without allocating each item on the heap separately?

6
votes

I want an owned list of Rust trait objects. I could implement it as Vec<Box<dyn Trait>> but that allocates space on the heap for every trait object. What I’d prefer is a CompactList<dyn Trait> type with a memory representation that looks like:

[vtable1, size1, data1, vtable2, size2, data2, vtable3, size3, data3]

size* is the size in bytes of the corresponding data*.

With this, I could create an Iterator<Item = &dyn Trait>. The only operations I need on CompactList<T> are push() and iter().

1
rusttrait-objects
You could do that with std::raw::TraitObject. – mcarton
I'm pretty sure any solution is going to involve unsafe, rely on nightly features, and very likely to be undefined behavior. – Shepmaster
@mcarton, that would still only allow you to pack raw pointers together, not the actual data. Although you could pack them as vtable ptr, size, data, and then provide an iterator or index, that exposes raw::TraitObjects. – Peter Hall
You may be able to borrow some ideas from untyped arenas, for example bumpalo, which can allocate differently-typed values in chunks of memory using unsafe. – trent ᶠᵒʳᵐᵉʳˡʸ ᶜˡ
I wanted to avoid nightly and it didn’t look like there was much appetite for stabilizing std::raw::TraitObject. – Calebmer

1 Answers

5
votes

The dynstack crate does what you want. It relies on the representation of fat pointers, which is what trait objects are, and that representation could theoretically change some day.

While it solves the problem of avoiding heap allocations for each object, its in-memory representation is different: Instead of a flat list, there are basically two lists:

  • [data1, data2, ...]
  • [(vtable1, size1), (vtable2, size2), ...]

Since the data structs can have different sizes, your representation doesn't support O(1) random access, while this one does. See this blog post for details.

Example, adapted from the documentation:

use dynstack::{dyn_push, DynStack};
use std::fmt::Debug;

let mut stack = DynStack::<dyn Debug>::new();
dyn_push!(stack, "hello, world!");
dyn_push!(stack, 0usize);
dyn_push!(stack, [1, 2, 3, 4, 5, 6]);

for item in stack.iter() {
    println!("{:?}", item);
}