AoS and SoA · Lablypedia

Structure of arrays

Structure of arrays (SoA) is a layout separating elements of a record (or 'struct' in the C programming language) into one parallel array per field. The motivation is easier manipulation with packed SIMD instructions in most instruction set architectures, since a single SIMD register can load homogeneous data, possibly transferred by a wide internal datapath (e.g. 128-bit). If only a specific part of the record is needed, only those parts need to be iterated over, allowing more data to fit onto a single cache line. The downside is requiring more cache ways when traversing data, and inefficient indexed addressing.

For example, to store N points in 3D space using a structure of arrays:

<span id="mwJw"></span><span class="linenos" data-line="1" id="mwKA"></span><span class="k" id="mwKQ">struct</span><span class="w" id="mwKg"> </span><span class="nc" id="mwKw">pointlist3D</span><span class="w" id="mwLA"> </span><span class="p" id="mwLQ">{</span> <span class="linenos" data-line="2" id="mwLg"></span><span class="w" id="mwLw"> </span><span class="kt" id="mwMA">float</span><span class="w" id="mwMQ"> </span><span class="n" id="mwMg">x</span><span class="p" id="mwMw">[</span><span class="n" id="mwNA">N</span><span class="p" id="mwNQ">];</span> <span class="linenos" data-line="3" id="mwNg"></span><span class="w" id="mwNw"> </span><span class="kt" id="mwOA">float</span><span class="w" id="mwOQ"> </span><span class="n" id="mwOg">y</span><span class="p" id="mwOw">[</span><span class="n" id="mwPA">N</span><span class="p" id="mwPQ">];</span> <span class="linenos" data-line="4" id="mwPg"></span><span class="w" id="mwPw"> </span><span class="kt" id="mwQA">float</span><span class="w" id="mwQQ"> </span><span class="n" id="mwQg">z</span><span class="p" id="mwQw">[</span><span class="n" id="mwRA">N</span><span class="p" id="mwRQ">];</span> <span class="linenos" data-line="5" id="mwRg"></span><span class="p" id="mwRw">};</span> <span class="linenos" data-line="6" id="mwSA"></span><span class="k" id="mwSQ">struct</span><span class="w" id="mwSg"> </span><span class="nc" id="mwSw">pointlist3D</span><span class="w" id="mwTA"> </span><span class="n" id="mwTQ">points</span><span class="p" id="mwTg">;</span> <span class="linenos" data-line="7" id="mwTw"></span><span class="kt" id="mwUA">float</span><span class="w" id="mwUQ"> </span><span class="nf" id="mwUg">get_point_x</span><span class="p" id="mwUw">(</span><span class="kt" id="mwVA">int</span><span class="w" id="mwVQ"> </span><span class="n" id="mwVg">i</span><span class="p" id="mwVw">)</span><span class="w" id="mwWA"> </span><span class="p" id="mwWQ">{</span><span class="w" id="mwWg"> </span><span class="k" id="mwWw">return</span><span class="w" id="mwXA"> </span><span class="n" id="mwXQ">points</span><span class="p" id="mwXg">.</span><span class="n" id="mwXw">x</span><span class="p" id="mwYA">[</span><span class="n" id="mwYQ">i</span><span class="p" id="mwYg">];</span><span class="w" id="mwYw"> </span><span class="p" id="mwZA">}</span>

5 more chapters are free with a Lably account.

Array of structures

Array of structures (AoS) is the opposite (and more conventional) layout, in which data for different fields is interleaved. This is often more intuitive, and supported directly by most programming languages.

For example, to store N points in 3D space using an array of structures:

