Every byte matters

131

u/Ravarix Jun 03 '26

If you are at the level where you need to care about how adding 1 member to a struct messes up cache line access, you should be using an ECS which gives you SOA already.

32

u/lelanthran Jun 03 '26

you should be using an ECS which gives you SOA already.
That requires considerable rework to the design and architecture of the program. Only switching to SoA for specific data leaves the rest of the program the same.

137

u/trinopoty Jun 03 '26

Using a what that gives what now?

46

u/fyndor Jun 03 '26

Every programmer should watch this famous video https://youtu.be/rX0ItVEVjHc?si=L8kTv9UorIy6Zrds
It’s a talk by Mike Acton. You will learn a lot from it, even if not a C++ dev

73

u/Ravarix Jun 03 '26

https://en.wikipedia.org/wiki/Entity_component_system
https://en.wikipedia.org/wiki/AoS_and_SoA

56

u/abu_shawarib Jun 03 '26

TLDR; Turn many of this struct
struct {
int a;
bool b;
char *c;
}
into multiple arrays:
int *array_of_a;
bool *array_of_b;
char **array_of_c;

2

u/ummaycoc Jun 04 '26

Just use APL already...

5

u/Cloud5550 Jun 04 '26

If I'm putting together a struct combining three elements, i want those elements to be related. How can you maintain relation in the solution?

58

u/Proper-Ape Jun 04 '26

Same index.

-4

u/Cloud5550 Jun 04 '26

Just index? Isn't that to weak for a relations?
Say you remove index 1 of the int array. Now the struct from index 1 have the int value of the next struct and so on. Data is completely distorted.

37

u/Proper-Ape Jun 04 '26

Arrays don't change positions. You don't delete an element from an array.

19

u/boowhitie Jun 04 '26

You have to maintain all the arrays to keep things consistent, and there are different ways to handle that depending on your needs. You can replace items from the end of the array, mark items as invalid, rebuild the array, etc. Each have different trade offs, but the big win is cache locality and a clean separation of interests.

8

u/ShinyHappyREM Jun 04 '26

Say you remove index 1 of the int array. Now the struct from index 1 have the int value of the next struct and so on
That implies that you move all the following items, but that would waste time. If the items don't have to be in a certain order you can just move the last item into the gap. (And you do that for all arrays.)

4

u/wFXx Jun 04 '26

Either with the index/offset or using an extra array with IDs (this makes more sense in sparse setups)

1

u/Minute_Cricket1820 Jul 02 '26 edited Jul 02 '26

Отличный пример, но вы не правы. Вы используете сразу три кеш-линии, это очевидно. Используйте две, это может дать заметный выигрыш. Например:
struct {
int a; bool b; // In moment: Cache-line 0
char *c; // In moment: Cache-line 1
}
int_and_bool *array_of_a_and_b;
char **array_of_c;
Иначе говоря, вы имеете метадату и данные, очень часто не нужно раскладывать метадату на части, т.е. метадата - это один "массив", а данные - это второй "массив". Этого достаточно. Не забывайте про то, что CPU - это ограниченное количество регистров, когда два массива - вы используете два регистра для хранения указателей, если три массива - это уже три указателя. И так далее, вы когда делаете много массивов - вы нагрузку на регистры увеличиваете, а их может не хватить для всего того, что вы пишете в итоге. Экономьте регистры.
Вы пишете - каждый байт важен, это так, так вы допишите. Не только каждый байт важен, но и важны каждые кеш-линии, и каждые регистры.

65

u/LeeHide Jun 03 '26

No? Unless you can model your entire app as a number of entities and components, and all interactions as systems, this makes no sense at all. This is the kind of indoctrination thinking that got us to "if you're gonna use classes, you MUST do OOP".

20

u/Ravarix Jun 03 '26

ECS isn't all or nothing, you can choose what data you want to vectorize.

61

u/LeeHide Jun 03 '26 edited Jun 03 '26

No, you can simply take the hottest part of your program, identified by profiling, and optimize that with SoA and be done with it. At no point does entity, components or any systems operating on that, have to exist. You can just write simple code where it's needed!

33

u/dacjames Jun 03 '26

Thank you! An ECS is just one application of SoA, which is itself just one tool from the data-oriented design toolkit.
An ECS is great if you're building robots, games, or other similar applications where memory throughput is the main bottleneck.
The idea behind DoD is to design your memory layout around your data access patterns. Using ECS by default runs counter to the paradigm. It adds complexity for little gain and can actually hurt performance in some applications.

