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

Introduction to Data-Oriented Design [pdf]

gamedevs.org

Post reply on HN
Print view View original

61–70 of 83 posts

Re: Introduction to Data-Oriented Design [pdf]

#61

Post by andreygrehov »

I would strongly recommend reading Data-Oriented Programming in Java by Chris Kiehl [1]. Chris introduces you to the data-oriented thinking through a series of super basic examples, gradually making things more interesting. He leverages the latest Java features (e.g. record classes) to illustrate the ideas and explains why these features are important. I don't know him personally, but we both work at AWS. I liked the book so much, that I reached out internally thanking him for writing the book.

[1] https://www.manning.com/books/data-oriented-programming-in-j...

Re: Introduction to Data-Oriented Design [pdf]

#62

Post by meta_gunslinger »

shoo wrote: post #19
ghosty141 wrote: post #15

I personally love the idea of DoD but from my experience it rarely works well in practice since one of the key assumptions of understanding ur problem is often not given as new requirements pop up and change all the time. At work we are rewriting and reengineering system from scratch and its crazy because the limitations of the old system are now gone we get the most insane feature requests that are even accepted by…

DoD may be a good idea for a business context where one of your main priorities is getting the most efficient use out of memory bandwidth & cache. E.g. if your job is writing game engines or middleware used by AAA games with fancy graphics to run on consumer hardware, getting the most efficient use out of the players' limited memory bandwidth may be very important. For many (most?) arbitrary commercial software proje…

A mindset like this has led to my TV taking 40 seconds to boot and glitching/lagging just during simple navigation, even though its hardware is about 10,000x better than what got us to the moon.

Re: Introduction to Data-Oriented Design [pdf]

#63

Post by cmrdporcupine »

PessimalDecimal wrote: post #14

This seems like a particular branding on cache-aware data structures and algorithms. Is there more to it?

I actually see ECS as a subset of the relational data model. It's effectively binary relations, in database / E.F. Codd terms.

When you look at it from that angle, rather than as an optimization technique, it makes it clear there is actually an elegant programming model here.

Unfortunately game engine programmers tend to think databases are super uncool and not relevant. They could actually learn a lot.

"flecs" pulls in some concepts from the relational algebraic world in that it has some sense of joins, etc. but it's a bit ad hoc.

The ultimate "data oriented design" game engine could be a high speed, GPU/SIMD accelerated, in-memory Datalog engine. And then the game world expressed in Horn clauses and logic.

https://github.com/timbran-project/mica is some of my playing in this area.

Re: Introduction to Data-Oriented Design [pdf]

#64

Post by Tiktaalik »

nextaccountic wrote: post #47
inigyou wrote: post #17

Earlier quoted context omitted.

My experience with ECS is that you shouldn't use an "ECS system". You should just do ECS. Have an array of all your particles and then update all the positions according to the velocities. Don't use a framework where you do something like get_all_entities_with (). Just have struct particles {vector positions, velocities;}. Well, managing those parallel arrays gets pretty annoying, but you solve that with a parallel-a…

But why? This looks like the mother of all boilerplates. And for what purpose? Also: just having stuff in an array or vector invites you to the ABA problem. You need a generation counter in there too, or else the array indice may get reused if something is deleted and another thing is reinserted at the same index. But that's yet another boilerplate that would easily be overlooked if you had to do everything manually.…

As I recall the reason for managing blocks of data this way was memory cache efficiency.

Re: Introduction to Data-Oriented Design [pdf]

#65

Post by g9550684 »

these are obvious techniques from array world, j/k/apl, and the source of e.g. arthur's bold speed claims.

personally I've discovered it insufficient to "just" convert tables to lists, you also need to understand the rest of the array principles to then effectively manipulate your data, and just to be able to hold compute in your head. because I believe in this approach I spent time learning j and k, but the end result is that my solutions become too alien for the general practitioner. it becomes apl written in whatever host language.

this is something that is not addressed in a lot of DOD talks, what happens when you do the full realization of technique: bulk list primitives, bulk transforms, SIMD optimizations, list compression, etc. and it's also the reason people claim this only works in narrow scopes (like gamedev). in reality you can write all your code for lack of better term the apl way, you're just going to make it unreadable to non apl practitioners. I'm not quite sure how to reconcile this in general, short of forcing apl to be part of general CS curriculum.

Re: Introduction to Data-Oriented Design [pdf]

#66

Post by inigyou »

HelloNurse wrote: post #56
inigyou wrote: post #51

Earlier quoted context omitted.

> You need a generation counter in there too, or else the array indice may get reused if something is deleted and another thing is reinserted at the same index. It's really sounding like you're pretending not to know what your program does, which is one of the core OOP ideas that DOD refutes. In OOP you have an array of Shape and you pretend not to know which shapes your program implements, so the only way to draw th…

