Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An Introduction to Data Oriented Design with Rust

jamesmcm.github.io

Post reply on HN
Print view View original

71–80 of 161 posts

Re: An Introduction to Data Oriented Design with Rust

#71

Post by dragontamer »

Rusky wrote: post #67
dragontamer wrote: post #62

Earlier quoted context omitted.

> A popular one is to group your entities by "archetype"- you have two arrays of Point2Ds, one for those without a Z coordinate and one for those with a Z coordinate. Now if you want all Point2Ds, you loop over both arrays; if you want all Point3Ds, you just loop over one. (This generalizes cleanly to larger numbers of "components.") But now your Point2D code needs to be aware of the Point3D code. Violating the open-…

> But now your Point2D code needs to be aware of the Point3D code. Not at all! You write the archetype management code once, and then the Point2D code just asks it for Point2Ds, nothing else, and that doesn't change no matter how you use Point2D elsewhere.

I'm having difficulty understanding how your proposal works.

In the beginning, there was one struct-of-arrays, the Point2D x and y arrays.

    int Point2D_x[];
    int Point2D_y[];
We also have a number of functions that use these two arrays. Point2D_foo(Point2D_index), Point2D_bar(Point2D_index).

Then, later, we discovered the need of Point3D code. Leading to the creation of one more struct-of-arrays (or 3-more arrays).

    int Point3D_x[];
    int Point3D_y[];
    int Point3D_z[];
Point3D_foo(), Point3D_bar(). Theres a 3rd function, Point3D_baz() that is specific to 3d code, but foo() and bar() are defined to be identical as the 2d versions. I haven't really figured out what parameters these 3d-versions of foo, bar, and baz would be like.

All "old" Point2D code was written only knowing about the first two arrays (Point2D_x and Point2D_y). The new Point3D code can be written knowing about all 5 arrays.

But I'm having difficulty seeing how you extend the old Point2D code to work on the new Point3d Arrays in the DOD case.

Re: An Introduction to Data Oriented Design with Rust

#72

Post by FartyMcFarter »

I find it sad that every time the subject of DoD comes up, lots of people act like it's incompatible with Object Oriented Programming.

This is not the case. You can program in a data-oriented, cache-efficient way using OOP. To give a super basic example: in a game, this could mean writing a class that contains data for many game objects, instead of a single one.

Re: An Introduction to Data Oriented Design with Rust

#73

Post by renewiltord »

algorithmsRcool wrote: post #48
renewiltord wrote: post #34

The cost to legibility for the vectorization seems high. I wish there were a way to get the best of both worlds, i.e. specify the type you want and have it striped so that the struct is then vectorified.

Part of the Trill[0] processing engine in C# does this. It uses reflection to vectorize normal objects into a columnar format internally. [0] : https://github.com/microsoft/Trill

Fascinating. Isn't reflection in these VM languages pretty slow usually? Won't you pay that cost on access each time? Still, C# seems to be capable of a lot if you can do this ergonomically. Very cool.

Re: An Introduction to Data Oriented Design with Rust

#74

Post by Rusky »

dragontamer wrote: post #71
Rusky wrote: post #67

Earlier quoted context omitted.

> But now your Point2D code needs to be aware of the Point3D code. Not at all! You write the archetype management code once, and then the Point2D code just asks it for Point2Ds, nothing else, and that doesn't change no matter how you use Point2D elsewhere.

I'm having difficulty understanding how your proposal works. In the beginning, there was one struct-of-arrays, the Point2D x and y arrays. int Point2D_x[]; int Point2D_y[]; We also have a number of functions that use these two arrays. Point2D_foo(Point2D_index), Point2D_bar(Point2D_index). Then, later, we discovered the need of Point3D code. Leading to the creation of one more struct-of-arrays (or 3-more arrays). int…

Here's a library in Rust that works this way: https://docs.rs/hecs/

