Enum of Arrays

and an array of Things,

it’s possible to wrap the data inside out and use

instead. The benefits are:

• Reduced memory usage due to amortized padding. As flag
  is a byte, it requires some padding to align with larger fields like
  checksum. In AoS, each individual struct has
  this padding. In SoA, there’s still padding for
  flag, but it’s just one instance of padding for all the
  Things.
• Better memory bandwidth utilization for batched code. If a loop
  needs to process all things, but the processing doesn’t require all
  fields (at least for the majority of objects), then an array-based
  representation reduces the amount of data that needs to be loaded.

You can use the same trick also for a more SIMD-friendly data layout.
A bad way to use SIMD is to try to vectorize the processing of an
individual item. A good way to use SIMD is to process several items at
once.

For example, if a Thing in question is a 3D vector, it’s
usually not a good idea to implement the dot product of two vectors by
loading xyz of one vector into a SIMD register
a, xyz of another vector into a SIMD register
b, and then performing a SIMD multiplication of
a * b. The reason is that your “SIMD width” is still only
three numbers:

Much better to simultaneously compute the dot products of multiple
pairs of vectors. Then, you can load a SIMD vector with
xxxxxxx, which is the x coordinate for the
first vector of multiple pairs. And so, the full width of SIMD registers
is used:

This post is to raise awareness that the same trick works with
enums:

Here’s an array of enums:

And here’s the dual, an enum of arrays:

The key idea is that there’s only a single tag
per an entire batch of things. If a batch size is 1024, you can have
1024 spams or 1024 eggs, but not a mix of the two.

The benefits of this representation:

• Tags occupy less bytes in total, because a single tag can be
  amortized across many objects at once.

• If individual enum variants are of different sizes, then no
  memory is wasted when storing the gap between a small variant and a
  large one.

• Finally, the purpose of the tag is for the CPU to branch on it.
  By having only one tag per batch of objects, the amount of branching the
  CPU has to do is dramatically reduced, which is a very good thing in
  itself—unpredictable branching slows down the CPU a lot. But what’s
  more, with branching out of the way, the processing is opened up for
  SIMD optimizations!

TigerBeetle is built around this idea of AoE => EoA
optimizations. TigerBeetle can do two things: create new accounts, and
then create transfers between accounts. This could have been
represented as a heterogeneous enum of the two kinds of operation.
Instead, TigerBeetle uses homogeneous batches. TigerBeetle does eight
thousands operations at a time, and there’s one tag for an entire batch.
So, it’s always 8k transfers followed by 8k accounts, not a mixture of
the two.

This optimization is related to the concept of data plane and control
plane separation. The tag is control plane, a small,
infrequent piece of information which informs decisions. The data plane
then is more voluminous, but processing it doesn’t require many
individual decisions. Just. One. Branch!

That’s all for today. Support your local branch predictor, convert
your AoE to EoA!