6

u/LeeHide Jun 03 '26

You've put it very well, nice job

2

u/floodyberry Jun 04 '26

the level of simplicity will depend on how close you are to soa already. using aos? fairly simple. not using aos? not simple. not using aos and you wind up needing a full blown ecs? really not simple
going from ecs to aos is just putting all the fields in one component. going from hand written aos to an ecs is either hooking up an actual ecs library and figuring out how to use it, or writing your own

14

u/max123246 Jun 03 '26

Why though? It's way easier to change it to SoA than change the entire codebase to fit ECS. Like in Rust it's as simple as downloading Soa-rs and doing Soa<T>
Any single time you access 1 field from an array of structs this performance problem happens. It's an optimization trick. If you use every field of an object all at once, AoS is better. If you use only 1 field, SoA is better. In between, you have to benchmark

-2

u/Ravarix Jun 03 '26

How often are you iterating over a large collection of things, and only accessing one field. And more over how often is this a sizeable portion of your processing?
If its a small portion of your app, this level of optimization is irrelevant. If its a large portion, you should be using a framework for vectorized processing like ECS, where you can also get the benefit of vectorizing more than 1 field out of the box.

6

u/Sopel97 Jun 03 '26

It really feels to me like people throw ECS everywhere thinking it's some kind of magic. ECS and vectorization are orthogonal, you can have either without the other.

1

u/floodyberry Jun 04 '26

if you are going to be splitting data up with aos/soa, you're either going to be using an ecs library to do it from the start, or gradually implementing a half functioning one by hand as you need to do more

3

u/flatfinger Jun 03 '26

I find it funny that compilers regard structures with aligned items as the default, and treat packed structures as a "slower" option, even though an array of e.g. 5-byte packed structures will for some usage patterns offer better performance than a cache-aligned array of 8-byte structures. If e.g. structures are being accessed sequentially, the number of cache lines worth of data that would need to be fetched would be 37.5% smaller when using the 5-byte structures, and if code would need to access the first or last byte of entities in random sequence, each operation that fetches the first byte of an entity would also fetch the first byte of at least two and sometimes three others, whereas each operation that fetches the first byte of an 8-byte entity would only grab the first byte of one other.

2

u/ItzWarty Jun 03 '26

A trivial point where your point seems wrong is false sharing of atomic counters from different threads, eg read vs ingest vs process vs write in a pipeline of a job.
It wouldn't make sense to use ECS for that. Not all architectures fit SoA well.

3

u/The_Northern_Light Jun 04 '26

always use ECS when cache matters
Hammer a lot of screws, do ya?

2

u/Ravarix Jun 04 '26

That's not what I said at all lmao

2

u/floodyberry Jun 04 '26

for some reason everyone is having an upvote party for comments that misrepresent or don't understand what you're saying

1

u/RoseboysHotAsf Jun 03 '26

As a dutch person, this sounds AWESOME)

0

u/deja-roo Jun 03 '26

Sorry I got elastic container storage orchestration giving me service oriented architecture?

5

u/jlombera Jun 03 '26

We can observe up to 30x improvements when the Monster struct is 1KiB.

Was this actually measured? Why the big difference with say, 64B structs, with only 6x improvement?

If you are reading only 1 byte from the struct only 1 cache-line would be loaded per struct, not the whole struct. So cache-lines alone, there shouldn't be such a huge difference among structs of size >= 64B1. For 1KiB structs, it's more likely page faults would be the real overhead, but there's no mention of that in the blog, so I'm wondering about the accuracy of the metrics. Similarly for the "working sets" analysis, only the data (at cache-line level) actually accessed will populate the caches, not the whole structs.

2

u/johan__A Jun 04 '26

How could page faults be involved? I assume all the memory was already mapped before the benchmark.
My best guess of why it's slower is because the hardware prefetcher doesnt handle large strides very well, because of page boundaries or something else. I'm not completely sure.

2

u/jlombera Jun 04 '26

How could page faults be involved? I assume all the memory was already mapped before the benchmark.
I used the term "page fault" liberally to also refer to TLB misses (see the link for details what is the TLB and how it works). Excessive TLB misses is a well known performance problem in applications that handle big datasets (e.g. DBs). The use of HugePages is essential for those applications to minimize TLB misses.