You don't just have bare arrays sitting there. You have a separate part of your program that is responsible for managing them, playing a role similar to a relational database.

Now, to be clear, DOD/ECS/whatever doesn't mean "change all your Point2D methods to take an index instead of a `this` pointer." That gains you nothing on its own. If your `foo` and `bar` are just working with individual Point2Ds, then you can just write them that way- hand them a `Point2D* p` or `int* x, int* y` or something.

It's when you're working with large collections of these things, which exist as pieces of larger (conceptual) entities, that the arrays become important. And you can't know what that looks like until you have a particular operation in mind- are you stepping a physics simulation, or computing a shortest path, etc?

Now the trick is to write those larger-scale bulk operations in terms of queries, instead of direct access to the arrays. If your pathfinding algorithm is 2D, you can run it on all Point2Ds with a query for x and y components. If you later add a z component to some of your entities that already have x and y components, the pathfinding algorithm will keep working and just ignore the z component.

Re: An Introduction to Data Oriented Design with Rust

#75

Post by carteloupe »

meheleventyone wrote: post #68
bfrydl wrote: post #64

Earlier quoted context omitted.

I think this is because of Rust. In my opinion the Rust game dev community is overly fixated on ECS. On the bright side, Rust has some damn good ECS libraries.

I’d agree to a point but it really crosses the whole gamut of hobby game engine development. It’s weirdly self reinforcing even in the face of more interesting architectural choices like DOOM Eternal’s.

Interested what the architecture of DOOM Eternal is like, was there some talk / blog post about it?

Re: An Introduction to Data Oriented Design with Rust

#76

Post by meheleventyone »

carteloupe wrote: post #75
meheleventyone wrote: post #68

Earlier quoted context omitted.

I’d agree to a point but it really crosses the whole gamut of hobby game engine development. It’s weirdly self reinforcing even in the face of more interesting architectural choices like DOOM Eternal’s.

Interested what the architecture of DOOM Eternal is like, was there some talk / blog post about it?

I believe it’s only been mentioned in passing and likely will be talked about at conferences soonish. Here’s a HN thread from when it was first talked about:

https://news.ycombinator.com/item?id=22700563

There was an early talk about using a job system to run the Destiny renderer and then this one for the whole engine which is a very similar premise to the way DOOM(2016) and then DOOM Eternal evolved.

https://www.gdcvault.com/play/1022164/Multithreading-the-Ent...

The renderer talk is here: https://youtu.be/0nTDFLMLX9k

Re: An Introduction to Data Oriented Design with Rust

#77

Post by narwally »

I find it interesting, and somewhat amusing, that we're seeing Data-Oriented-Design becoming popular in C++ and Rust while Data-Oriented-Programming/Data-Driven-Design[1] is being promoted in languages like Clojure and Elm. Both have similar names, and seem to have arisen out of frustrations with OOP. However, their solutions went in completely opposite, though not unrelated, directions. Seems like DOD is about improving program performance by optimizing for data locality in memory; while DOP/DDD is about improving programer performance by optimizing for data locality in source code.

On the other hand, maybe this isn't interesting at all and I'm just thinking about it too hard.

[1] This one isn't a well defined, and there's no commonly agreed upon terminology for the concept. But there is this: https://livebook.manning.com/book/the-joy-of-clojure-second-...

Re: An Introduction to Data Oriented Design with Rust

#78

Post by cogman10 »

Arelius wrote: post #31
cogman10 wrote: post #10

Earlier quoted context omitted.

DOD generally implies a high level of coupling on the system. That's it's biggest weakness. It also pushes even more data management problems onto programmers which makes it easy to get things wrong. You take those downsides and you trade them for higher performance. Now, that doesn't mean that you can't have hybrid systems and get most of the benefits of both worlds. It does, however, mean that you will end up with…

> DOD generally implies a high level of coupling on the system. That's it's biggest weakness. I'm not sure I understand what you mean by DOD generally implies a high level of coupling? Could you perhaps elaborate a bit?

