performance consideration for the quads sparse array used in the quadtreebh

[LClauss]

http://jsperf.com/quadtest

[anvaka]

Thank you very much for this!

I've updated the quadtree module, and was impressed to see 1.6x performance boost.

Please feel free to share more ideas or contribute to https://github.com/anvaka/ngraph.quadtreebh if you see more opportunities for performance improvements

[LClauss]

Hi, i will work on that subject. i translated your whole library in typescript 2 weeks ago. no sure i translated every thing but i have nice results

i tried to made several changes ...

tried to change the way Math.sqrt is used (replacing with an approximation) but had some precision issues ( i will organize a jsperf on the subject as it was clearly very funny )

if you found the revision 2 of the quadtree test. i tried to replace the usage of mass , massX and some other vars in the body with a float32array and some get/set property (to have no impact on the rest of the code...)

next step for me is to organize the step computation in a worker (full computation or partial ) my target is to have the browser main tread with full reactivity.

i will share all the changes if they improve your library. regards (from France), Laurent

[anvaka]

Glad to hear! I'm going to add webworkers too, since they did improve performance significantly.

You can also run performance tests in the quatree module itself:

git clone https://github.com/anvaka/ngraph.quadtreebh
npm install
npm run perf

This will execute local benchmarks.

[LClauss]

Hi i made a small change in updateBodyForce . target idea was not to make less sqrt compute if we recurse on the children Math.sqrt is not called

updateBodyForce(sourceBody) {
  var queue = this.updateQueue,
    v = 0,
    dx = 0,
    dy = 0,
    r = 0,
    queueLength = 1,
    shiftIdx = 0,
    pushIdx = 1,
    body = null,
    node: Node = null,
    cmpare = 0,
    sumdxdy = 0;

  queue[0] = this.root;

  while (queueLength) {
    node = queue[shiftIdx],
    body = node.body;

    queueLength -= 1;
    shiftIdx += 1;
    // technically there should be external "if (body !== sourceBody) {"
    // but in practice it gives slightghly worse performance, and does not
    // have impact on layout correctness
    if (body && body !== sourceBody) {
      // If the current node is a leaf node (and it is not source body),
      // calculate the force exerted by the current node on body, and add this
      // amount to body's net force.
      dx = body.pos.x - sourceBody.pos.x;
      dy = body.pos.y - sourceBody.pos.y;
      sumdxdy = dx * dx + dy * dy;

      if (sumdxdy === 0) {
        // Poor man's protection against zero distance.
        dx = (this.random.nextDouble() - 0.5) / 50;
        dy = (this.random.nextDouble() - 0.5) / 50;
        sumdxdy = dx * dx + dy * dy;
      }
      r = Math.sqrt(sumdxdy);

      // This is standard gravition force calculation but we divide
      // by r^3 to save two operations when normalizing force vector.
      v = this.gravity * body.mass * sourceBody.mass / (r * r * r);
      sourceBody.force.x += v * dx;
      sourceBody.force.y += v * dy;
    } else {
      // Otherwise, calculate the ratio s / r,  where s is the width of the region
      // represented by the internal node, and r is the distance between the body
      // and the node's center-of-mass
      dx = node.massX / node.mass - sourceBody.pos.x;
      dy = node.massY / node.mass - sourceBody.pos.y;
      sumdxdy = dx * dx + dy * dy;

      if (sumdxdy === 0) {
        // Sorry about code duplucation. I don't want to create many functions
        // right away. Just want to see performance first.
        dx = (this.random.nextDouble() - 0.5) / 50;
        dy = (this.random.nextDouble() - 0.5) / 50;
        sumdxdy = dx * dx + dy * dy;
      }
      cmpare = ((node.right - node.left) / this.theta) * ((node.right - node.left) / this.theta);
      // If s / r < θ, treat this internal node as a single body, and calculate the
      // force it exerts on body b, and add this amount to b's net force.
      if (cmpare < sumdxdy) {
        r = Math.sqrt(sumdxdy);

        // in the if statement above we consider node's width only
        // because the region was squarified during tree creation.
        // Thus there is no difference between using width or height.
        v = this.gravity * node.mass * sourceBody.mass / (r * r * r);
        sourceBody.force.x += v * dx;
        sourceBody.force.y += v * dy;
      } else {
        // Otherwise, run the procedure recursively on each of the current node's children.

        // I intentionally unfolded this loop, to save several CPU cycles.
        if (node.quad0) { queue[pushIdx] = node.quad0; queueLength += 1; pushIdx += 1; }
        if (node.quad1) { queue[pushIdx] = node.quad1; queueLength += 1; pushIdx += 1; }
        if (node.quad2) { queue[pushIdx] = node.quad2; queueLength += 1; pushIdx += 1; }
        if (node.quad3) { queue[pushIdx] = node.quad3; queueLength += 1; pushIdx += 1; }
      }
    }
  }
}

with previous version

with modified code

tested with chrome, ie , firefox