17 ms·
An Introduction to Data Oriented Design with Rust
- knowuh 6y agoFor a 2x speed up, I am not sure I would be willing to sacrifice legibility as in the example. The OOP method definition reads like english. 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.
- ekidd 6y agoAs always, it depends on the problem you're solving. 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.
- oehtXRwMkIs 6y agoI think the data-oriented version is very appropriate for a game, where performance is king and there's not that much maintenance afterwards once its done. Perhaps I'm wrong but games seem to be very much a finish and toss it over the wall sort of project. Much less iteration than other contexts.
- Hammershaft 6y agoThat is changing over time as post launch support grows and some games shift to games as a service
- square_usual 6y agoAre the "games as a service" games adding significant code after launch? I think most of the performance critical stuff is in the engine and core game loops. Content packs and seasons aren't likely to change those core bits, and instead be more assets and scripting intensive.
- meheleventyone 6y agoYes they do quite often. A certain amount of maintainance (bugfixing and optimisation) is required but also you are improving core systems to enable new capabilities and increase other developers productivity.
- steveklabnik 6y agoDestiny 2 just had to announce a complete re-do of how they're doing content now and in the future, because the game is significantly held down by technical debt from previous content. https://www.bungie.net/en/Explore/Detail/News/49189 https://www.bungie.net/en/Explore/Detail/News/49189
- estebank 6y agoThe interesting thing to me from these patterns is the possibility of using proc_macros to write code in the "array of structs" style while the code gets desugared to "struct of arrays". I don't know how beneficial that would be, but having it as an option would make this pattern more approachable to people that would otherwise not use it, due to verbosity, mental model mismatch or any other reason people might have not to do this. 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.)
- zozbot234 6y ago> The interesting thing to me from these patterns is the possibility of using proc_macros to write code in the "array of structs" style while the code gets desugared to "struct of arrays". 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.
- jlokier 6y agoIn "struct of arrays" all the arrays have the same size and indexing, so the array index into "array of structs" is the same as the index into each array in "struct of arrays". 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.
- 6y ago
- nikki93 6y agoI think DoD can be ergonomic, actually, if you're doing it just for the architecture reasons vs. the optimizations reasons, to the point that you choose DoD due to them. At least I personally have found that eg. an ECS architecture can lead to separations and structurings of logic code that were helpful, while still defining data in ways that I could just make accessible to tooling and so on. In this talk on their architecture for Overwatch: https://youtu.be/W3aieHjyNvw 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.
- byproxy 6y agosee also: https://news.ycombinator.com/item?id=24447023 https://news.ycombinator.com/item?id=24447023 ;)
- justaguy88 6y agoThat's not really helpful as there is no discussion on that post
- blovescoffee 6y agoI've read quite a few articles about DOD. I get how DOD is great but there are reasons OOP is still around (surely?) 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?
- jayd16 6y agoThey're not really exclusive concepts and you don't want to bother with DOD if your n is low. I would go as far as to say most DOD implementations are done along side the use of objects.
- blovescoffee 6y agoSure, although there's room for distinction between programming with objects and OOP.
- adamnemecek 6y agoI think oop is easier to understand in small examples but gets really inscrutable as your code base grows so you only start questioning oop if you have worked on large code bases. 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. https://en.wikipedia.org/wiki/Row_polymorphism https://en.wikipedia.org/wiki/Row_polymorphism
- mdtusz 6y agoPartially, but DOD like in the article examples work great when you have a "rigid" architecture like a game where having a struct to contain vecs/arrays of player attributes makes sense. This can break down when your "objects" require more flexibility and are used in multiple different contexts where an aggregate `PlayerState` struct doesn't play nicely. 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.
- hknapp 6y agoWhen i first started programming and before i had learned of structs, my intuition led me to organize data with arrays of fields. Turns out, i was on to something.
- zozbot234 6y agoAs they say, you can write FORTRAN in any language.
- TheRealKing 6y agoyou can write write anything in anything these days. This sentence bears no value.
- adamnemecek 6y agoA lot of people in the Rust community (yours truly including) are trying to work out how to build UI frameworks in this paradigm. It's a really interesting question, if anyone has any good input, I'm alll ears.
- fsociety 6y agoModern React/Relay with GraphQL fragments does this semi-well I think. Sources of data include the fragment in their GraphQL query and can blindly pass that to components which depend on it. 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.
- adamnemecek 6y agoModern React meaning Hooks?
- fsociety 6y agoI like Hooks a lot but I’m not sure how it’d apply in the Rust UI sense (maybe well, maybe not). It is nice to not be forced into building classes and to also ensure that specific state changes will force partial re-renders. I’m talking more about https://relay.dev/docs/en/fragment-container 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.
- 6y ago
- hu3 6y agoThis is known and heavily used by the game industry for a long time now. 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 https://www.youtube.com/watch?v=JxI3Eu5DPwE
- hu3 6y agoI like that my constructive comment is currently downvoted even below another that reads "Rust is a scam". Absolute state of the language's community. And yes, it happens specially on rust related posts. I'm not the first to write about this. 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_doing_something_wrong_because_it_seems/ https://www.reddit.com/r/rust/comments/iab9iv/i_must_be_doin...
- iherbig 6y agoIt 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 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.
- meheleventyone 6y agoLikewise the focus on ECS architecture as being the one true DoD pattern when it’s not necessarily data oriented at all and the unfounded assumption it’s used everywhere in game development when it isn’t . And somehow the idea that DoD is a replacement for OOP when it’s really an orthogonal concern. 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.
- bfrydl 6y agoI 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.
- meheleventyone 6y agoI’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.
- beders 6y agoA 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 https://www.youtube.com/watch?v=rX0ItVEVjHc Very enlightening and entertaining!
- Jare 6y agoWas, now pushing DoD at Unity.
- nwsm 6y agoThis video is linked in the first paragraph of the article.
- beders 6y agoSo?
- mcraiha 6y agoMike works at Unity https://blogs.unity3d.com/2017/11/08/were-joining-unity-to-help-democratize-data-oriented-programming/ https://blogs.unity3d.com/2017/11/08/were-joining-unity-to-h...
- renewiltord 6y agoThe 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.
- throwaway894345 6y agoIsn’t that a feature in Jai?
- Rusky 6y agoIt was thrown around in early streams on Jai, but it was removed. (IIUC, with the intent to let it happen in a library using Jai's metaprogramming.)
- algorithmsRcool 6y agoPart 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 https://github.com/microsoft/Trill
- renewiltord 6y agoFascinating. 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.
- yumaikas 6y agoThat really depends which reflection APIs are being used. 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.
- shmerl 6y agoHow much of it you'd recommend to think of in advance when working on something vs the opposite guideline of avoiding premature optimization?
- adamnemecek 6y agoIt's not premature optimization since this is not something you can bolt on later.
- shmerl 6y agoA lot of optimizations can't be easily added later without redesign. But it doesn't mean they are always necessary. Question is, how deep to go first.
- adamnemecek 6y agoOk, but this one is literally an upfront architecture decision.
- shmerl 6y agoRight, but it's optimization focused one, so that was my question.
- adamnemecek 6y agoNo, it's an architecture. The speedup is a nice corollary.
- RussianCow 6y agoIt's an architecture that is specifically designed to maximize performance. I think few people would argue that it is more readable or simpler than most other common architectures.
- RussianCow 6y ago
- deleted 6y ago[deleted]
- strictfp 6y agoI share the opinion that DoD is an optimization technique, and that it shouldn't be applied too generously from the get-go; you're essentially optimizing for specific usage patterns, which might be difficult to predict and often are contradictory. 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.
- deleted 6y ago[deleted]
- FartyMcFarter 6y agoI 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.
- narwally 6y agoI 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-edition/chapter-14/ https://livebook.manning.com/book/the-joy-of-clojure-second-...
- Jtsummers 6y ago"Data-driven programming" tends to give more results than "data-driven design" which mostly (on my Google search) turned up content about usage data driving interface design. https://en.wikipedia.org/wiki/Data-driven_programming https://en.wikipedia.org/wiki/Data-driven_programming
- narwally 6y agoThanks, I knew it was some permutation of those words.
- Jtsummers 6y agoNP. You may also want to check out Norvig's Paradigms of AI Programming if this interests you. A lot of that text involves creating data-driven programs, and some of the benefits (like creating a grammar lets you recognize sentences that satisfy it, or with little extra effort generate sentences from it).
- narwally 6y agoI'm actually working through SICP for the second time right now[1]. This looks like a great place to go after I finish that. I've been meaning to roll my sleeves up and finally dig into the Common Lisp ecosystem, so far it's been mostly Clojure, emacs-lisp, and a bit of Guile[2]. The incredible depth and breadth of the language, and the fact that good documentation seems to be split across all of its various implementations, makes approaching it feel like swimming into the deep end without your water wings. [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 https://www.youtube.com/watch?v=uwiaT3MoDVs
- historyremade 6y agoRust is scam. Stay away.
- thinxer 6y agoThis looks like Entity-Component-System[1] in game development. Entities are composed of components, and components are often stored vectorized. [1]: https://en.wikipedia.org/wiki/Entity_component_system https://en.wikipedia.org/wiki/Entity_component_system
- jakuboboza 6y agoCorrect if i'm wrong: The general conclusion is Vectors are faster and pattern matching is slower in observable way when generating vectors. 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."
- LockAndLol 6y agoUnless I missed a comment, I'd be interested in how fast adding and removing Players is in the first example. I imagine it's O(n) where n is the number of fields. Maybe even O(nm) with m being the number of items being inserted/removed.