Why is struct of arrays not vastly faster than array of structs in Javascript?-CodePudding

I've been reading about data-oriented programming in the context of Entity Component Systems. Apparently, using a struct of arrays can more effectively leverage the cache and give substantial performance increases. Basically, if all of the data you're iterating over is contiguous, then cache locality is leveraged to give a large performance increase.

Because I'll be working in Javascript, I figured I'd first devise a small little benchmark to see how much of a performance increase is possible under ideal conditions. I made it very simple. In the first test I benchmark the speed of iterating over an array of structs, and in the second I benchmark the speed of iterating over a struct of arrays.

Here is the code:

function randomInt() { return Math.floor(Math.random() * 100)   1; }
function randomStr() { return Math.random().toString(36).substring(7); }

let samples = 1000;
let count = 10000000;

function benchmarkArrayOfStructs() {
  let AOS = [];

  for (let i = 0; i < count; i  ) {
    AOS.push({ health: randomInt(), name: randomStr(), damage: randomInt() });
  }

  let t1 = performance.now();
  
  let sum = 0;

  for (let x = 0; x < samples; x  ) {
    for (let i = 0; i < AOS.length; i  ) {
      let item = AOS[i];
    
      sum  = item.health   item.damage;
    }
  }
    
  console.log(performance.now() - t1);
}

function benchmarkStructOfArrays() {
  let SOA = { health: [], name: [], damage: [] }

  for (let i = 0; i < count; i  ) {
    SOA.health.push(randomInt());
    SOA.name.push(randomStr());
    SOA.damage.push(randomInt());
  }

  let t2 = performance.now();
  
  let sum = 0;

  let h = SOA.health;
  let d = SOA.damage;

  for (let x = 0; x < samples; x  ) {
    for (let i = 0; i < count; i  ) {  
      sum  = h[i]   d[i];
    }
  }

  console.log(performance.now() - t2);
}

benchmarkArrayOfStructs();
benchmarkStructOfArrays();

Interestingly, the latter solution is only 20% or so faster than the first solution. In the various talks that I've watched, they've claimed 10x speed increases for this type of operation. Also, intuitively I feel as if the latter solution should be much faster, but it isn't. Now I'm beginning to wonder if this sort of optimization is even worth integrating into my project, as it severely decreases ergonomics. Have I done something wrong in my benchmark, or is this the actual expected speedup?

CodePudding user response：

JavaScript isn't going to auto-vectorize with SIMD while JITting. That's one of the biggest advantages that an SoA layout allows, but you aren't taking advantage of it. (And AFAIK can't easily in JS.)

Also, if your code is the only thread running on an otherwise-idle desktop machine, you have much more memory bandwidth available to your thread than on a typical server, or on a busy machine with all cores competing for memory access. (Intel Xeons have lower max per-core DRAM memory bandwidth due to higher latency interconnects, but higher aggregate bandwidth with all cores busy. That's assuming you miss in private L2 cache.) So your benchmark probably tested a case where you have lots of excess memory bandwidth.

You might also see more benefit from SoA if your objects are bigger. Your AoS loop is reading 2 of the 3 objects from every array element, so only a small part of the data brought into cache is "wasted". If you try with more fields that your loop doesn't use, you may see a bigger advantage.

CodePudding user response：

In Javascript, there is no guarantee that an Array is a true array - for all you know the engine could be storing elements all over memory, nullifying cache locality. To force the engine to store an array in contiguous memory, you must use a TypedArray.

TypedArrays are also intrinsically faster than regular arrays since the JS engine doesn't have to do any guesswork whatsoever about usage patterns.