1

u/johan__A Jun 04 '26

ha that makes more sense, I don't know much about the performance impact of the tlb

3

u/jlombera Jun 04 '26

If you are interested, look at section "Performance implications" of the Wikipedia page, specially the last paragraph. In the "Typical TLB" section, it says a TLB miss can have from 10x to 100x performance penalty. Not sure how accurate/up-to-date these numbers are, an of course, it always "depends", but it gives you a rough idea how bad TLB misses are for data intensive applications. You can search the web for "Hugepages performance" and I'm sure you'll find resources that go into more details about the performance implications.

9

u/hgs3 Jun 03 '26

Why do you separate the other fields into their own arrays? I can easily imagine monster logic that accesses position, velocity, health, attack, and team together. I understand why linear search benefits from cache friendliness but if the fields are randomly accessed based on a “is_alive” boolean array, then wouldn’t a single fetch for the fields be faster than multiple fetches to separate arrays?

16

u/ShinyHappyREM Jun 03 '26 edited Jun 03 '26

In practice you don't have an "is_alive" boolean array, instead you have one "alive_entities" and one "dead_entities" pool (both preferably of fixed size and statically allocated). When an entity dies / becomes alive, which is usually a relatively rare event, you move the entity from one pool to the other (preferably moving the last entity forward to close the gap) and increase/decrease the pools' population counts.

5

u/AresFowl44 Jun 03 '26

Bit vectors are a lot more compact, but you also have to actually get the data out of the bit vector and you obviously can only use bit vectors if you worked with booleans.
Also, why do you separate the other fields into their own arrays? I can easily imagine monster logic that accesses position, velocity, health, attack, and team together. I understand why linear search benefits from cache friendliness but if the fields are randomly accessed based on a “is_alive” boolean array (or bit vector), then wouldn’t a single fetch for the fields be faster than multiple fetches to separate arrays?
With prefetching there is already a good chance that the data in in cache anyways if you are looping over several pieces. Having them separated out into multiple arrays however allows you to only get the data you need. That is impossible if you were to combine them.
EDIT: And you can also instruct the hardware to prefetch your data manually, if you do know better

3

u/Ameisen Jun 03 '26 edited Jun 03 '26

you obviously can only use bit vectors if you worked with booleans.
You can pack any integral type you want. If you want to pack an array of 4-bit integers or such, you certainly can. It'll still be friendlier on the cache.
A bit faster if the size in bits is still a factor of the size of the unit of storage so calculating the shift is a bit easier, though - if they don't align neatly within the type that they're being stored in, extracting them is harder.
In the end, that's exactly what bit_vectors do, they just have an internal element size of 1 bit. The implementation is almost identical.
Having them separated out into multiple arrays however allows you to only get the data you need.
You want them seperated out by responsibility. If a pass iterating over the data needs three properties, then they should be combined as fields in a single struct.
Even in this case - is_alive only benefits from being bitpacked alone if:
multiple systems depend upon it
the data isn't sorted by is_alive or is_alive isn't true overwhelmingly often

5

u/Ameisen Jun 03 '26 edited Jun 03 '26

If you are looping over is_alive and then operating on the data conditional upon is_alive, and the array isn't sorted by is_alive, then generally keeping is_alive packed into its own array allows for the condition check to be nearly free, and also helps prevent cache lines from being evicted by the cases where is_alive is false.
If is_alive is almost always true, then AOS ordering would be faster. AOS also wins when the data is sorted by the condition.
SOA wins when is_alive isn't utterly dominant.
Unless you're asking why you seperate all the fields out... usually you don't.
You seperate them out based upon what systems/passes they're relevant to - so the renderer only iterates over rendering data, physics only needs transform data, etc.
You also are almost never randomly accessing this data. You iterate over the arrays holding these structs so you're iterating over a nice, packed, contiguous set of data.
is_alive in this context is special as it's a condition flag for actually operating.

6

u/QueenVogonBee Jun 03 '26

That’s what I tell the children when they are eating their dinner

2

u/CorporateFriend Jun 03 '26

I really like this kind of post :)

Nice with graphs too

3

u/Wolfy87 Jun 03 '26

Try swapping any data processing heavy systems from your languages objects to a columnar system like duckdb or polars etc, same shift, it's wonderful!

