Hacker News Reader

Comment by Altern4tiveAcc | Hacker News Reader

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.

Sure, but these schemes might have their own drawbacks depending on the exact use case - especially if you have a very dynamic number of monsters and constantly add and remove them (say, some kind of bullet hell style game).

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.

Two fields should be fine, actually. The way caches are organized you are very unlikely to thrash with the lookups (due to n-way associativity) while only keeping relevant data in the cache at the same time. You still have roughly the following layout (in the cache), where A is the field and V is valid:

  | A1 A2 A3 A4 | A5 A6 A7 A8 | ...
  | V1 V2 V3 V4 | V5 V6 V7 V8 | ...

The former access pattern still yields a clean cache layout where no unnecessary data is loaded (which is the most costly operation here by far) as opposed to

  | A1 V1 B1 C1 | ... | A2 V2 B2 C2  | ...

In the general case there will exist a number of fields for which SOA layout will be worse if all are accessed close to each other, but for just a validity indicator this should not be the case. I think your statement is not wrong, but also not 100% correct.

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.

Reply on news.ycombinator.com