101–110 of 159 posts
> The cost of each new field is rarely considered Most developers, in Java and in most other languages, do not consider the cost of every field, but I can tell you that people who need micro-optimisations certainly do care, and in Java's standard library, a layout is very much a concern (except, as always, you want to optimise what really matters; there's no point in optimising something that is unlikely to be a hot…
The size of an ordinary cache is rows × ways × size(line), where rows = 2 ↑ num-idx-bits. For example, most Intel 64 and AMD 64 processors use log₂(size(page)) − log₂(size(line)) = 12 − 6 = 6 index bits for the L1 cache*, so an L1 cache with 8-way associativity is 64 sets × 8 lines/set × 64 bytes/line = 32 KB large, and an L1 cache with 12-way associativity is 64 × 12 × 64 = 48 KB large. I remember being surprised to learn that most processors have only 64 rows in the L1 cache!
*So that virtual indexes and physical indexes are identical (so that retrieval of the row can happen in parallel with TLB lookup).
Earlier quoted context omitted.
Assuming ordering isn't a concern, can't you just have a field called "removed" and skip those when iterating? Or swap it with the last monster, and keeping an index for the last monster alive.
Then you have to read the "removed" field on every field read on every operation. SoA is only useful when you don't read multiple fields for most operations.
| A1 A2 A3 A4 | A5 A6 A7 A8 | ...
| V1 V2 V3 V4 | V5 V6 V7 V8 | ...
| A1 V1 B1 C1 | ... | A2 V2 B2 C2 | ...
This is on par to linear search being faster than binary search for small n. As soon as caches and branch prediction chime in many rules of thumb just change. Most importantly, however, is that a distinction between small and large n basically _needs_ to happen at that point.
Earlier quoted context omitted.
This is valid for sequential scanning of the data. The CPU will fill whole cache lines at once with the arrays that do get used and the algorithm touches all the field instances in the array. Now think about random access to single struct instances instead: the CPU loads a cache line worth of data for each field and uses only one element out of the whole cache line. This is much worse than a compact structure represe…
This sounds similar to relational databases vs document oriented databases, at least when I briefly looked into database like MongoDB when such things were all the rage 15-20 years ago. For the internal web site that customer support people used a document oriented database would be great because that wants to load everything about one customer and pretty much doesn't need anything else until the user is done support…
So if you need speed, you just have to swallow your OO programmer's pride and put your data in arrays.
I already know I'm dealing with huge perf issues caused by ORM & lazy-load semantics. I/O abuse is usually going to be so, so much worse than memory/cache issues. Java is mainly used for business information systems, where I/O is king. Plain vanilla memory abuse is also a big one.
But my main problem is a mgmt convinced the magic wand of AI will make all sorts of problems dissapear, and it's going to take 5 years for them to realize nope.
It's still fun to learn about cache optimization though, esp. when someone makes it reasonably digestible like this. And maybe it also helps people to recognize that OOP is not some great over-arching zen truth of truths.
Data Oriented Design rocks. It was the subject for my CppCon 2025 keynote: https://youtube.com/watch?v=SzjJfKHygaQ
Earlier quoted context omitted.
It's because removing a monster with 20 fields from an SoA structure means resizing 20 arrays. Removing the same monster from an AoS array involves resizing a single array, which you're going to process in a very cache friendly way.
I'm not sure why anybody would at the same time be implementing SoA AND resizing 20 arrays for a single delete, those things seem to be on either ends of the "I care about performance" spectrum.
Now, as others have suggested, you can have a more complex implementation, where instead of removing the monster's fields from those arrays, you just mark them as "dead" or whatever and then skip them when consuming the relevant arrays, with some relatively small extra bookkeeping overhead. Of course, this comes with its own drawbacks, especially if the number of monsters is very dynamic and you are memory constrained.
The point is not to say that SoA is never good for performance, it obviously and certainly is, probably even in most cases. It's just not always best for performance, this was all.
Earlier quoted context omitted.
It's because removing a monster with 20 fields from an SoA structure means resizing 20 arrays. Removing the same monster from an AoS array involves resizing a single array, which you're going to process in a very cache friendly way.
Assuming ordering isn't a concern, can't you just have a field called "removed" and skip those when iterating? Or swap it with the last monster, and keeping an index for the last monster alive.
So if you need speed, you just have to swallow your OO programmer's pride and put your data in arrays.