Trait objects with data-oriented / ECS style?

help
1

I recently learned about this design pattern where you have an integer ID for your "things" and then various arrays containing the "components" that make up those things. The pattern is sometimes called "struct of arrays" or "entity component system" (ECS). I'm trying to use this idea in a fledgling UI library I'm tinkering with. I'm using the slotmap crate for the "arrays".

Maybe I need to forget about trait objects here, but they seem very nice for some things. I had a UI Widget trait that had methods related to layout, rendering, and event handling. Eg:

trait Widget {
    fn try_layout(&mut self, w: f32, h: f32) -> LayoutTry;
    fn layout_decision(&mut self, w: f32, h: f32);
    fn render(&self, rc: &RenderContext, ...) 
    ...
}

Those layout methods implement a kind of "layout protocol". The VStack struct, for example, implemented them to layout children widgets in a vertical stack. I'm tempted to keep these dynamic pieces around, even in the data oriented design. Something like:

widget_geometry: SlotMap<WidgetGeometry>,                // location, size, 
widget_tree:     SecondaryMap<WidgetId, WidgetTreeInfo>, // parents, children
widget_layout:   SecondaryMap<WidgetId, Box<dyn WidgetLayout>>

In effect the widget_layout array would contain vtables for the layout functions. The weird thing is, what is self for those functions? I supposed I could create a kind of proxy struct that contained only the WidgetId (the slot map integer ID).

struct VStackId { id: WidgetId }
impl WidgetLayout for VStackId { .... }

So I'm wondering if anything has been written about this already. So I don't re-invent wheels here.

2

Traditionally, you iterate over all the arrays in parallel, so if you need a layout for one pass you simply skip any that don't have an entry, logically:

for (id, geo) in &widget_geometry {
  let Some(layout) = widget_layout.get(id) else { continue };
  ...
}

Though ideally you would use iterators to reduce redundant lookup work (by using ordered iteration, eg BTreeMap not HashMap)

The main thing to be aware of is potentially the biggest benefit of using this style is much higher performance, by keeping the memory together and avoiding branching logic inside the inner loop - you're losing both of those with trait objects. The alternative would be having a separate array per layout type that you do separate passes over. Up to you if that matters.

The ultimate avoiding wheel reinvention would be using an existing ECS implementation like bevy_ecs — Rust game dev // Lib.rs

2 Likes
3

I have to nitpick this framing a bit. I presume "this style" is referring to ECS (not a BTreeMap, mentioned just prior).

The biggest benefit to ECS is flexibility to defer decisions to runtime. A classic example is emergent behavior and emergent design: In a crafting game, if the player can combine items with logically competing properties (a "fire-ice sword") that's no problem for an ECS, because Fire and Ice are distinct components. The game doesn't have to be designed with fire-ice swords in mind, it's just something that emerges combinatorially. If you don't need this combinatorial flexibility, you probably don't need an ECS. At that point, it's just interface overhead that gets in the way. [1]

Performance benefits come from data-oriented designs, not data-driven. An ECS may be data-oriented, but this is an implementation detail. (A detail that the popular ECS crates pay close attention to, nonetheless.) My point here is that you don't need data-oriented state to make a functional ECS. Likewise, you don't need an ECS for data-oriented design.

I think it is easy to conflate these. "Data-driven" and "data-oriented" are similar-looking terms. Data-driven design is about creating a DSL in the Greenspun's Tenth Rule sense, where the native code is mostly just a DSL interpreter. Data-oriented design is about exploiting mechanical sympathy for performance reasons (cache locality, SIMD, et al). While the techniques can be combined, they are certainly separate topics. And it's worth identifying and applying them separately to the problem space.

  1. I'm really not sure why a UI would want emergent behavior. That's pretty much the opposite of what you want for consistent UX and accessibility. ↩︎

6 Likes
4

Well, no the "this style" was more about the "struct of arrays" vs "arrays of structures" and using IDs instead of object references.

The counterexample of using composition bit not data orientation is Unity's GameObject / Component split, which is functionality-wise identical to ECS, but trades more familiar usage for far worse performance.

5

I wasn't well aware of the distinction there, between "data-driven" and "data-oriented", so I just edited the post title, changing it from the former to the latter. I think that is more what I meant.

It sounds like these designs are used for different reasons, like extreme flexibility in games, and high performance. I'm interested in those things, but they are not the reason I first reached for these ideas. My first motive was simply that Rust (which I'm learning) makes it a pain to have a tree of objects with pointers going downward and upward, which is what I want for my UI widgets, especially with algorithms around event handling. So I started looking at slotmap and indextree crates, and then thought, okay, what do I put in these arrays?

It does seem like ECS is a way to combine ideas, similar to multiple inheritance, but without some of the problems. And I can see how that type of combination could be useful for UI objects.

6

If you look at a particular combination of component types (“archetype”) as like a class, then it has the following restrictions compared to general multiple inheritance:

  • The concrete class’s superclasses are all component classes.
  • The concrete class has no fields and does not override any methods.
  • Component classes have zero superclasses.

If you were to write an OOP program under these odd restrictions, the diamond problem of multiple inheritance would not arise (because there cannot be a common ancestor class), and you’d also end up having to write things in a more ECS-like fashion due to the restrictions on what you can do with methods.

7

You can implement the Unity design somewhat well in Rust with just a simple helper like https://lib.rs/crates/type-map:

struct Object {
  // Anything common ..

  pub components: TypeMap,
}

Whether that's actually better is fairly dubious...

8

The colon is being treated as part of the URL so the link doesn't work. You can surround the URL with <..> to fix it.

1 Like