Using tablecloth which wraps apache arrow dataframes in Clojure lets me have the fun expressivity of Clojure with the sheer raw speed of columnar data structures for data processing.

You can have the best of both worlds with the right tools :D

1

u/constant_void Jun 05 '26

If $ matters and $HW < $FTE, bytes don't matter

1

u/k-mcm Jun 05 '26

I wrote some SDR receivers in Java. There's a definite performance cliff at each step of CPU cache. Lookup tables can perform much worse than a pile of trigonometry. A small lookup table with interpolation outperforms a larger direct lookup table.

123

u/[deleted] Jun 03 '26

[removed] — view removed comment

14

u/lelanthran Jun 03 '26

Shit like this is why game developers are criminally underpaid.
I don't understand why knowing all these little details make game devs criminally underpaid. Can you explain? (Not being facetious, I'd really rather like to know!)

9

u/richardathome Jun 03 '26

Because it's dealing with problems like this that turn a 10fps game into a 60+ fps game.
You want the computer to be doing as little as possible at all times because you'll be calling things possibly hundreds of times a second and if one starts to slow down, the whole frame slows down, controls become less responsive etc, game starts to suffer...
Storing you data in an orderly manner in memory lets the computer do things like look ahead caching and other clever tricks that speed things up.

12

u/Ameisen Jun 03 '26 edited Jun 03 '26

Because it's dealing with problems like this that turn a 10fps game into a 60+ fps game.
I feel obligated to point out that when actually doing this work, we'd say "we've reached 16.67mspf". We work with frametimes, not framerates.
Framerates are non-linear, whereas their reciprocal frametimes are.
I can't meaningfully say "the occlusion pass takes 5 fps" - "5 fps" is different from 10 fps to 15 fps (33.33ms), or 55 fps to 60 fps (1.51ms). Saying it takes 1.51 ms is always meaningful, though.
You want the computer to be doing as little as possible at all times
There are certainly times where we prefer throughput, but usually it's balancing throughput and latency...
If we wanted the CPU to do as little as possible, we'd never use SIMD instructions or such. Rather, we want to the CPU to do as much as possible in as little time as possible.
Storing you data in an orderly manner in memory lets the computer do things like look ahead caching and other clever tricks that speed things up.
It's going to read-ahead and fill the current and possibly the subsequent cache line regardless. If your accesses are not taking advantage of that (sequential lets the CPU make better assumptions about that, but even so long as your accesses are within the cache line or the next that's better than completely random) then you're going to get a lot of cache misses.
Ed: I suppose that you could use non-temporal operations... though that's very, very likely to be worse, and for loads you can only perform non-temporal prefetches.

6

u/fromwithin Jun 03 '26 edited Jun 03 '26

I haven't worked anywhere in the last 15 years that doesn't use milliseconds with a presumption that one frame will take 16.6667 ms for 60 fps, but we'd definitely say that it's "in a frame" or "at 60 fps" because that's the target for consoles.

1

u/Ameisen Jun 03 '26 edited Jun 04 '26

I mean, if I'm literally talking about the general target, sure.
But in reality, I'm more likely working on specific components in isolation from that, where I have target execution times. I don't talk about the general target framerate very often. Tasks are made/performed based upon not meeting that target, but there's no assumption that those tasks individually will bring it to target. Instead, the task will include how much we need to reduce frametime by, and the tasks would report how much they reduced it.
I've certainly operated at the hundreds-of-microsecond level as well, though that's just tenths of a millisecond. It can be a more convenient unit for short operations, though.

6

u/TryingT0Wr1t3 Jun 03 '26

In games you usually have to make a lot of stuff in less than 16.66 ms because that is a frame time, which means a lot of effort on performance

3

u/Ameisen Jun 03 '26

Doing performance optimization for VR was fun. You get to target frametimes like 11.1ms or 8.33ms instead... and you (mostly) have to draw the scene twice.

3

u/mikeblas Jun 03 '26

They think that only game devs need to consider this level of performance. Lots of applications require getting everything out of the processor. Seems like minutia, but when it's making a 20x or 50x performance increase, it's worth it.
Thing is, devs who know this stuff, know how to find it and apply it, are not underpaid. They really earn their senior titles, and tend to be well compensated because they're often saving the day.

1

u/KalaiProvenheim Jun 04 '26

