Benchmark: Multiplying lists of vectors - SoA vs AoS vs interlaced array

Multiplying lists of vectors - SoA vs AoS vs interlaced array (version: 0) Benchmark.js

What's the fastest way to process a list of vectors? Do you go the OO route, with an array of Vector() objects? Do you create a new data structure, using Float32Arrays for x, y, and z? Do you create a single Float32Array and interlace values for x, y, and z within it? Let's find out!

Comparing performance of: `AoS vs SoA - one loop vs SoA - one component per loop vs Interlaced Array - no loop unrolling vs Interlaced Array - with loop unrolling`

Created: 9 years ago by: Guest

Go to the latest result

Script Preparation code:

var N = 1000000

var x = new Float32Array(N);
var y = new Float32Array(N);
var z = new Float32Array(N);

var interlaced = new Float32Array(3*N);

var vectors = [];

for (var i = 0, li=x.length; i < li; ++i) {
	x[i] = Math.random();
	y[i] = Math.random();
	z[i] = Math.random();
	vectors.push( {x:Math.random(), y:Math.random(), z:Math.random()} );
}

for (var i = 0, li=interlaced.length; i < li; ++i) {
	interlaced[i] = Math.random();
}

Tests:

AoS
var vector; for (var i = 0, li=vectors.length; i < li; ++i) { vector = vectors[i]; vector.x = 2 * vector.x; vector.y = 2 * vector.y; vector.z = 2 * vector.z; } for (var i = 0, li=vectors.length; i < li; ++i) { vector = vectors[i]; vector.x = 2 / vector.x; vector.y = 2 / vector.y; vector.z = 2 / vector.z; } for (var i = 0, li=vectors.length; i < li; ++i) { vector = vectors[i]; vector.x = 2 * vector.x; vector.y = 2 * vector.y; vector.z = 2 * vector.z; }
SoA - one loop
for (var i = 0, li=x.length; i < li; ++i) { x[i] = 2 * x[i]; y[i] = 2 * y[i]; z[i] = 2 * z[i]; }
SoA - one component per loop
for (var i = 0, li=x.length; i < li; ++i) { x[i] = 2 * x[i]; } for (var i = 0, li=y.length; i < li; ++i) { y[i] = 2 * y[i]; } for (var i = 0, li=z.length; i < li; ++i) { z[i] = 2 * z[i]; }
Interlaced Array - no loop unrolling
for (var i = 0, li=interlaced.length; i < li; ++i) { interlaced[i] = 2*interlaced[i]; }
Interlaced Array - with loop unrolling
for (var i = 0, li=interlaced.length; i < li; i+=3) { interlaced[i] = 2*interlaced[i]; interlaced[i+1] = 2*interlaced[i+1]; interlaced[i+2] = 2*interlaced[i+2]; }

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
AoS
SoA - one loop
SoA - one component per loop
Interlaced Array - no loop unrolling
Interlaced Array - with loop unrolling

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 2 years ago)

User agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/123.0.0.0 Safari/537.36

Browser/OS: Chrome 123 on Windows

View result in a separate tab

AoS

7/s

Interlaced Array - no loop unrolling

4/s

SoA - one component per loop

4/s

SoA - one loop

4/s

Interlaced Array - with loop unrolling

4/s

View exact numbers

Test name	Executions per second
✓ AoS	7 Ops/sec
Interlaced Array - no loop unrolling	4 Ops/sec
SoA - one component per loop	4 Ops/sec
SoA - one loop	4 Ops/sec
Interlaced Array - with loop unrolling	4 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

Let's dive into the benchmark and explain what's being tested.

**Benchmark Definition**

The benchmark is designed to measure the performance of three different approaches for processing lists of vectors:

1. **Array of Objects (AoS)**: This approach involves creating an array of `Vector` objects, where each object represents a vector with x, y, and z components.
2. **Structured Array of Arrays (SoA)**: This approach involves creating separate arrays for the x, y, and z components of the vectors.
3. **Interlaced Array**: This approach involves creating a single array that interlaces the values for each component (x, y, and z) in an interleaved pattern.

**Options Compared**

The benchmark compares the performance of these three approaches under different conditions:

* `SoA - one loop`: The vectors are processed using a single loop that accesses all components simultaneously.
* `SoA - one component per loop`: The vectors are processed using separate loops for each component (x, y, and z).
* `Interlaced Array - no loop unrolling`: A basic implementation of the interlaced array approach without any loop unrolling optimizations.
* `Interlaced Array - with loop unrolling`: An optimized version of the interlaced array approach that uses loop unrolling to reduce overhead.

**Pros and Cons**

Here's a brief summary of the pros and cons of each approach:

* **AoS**: Pros: Easy to implement, good for small datasets. Cons: Poor cache locality, can lead to slower performance on large datasets.
* **SoA**: Pros: Good cache locality, can lead to faster performance on large datasets. Cons: More complex implementation, requires more memory for separate arrays.
* **Interlaced Array**:
	+ `No loop unrolling`: Pros: Simple to implement, good for small datasets. Cons: Poor performance on large datasets due to excessive overhead.
	+ `With loop unrolling`: Pros: Optimized performance on large datasets, reduced overhead. Cons: More complex implementation.

**Latest Benchmark Results**

The latest benchmark results show the performance of each approach under the same conditions:

| TestName | ExecutionsPerSecond |
| --- | --- |
| AoS | 7.208 |
| Interlaced Array - no loop unrolling | 4.090 |
| SoA - one component per loop | 4.077 |
| Interlaced Array - with loop unrolling | 3.544 |

The results suggest that the optimized interlaced array approach (`With loop unrolling`) outperforms the other approaches, followed closely by the structured array of arrays (`SoA - one component per loop`). The array of objects (`AoS`) is the slowest.

In summary, this benchmark highlights the importance of considering cache locality and memory layout when designing algorithms for processing large datasets. The optimized interlaced array approach demonstrates the benefits of using loop unrolling to reduce overhead, while the structured array of arrays approach shows good performance due to its cache-friendly design.