This article reminds me of performance advice I was starting to see in the 2000s decade. Basically it was to not introduce a bunch of pointer heavy data structures to get lower algorithmic complexity. Stuff it all into a vector. You will use some algorithms that the computer science textbook will say it's slower, but if it fits all in cache it doesn't matter. The cache misses following pointers all over town hurts you more.
It's interesting because I tried to follow this advice when I wrote my own interpreter, but either 1. I just had a bad intuition and it's gotten better, or 2. It's trickier with interpreters when you have thousands of objects.
For example, since I allowed for objects to be shared between threads, I decided to use struct of arrays so the reference count, metadata, and value would be stored in separate cache lines. This ended up hurting me because object initialization touched three separate cache lines (obvious in hindsight, but the advice of using SoA failed me here). I also heard that you want to pack your values as tight as possible, so I used a packed string index, but then I ended up with integer division to unpack the string (also a mistake, but again the advice failed me). I used a custom allocator to avoid indirection with lists (list items were allocated directly after the list head), but then I had heap fragmentation and the implementation complexity exploded.
Anyways, I am now happily using two to three levels of indirection in my data structures, large structs, and malloc for individual objects, and it's still been faster in my end to end testing. So maybe this is unique to interpreters, and maybe I could have done it better, but the suggestions don't automatically apply in my experience.
>This ended up hurting me because object initialization touched three separate cache lines (obvious in hindsight, but the advice of using SoA failed me here).
I mean this is kind of what happens with any advice that has nuance to it, that's not carried with the advice.
E.g. if you have a point in 3D space with x, y, z coordinates. Array points as SoA of individual dimensions makes sense only if you do a lot of averaging and such on the individual dimensions.
If you mostly use the 3 coordinates together, SoA will have bad caching behavior.
So the better advice would be to try to keep things that are used together in the same cache line, whether it's on dimension or all 3. Usage makes the difference.
asveikau · · focus · HN ↗
smj-edison · · focus · HN ↗
For example, since I allowed for objects to be shared between threads, I decided to use struct of arrays so the reference count, metadata, and value would be stored in separate cache lines. This ended up hurting me because object initialization touched three separate cache lines (obvious in hindsight, but the advice of using SoA failed me here). I also heard that you want to pack your values as tight as possible, so I used a packed string index, but then I ended up with integer division to unpack the string (also a mistake, but again the advice failed me). I used a custom allocator to avoid indirection with lists (list items were allocated directly after the list head), but then I had heap fragmentation and the implementation complexity exploded.
Anyways, I am now happily using two to three levels of indirection in my data structures, large structs, and malloc for individual objects, and it's still been faster in my end to end testing. So maybe this is unique to interpreters, and maybe I could have done it better, but the suggestions don't automatically apply in my experience.
carlmr · · focus · HN ↗
I mean this is kind of what happens with any advice that has nuance to it, that's not carried with the advice.
E.g. if you have a point in 3D space with x, y, z coordinates. Array points as SoA of individual dimensions makes sense only if you do a lot of averaging and such on the individual dimensions.
If you mostly use the 3 coordinates together, SoA will have bad caching behavior.
So the better advice would be to try to keep things that are used together in the same cache line, whether it's on dimension or all 3. Usage makes the difference.