I certainly don't know "what my program does" if it's a game where, at every frame of the simulation, thousands of entities might or might not be created, deleted and recycled depending on player inputs. Can you describe a superior replacement for generation counters?

If you don't know what your program does, DOD asserts that you are a bad programmer and you should first figure out what your program does before continuing.

Sounds like you're writing a game engine, not a game?

Re: Introduction to Data-Oriented Design [pdf]

#67

Post by inigyou »

pdpi wrote: post #54
slopinthebag wrote: post #35

Earlier quoted context omitted.

“Prematurely generalizing” is now an OOP thing? Are we just using OOP as a term for anything bad now? Ooh here is a controversial one. DOD is premature optimization. Most programs don’t have enough data where the storage and access is a factor for performance. In fact it might be slower to use DOD.

> Are we just using OOP as a term for anything bad now? Different paradigms come with different pathological cases. I've had to deal with Scala programmers whose notion of FP is making everything generic on the Monad it abstracts over, even when it'll only ever be instantiated on the one effect system the team uses. Nonsensical levels of generality is one of the classic OOP pathologies, and is the reason why we have…

oh my god. I thought that class was just a joke, but it's real.

Re: Introduction to Data-Oriented Design [pdf]

#68

Post by inigyou »

FpUser wrote: post #58
pdpi wrote: post #54

Earlier quoted context omitted.

> Are we just using OOP as a term for anything bad now? Different paradigms come with different pathological cases. I've had to deal with Scala programmers whose notion of FP is making everything generic on the Monad it abstracts over, even when it'll only ever be instantiated on the one effect system the team uses. Nonsensical levels of generality is one of the classic OOP pathologies, and is the reason why we have…

>"Nonsensical levels of generality is one of the classic OOP pathologies" I think it has nothing to do with OOP which I find very convenient for some domains and not so much or even opposite for others. These "Nonsensical levels" of anything is a disease which is called Architecture Astronauts Syndrome and victims apply it to any paradigm

OOP can be convenient for prototyping a game because you can just write new stuff at high velocity like "yeah a cow is a pig but it's brown and drops leather, a skeleton is a zombie that shoots arrows, and a client is just a server with graphics". Figuring out the right decomposition right from the start can be harder.

Re: Introduction to Data-Oriented Design [pdf]

#69

Post by g9550684 »

g9550684 wrote: post #65

these are obvious techniques from array world, j/k/apl, and the source of e.g. arthur's bold speed claims. personally I've discovered it insufficient to "just" convert tables to lists, you also need to understand the rest of the array principles to then effectively manipulate your data, and just to be able to hold compute in your head. because I believe in this approach I spent time learning j and k, but the end resu…

> convert tables to lists

array languages give you concepts for thinking about these problems where you can succinctly express that entire talk in a single sentence, something like "inverted tables improve cache locality and optimize for time and space, prefer them where it matters". yes, got it, also a well known conclusion in array world.

a table is a 2 dimensional data that stores your records row by row and the items of a column all have the same data type. the way an array of structs would. an inverted table is a list of original table's columns. like a struct of arrays.

so if you have a table,

     x
  ┌────┬──────┬─┬─────────┐
  │mob1│level1│0│0.0243902│
  ├────┼──────┼─┼─────────┤
  │mob2│level2│1│0.0147059│
  ├────┼──────┼─┼─────────┤
  │mob3│level2│0│0.0120482│
  └────┴──────┴─┴─────────┘
there's an idiom for converting it to an inverted table

     ]y=:("1)@|:)x
  ┌────┬──────┬─────┬─────────────────────────────┐
  │mob1│level1│0 1 0│0.0243902 0.0147059 0.0120482│
  │mob2│level2│     │                             │
  │mob3│level2│     │                             │
  └────┴──────┴─────┴─────────────────────────────┘
you can then splice it across variables,

     'name level isactive v'=:y
     isactive
  0 1 0
so you have converted a table to lists.

Re: Introduction to Data-Oriented Design [pdf]

#70

Post by slopinthebag »

inigyou wrote: post #52
slopinthebag wrote: post #35

Earlier quoted context omitted.

“Prematurely generalizing” is now an OOP thing? Are we just using OOP as a term for anything bad now? Ooh here is a controversial one. DOD is premature optimization. Most programs don’t have enough data where the storage and access is a factor for performance. In fact it might be slower to use DOD.

I don't think that's all that controversial. DOD comes out of the field of video games where people were frustrated by only being able to process ten thousand things sixty times per second and wanted to process ten million things sixty times per second. While it's also been used to speed up things like the Zig compiler, it's definitely not necessary for all software. One of the ideas in OOP that DOD is explicitly ref…

You don't always know what subtypes will exist, either at runtime or in future iterations of the program.
Post reply on HN