# Efficient Data Exchange between WebAssembly Modules
## 4 Karmem Approach
### Data Layout
#### 4.2.3 Unions  
Unions are one of the most basic data structures to enable polymorphism, even though each programming language names this type differently. It can be classified as Tagged-Union or Untagged-Union, relative to the explicit knowledge of the type being stored. It can also be classified as direct or indirect, relative to how it uses the space and how much space it can take. For instance, C uses the largest value size as the union size and for additional paddings, and it does not store the type of data. Languages such as Go or Java implement their interface using a fixed size and use pointers to the actual data and metadata.  
Karmem stores the metadata of the current type inline but does not necessarily use the naive approach of Go, which stores two words (one pointer to metadata and another to the actual data). Instead, we can also gain some advantages when combining unions with arrays.  
When used as a single value, Karmem's storage mechanism includes an identifier number (a tag) and the offset to the actual data. By default, the tag is 32 bits, though this can be adjusted in the schema. While using smaller numeric types (such as uint8) does not provide an advantage in this context, the feature is supported for reasons that will be discussed later.  
Using unions within arrays allows for various memory layout configurations. Karmem enables programmers to define these arrays using different layouts such as AoS, SoA, and Bunch of Values (BoV). Due to the lack of formal nomenclature, we name BoV a data type, which contains multiple vectors for each of the data types represented in a union; this method lacks the proper insertion ordering. BoV's name is inspired by \"Just a Bunch of Disks\" (JBOD), which is used in data-storage systems where multiple hard drives operate independently without any interrelation. This definition can be extended to BoVoA (Bunch of Values of Arrays) and BoVoS (Bunch of Values of Structures), which combines the representation of the inner union as AoS or SoA, respectively.  
The code, in Figure 3, defines a structure for a particle that contains an array, \"pos\", which can consist of either 2D or 3D points. The union definition (any_point) employs an 8-bit tag, with each tag explicitly defined, although this is entirely optional.  
Figures 4-7 illustrate the memory layout of each representation, with padding and size considerations omitted for simplicity. The AoS (depicted in Figure 4) is the most common method. However, searching for a specific tag can be inefficient due to the constant 32-bit offset between each tag. Additionally, AoS cannot leverage shorter tag types effectively, resulting in an additional 24 bits of padding when using an 8-bit tag.  
SoA can optimize linear search and enable the use of SIMD (single instruction, multiple data) instructions. Specifically, with an 8-bit tag, it is possible to compare one tag against 64 tags per loop using a single AVX512 instruction. In contrast, using the same AVX512 instruction with AoS limits the comparison to a maximum of eight tags due to padding and pointer data. Furthermore, accessing the pointer can lead to cache misses if prefetching is not employed for the second array.  
In cases where the order is not important, BoV (either BoVoA or BoVoS) can be advantageous. These configurations create separate arrays for each type declared in the union, thus eliminating the need for searching and enabling the use of non-polymorphic functions. Figures 6 and 7 illustrate this type of construction.  
Figure 2: Comparing AoS, SoA, and AoP.  
Figure 4: Simplified memory layout of AoS of unions.  
Figure 5: Simplified memory layout of SoA of unions.  
Figure 6: Simplified memory layout of BoVoA.  
Figure 3: Example of a union capable of holding either a 2D point or a 3D point.  
Figure 7: Simplified memory ILayout of BoVoS.