6 ms·

Summary: the computer has changed -- memory latency measured in CPU cycles has grown a lot. So we should not be using traditional struct/class-like programming

by theamk 6y ago

Summary: the computer has changed -- memory latency measured in CPU cycles has grown a lot. So we should not be using traditional struct/class-like programming model, where we put all properties of an object next to each other. Instead, we should be using game-style "data oriented programming" a.k.a. "column databases" for a much higher performance. However, most modern languages (C, C++, Python, Java, etc..) are not making it easy, and this is bad! Meanwhile you can data into columns and enjoy faster programs.

aparsons 6y ago
What do you mean by game-style here? I’m very intrigued. Any place to read more about these?
- foota 6y ago
  The keywords here are things like data oriented or "structures of arrays". Some examples are unity ECS or amethyst and bevy in Rust language.
- astrange 6y ago
  It's called entity-component systems in games. Note that OOP was designed for simulations but games, the only kind of simulation people like using, don't use OOP.
  - astrobe_ 6y ago
    I think the more accurate references is "Parallel arrays", aka "Structure of Arrays" (SoA) [1] The amusing thing is that SoA is something you could see in old languages that didn't have data structures, or the code of newbies that don't know data structures. [1] https://en.wikipedia.org/wiki/Parallel_array https://en.wikipedia.org/wiki/Parallel_array
  - scambier 6y ago
    It's "Entity Component System". The "system" is part of the pattern name.
  - BlueTemplar 6y ago
    Plenty of games use OOP (C++ !). And ECS is just relational OOP.
- loopz 6y ago
  Gaming has always been pushing boundaries of what's possible performance-wise. For high-throuhput data loops, there's already established patterns used by gamedevs that maximize use of cache and cpu/gpu.
- elcapitan 6y ago
  Look for "Data oriented design" or "Structs of arrays". Here's a talk on the former by Mike Acton: https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc On the latter, there's Jai, a new programming language for games (WIP, unpublished) by Jonathan Blow, who has been very public in documenting the process creating it, and which is centered around such concepts. There is some unofficial documentation of the ideas on SoA vs AoS and how the language can help switching between the two, e.g. here: https://pixeldroid.com/jailang/overview/Features/SOA/#/overview/ https://pixeldroid.com/jailang/overview/Features/SOA/#/overv... and here: https://github.com/BSVino/JaiPrimer/blob/master/JaiPrimer.md#data-oriented-structures https://github.com/BSVino/JaiPrimer/blob/master/JaiPrimer.md... Edit: Just realized that the articale even mentions Jai towards the end.
- CodeArtisan 6y ago
  https://gameprogrammingpatterns.com/component.html https://gameprogrammingpatterns.com/component.html https://gameprogrammingpatterns.com/data-locality.html https://gameprogrammingpatterns.com/data-locality.html
speedplane 6y ago
> Instead, we should be using game-style "data oriented programming" a.k.a. "column databases" for a much higher performance. This makes logical sense, but I don’t buy it in practice. Most of the heavy data reads are handled by databases, which do optimize for this stuff. I just doubt that, in most software, a significant amount of software performance issues are a result of poor memory alignment of data structures.
- gumby 6y ago
  When your datasets are quite large a sql database becomes an absurd bottleneck. Think of weather or aerodynamics simulations.
- nine_k 6y ago
  Cache misses can lead to major slowdowns. Everything depends on the access patterns in critical loops. If you need most of the fields of a struct in each iteration, the classic way is beneficial. If you need a narrow subset (a "column") of fields in a large collection of objects, splitting objects into these columns speeds things up.
  - tpxl 6y ago
    The most upvoted stackoverflow question is about branch prediction (which is caching in a way): https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi...