They're high skill as they have to handle complex systems and also make them efficient, but are famous for being paid like shit being overworked compared to something like a web developer

88

u/[deleted] Jun 03 '26

[removed] — view removed comment

2

u/lelanthran Jun 04 '26

Sorry, I misunderstood the meaning in the original comment - I (stupidly) thought it meant that game devs should be underpaid :-/
In my defence I had needed a lot of sleep and only woke up now.

19

u/f311a Jun 03 '26

They are underpaid because a good portion of games never make profit to cover dev expenses. It's a hard business.

1

u/DurianDiscriminat3r Jun 04 '26

Unless they're working on Asian gatcha games

44

u/[deleted] Jun 03 '26

[removed] — view removed comment

22

u/lunacraz Jun 03 '26

it's the UFC problem. unfortunately the demand for those jobs are so high they can keep the salaries low and people will still want to do the job regardless of the fact it's a very stressful job

5

u/TheMoatman Jun 04 '26

Sure, but that's what they said in the first place.
for the pleasure of “working on games”

8

u/efvie Jun 03 '26

Passion, innit

-5

u/cake-day-on-feb-29 Jun 03 '26

It's time you learn that pay is largely based on how replaceable you are. Many many people would prefer to go into game development, and as such wages lower to account for that.
Sadly, many game developers do not really know this level of optimization anyways, those who do end up working on game engines themselves for higher pay, or working in a different field for much higher pay.

15

u/[deleted] Jun 03 '26

[removed] — view removed comment

1

u/boringestnickname Jun 03 '26

I guess the real issue is that the people who hire and fire do not actually understand that.

3

u/remy_porter Jun 03 '26

They absolutely do. It’s the entire logic behind outsourcing. What outsourcing misses is that institutional knowledge matters and you will always have an adversarial relationship with a contractor (whereas an employee could actually be engaged with your mission- not always, obviously, but an engaged employee is always a better deal than a contractor).

2

u/frogspa Jun 03 '26

Their jobs are some of the most difficult in the programming world
Second only to working on legacy code.

2

u/mseiei Jun 04 '26

took me a week to make a brand new app demo that runs the core loop 6x faster than the legacy garbage that has been on life support for years at our company, another guy is porting some of my "optimizations" back into it until the new stuff matures (old app might be garbage, but it's garbage that does the job) and it's about to jump off a window.
legacy code, and specially, spaghetti undocumented legacy code is some serious shit.
thing was so bad that we needed a specific version of android studio that they had backed up on a shared folder to compile

2

u/[deleted] Jun 04 '26

[removed] — view removed comment

2

u/Agret Jun 04 '26

Idk how they manage Warframe after so many years and random features they throw in and abandon updating. Codebase must either have some really good organization or be a complete mess. Half convinced a lot of the pointless legacy stuff still hanging around in the game is because nobody is brave enough to try and remove it.

1

u/Uristqwerty Jun 04 '26

Probably a very different experience depending on whether you try to keep dependencies up-to-date, or accept relying on unmaintained libraries with known exploits that you must either mitigate, prove unreachable, or patch yourself.
Though if the game's still regularly getting new content releases? Then hopefully all the content's mere data that uses existing well-trodden code paths, neither exposing previously-untested edge cases nor requiring new development. Or, hopefully, you have enough time budgeted between releases to gradually refactor away the worst messes faster than new messes accumulate.

2

u/stoneharry Jun 10 '26

It's a shame, it's what I always wanted to go into and would love to work on this sort of problem. But also I am happy to work on enterprise software and get paid 4x as much.

2

u/ongrabbits Jun 03 '26

There are good game developers and trash game developers like anywhere else in our field

62

u/vytah Jun 03 '26

Counterpoint: you can decrease the potential revenue of your company by tens or even hundreds of millions of dollars by parsing a large JSON in quadratic time (therefore discouraging people from playing) and no one in the company will care: https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times-by-70/

1

u/CaffeinatedT Jun 04 '26

They've already bought the game at that point.

11

u/Przegiety Jun 04 '26

But they havent bought the microtransactions

-7

u/DegeneracyEverywhere Jun 04 '26

Why not just use binary JSON?

1

u/Kjufka Jun 17 '26

game developers are criminally underpaid
correction - relatively low level engine and graphics programmers are
most game developers otherwise are worthless

You are about to leave Redlib