Optimizing rendering with a lot of transformations and save/restore

Question

I have implemented a renderer for shapes described with a L-System grammar. Implementation of that is not important. Basically you feed it an angle and some rules, and it spits out a string of characters that represents instructions. For example, "+" means turn right n radians and vice versa. The instructions will only be computed once.

The job of the method .draw is to read the instructions and draw it on a canvas continuously. The angle is always changing (however the instructions stay the same) and therefore this method will be called repeatedly:

LSystem.prototype.draw = function(ctx, x, y) {
    var self = this;
    var path = this.path;
    var table = {
        "F": function(ctx) {
            // draw forward
            ctx.moveTo(0, 0);
            ctx.lineTo(0, -5);
            ctx.translate(0, -5);
        },
        "+": function(ctx) {
            // turn right
            ctx.rotate(self.angle);
        },
        "-": function(ctx) {
            // turn left
            ctx.rotate(-self.angle);
        },
        "[": function(ctx) {
            // save location and rotation
            ctx.save();
        },
        "]": function(ctx) {
            // restore location and rotation
            ctx.restore();
        }
    };
    ctx.save();
    ctx.beginPath();
    ctx.moveTo(x + 0.5, y + 0.5);
    ctx.translate(x + 0.5, y + 0.5);
    for (var i = 0; i < path.length; i++) {
        // take a character from the path
        // and call the corresponding function (if exists)
        var char = path[i];
        var cmd = table[char];
        cmd && cmd(ctx);
    }
    ctx.stroke();
    ctx.restore();
};

A path (in my case) consists of over 6000 characters. It has no problem in drawing at 60FPS. However the main problem is that it uses a lot of CPU and I can hear the fans in my laptop starts spinning. This is not optimal and I'm looking for a way to solve this.

By looking at the profiling tool in Chrome, we can see that it doesn't like .rotate and .restore being called repeatedly. On a 16ms budget it already takes up half of it:

What is a good way of optimizing the rendering and minimize CPU usage? Would calculating the coordinates for the entire path first then pass it to .lineTo be a better choice? Keep in mind that the angle is different every time .draw is called, so the coordinates cannot be cached and reused.

A demo can be viewed here.

Answer 1

I see this was the second javascript question you posted here and it is unfortunate that there have been no responses in the nearly four years since then. Perhaps you have learned a few things about JavaScript since then.

Looking at the draw method I see that it stores a reference to this in a variable called self. This pattern happens frequently in JavaScript code but it is unnecessary. I see that some of the functions in table utilize self but that could be avoided by binding those functions to this with Function.bind().

It also appears that ctx is passed to each function as a parameter, which is also unnecessary because ctx is hoisted at the top-level and visible within each function as well.

The functions in table associated with keys "[" and "]" could be simply set to ctx.save.bind(ctx) and ctx.restore.bind(ctx), respectively. Furthermore, the functions in table associated with keys "+" and "-" can be set to ctx.rotate.bind(ctx, this.angle) and ctx.rotate.bind(ctx, -this.angle), respectively.

I'm not sure if those changes will be enough to reduce the CPU load. If not, then consider taking out function calls (i.e. calling table[char]) and using a series of if statements or switch statement in the for loop.

Demo

While it may not be much, see the demo below which hopefully provides some proof that the suggestions lead to a slight performance gain (see the drawB() method). I considered using jsPerf but that might be a bit of a stretch to use for this code.

var rules = [
  //["F", "F[+F]F[-F]F"]

  //["F", "F+F--F+F"]

  //["1", "1F1F"],
  //["0", "1F[+0][-0]"]

  //["F", "F+F-F-F+F"]

  ["F", "FF"],
  ["X", "F-[[X]+X]+F[+FX]-X"]
];
var angle = 10;
const times = [{
  y: [],
  line: {
    color: "blue",
    width: 4,
    shape: "line"
  },
    name: "Original draw()"
}, {
  y: [],
  line: {
    color: "green",
    width: 4,
    shape: "line"
  },
    name: "Simplified draw()"
}];

