Why does javascript process an array of structures faster than a structure of arrays?

Question

I've been looking for an efficient way to process large lists of vectors in javascript. I created a suite of performance tests that perform in-place scalar-vector multiplication using different data structures:

AoS implementation:

var vectors = [];
//
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;
}

SoA implementation:

var x = new Float32Array(N);
var y = new Float32Array(N);
var z = new Float32Array(N);
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];
}

The AoS implementation is at least 5 times faster. This caught me by surprise. The AoS implementation uses one more index lookup per iteration than the SoA implementation, and the engine has to work without a guaranteed data type.

Why does this occur? Is this due to browser optimization? Cache misses?

On a side note, SoA is still slightly more efficient when performing addition over a list of vectors:

AoS:

var AoS1 = [];
var AoS2 = [];
var AoS3 = [];
//code for populating arrays
for (var i = 0; i < N; ++i) {
    AoS3[i].x = AoS1[i].x + AoS2[i].x;
}

SoA:

var x1 = new Float32Array(N);
var x2 = new Float32Array(N);
var x3 = new Float32Array(N);
for (var i = 0; i < N; ++i) {
    x3[i] = x1[i] + x2[i];
}

Is there a way I can tell when an operation is going to be more/less efficient for a given data structure?

EDIT: I failed to emphasize the SoA implementation made use of typed arrays, which is why this performance behavior struck me as odd. Despite having the guarantee of data type provided by typed arrays, the plain-old array of associative arrays is faster. I have yet to see a duplicate of this question.

EDIT2: I've discovered the behavior no longer occurs when the declaration for vector is moved to preparation code. AoS is ostensibly faster when vector is declared right next to the for loop. This makes little sense to me, particularly since the engine should just anchor it to the top of the scope, anyways. I'm not going to question this further since I suspect an issue with the testing framework.

EDIT3: I got a response from the developers of the testing platform, and they've confirmed the performance difference is due to outer scope lookup. SoA is still the most efficient, as expected.

Please post your code here, not just as a link to the benchmarking site. — Barmar, Sep 30 '16 at 20:57
Modern Javascript engines have special optimizations of object accesses. — Barmar, Sep 30 '16 at 21:05
In the AoS test my "structures" are associative lists. In the SoA test I don't implement the "structure" and the arrays are in the global scope. I presume its not relevant to performance. https://en.wikipedia.org/wiki/AOS_and_SOA — 16807, Sep 30 '16 at 21:11
Related, if not dupe: http://stackoverflow.com/q/17295056/215552 — Heretic Monkey, Sep 30 '16 at 21:35
@16807 FWIW, I found `*= 2` to be a lot more efficient. No idea why. — Veedrac, Oct 01 '16 at 17:51

Travis J · Accepted Answer · 2016-09-30T23:37:23.867

3

The structure of the tests being used for benchmarking seem to have overlapped each other causing either undefined or undesired behavior. A cleaner test (https://www.measurethat.net/Benchmarks/Show/474/0/soa-vs-aos) shows little difference between the two, and has SOA executing slightly (30%) faster.

However, none of this matters to the bottom line when it comes to performance. This is an effort in micro-optimization. What you are essentially comparing is O(n) to O(n) with nuance involved. The small percent difference will not have an effect overall as O(n) is considered to be an acceptable time complexity.

edited Sep 30 '16 at 23:37

answered Sep 30 '16 at 21:54

Travis J

81,153
41
202
273

"whereas the array of structures only requires 1 lookup per iteration". An Attribute lookup on an associative array (e.g. "vector.x") is still a lookup. I'm counting 6 lookups for the SoA and 7 lookups for the AoS. I don't see where you get the additional 3 lookups for SoA. The complexity is the same, but consider there are applications where a factor of 5 improvement makes a world of difference. – 16807 Sep 30 '16 at 22:29
I corrected the lookup count to be 6, that is accurate. – Travis J Sep 30 '16 at 22:34
The attribute lookup is not going to be the same as the index lookup as the size of the set contributes to how much time the lookup takes. There are only a small amount of attributes on your object versus potentially thousands of items in the set. – Travis J Sep 30 '16 at 22:35
A factor of 5 times? Heh, no no, the difference between two O(n) operations should be closer to a 3% difference, not a 500% difference. – Travis J Sep 30 '16 at 22:36
As I mention in the question, the observed difference on chrome is a factor of 5. I just got around to testing in firefox and I see a 250% difference. – 16807 Sep 30 '16 at 22:48
@16807 - The test you are running is being influenced by the other tests present. Here is one without the noise: https://www.measurethat.net/Benchmarks/Show/474/0/soa-vs-aos You can see there is only a 30% difference, which is slightly significant but that is also at a set of 1,000,000 items, and again we are talking about 30% of what probably amounts to a millisecond. – Travis J Sep 30 '16 at 22:56
Also note, without the noise, that your claim is refuted. The AOS runs slower. – Travis J Sep 30 '16 at 22:58
On creating a new test without the code for interlacing I am no longer able to reproduce the behavior. – 16807 Sep 30 '16 at 23:27
@16807 - Removed the front part of the answer and replaced it with the new found benchmarking. However, I did leave the latter part as it still remains the bottom line here in my opinion. – Travis J Sep 30 '16 at 23:38
7

@TravisJ "The small percent difference will not have an effect overall as O(n) is considered to be an acceptable time complexity." // If this is your code's bottleneck, a 30% improvement isn't trivial. You can't just say "O(n) is an acceptable time complexity" without knowing the context. – Veedrac Oct 01 '16 at 17:46
2

The very benchmark you linked shows a whopping 43% percent improvement! I think you must have mixed up the numbers: AOS is 30% slower than SOA. SOA is 43% faster than AOS. It's also very much worth noting that in practice, for large arrays in large programs, the gains can be significantly greater, as SOA will NOT thrash the CPU caches with irrelevant object data, while simultaneously making the CPU prefetcher's life easy! Effectively, depending on context, this may well change the factor by an order of magnitude (or theoretically even two in extreme cases!) – Martin Grönlund Apr 28 '21 at 13:40

Why does javascript process an array of structures faster than a structure of arrays?

1 Answers1