<span id="mwbQ"></span><span class="linenos" data-line="1" id="mwbg"></span><span class="k" id="mwbw">struct</span><span class="w" id="mwcA"> </span><span class="nc" id="mwcQ">point3D</span><span class="w" id="mwcg"> </span><span class="p" id="mwcw">{</span> <span class="linenos" data-line="2" id="mwdA"></span><span class="w" id="mwdQ"> </span><span class="kt" id="mwdg">float</span><span class="w" id="mwdw"> </span><span class="n" id="mweA">x</span><span class="p" id="mweQ">;</span> <span class="linenos" data-line="3" id="mweg"></span><span class="w" id="mwew"> </span><span class="kt" id="mwfA">float</span><span class="w" id="mwfQ"> </span><span class="n" id="mwfg">y</span><span class="p" id="mwfw">;</span> <span class="linenos" data-line="4" id="mwgA"></span><span class="w" id="mwgQ"> </span><span class="kt" id="mwgg">float</span><span class="w" id="mwgw"> </span><span class="n" id="mwhA">z</span><span class="p" id="mwhQ">;</span> <span class="linenos" data-line="5" id="mwhg"></span><span class="p" id="mwhw">};</span> <span class="linenos" data-line="6" id="mwiA"></span><span class="k" id="mwiQ">struct</span><span class="w" id="mwig"> </span><span class="nc" id="mwiw">point3D</span><span class="w" id="mwjA"> </span><span class="n" id="mwjQ">points</span><span class="p" id="mwjg">[</span><span class="n" id="mwjw">N</span><span class="p" id="mwkA">];</span> <span class="linenos" data-line="7" id="mwkQ"></span><span class="kt" id="mwkg">float</span><span class="w" id="mwkw"> </span><span class="nf" id="mwlA">get_point_x</span><span class="p" id="mwlQ">(</span><span class="kt" id="mwlg">int</span><span class="w" id="mwlw"> </span><span class="n" id="mwmA">i</span><span class="p" id="mwmQ">)</span><span class="w" id="mwmg"> </span><span class="p" id="mwmw">{</span><span class="w" id="mwnA"> </span><span class="k" id="mwnQ">return</span><span class="w" id="mwng"> </span><span class="n" id="mwnw">points</span><span class="p" id="mwoA">[</span><span class="n" id="mwoQ">i</span><span class="p" id="mwog">].</span><span class="n" id="mwow">x</span><span class="p" id="mwpA">;</span><span class="w" id="mwpQ"> </span><span class="p" id="mwpg">}</span>

Array of structures of arrays

Array of structures of arrays (AoSoA) or tiled array of structs is a hybrid approach between the previous layouts, in which data for different fields is interleaved using tiles or blocks with size equal to the SIMD vector size. This is often less intuitive, but can achieve the memory throughput of the SoA approach, while being more friendly to the cache locality and load port architectures of modern processors. In particular, memory requests in modern processors have to be fulfilled in fixed width (e.g., size of a cacheline). The tiled storage of AoSoA aligns the memory access pattern to the requests' fixed width, leading to fewer access operations to complete a memory request and thus increasing the efficiency.

For example, to store N points in 3D space using an array of structures of arrays with a SIMD register width of 8 floats (or 8×32 = 256 bits):

