Language feature to pass a collection of structs to llvm as struct of collections

I'm currently working through a problem, where the desired semantics is to have a struct of vectors for performance reasons, but the vector of structs is much simpler.

soa-derive appears to be promising, but I feel like its usage is at a higher level of abstraction than the language design is capable of.

I was hoping to start a discussion around the prospect of being able to have a collection of structs, but at compile time, you can opt into reinterpreted as a struct of collections. To the user, the only change is the ability to opt in, and (theoretically) optimized performance.

I can see a few benefits of bringing in such a feature that are not immediately obvious. One that immediately comes to mind, is that it could open the door to seamless comparative benchmarking - could annotate a bench test, or perhaps a vector of structs, to run a benchmark for each layout and output the difference.

Can you give a few examples of code that you'd like to write, but isn't currently possible with soa-derive?

1 Like

The specific use case I have in mind is an indexed BinaryHeap in a very performance sensitive context. The BinaryHeap consists of entries with both unique id, and the priority value, like so

struct KeyedBinaryHeapEntry {
    id: u32, // unique id's 
    priority: u32, // implement partial order on only this, ignoring id
    /* other fields */
}

soa_derive doesn't have the means to make priority an arbitrary collection (such as Heap, Queue, etc), or to have finer-grained control to optimise cache friendliness.

This could possibly be resolved by annotating with #[derive(StructOfBinHeap)]

This, however, might be problematic when you try to couple together two different structs.

type Id = NonZeroU32;
type Priority = NonZeroUsize;
type HeapPos = usize;
struct IndexedBinHeap {
    // push() will sort with this first, can cache the movements for updateing the table.
    // holds an ID so it can update the entries table to lookup heap entry by Id in O(n)~
    #[collected_field = "BinaryHeap"]
    pr: id,
    #[couple_with(id)]
    priority: Priority,

    // By coupling the two collections at language implementation level, I'm thinking can optimise
    // some of the workload, such as opportunistic updating of HeapPos
    #[collected_field = "HashMap"]
    entries: Entry<Id, HeapPos>,
}

#[bench]
fn split_test_idx_bin_heap_layout()
    // repeats bench with two of member vecs together as one Vec of a tuple, and compares
    // with the bench run with default layout
    #[bench_layout(Vec<(id, priority)>)]
    let testee = IndexedBinHeap::new();
    /* performance torture test */

as an alternative to the #[bench] split testing, you could start to give clues to a run-time profiler/optimiser, allowing it to seek out ways to play around with the layout to maximise cache affinity.

Another limitation of soa_derive is the limitations that comes with proc_macros. Being able to have the ergonomics that come with this crate become seamlessly integrated with the language is something that I think is worth discussing.

It sounds like what you really want/need is an ECS. Have you looked into specs and/or legion?

1 Like

You're implying that the fact that soa_derive cannot perform these operations means that we need it as a language feature, but one doesn't really follow the other.

It sounds like what you want could mostly be achieved by improving/forking/replacing soa_derive, to include the features you want.

In general, the Rust community is very prudent about adding new features to the language. You want new features to add expressiveness to the language, to add concepts that can't be described using existing language constructs (eg macros). Ideally, these new concepts should be orthogonal to existing concepts, to have synergies that don't require additional syntax.

What you suggest isn't really it. It improves performances in some niche cases (SAO in cache-constrained workflows), but it does so in a way that could probably mostly be done with macros.

3 Likes

I can see that.