An Introduction to Data Oriented Design with Rust
jamesmcm.github.io
jamesmcm.github.io
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 often show up in data-oriented designs, they are not themselves foundational to data-oriented design.
This is interesting to me because it seems to obviously be missing something. If the article went through a list of the design patterns present in the GOF book and framed them as the main concepts of OOP, I would imagine people would be a little bit suspect, right?
That's because it's kind of the reverse, isn't it? The main concepts of OOP may result in certain common PATTERNS of code structure and layout -- which have usually been given names like "Strategy" and "Visitor" and "Singleton" -- but those patterns are not themselves the main concepts of OOP.
Likewise, data-oriented design might lead you to convert an array-of-structures into a structure-of-arrays or avoid branching on a hot path but those patterns are not themselves DOD.
DoD is about recognising data use patterns in your software and organising your software architecture around them in a way that suits the constraints of modern hardware. That’s all.
On the bright side, Rust has some damn good ECS libraries.
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
Not just Rust. The game dev community everywhere is infatuated with ECS.
It's basically cargo culting. There is a large base of amateur or indie game developers who want to feel like they are doing game development the "right" way. One big aspect of that is performance. ECS has a reputation for efficiency (which is true, when used well in a context where your performance problems are related to caching), so you see a lot of game devs slavishly applying it to their code in hopes that the "go as fast as a AAA game" Gods will land on their runway and deliver the goods.
Every time I see a new ECS framework in JavaScript, I die a little on the inside.
Polymorphism has costs, and while dynamic languages work hard to remove them, they still work best when they're able to monomorphize the call site, because that enables inlining without combinatoric explosion from chained polymorphic calls.
Having a single type in your array means field accesses, method calls etc. have the potential to be monomorphized. There are performance wins to laying out your data in ways that avoid the need for polymorphism.
I think the burden of proof is on the part of JS ECS frameworks to show they do have better performance by virtue of DoD and, if so, why. JS engine programmers have been optimizing object-oriented code for literally forty years, all the way back to when they were making Smalltalk VMs.
If somehow a couple of folks hacking on ECS frameworks have managed to write code that runs faster on those JS engines than the kind of code they were designed for, I'd like to see it.
> Having a single type in your array means field accesses, method calls etc. have the potential to be monomorphized.
Sure, but object-oriented code does not require any more polymorphism than DoD does. Consider:
* Iterate over an array of monomorphic components and call a method on each one.
* Iterate over an array of monomorphic entities, access a monomorphic property, and call a method on the latter.
There's an extra property access in the latter (which can easily be inlined), but no polymorphic dispatch. In practice, yes, it is possible to reorganize your JavaScript code in ways that play nicer with inline and possibly even code caching. But I have never seen any evidence that JS ECS frameworks actually do that. Instead, the few I've poked around in seem like typical slow imperative dynamically-typed JS.
If someone is going to take a pattern that was invented specifically for a language like C++ that gives you precise control over memory layout and then apply it to a language that not doesn't give you that control but often uses hash tables to store an object's state, I think the burden of proof is on the framework to show that the pattern actually applies.
https://github.com/thi-ng/umbrella/tree/master/packages/ecs
Optimized Typescript ECS with a demo rendering 100,000 live 3D particles
Super nice guy too, always willing to share information or explain stuff to you if he's around.
I'd expect the wins from reworking your JS so that your target JS engine lays out data out better would often be larger than the wins in C++, simply because the worst case is so bad.
I'd add a third option to your pair: iterating over several arrays of properties - especially numeric properties - rather than an array of objects which each have numeric properties. That can get you substantial wins in Java, never mind JS.
The type checks themselves have significant overhead, and it's easier to fall off the shadow class fast path than you might expect.
> Initialize your objects carefully in a deterministic order, and I'd expect you can control field order and adjacency.
True, but that's equally true of non-ECS architectures. I have yet to see much evidence that the ECS JS engines I've looked at are actually taking that into account.
I think you're getting at the idea that instead of having objects differ in their behavior by overriding methods, you have them differ by having fields bound to objects that implement different behavior.
Assuming I understand you right, that's an excellent insight, but it's just the classic principle:
Favor object composition over class inheritance.
There's nothing new in that idea or anything special to ECS. Do you know how I know? Because that sentence here is directly quoted from page 20 of "Design Patterns", which ECS and DoD are often claimed to be in direct opposition to. :)
I guess I'm more getting at the idea of changing the game design at any point by adding or removing components, a way to make it easier for devs to cope with changing requirements (and they are always changing ofc), but you are right about favoring composition over inheritance, that by itself is pretty good.
I can't really talk about "things that are often claimed" and from the way you talk about this it seems like you have come across different opinions from mine on what ECS is or its value. Sad to see such a useful pattern get "corrupted", but I suppose that is inevitable.
But that is how cargo cult usually goes.
ECS is good though, it's a perfectly solid answer to a lot of thorny design questions. Where problems frequently arise is when you try to jam absolutely everything in your game into the ECS structure. In practice you're probably going to have a lot of data which lives outside the system and is not attached to any entity.
I watched this sentence unfold with bated breath, waiting to yell "and ze sticks the landing!", only to see it end with "goods" instead of "cargo". It's frustratingly close to perfect, though perhaps to end the paragraph with "cargo", you'd have to begin with some synonym for cargo culting.
I’m sure this is true for some definition of OOP, but I’ve seen too much OOP code that insists on hanging every method off of the most plain-old-data of classes. A Book class has to have a buyFromAmazon() method and consequently each instance has a private reference to an Amazon SDK client, and if you want to buy 10K books, you iterate over a list and invoke this method 10K times.
Of course, some will argue that this is bad OOP and true OOP doesn’t look like this, and anyway you can write bad code in any paradigm! Of course, OOP is uniquely plagued with bad code (much more so than other paradigms) and this pretty transparent no-True-Scotsman argument is just moving semantic goalposts (as such arguments do).
Likewise critics might focus heavily on inheritance or some other feature of OOP that is easy to critique.
And whilst I’m not particularly interested in defending OOP I think describing it as uniquely plagued with bad code is not something anyone should just take axiomatically.
I like to address the boringly predictable responses up front so we can avoid rehashing the same silly arguments over and over. I apologize if that spoiled your fun.
> Is immutability a defining feature of FP? Let the battles commence.
I think most would agree that immutability is more prevalent in FP even if struct immutability isn’t required. Moreover, everyone would agree that first class functions and functional composition are key characteristics. Contrast that with OOP where you have some OOP enthusiasts arguing that inheritance is a defining feature and others who argue it isn’t. Some argue that the “kingdom of nouns”, banana-gorilla-jungle design is inherently OOP and others argue it’s “bad programming and not true OOP”. Others argue that message passing is required, but many others argue to the contrary. While other programming paradigms have fuzzy edges, OOP has no discernible shape at all.
> And whilst I’m not particularly interested in defending OOP I think describing it as uniquely plagued with bad code is not something anyone should just take axiomatically.
Why are there no equivalent criticisms of FP or DO? We might find FP codebases that are overly abstract or a bit slow, but we don’t tend to find (m)any that are designed such that a Book object holds a reference to an Amazon SDK client or a banana with a reference to the gorilla holding it with a reference to the entire jungle. There aren’t prevalent guidance to write code like that in other communities like there is (or perhaps “was”) in OOP circles. Similarly, there aren’t enterprise-y abstract factory beans or anything like that in the FP world.
Mind you, I’m not dumping on OOP—indeed I couldn’t if I wanted to because it has no agreed upon definition, per its proponents.
Object oriented to me has always been about encapsulation, sending messages, and late-binding.
Otherwise it's obvious, cheap to write, easier to get right than more complicated approaches, and good enough. True OOP is OOP that meets goals.
But more importantly, my point is that you have your definition of whether this is OOP or not but lots of OOP proponents will say that this is not true OOP.
Moreover, inevitably someone downstream from the author of the Book class will have a use case for dealing with books that the author hasn't accounted for, so they have to extend the book class for their own use case, tacking ever more fields onto that book even though their use case only cares about a few of the fields.
Additionally, some of the things you might want to do with a book might also involve some other plain-old-data-structure--how do you determine which plain-old-data should host the method? Why is it `Book.doThingWithCar(Car c);` and not `Car.doThingWithBook(Book b);` or simply a static method `doThing(Car c, Book b);`?
Further still, why create a Book.buy() method that's just going to delegate to `Retailer.buyBook(this)` anyway? If the advantage is that you don't have to explicitly pass the `retailer` around, that's fine enough but there are ways to do that without baking retailer details into every book instance (e.g., a closure: `buyBook = function() { retailer.buyBook(book) }` or if you're a glutton for punishment, you can create a class weds a book and a retailer together:
class BuyBookOperation {
private Retailer _retailer;
private Book _book;
public BuyBookOperation(Retailer retailer, Book book) {
this._retailer = retailer;
this._book = book;
}
public do() { this._retailer.buyBook(this._book); }
}
Lastly, if at some point you do need to buy books in batch, how do you support that? Does each book class also need a reference to every List<Book> that references it so it can do book.buyInBatch()? Do you make a book.buyInBatch(List<Book> otherBooks) method? Do you just eat the performance hit and make individual calls to book.buy() even though the Retailer interface has a buyManyBooks(List<Book> books) method that could buy all books in a single HTTP request? What advantages do these approaches have over `retailer.buyManyBooks(books)`?
So this "plain old data needs to depend on everything that might be necessary for any activity involving a book" pattern has no obvious benefits, but it creates a lot of unnecessary coupling, creates a lot of awkward interface decisions when there are other objects involved in an action (including efficiently dealing with collections of your plain old data structure), and it probably pushes you into mutation unnecessarily which makes it a lot more difficult to parallelize your code.
This pattern seems to be a pretty transparent anti-pattern to me, and if it's "inherently OOP" then OOP is problematic.
So a 1986 concept rediscovered by game developers and cargo culted ever since, although it has its roots on the OOP they love to hate.
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.
https://www.youtube.com/watch?v=rX0ItVEVjHc
Very enlightening and entertaining!
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-...
[1] The first time was my introduction to lisp, so only bits of it stuck.
[2] A criminally underrated language IMHO| "Knit, Chisel, Hack: Building Programs in Guile Scheme" by Andy Wingo - https://www.youtube.com/watch?v=uwiaT3MoDVs
The article suggests the true benefits of DOP aren't all that great unless you understand the target architecture.
I feel like the pendulum is at its new zenith.
A 2x speedup in the inner loops of a game can be a very big deal. And for business workloads, I occasionally spend time babysitting clusters running batch jobs. A 2x performance increase in the right inner loop might save a couple hundred dollars per run.
So certainly, profile before you optimize, as the article demonstrates. But 2x speedups can be worth applying a "struct of arrays" transform.
I don't think Rust itself will ever incorporate this feature into the language, just like it doesn't transparently wrap a `dyn Trait` into a `Box<dyn Trait>`, but I would expect that it will never put active roadblocks for libraries to extend the language in such a way. (The regular proc_macros caveats would apply, of course.)
This is not possible in the general case, because you can have a general pointer/reference to a single struct in an "array of structs" but a "struct of arrays" can only be accessed by indexing each array separately. So only very simple and self-contained programs can possibly be "desugared" in this way.
A general pointer/reference type that might point to a single struct in "array of structs" can be transformed to a "wide pointer" representation as pointer/reference to the array and index into the array.
If analysis can't prove the pointer is constant, then the representation will be an opaque wide token outside the transformed code, which is fine. If it can prove the pointer is constant, the run time representation does not need to be wide, as it's just the index, also opaque outside the transformed code.
There's no need to have a representation as a regular pointer, because there's no way the struct pointer/reference type can be dereferenced outside of transformed code anyway, only passed around.
In archetype-based ECS libraries (which the ecosystem seems to be converging on or near) you write a query asking for a particular subset of "component" types, where each type is stored in its own array(s), and then for each iteration of the query you get back one reference to each component type.
As a result, all the extra zipping (which I'm assuming is what people find less readable about the article's example) is handled in the query implementation, and you get this sort of hybrid between the two, syntactically speaking:
for (location, velocity, acceleration) in players.query::<(Location, Velocity, Acceleration)>() {
*location = (
location.0 + velocity.0,
location.1 + velocity.1,
);
*velocity = (
velocity.0 + acceleration.0,
velocity.1 + acceleration.1,
);
}
In this talk on their architecture for Overwatch: https://youtu.be/W3aieHjyNvw (highly recommend) you can see that the wins / concerns they talk about have to do with architecture more than perf. Big insights at 8:00 in the video.
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.
I suppose I'm still hung up on, what are the benefits of OOP that I'm missing?
It seems like there are reasons OOP is so ingrained. I can see a couple of reasons that are environmental. For instance, OOP is taught in schools because students are often taught to program before they're taught about computer architecture - thus DOD would be lost on them. It would be a huge barrier to entry to introduce cache hit rates as a design concern when people are just learning what a class is (in the current standard model of CS education).
Still, it feels like there are other practical reasons to keep OOP around. Perhaps OOP is the React Native of design patterns - poor performance but quicker to write and add new members to. It does seem like there are also legitimate concerns about refactorability and extensibility of DOD code. Anyone have any more refined ideas here?
Also the lack of dod/ecs languages is a problem. I realized the other day that row polymorphism is the type theoretical concept that would make this work.
Not to say that DOD is bad, just that it shouldn't always be the go-to choice. Rust _does_ make this sort of design much nicer to work with because you can in many ways have your cake and eat it too using `from` and `into` and go back and forth from DOD to OOP type structures.
On the contrary, that's why people adopt DOD designs. It's way easier to add new stuff without breaking existing code/designs in a way that harms them.
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 a more complex system to manage and maintain.
A simple OO system is relatively easy to craft without a whole lot of ceremony. That's the prime benefit of OO.
It's not a weakness to integrate more information about the problem space into the solution. It's engineering. To _ignore_ information about the problem space is certainly a weakness, and is partly responsible why the Windows boot time appears to be a cosmological constant.
You want your solution to depend on the right abstract model of the problem, not on the particulars of the problem.
Otherwise your solution is difficult to extend, and is generally expensive and error prone to change when your problem changes, which happens with 100% probability.
If your data changes, your problem changes. We only ever solve particular problems, given the distribution, shape and density characteristics of input data.
I'm not sure I understand what you mean by DOD generally implies a high level of coupling? Could you perhaps elaborate a bit?
Suddenly, you want "struct Point3D {int x; int y; int z;}". How would you change the code?
In OOP, maybe you'd compose a Point3D as such: struct Point3D { Point xy; int z; }; You can now "capture" all of the Point xy; functionality, and extended it to a 3rd "z" coordinate just fine. All old Point code still works, and you have a few functions that work with Point3D now (maybe with a bit of redundant wrapper functions, but such code is straight forward)
The equivalent in DOD seems less obvious. You'd have to make a new "z" array. But the arrays of Point and Point3d wouldn't line up anymore. (If you had 300 Points, and 20 Point3Ds, is Point#315 a Point3D, or is it a Point? Do you "pad" the "z" arrays to ensure that the struct-of-arrays line up?)
There's no obvious way to benefit from a "z-vector", extending the functionality off of your Point to Point3D. I think the DOD design would create a 3rd "z-vector", and shove a "dummy value" into z for all of the points, to make sure all the vectors would have an ideal set of indexes.
Which demonstrates the coupling factor: its not really easy to compose objects in DOD. While in OOP, composing and inheriting classes and objects is the very point.
In the DOD version you'd create a new record containing 3 arrays instead of 2 (x,y,z) and write or extend your functions to support this new record type.
In the OOP version (NB: blech, it's not OOP, it's just records) you'd also need new functions to support the new type.
There are definitely benefits and drawbacks to both approaches, but what you've written is not a drawback for structure-of-arrays or a benefit for array-of-structures.
But now you're violating DRY: don't repeat yourself. Bugfixes found in Point3D will have to be manually "ported" to Point functions (and vice versa).
> In the OOP version (NB: blech, it's not OOP, it's just records) you'd also need new functions to support the new type.
Those new functions can largely be written as foo3D(Point3D a, Point3D b) {return foo(a.xy, b.xy); }.
DRY is kept, your bugs fixed in foo will automatically apply to foo3D. If you use inheritance (which... probably would be a mistake... but its possible and an "OOP" solution), your Foo functions would automatically work on Point3d.
EDIT: Hmm... maybe Point and Point3D keep the Liskov Substitution Principle and therefore work for inheritance. Maybe inheritance is a valid solution in this case?
DRY is also not a law which must always be followed. You often don't even know when you're repeating yourself until you do, and the first time you see a repetition is not when you should eliminate it (in most cases). You often see people reference the rule of three here.
The first repetition should make you pay attention. The second lets you know that it's probably (not necessarily) time to refactor. Premature DRY is as bad as premature optimization.
Your proposed solution violates the open-closed principle. Which means you have to modify "old working code" to get anything done.
If your "solutions" to fixing code issues is "rewrite and extend the old code to cover the new case", then it becomes impossible to build libraries.
----------
Lets say ApplicationFoo has been written using Point2D, either using OOP or DOD principles. In the real world, ApplicationFoo is often written by another team outside of your direct control.
Your ApplicationBar wants Point3D, and realizes that Point2D largely implements the functionality you want (2d-distances, line-drawing, intersections, etc. etc.)
Your solution forces you to rewrite Point2D, which therefore creates a change in ApplicationFoo. (Or more likely, ApplicationFoo is going to refuse to update to the new library: ApplicationFoo is now stuck on Point2D 1.0, while ApplicationBar is using Point2D 1.1. And now your organization is no longer sharing code effectively).
I don’t see how this is the case. You don’t change Point2D at all, you simply add a second type Point3D. ApplicationFoo can happily continue to use Point2D from your library while you use Point3D.
I think the example of Point2D and Point3D is not very well chosen. Your proposed solution of Point3D = { xy : Point2D, z : Float } is also leads to lots of duplication in the sense that (for example) to add two of these points you would have to do
{ xy = add2D(xy1, xy2), z = z1 + z2 }
For more complicated operations on points, the maths is mostly completely different in 2D and 3D (the same concepts might not even make sense, especially if you don’t generalize to n dimension right away), so sharing of code between the two points seems difficult.
The main problem with this solution, I think, is that you picked one specific projection from 3D space to 2D space. It might line up with a projection that is relevant to your domain but it probably won’t. So if you use inheritance and call a function requiring a Point2D with one of your Point3D’s you secretly project the point to the xy-plane which seems like something that should be explicit in the code.
Point2D, under DOD, doesn't exist. There's "array_x" and "array_y". See the article under question. Point2D would be the index into the "x" and "y" arrays, or an "id" returned by the ECS system.
The "x" and "y" fields, under DOD, are dispersed into different areas, allegedly for SIMD / auto-vectorization benefits. I'm trying to discuss the effects of a decision like this.
> I think the example of Point2D and Point3D is not very well chosen.
There are multiple users who understand software engineering who disagree with me, but understand what I'm trying to discuss.
There are also multiple users who prefer to be pedantic and focus on this issue. For the most part, I'm able to ignore these unimaginative users pretty easily. So the example is working pretty well as a filter.
If you wish for more people to participate in the discussion without getting distracted, maybe a better example would have been recycling the example from the article:
pub struct Enemy {
name: String,
health: f64,
location: (f64, f64),
velocity: (f64, f64),
acceleration: (f64, f64),
}
pub struct FastEnemy {
name: String,
health: f64,
location: (f64, f64),
velocity: (f64, f64),
acceleration: (f64, f64),
jerk: (f64, f64), // 3rd derivative of location
jounce: (f64, f64), // 4th derivative
}
pub struct GalaxianEnemy{
name: String,
health: f64,
location: (f64, f64),
velocity: (f64, f64), // Constant vertical velocity
loopiness: (f64, f64), // cos / sin based horizontal movement
}
---------
But if we focus on this pedantry, we wouldn't be able to discuss software engineering. Surely you've come across an example in your programming life where code-reuse would be useful with a subset of parameters, but needed to be extended into an additional parameter?
> The main problem with this solution, I think, is that you picked one specific projection from 3D space to 2D space. It might line up with a projection that is relevant to your domain but it probably won’t. So if you use inheritance and call a function requiring a Point2D with one of your Point3D’s you secretly project the point to the xy-plane which seems like something that should be explicit in the code.
Is it so hard to imagine a video game, where my Point2D and Point3D interpretation is in fact correct? The point of the discussion is to point out software engineering principles: recycle code where possible, open-to-extension but closed-to-modification, and other such principles.
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.")
In some ways, this is actually quite a bit easier to use than OOP composition+inheritance. You don't need to build your compositions up front as classes or types- you just build them directly as values, throw them all into your archetype system that manages the arrays, and query them however you like. It feels similar to a relational database.
But now your Point2D code needs to be aware of the Point3D code. Violating the open-closed principle (which is an OOP principle, but one that's extremely useful in software engineering).
You NEVER want to change working code. That's the fundamental basis of the open-closed principle. Figuring out how to extend the code to new functionality ("open to extension"), WITHOUT risking any breaks on old code ("closed to modification"), is core to software engineering principles.
Any "solution" that relies upon changing Point2D is null-and-void to my software engineering brain. You cannot build libraries or reusable code if your solution is "rewrite the old code to support new functionality".
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.
In the beginning, there was one struct-of-arrays, the Point2D x and y arrays.
int Point2D_x[];
int Point2D_y[];
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[];
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.
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.
I would argue that an ECS is quite far removed from what the original article was talking about however. But perhaps the original article was too superficial in its discussion of DOD.
More generally, this sounds like a language support problem: most languages are built around arrays of structs because it's easier to codegen for. If you're composing structures, just treat the composed-over struct as one very wide field and continue counting your offsets for the next fields down. Need to reference a struct? Just take a pointer to it and all the fields are a fixed offset. Want a bunch of the same struct? Put them next to one another in memory and you can go from one to the next by just bumping a pointer.
What we need is some sort of language support for "intrusive arrays", where you can declare a struct, create an intrusive array of it, and that array is laid out as structs of arrays. When you request an intrusive array, the language would need to recursively construct intrusive arrays for each non-primitive field (e.g. your IntrusiveVec<Point3D> would hold IntrusiveVec<Point> plus Vec<int>, which flattens down to 3 Vec<Int>s). References would consist of a pointer to the whole array plus an index, and methods on structs (er, "classes", in this case) would need to accept this new pointer-to-intrusive-vector format.
Strong disagree. The traditional OOP approach is passing indirect pointers to everything and incurring an inefficient level of indirection.
Ex:
vector<Point*> blah;
blah.push_back(&somePoint2D);
blah.push_back(&somePoint3D.xy);
foo(blah); // "Function foo" works on Point2D and Point3Ds, none the wiser
// Note that foo may change *blah[10].x += 5
// and it updates the original Point2D or Point3D. This
// wouldn't work for a copied array.
> In Rust the AOS case would be an Enum of Point and Point3D, and the SOA case would be two Vecs of ints and one Vec of Option<int>s.
Rust is a general purpose language. I'm not too good at Rust, but the AOS case would simply be a Box(Point2D).
> More generally, this sounds like a language support problem <snip>
ISPC got SOA types by the way. Check em out if you're interested:
https://ispc.github.io/ispc.html#structure-of-array-types
You don't need a very large SOA-type to take advantage of SIMD or auto-vectorization. You can "gather" into an SOA, then "scatter" back to your main representation.
ISPC sounds pretty cool.
How much of a performance penalty is scatter/gather into and out of an SOA? I assumed you'd want to store all of your data-parallel fields in SOA format, rather than gathering into one every time you wanna do some maths-heavy operation.
But if you are doing any big o bigger than O(n) (ex: matrix multiplication, which is O(n^2.4) or so), then it's relatively cheap. Indeed, optimized matrix multiplications transpose the data to speed it up!!
There is something to be said about gather and scatter patterns as a methodology, especially as a first step into optimizing your algorithms. It's not the ultimate speed form, but relatively straightforward and simple to implement.
It should also be noted that in ISPC, CUDA, ROCm, OpenCL (etc. etc.), your thread-local variables are compiled into SOA form for maximum performance.
SIMD architectures benefit more from SOA, and as such... making maximum use of SOA is built into those languages implicitly. If you're finding yourself reaching for SIMD-techniques, maybe its time to use a dedicated SIMD-language.
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!
> But you need to make sure as you are talking to each of the component you are doing the right thing.
I'm not clear on "doing the right thing". If you're looking at eg specs, at creation-time the only thing you're doing is constructing the entity correctly (adding values to the relevant arrays) with valid values. There's no real hooking into anything, or any intelligent behavior really, since you're just treating the entity as nothing more than the values its composed of.
The systems just pick it up "magically", and treat it as it would any other entity -- it doesn't need to know anything really about the new entity, except that all of the necessary components have been slotted, before executing. And if they aren't.. it won't execute, at least not for that entity.
Which I think is almost by definition de-coupled. The system knows nothing about the entity, and the entity knows nothing about the system -- the system just looks for anything that fulfills the correct set of components, and the entity just looks to fulfill all components needed to describe it. What behavior that will lead to... the entity itself has no idea. And of course, new systems and new entities (and new components) can be plugged in without knowing anything about the others.
>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!
Something seems very wrong here -- bevy, specs, legion etc (rust ecs frameworks) all basically suggest multithreading comes for almost free, because you're being very clear about what you're accessing and when (the systems are defined with the components they rely on, and have access to). So they can represent systems as a dependency graph, and parallelize independent systems appropriately. eg https://specs.amethyst.rs/docs/tutorials/09_parallel_join.ht...
The problem is really the other way around -- since its parallelized for you, the difficulty is in defining an ordered sequence of events (when needed); I believe the simple solution is generally adding a component that's really just a flag, and the more general solution is utilizing event queues and event chaining
specs doesn't iterate the array itself in parallel though, at least not automatically, but there's nothing stopping you (since it's already locked the array on your behalf), hence it provides par_iter
The trouble ECS can get into is where you want a set of components to relate to an Entity but don’t want one or more of the Systems that update that set to run. You end up with more complex System definitions that need to exclude Entities based on extra Component criteria. It gets quite messy to work out looking at the Components that make up an Entity what Systems will run on it.
I would go as far as to say most DOD implementations are done along side the use of objects.
Iterate by rows is far more common that by just "a column". Also, constant update of the rows is more common that have a static, full materialization of the data that only need to be queried.
So, doing DOD only work in some scenarios, but do "by rows" is the common one.
P.D: I tried to go full columnar building a relational language, but get very obvious very fast that it not work for the general case. Is telling that kdb+ (probably the biggest proponent in the area) work in a OLAP-like niche...
If you generally only add new entities, and generally perform operations on all entities (or large subsets) and specifically only need some columns, then the column-oriented approach is more likely what you want.
If you find you delete entities frequently enough, or operate on individual entities more than groups, then row-oriented may be better. Performance will improve (deletes are expensive in arrays/vectors) and code may be cleaner.
There are lots of other factors, but these are the bigger ones (IME).
1. Making data structures as tiny databases with an interface that simplifies storing and retrieving data correctly (no transformations in the class itself to other data types hopefully to minimize dependencies!)
2. The school taught java/old C++ debacle of inheritance. This is where things fall apart. Inheritance means not only dependencies but opaque dependencies. It almost always means pointer chasing and lots of allocations. It used to be necessary because it was the only way to get generic containers. The speed hit to use a chain of pointers was also much smaller. In modern times this destroys performance and is not needed due to templates.
3. Message passing - 'at a certain scale, everything becomes a network problem'. I think the flexibility in having this integrated into the core of a language like smalltalk is not a good trade off, but I do think message passing at a courser architectural level offers large benefits without limiting the speed of more granular and fundamental data structures and functions.
I think OOP will always be debated in a circle because people conflate these three aspects. The first I think is extremely useful and vital. The second I think is obsolete. The third I think should be treated as a higher level architecture approach with large chunks of data passed around to large non-trivial modules/libraries/nodes/plugins etc. The higher level can be more dynamic and flexible because the overhead for a flexible structure is much smaller if it is done with large chunks of data and not integrated into a language and used for vectors / hash maps / one line math functions, etc.
What one can consider is to use ECS. The separation of data and logic into components allows you to apply DoD in a more predictable way. The data which is unique to a particular component can in this way be vectorized across entities.
The ECS approach doesn't solve the problem of data shared between components though, and like others in here I'm also interested in solutions which could optimize access in the same way that relational databases can optimize multiple different access patterns to the same data.
I wonder if it changes when vec items becomes bigger structs and size goes to millions.
Rust dosc says with LinkedLists that you should better use Vec for speed. I think just raw array of bytes is always faster than linked pointers. But LinkedList will probably have less of a memory pressure in cases where you have to maintain large list and remove elements at random while keeping coherency.
from Rust docs: Vector = "A contiguous growable array type, written Vec<T> but pronounced 'vector'."
LinkedList = "A doubly-linked list with owned nodes.
The LinkedList allows pushing and popping elements at either end in constant time.
NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache."
Ultimately it comes down to data locality and there's no silver bullet. Performance varies with your data access pattern and code must be adapted to keep caches as warm as possible.
There are also maintainability trade-offs. In general I'd advise this kind of optimization only for performance-critical code like games.
For more information on how game development approaches this, read about Entity Component Systems. Here's a good start: https://www.youtube.com/watch?v=JxI3Eu5DPwE
Someone else's comment about jai received similar treatment. Good thing that on important technologies their communities tend to be friendly. As a niche language striving to become relevant, I'd adopt similar approach.
As a consultant I get asked almost on a daily basis: what technology could solve my problem? Community is heavily weighted in that decision because once I deliver the project, my clients will invariably have to deal with the tech communities.
Regardless, maturity problems like this currently rule it out anyway: https://www.reddit.com/r/rust/comments/iab9iv/i_must_be_doin...
That lets you re-use components quickly and easily. Changing the downstream component which consumes the fragment just requires changes in that component and nothing else.
I’m talking more about https://relay.dev/docs/en/fragment-container. Creating opaque types that can be fetched from a data source and passed off to a child component is more what I am thinking of.
I mention it because I recall working on a Qt product where you have to parse data from a source, then you bring it throughout your program and try to keep it in the right form for every UI component that uses it.
It was easy for the project but we had no composability of components.
With fragments, you don’t really care and duplication of data between fragments on the same source of data generally just works. That way you can pass the fragments to each component as required.
The idea behind that being that, you can have “efficient” and opaque data structure received from a data source which can be blindly passed to a component to consume.
I say data source but in this instance I mean GraphQL... so maybe it doesn’t apply to a generic UI library.
* Use a special allocator for objects which reserves a vector slot from your structure-of-arrays.
* Objects records are offsets instead of pointers
* Object definition includes getter/setters which index the columnar vectors
* Store fields declared 'columnar' in a value vector. This could even give flexibility to group columns for locality where needed, and allow ancillary data to be stored in a "leftover" struct.For C#, you can use type reflection to get the data or shape of a piece of code or a type (GetType and friends). That isn't super fast, and isn't intended to be.
The other major C# reflection API is Reflection.Emit, which allows you emit IL at runtime. The Emit->IL->JIT process is slower than executing the code outright the first time, but once you've done it, you can get code that's as fast as as if it were compiled from source. And, in the case, you might end up with faster code, since it allows you to do transforms on how the data is laid out and compiled.
Notably, the .NET regex engine exposes options for compiling the regex down to IL if it's going to be used a lot, so a library like Trill using reflection to accelerate code by vectorizing it, while keeping better ergonomics makes a lot of sense. You still pay the cost of compiling at runtime, since it's not a compile-time transform. Those do exist for .NET, in the form of Rosalyn plugins, but that's a bit more involved still.
Question is, how deep to go first.
;)