<span id="mwtQ"></span><span class="linenos" data-line="1" id="mwtg"></span><span class="k" id="mwtw">struct</span><span class="w" id="mwuA"> </span><span class="nc" id="mwuQ">point3Dx8</span><span class="w" id="mwug"> </span><span class="p" id="mwuw">{</span> <span class="linenos" data-line="2" id="mwvA"></span><span class="w" id="mwvQ"> </span><span class="kt" id="mwvg">float</span><span class="w" id="mwvw"> </span><span class="n" id="mwwA">x</span><span class="p" id="mwwQ">[</span><span class="mi" id="mwwg">8</span><span class="p" id="mwww">];</span> <span class="linenos" data-line="3" id="mwxA"></span><span class="w" id="mwxQ"> </span><span class="kt" id="mwxg">float</span><span class="w" id="mwxw"> </span><span class="n" id="mwyA">y</span><span class="p" id="mwyQ">[</span><span class="mi" id="mwyg">8</span><span class="p" id="mwyw">];</span> <span class="linenos" data-line="4" id="mwzA"></span><span class="w" id="mwzQ"> </span><span class="kt" id="mwzg">float</span><span class="w" id="mwzw"> </span><span class="n" id="mw0A">z</span><span class="p" id="mw0Q">[</span><span class="mi" id="mw0g">8</span><span class="p" id="mw0w">];</span> <span class="linenos" data-line="5" id="mw1A"></span><span class="p" id="mw1Q">};</span> <span class="linenos" data-line="6" id="mw1g"></span><span class="k" id="mw1w">struct</span><span class="w" id="mw2A"> </span><span class="nc" id="mw2Q">point3Dx8</span><span class="w" id="mw2g"> </span><span class="n" id="mw2w">points</span><span class="p" id="mw3A">[(</span><span class="n" id="mw3Q">N</span><span class="o" id="mw3g">+</span><span class="mi" id="mw3w">7</span><span class="p" id="mw4A">)</span><span class="o" id="mw4Q">/</span><span class="mi" id="mw4g">8</span><span class="p" id="mw4w">];</span> <span class="linenos" data-line="7" id="mw5A"></span><span class="kt" id="mw5Q">float</span><span class="w" id="mw5g"> </span><span class="nf" id="mw5w">get_point_x</span><span class="p" id="mw6A">(</span><span class="kt" id="mw6Q">int</span><span class="w" id="mw6g"> </span><span class="n" id="mw6w">i</span><span class="p" id="mw7A">)</span><span class="w" id="mw7Q"> </span><span class="p" id="mw7g">{</span><span class="w" id="mw7w"> </span><span class="k" id="mw8A">return</span><span class="w" id="mw8Q"> </span><span class="n" id="mw8g">points</span><span class="p" id="mw8w">[</span><span class="n" id="mw9A">i</span><span class="o" id="mw9Q">/</span><span class="mi" id="mw9g">8</span><span class="p" id="mw9w">].</span><span class="n" id="mw-A">x</span><span class="p" id="mw-Q">[</span><span class="n" id="mw-g">i</span><span class="o" id="mw-w">%</span><span class="mi" id="mw_A">8</span><span class="p" id="mw_Q">];</span><span class="w" id="mw_g"> </span><span class="p" id="mw_w">}</span>

A different width may be needed depending on the actual SIMD register width. The interior arrays may be replaced with SIMD types such as float32x8 for languages with such support.

Alternatives

It is possible to split some subset of a structure (rather than each individual field) into a parallel array – and this can actually improve locality of reference if different pieces of fields are used at different times in the program (see data oriented design).

Some SIMD architectures provide strided load/store instructions to load homogeneous data from the SoA format. Yet another option used in some Cell libraries is to de-interleave data from the AoS format when loading sources into registers, and interleave when writing out results (facilitated by the superscalar issue of permutes). Some vector maths libraries align floating point 4D vectors with the SIMD register to leverage the associated data path and instructions, while still providing programmer convenience, although this does not scale to SIMD units wider than four lanes.

4D vectors

AoS vs. SoA presents a choice when considering 3D or 4D vector data on machines with four-lane SIMD hardware. SIMD ISAs are usually designed for homogeneous data, however some provide a dot product instruction and additional permutes, making the AoS case easier to handle.

Although most GPU hardware has moved away from 4D instructions to scalar SIMT pipelines, modern compute kernels using SoA instead of AoS can still give better performance due to memory coalescing.

Software support

Most languages support the AoS format more naturally by combining records and various array abstract data types.

SoA is mostly found in languages, libraries, or metaprogramming tools used to support a data-oriented design. Examples include:

"Data frames," as implemented in R, Python's Pandas package, and Julia's DataFrames.jl package, are interfaces to access SoA like AoS.
The Julia package StructArrays.jl allows for accessing SoA as AoS to combine the performance of SoA with the intuitiveness of AoS.
Code generators for the C language, including Datadraw and the X Macro technique.

Automated creation of AoSoA is more complex. An example of AoSoA in metaprogramming is found in LANL's Cabana library written in C++; it assumes a vector width of 16 lanes by default.