Notes Experiments

Coordinate pairs in JavaScript

Any application that works with 2D spaces, grids or tile maps needs a way of representing individual points as coordinate pairs. These will be extremely common short-lived objects in a wide variety of scenarios so I was curious to see the impacts of different representations across different browsers.

Overview

There’s a huge variety of things to look at here. To scratch the surface, I constructed a series of jsPerf benchmarks using the common pattern of enumerating neighbouring grid cells for a given x,y point as an adjacency list (without actually using an adjacency list data structure).

This approach is widely used to generate maps using cellular automata and run pathfinding algorithms, so the tests roughly approximate the kinds of real workloads one might see in a game or simulation.

The tests are initialised with a set of identical map grids containing a random distribution of cells marked as either ‘ocean’ or ‘land’ tiles. Each test iterates through every cell in the map and flips the marked tile if the majority of surrounding cells are a different kind of tile.

Representations

Array with two indices

[x, y]

Object literal with x,y properties

{
  x: x,
  y: y
}

Prototype constructor with x,y properties

function Point(x, y) {
  this.x = x
  this.y = y
}

ES6 class with getters

class Position {
  constructor(x, y) {
    this._x = x
    this._y = y
  }

  get x() {
    return this._x
  }

  get y() {
    return this._y
  }
}

Disclaimer

These benchmarks aren’t authoritative or definitive. At best, they give a rough overview of the characteristics of allocating memory in several different ways in the specific context of these tests.

It’s possible that the way I’ve implemented the loops could be confounding the measurements and there are a couple of changes I can make that will have a major impact on garbage collection. I’ll keep this post updated as I learn more.

Browser JavaScript engines change often (usually getting faster and faster) so this is really just a snapshot in time. YMMV.

Measurements

All results measured in ops/sec (higher is better).

Tested on: Mac OS X 10.12.5, 2.2 GHz Intel Core i7, 16 GB 1600 MHz DDR3.

Array with two indices

Grid size Safari 10.1.1 Firefox 54.0.0 Chrome 59.0.3071
2000 2.17 (±0.86%) 1.30 (±20.41%) 2.09 (±7.21%)
1000 7.81 (±1.01%) 4.20 (±9.84%) 6.86 (±5.95%)
500 30.55 (±2.60%) 15.83 (±2.69%) 33.02 (±1.93%)
200 127 (±3.23%) 99.36 (±0.67%) 214 (±1.59%)
100 152 (±16.04%) 387 (±0.50%) 854 (±1.43%)

Object literal with x,y properties

Grid size Safari 10.1.1 Firefox 54.0.0 Chrome 59.0.3071
2000 2.39 (±1.51%) 1.11 (±1.61%) 2.33 (±6.94%)
1000 8.56 (±0.98%) 4.04 (±2.41%) 7.69 (±5.69%)
500 33.24 (±2.76%) 16.56 (±1.01%) 37.31 (±2.04%)
200 157 (±5.30%) 101 (±0.54%) 251 (±2.19%)
100 261 (±31.46%) 419 (±0.97%) 987 (±1.32%)

Prototype constructor with x,y properties

Grid size Safari 10.1.1 Firefox 54.0.0 Chrome 59.0.3071
2000 2.38 (±0.90%) 1.07 (±2.50%) 2.28 (±3.56%)
1000 8.63 (±0.68%) 4.11 (±1.21%) 7.60 (±8.21%)
500 33.24 (±2.55%) 16.44 (±0.64%) 35.50 (±3.16%)
200 158 (±3.91%) 101 (±0.60%) 244 (±2.30%)
100 197 (±26.54%) 413 (±1.32%) 991 (±1.79%)

ES6 class with getters

Grid size Safari 10.1.1 Firefox 54.0.0 Chrome 59.0.3071
2000 2.41 (±1.69%) 1.02 (±3.24%) 1.11 (±3.24%)
1000 8.56 (±0.86%) 3.94 (±0.93%) 3.86 (±2.59%)
500 33.33 (±2.61%) 15.48 (±0.84%) 15.77 (±5.08%)
200 139 (±3.61%) 93.09 (±0.66%) 96.87 (±1.56%)
100 157 (±18.82%) 386 (±1.01%) 395 (±1.11%)

ES5 Object.assign

Grid size Safari 10.1.1 Firefox 54.0.0 Chrome 59.0.3071
2000 0.10 (±0.59%) 0.06 (±43.13%) 0.20 (±0.57%)
1000 0.41 (±1.79%) 0.26 (±44.64%) 0.78 (±2.99%)
500 1.59 (±2.65%) 0.92 (±21.03%) 3.07 (±2.74%)
200 7.96 (±4.50%) 5.29 (±6.94%) 17.42 (±1.62%)
100 28.80 (±2.27%) 20.44 (±1.37%) 68.08 (±1.23%)

Chrome

Firefox

Safari

Summary

There’s probably nothing here that is remarkable or unexpected.

Chrome wins at smaller collection sizes. Safari wins at larger collection sizes.

Between 200 and 500 cells, garbage collection seems to wash out any major differences between implementations.

Storing points in two element arrays is slightly slower than using object properties. Firefox arrays are closer to object properties in performance than in the other browsers.

Safari seems to exhibit a much greater standard deviation at smaller grid sizes.

In general, getter method wrappers are slower than direct property access.

Don’t use Object.assign in hot code paths. I included this out of curiosity and unsurprisingly, it was much, much slower. It’s also not a great fit for the problem of creating thousands of short-lived objects (though this isn’t a reason to avoid it in general—it’s a really useful feature!).

Resources

  • Fast properties in V8 explains how properties are handled internally in the V8 engine, which provides useful context for understanding these results.