function LSystem(rules, angle, init, level) {
  this.rules = {};
  this.angle = angle * Math.PI / 180;
  this.parseRules(rules);
  this.path = this.generateLevel(init, level);
}
LSystem.prototype.parseRules = function(rules) {
  var self = this;
  rules.forEach(function(rule) {
    self.rules[rule[0]] = rule[1];
  });
};
LSystem.prototype.applyRule = function(input) {
  var output = "";
  for (var i = 0; i < input.length; i++) {
    var char = input[i];
    if (char in this.rules) {
      output += this.rules[char];
    } else {
      output += char;
    }
  }
  return output;
};
LSystem.prototype.generateLevel = function(input, level) {
  if (level == 0) return input;
  return this.generateLevel(this.applyRule(input), level - 1);
};
LSystem.prototype.draw = function(x, y) {
  var start = +new Date();
  var self = this;
  var path = this.path;
  var table = {
    "F": function(ctx) {
      ctx.moveTo(0, 0);
      ctx.lineTo(5, 0);
      ctx.translate(5, 0);
    },
    "+": function(ctx) {
      ctx.rotate(self.angle);
    },
    "-": function(ctx) {
      ctx.rotate(-self.angle);
    },
    "[": function(ctx) {
      ctx.save();
    },
    "]": function(ctx) {
      //ctx.stroke();
      ctx.restore();
      //ctx.beginPath();
    }
  };
  ctx.save();
  ctx.clearRect(0, 0, 500, 500);
  ctx.beginPath();
  ctx.moveTo(x + 0.5, y + 0.5);
  ctx.translate(x + 0.5, y + 0.5);
  for (var i = 0; i < path.length; i++) {
    var char = path[i];
    var cmd = table[char];
    cmd && cmd(ctx);
  }
  ctx.stroke();
  ctx.restore();
  const end = +new Date();
  times[0].y.push((end - start));
  if (times[0].y.length > 1) {
    avg.innerText = times[0].y.reduce((a, b) => a + b) / times[0].y.length;
  }
};
LSystem.prototype.drawB = function(x, y) {
  var start = +new Date();
  var table = {
    "F": function() {
      ctxB.moveTo(0, 0);
      ctxB.lineTo(5, 0);
      ctxB.translate(5, 0);
    },
    "+": ctxB.rotate.bind(ctxB, this.angle),
    "-": ctxB.rotate.bind(ctxB, -this.angle),
    "[": ctxB.save.bind(ctxB),
    "]": ctxB.restore.bind(ctxB)
  };
  ctxB.save();
  ctxB.clearRect(0, 0, 500, 500);
  ctxB.beginPath();
  ctxB.moveTo(x + 0.5, y + 0.5);
  ctxB.translate(x + 0.5, y + 0.5);
  for (var i = 0; i < this.path.length; i++) {
    var char = this.path[i];
    var cmd = table[char];
    cmd && cmd();
  }
  ctxB.stroke();
  ctxB.restore();
  const end = +new Date();
  times[1].y.push((end - start));
  if (times[1].y.length > 1) {
    avgB.innerText = times[1].y.reduce((a, b) => a + b) / times[1].y.length;
    avgB.classList.toggle('faster', parseFloat(avgB.innerText) < parseFloat(avg.innerText));
    avgB.classList.toggle('slower', parseFloat(avgB.innerText) > parseFloat(avg.innerText));
    avg.classList.toggle('faster', parseFloat(avg.innerText) < parseFloat(avgB.innerText));
    avg.classList.toggle('slower', parseFloat(avg.innerText) > parseFloat(avgB.innerText));
  }
}


// main
var ctx,
  ctxB,
  s = new LSystem(rules, angle, "X", 5),
  sB = new LSystem(rules, angle, "X", 5),
  output;
window.onload = function() {
  ctx = document.querySelector("canvas").getContext("2d");
  ctxB = document.getElementById("cnvB").getContext("2d");
  output = document.querySelector("pre");

  ctx.translate(50, 500);
  ctx.rotate(Math.PI / 180 * -65);
  ctx.translate(0, -250);

  ctxB.translate(50, 500);
  ctxB.rotate(Math.PI / 180 * -65);
  ctxB.translate(0, -250);

  //ctx.translate(250, 500);
  function d(t) {
    requestAnimationFrame(d);
    ctx.clearRect(0, 0, 500, 500);
    ctxB.clearRect(0, 0, 500, 500);
    s.draw(0, 250);
    sB.drawB(0, 250);

    s.angle = Math.PI / 180 * (25 + Math.sin(t / 1000));
    sB.angle = Math.PI / 180 * (25 + Math.sin(t / 1000));
  }
  output.textContent = s.path.length;
  requestAnimationFrame(d);
};

canvas {
  border: 1px solid black;
}

output.slower {
  background-color: red;
  color: white;
}

output.faster {
  background-color: green;
  color: white;
}

<div id="chart">
  <div id="comparison"></div>
</div>
<table>
 <tr><td> Avg time for <code>draw()</code></td><td> <output id="avg"></output> ms
</td></tr>
<tr><td>
  Avg time for modified <code>draw()</code> </td><td><output id="avgB"></output> ms
</td></tr>
</table>
<canvas width="500" height="500"></canvas>
<canvas width="500" height="500" id="cnvB"></canvas>
<pre></pre>

Result

Below is a chart comparing the elapsed times of 100 calls to the original draw method and the modified draw method.