d3-force-reuse speed comparison

A performance comparison of d3.forceManyBodyReuse() in d3-force-reuse and the standard d3.forceManyBody() in d3-force. d3.forceManyBodyReuse() tends to perform faster than d3.forceManyBody(), often with a total runtime of about 70% of that in d3.forceManyBody(). It achieves this performance improvement by reusing Barnes-Hut approximations instead of calculating a new one at each tick of the algorithm. See d3-force-reuse and the research paper for more details:

Robert Gove. "It Pays to Be Lazy: Reusing Force Approximations to Compute Better Graph Layouts Faster." Proceedings of Forum Media Technology, 2018. Preprint PDF.

Contains code from Mike Bostock's force-directed layout example and my KDE heatmap example.

<!DOCTYPE html>
<meta charset="utf-8">
<style>

svg {
  overflow: visible;
}

text.runtime {
  text-anchor: middle;
  font-family: sans-serif;
  font-weight: bold;
  fill: #888;
  font-size: 72px;
}

.links line {
  stroke: #999;
  stroke-opacity: 0.6;
}

.nodes circle {
  stroke: #fff;
  stroke-width: 1.5px;
}

</style>
<svg id="d3-force" width="400" height="400"></svg>
<svg id="d3-force-reuse" width="400" height="400"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="d3-force-reuse.js"></script>
<script>

var svg = d3.select("#d3-force").attr('transform', 'scale(0.75)'),
    width = +svg.attr("width"),
    height = +svg.attr("height");

var svgReuse = d3.select("#d3-force-reuse").attr('transform', 'scale(0.75)');

var runtime = svg.append('text')
  .attr('class', 'runtime')
  .attr('x', width/2)
  .attr('y', height/4);

var runtimeReuse = svgReuse.append('text')
  .attr('class', 'runtime')
  .attr('x', width/2)
  .attr('y', height/4);

var dispatch = d3.dispatch('tickend');

var computeTimes = [
  {name: 'd3-force', values: []},
  {name: 'd3-force-reuse', values: []}
];

var chartMargin = {top: 10, right: 20, bottom: 30, left: 50};
var chartWidth = 800 - chartMargin.left - chartMargin.right;
var chartHeight = 175 - chartMargin.top - chartMargin.bottom;

var x = d3.scaleLinear().rangeRound([0, chartWidth]);
var y = d3.scaleLinear().rangeRound([chartHeight, 0]);

var chartSvg = d3.select("body").append("svg")
  .attr("width", chartWidth + chartMargin.left + chartMargin.right)
  .attr("height", chartHeight + chartMargin.top + chartMargin.bottom)
  .append('g')
  .attr("transform", "translate(" + chartMargin.left + "," + chartMargin.top + ")");

var line = d3.line()
  .x(function (d) { return x(d.i); })
  .y(function (d) { return y(d.time); });

var simulation = d3.forceSimulation()
    .force("link", d3.forceLink().id(function(d) { return d.id; }))
    .force("charge", d3.forceManyBody())
    .force("center", d3.forceCenter(width / 2, height / 2));

var simulationReuse = d3.forceSimulation()
    .force("link", d3.forceLink().id(function(d) { return d.id; }))
    .force("charge", d3.forceManyBodyReuse())
    .force("center", d3.forceCenter(width / 2, height / 2));