jhgb 6y ago
> So we should not be using traditional struct/class-like programming model, where we put all properties of an object next to each other. Instead, we should be using game-style "data oriented programming" a.k.a. "column databases" for a much higher performance. Something like DataDraw (http://datadraw.sourceforge.net/ http://datadraw.sourceforge.net/) does with C? > However, most modern languages (C, C++, Python, Java, etc..) are not making it easy Funnily enough, it was yesterday when I though about how cool it would be to make an implementation of Oberon-07 (http://oberon07.com http://oberon07.com , https://people.inf.ethz.ch/wirth/ProjectOberon/index.html https://people.inf.ethz.ch/wirth/ProjectOberon/index.html - a simple-enough language to experiment with in various ways) that would use something like this as its in-memory data representation. It came up as a consequence of me wanting to have an implementation of Oberon-07 for WebAssembly, and realizing that the necessity of "restarting" the whole binary at any code change (necessitated by how WebAssembly works) also allows for some liberties in data representation (for example running out of compressed IDs for instances of a type could be handled in exactly the same way as changing the code of the running program - by generating a new binary with expanded space for these IDs and restarting it using the serialized old heap).
tom_mellior 6y ago
> However, most modern languages (C, C++, Python, Java, etc..) are not making it easy, The article shows how easy it is to declare a struct of arrays in Java: You declare a struct (class). Inside it you declare arrays. Done.
- beagle3 6y ago
  It is easy to declare, but it is not easy to use: You can pass the whole thing, but if you want to pass a subset of it? just one element? When you want to extend it, you have to extend many individual arrays, etc. When you want to copy entry 17 to entry 50, you can't loop over the fields - you have to spell out every field.
  - tom_mellior 6y ago
    A subset of an AntColony is another AntColony containing sub-arrays. One element of an AntColony is an Ant which you can instantiate with the data at the appropriate index from each array. I'm not trying to be difficult, I really don't see the problem with implementing these basic programming tasks. I agree that spelling out the fields can become tedious if you have a lot of structures of arrays or lots of fields per structure. A 100-line Python script can generate all this code for you if you prefer. Sure, it's a "limitation" of most programming languages that they don't provide this out of the box. But not a big limitation, I'd argue. Many languages even have features that allow you to write this functionality as a library, 100% inside the language (Python and Java annotations, for example).
    - beagle3 6y ago
      > I really don't see the problem with implementing these basic programming tasks. That you have to write them over and over again for every single class. You offer to do that with Python. > But not a big limitation, I'd argue. Many languages even have features that allow you to write this functionality as a library, 100% inside the language (Python and Java annotations, for example). This is an argument of the "all languages that are Turing complete are essentially equivalent" kind. True, but not interesting in this context. Ecosystem matters. If your Java program is the only one that does these things, it may just as well not be Java. You will be unable to use any other library without back-and-force adapters, for example.
mjevans 6y ago
Structs are easy to envision as a repeating pattern tessellating across memory space; it makes slicing regions of data and bulk memory copy (e.g. DMA) easy. Yet if the algorithms mostly work with subsets of those fields then a 'column database' type of data layout clearly has benefits. Though for the complex case I would prefer more syntax sugar from the language. A "column struct" datatype that might include tuning suggestions for stride, size, etc; but would present a simple interface for humans. Given multiple underlying blocks of records a parallalizable foreach style loop might even shard across NUMA distributed threads if supported at runtime.
antpls 6y ago
columnar layout is only faster if reads are sequential
- cma 6y ago
  If things work one or a few columns at a time this isn't necessarily true. Prosumer CPU L3 caches are already up to 128MB and will be up to 1GB before long. If one or a few full columns fits fully in cache but all the data doesn't, columnar layout may still be faster in the face of random access within the column.

by theamk 6y ago

aparsons 6y ago

What do you mean by game-style here? I’m very intrigued. Any place to read more about these?

foota 6y ago
The keywords here are things like data oriented or "structures of arrays". Some examples are unity ECS or amethyst and bevy in Rust language.
astrange 6y ago
It's called entity-component systems in games. Note that OOP was designed for simulations but games, the only kind of simulation people like using, don't use OOP.
- astrobe_ 6y ago
  I think the more accurate references is "Parallel arrays", aka "Structure of Arrays" (SoA) [1] The amusing thing is that SoA is something you could see in old languages that didn't have data structures, or the code of newbies that don't know data structures. [1] https://en.wikipedia.org/wiki/Parallel_array https://en.wikipedia.org/wiki/Parallel_array
- scambier 6y ago
  It's "Entity Component System". The "system" is part of the pattern name.
- BlueTemplar 6y ago
  Plenty of games use OOP (C++ !). And ECS is just relational OOP.
loopz 6y ago
Gaming has always been pushing boundaries of what's possible performance-wise. For high-throuhput data loops, there's already established patterns used by gamedevs that maximize use of cache and cpu/gpu.
elcapitan 6y ago
Look for "Data oriented design" or "Structs of arrays". Here's a talk on the former by Mike Acton: https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc On the latter, there's Jai, a new programming language for games (WIP, unpublished) by Jonathan Blow, who has been very public in documenting the process creating it, and which is centered around such concepts. There is some unofficial documentation of the ideas on SoA vs AoS and how the language can help switching between the two, e.g. here: https://pixeldroid.com/jailang/overview/Features/SOA/#/overview/ https://pixeldroid.com/jailang/overview/Features/SOA/#/overv... and here: https://github.com/BSVino/JaiPrimer/blob/master/JaiPrimer.md#data-oriented-structures https://github.com/BSVino/JaiPrimer/blob/master/JaiPrimer.md... Edit: Just realized that the articale even mentions Jai towards the end.
CodeArtisan 6y ago
https://gameprogrammingpatterns.com/component.html https://gameprogrammingpatterns.com/component.html https://gameprogrammingpatterns.com/data-locality.html https://gameprogrammingpatterns.com/data-locality.html

speedplane 6y ago

> Instead, we should be using game-style "data oriented programming" a.k.a. "column databases" for a much higher performance. This makes logical sense, but I don’t buy it in practice. Most of the heavy data reads are handled by databases, which do optimize for this stuff. I just doubt that, in most software, a significant amount of software performance issues are a result of poor memory alignment of data structures.

gumby 6y ago
When your datasets are quite large a sql database becomes an absurd bottleneck. Think of weather or aerodynamics simulations.
nine_k 6y ago
Cache misses can lead to major slowdowns. Everything depends on the access patterns in critical loops. If you need most of the fields of a struct in each iteration, the classic way is beneficial. If you need a narrow subset (a "column") of fields in a large collection of objects, splitting objects into these columns speeds things up.
- tpxl 6y ago
  The most upvoted stackoverflow question is about branch prediction (which is caching in a way): https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array https://stackoverflow.com/questions/11227809/why-is-processi...

jhgb 6y ago

> So we should not be using traditional struct/class-like programming model, where we put all properties of an object next to each other. Instead, we should be using game-style "data oriented programming" a.k.a. "column databases" for a much higher performance. Something like DataDraw (http://datadraw.sourceforge.net/ http://datadraw.sourceforge.net/) does with C? > However, most modern languages (C, C++, Python, Java, etc..) are not making it easy Funnily enough, it was yesterday when I though about how cool it would be to make an implementation of Oberon-07 (http://oberon07.com http://oberon07.com , https://people.inf.ethz.ch/wirth/ProjectOberon/index.html https://people.inf.ethz.ch/wirth/ProjectOberon/index.html - a simple-enough language to experiment with in various ways) that would use something like this as its in-memory data representation. It came up as a consequence of me wanting to have an implementation of Oberon-07 for WebAssembly, and realizing that the necessity of "restarting" the whole binary at any code change (necessitated by how WebAssembly works) also allows for some liberties in data representation (for example running out of compressed IDs for instances of a type could be handled in exactly the same way as changing the code of the running program - by generating a new binary with expanded space for these IDs and restarting it using the serialized old heap).

tom_mellior 6y ago

> However, most modern languages (C, C++, Python, Java, etc..) are not making it easy, The article shows how easy it is to declare a struct of arrays in Java: You declare a struct (class). Inside it you declare arrays. Done.

beagle3 6y ago
It is easy to declare, but it is not easy to use: You can pass the whole thing, but if you want to pass a subset of it? just one element? When you want to extend it, you have to extend many individual arrays, etc. When you want to copy entry 17 to entry 50, you can't loop over the fields - you have to spell out every field.
- tom_mellior 6y ago
  A subset of an AntColony is another AntColony containing sub-arrays. One element of an AntColony is an Ant which you can instantiate with the data at the appropriate index from each array. I'm not trying to be difficult, I really don't see the problem with implementing these basic programming tasks. I agree that spelling out the fields can become tedious if you have a lot of structures of arrays or lots of fields per structure. A 100-line Python script can generate all this code for you if you prefer. Sure, it's a "limitation" of most programming languages that they don't provide this out of the box. But not a big limitation, I'd argue. Many languages even have features that allow you to write this functionality as a library, 100% inside the language (Python and Java annotations, for example).
  - beagle3 6y ago
    > I really don't see the problem with implementing these basic programming tasks. That you have to write them over and over again for every single class. You offer to do that with Python. > But not a big limitation, I'd argue. Many languages even have features that allow you to write this functionality as a library, 100% inside the language (Python and Java annotations, for example). This is an argument of the "all languages that are Turing complete are essentially equivalent" kind. True, but not interesting in this context. Ecosystem matters. If your Java program is the only one that does these things, it may just as well not be Java. You will be unable to use any other library without back-and-force adapters, for example.

mjevans 6y ago

Structs are easy to envision as a repeating pattern tessellating across memory space; it makes slicing regions of data and bulk memory copy (e.g. DMA) easy. Yet if the algorithms mostly work with subsets of those fields then a 'column database' type of data layout clearly has benefits. Though for the complex case I would prefer more syntax sugar from the language. A "column struct" datatype that might include tuning suggestions for stride, size, etc; but would present a simple interface for humans. Given multiple underlying blocks of records a parallalizable foreach style loop might even shard across NUMA distributed threads if supported at runtime.

antpls 6y ago

columnar layout is only faster if reads are sequential

cma 6y ago
If things work one or a few columns at a time this isn't necessarily true. Prosumer CPU L3 caches are already up to 128MB and will be up to 1GB before long. If one or a few full columns fits fully in cache but all the data doesn't, columnar layout may still be faster in the face of random access within the column.