From what I've seen in DOD systems, there are generally common structures that hold data for the entire application. The entire application has to know about these structures in order to function.

Take ECS [1] as an example.

In order to create a new entity on the system you might need to talk to a location component, a health component, a velocity component all to register a brand new entity on the system. Now, you might have an entity creation service that hides those creation details from you, and that's fine. But you need to make sure as you are talking to each of the component you are doing the right thing.

This is the coupling.

The traditional OO approach here would be to create a new entity with health, position, velocity, all contained within the same object and potentially referencable via a common interface for each.

Now, for ECS in a game there are definite benefits to this coupling. For example, it is a LOT easier in games to create universal systems which handle the physics for all objects irrespective of object type. Further, composing behavior onto entities can be much easier. You are free from a strict hierarchy. There's a reason this approach is popular there.

Now consider a very simple rest webservice. Now imagine trying to do that as an ECS system. You might have one component that is the header component and one component that is the body component and an entity that contains both. Now imagine processing that entity through the system. Who would be in charge of making sure all the right interactions happen at the right time? Who would be in charge of responding? Who would be in charge of deleting requests that had been fully handled? I'm sure that's all possible (I wonder if anyone has tried it? could be a fun side project) I'm also sure I'd very likely not want to deal with such a system, no matter how fast it is. It would be unreasonable to try and figure out all the life cycles of everything.

For business applications with a lot of rules to follow, this sort of system would be nightmarish to maintain. It'd be almost impossible to track down what is changing what. You need a lot of gatekeepers because the goal of business apps isn't to enable novel and unexpected interactions, but rather to very explicitly define what happens when and why. For a game, those novel and unexpected interactions are a huge boon and a feature. They make games fun!

As a side note, the coupling of ECS systems is one thing that makes it hard to properly thread games. That's because you've got this globally shared mutable state being accessed through a ton of systems throughout the game. It's frankly impressive that games are threaded at all!

[1] https://en.wikipedia.org/wiki/Entity_component_system

Re: An Introduction to Data Oriented Design with Rust

#79

Post by nwsm »

beders wrote: post #49

A lot more in-depth about caching, avoiding branching etc. can be found in this classic talk by Mike Acton who is Engine Director at Insomniac Games https://www.youtube.com/watch?v=rX0ItVEVjHc Very enlightening and entertaining!

This video is linked in the first paragraph of the article.

Re: An Introduction to Data Oriented Design with Rust

#80

Post by baryphonic »

iherbig wrote: post #21

It seems like a lot of the discussion surrounding DOD that gets popular interest is centered on a small set of patterns that you can apply. And the implication that DOD is the application of these patterns usually follows. Taking this article as an example, it frames DOD as an optimization technique and explicitly states that these patterns are the main concepts of DOD. But while these patterns are interesting and of…

In my understanding of DOD, I'm not sure there really is much of a basis that can be explored in a general way, beyond just adapting to whatever platform you are ultimately targeting. "The data" is supreme (this, along with an information theoretic understanding of "data," should be a hint that something is rotten in the state of DODmark; EDIT: this is extremely dismissive, which is not my intention, and I think DOD makes total sense in combination with other design approaches) and so the programmer tweaks representations of the data to best fit the platform she's working with. Thus DOD would have different positions for x86 or AArch64 or GLSL. DOD seems like a map of constraints x capabilities to strategies. For example, use struct-of-arrays when you need to access sequential elements repeatedly in a von Neumann system with CPU cache. A GPU-based solution might be entirely different, involving weird zipping and index mapping or something. The DOD approach (if it can be called that) seems undecidable when considering how an FPGA might be configured to solve this (or any) problem.

Maybe I'm way off-base, and if so, please correct me. Everything I've seen with DOD (from its inception years ago) seems in line with it, though.

Post reply on HN