ubilabs / kd-tree-javascript

JavaScript k-d Tree Implementation
MIT License
643 stars 109 forks source link

Performance drop since 0.12 #13

Open yamsellem opened 9 years ago

yamsellem commented 9 years ago

We've found a performance drop in our production code when migrating to node 0.12. Here is a benchmark that reproduces it (based on the readme sample):

var kdtree = require('./kdtree'); // an npm module would be awesome ;-)
var Benchmark = require('benchmark');

var points = [
  {x: 1, y: 2},
  {x: 3, y: 4},
  {x: 5, y: 6},
  {x: 7, y: 8}
];

var distance = function(a, b){
  return Math.pow(a.x - b.x, 2) +  Math.pow(a.y - b.y, 2);
}
var tree = new kdTree(points, distance, ["x", "y"]);

var suite = new Benchmark.Suite();
suite.add('Tree#nearest', function() {
    tree.nearest({ x: 5, y: 5 }, 2);
})
.on('cycle', function(event) {
    console.log(String(event.target));
})
.run({ 'async': true });

On node 0.10.24 (tested on 0.10.39 with similar results)

Tree#nearest x 321,548 ops/sec ±1.68% (92 runs sampled)

On node 0.12.6 (tested on 0.12.0 with similar results)

Tree#nearest x 82,008 ops/sec ±3.13% (75 runs sampled)

Any idea on the matter?

mirceapricop commented 9 years ago

It looks like this was caused by an across the board performance drop in node 0.12.

Apparently this is caused by them picking up some performance-degrading changes in V8 without the subsequent fixes.

I don't know what you could do here except for downgrading node, waiting for a release with a more recent V8 build, or switch to io.js maybe? (https://raygun.io/blog/2015/05/performance-showdown-node-js-vs-io-js-v2-0-0/)

yamsellem commented 9 years ago

We've been reviewing our code for the big jump to 0.12 and we've not found any global performance drop. Several things may seem slower (accessing or assigning object for instance) but this is more related to micro benchmark (in the cases we've found so far). On the other hand, there is some real performance boost as well.

Creating objects and arrays seems more expensive (in heavy algorithm mainly), but it seems that manipulating data is faster than ever.

I'm sorry that I cannot be more precise on a recipe to boost an algorithm for 0.12, I don't know any. It seems that a lot of libraries are not affected be this shift, but, for the others (uglify has a similar issue) solutions remain to be found.