d3.json("miserables.json", function(error, forceGraph) {
  if (error) throw error;

d3.json("miserables.json", function(errorReuse, forceReuseGraph) {
    if (errorReuse) throw errorReuse;

// Setup d3-force
    var link = svg.append("g")
        .attr("class", "links")
      .selectAll("line")
      .data(forceGraph.links)
      .enter().append("line")
        .attr("stroke-width", function(d) { return Math.sqrt(d.value); });

var node = svg.append("g")
        .attr("class", "nodes")
      .selectAll("circle")
      .data(forceGraph.nodes)
      .enter().append("circle")
        .attr("r", 5)
        .attr("fill", 'steelblue');

node.append("title")
        .text(function(d) { return d.id; });

simulation
        .nodes(forceGraph.nodes)
        .stop();

simulation.force("link")
        .links(forceGraph.links);

// Setup d3-force-reuse
    var linkReuse = svgReuse.append("g")
        .attr("class", "links")
      .selectAll("line")
      .data(forceReuseGraph.links)
      .enter().append("line")
        .attr("stroke-width", function(d) { return Math.sqrt(d.value); });

var nodeReuse = svgReuse.append("g")
        .attr("class", "nodes")
      .selectAll("circle")
      .data(forceReuseGraph.nodes)
      .enter().append("circle")
        .attr("r", 5)
        .attr("fill", 'maroon');

nodeReuse.append("title")
        .text(function(d) { return d.id; });

simulationReuse
        .nodes(forceReuseGraph.nodes)
        .stop();

simulationReuse.force("link")
        .links(forceReuseGraph.links);

dispatch.on('tickend', function () {
      drawGraph();
      updateChart();
    });

// Compute 300 ticks of each layout.
    var i = 0;
    var stepper = d3.timer(function () {
      var prevTime = i > 0 ? computeTimes[0].values[i-1].time : 0;
      var startTime = new Date();
      simulation.tick();
      var totalTime = new Date() - startTime;
      computeTimes[0].values.push({i: i, time: totalTime + prevTime});

prevTime = i > 0 ? computeTimes[1].values[i-1].time : 0;
      startTime = new Date();
      simulationReuse.tick();
      var totalTime = new Date() - startTime;
      computeTimes[1].values.push({i: i, time: totalTime + prevTime});

dispatch.call('tickend', simulation);

++i;
      if (i >= 300) {
        stepper.stop();
      }
    });

function updateChart () {
      var forceTime = computeTimes[0].values[computeTimes[0].values.length - 1].time;
      var forceReuseTime = computeTimes[1].values[computeTimes[1].values.length - 1].time;
      var percentTime = Math.round(100 * forceReuseTime / forceTime);
      runtime.text(forceTime +  ' ms');
      runtimeReuse.text(forceReuseTime +  ' ms (' + percentTime + '%)');

x.domain([0, computeTimes[0].values.length]);
      y.domain([0, d3.max(computeTimes, function (d) { return d3.max(d.values.map(function(v) { return v.time; })); })]);

chartSvg.selectAll('g').remove();

chartSvg.append('g')
          .attr('transform', 'translate(0,' + chartHeight + ')')
          .call(d3.axisBottom(x))
        .append("text")
          .attr("fill", "#000")
          .attr('transform', 'translate(' + 32 + ',' + 0 + ')')
          .attr("y", 19)
          .attr("dy", "0.71em")
          .attr("text-anchor", "begin")
          .text("Iteration");

chartSvg.append('g')
          .call(d3.axisLeft(y))
        .append("text")
          .attr("fill", "#000")
          .attr("transform", "rotate(-90)")
          .attr("y", 6)
          .attr("dy", "0.71em")
          .attr("text-anchor", "end")
          .text("Compute time (ms)");

var lineG = chartSvg.selectAll('g.line-g')
          .data(computeTimes)
        .enter().append('g')
          .attr('class', 'line-g');

lineG.append('path')
          .attr("fill", "none")
          .attr("stroke", function (d) { return d.name === 'd3-force' ? 'steelblue' : 'maroon'; })
          .attr("stroke-linejoin", "round")
          .attr("stroke-linecap", "round")
          .attr("stroke-width", 1.5)
          .attr("d", function (d) { return line(d.values); });

lineG.append("text")
          .datum(function(d) { return {name: d.name, value: d.values[d.values.length - 1]}; })
          .attr("transform", function(d) { return "translate(" + x(d.value.i) + "," + y(d.value.time) + ")"; })
          .attr("x", 3)
          .attr('y', -6)
          .attr("dy", "0.35em")
          .attr('text-anchor', 'end')
          .style("font", "10px sans-serif")
          .text(function(d) { return d.name; });
    }

node
          .attr("cx", function(d) { return d.x; })
          .attr("cy", function(d) { return d.y; });

linkReuse
          .attr("x1", function(d) { return d.source.x; })
          .attr("y1", function(d) { return d.source.y; })
          .attr("x2", function(d) { return d.target.x; })
          .attr("y2", function(d) { return d.target.y; });

nodeReuse
          .attr("cx", function(d) { return d.x; })
          .attr("cy", function(d) { return d.y; });
    }
  });
});

</script>

https://d3js.org/d3.v4.min.js