1. Staged Compilation
First you must understand that JavaScript compilers do not simply compile a program once, the way classical compilers do. Instead, code is compiled and recompiled as needed, while the program is running.
With most languages, compiling a big program takes a while. That is usually acceptable because programs are compiled ahead of time and distributed in compiled form.
For JavaScript the situation is different. A website might include a large amount of code that is retrieved in text form and must be compiled every time the website is opened. If that took five minutes, the user wouldn’t be happy. A JavaScript compiler must be able to start running a program—even a big program—almost instantaneously.
To do this, JavaScript compilers have multiple compilation strategies. When a website is opened, the scripts are first compiled in a cheap, superficial way. This doesn’t result in very fast execution, but it allows the script to start quickly. Functions may not be compiled at all until the first time they are called.
In a typical program, most code is run only a handful of times (or not at all). For these parts of the program, the cheap compilation strategy is sufficient—they won’t take much time anyway. But functions that are called often or that contain loops that do a lot of work have to be treated differently. While running the program, the JavaScript engine observes how often each piece of code runs. When it looks like some code might consume a serious amount of time (this is often called hot code), it is recompiled with a more advanced but slower compiler. This compiler performs more optimizations to produce faster code. There may even be more than two compilation strategies, with ever more expensive optimizations being applied to very hot code.
Interleaving running and compiling code means that by the time the clever compiler starts working with a piece of code, it has already been run multiple times. This makes it possible to observe the running code and gather information about it. Later in the chapter we’ll see how that can allow the compiler to create more efficient code.
2. Graph Layout
Our example problem for this chapter concerns itself with graphs again. Pictures of graphs can be useful to describe road systems, networks, the way control flows through a computer program, and so on. The following picture shows a graph representing some countries in the Middle East, with edges between those that share land borders:
Deriving a picture like this from the definition of a graph is called graph layout. It involves assigning a place to each node in such a way that connected nodes are near each other, yet the nodes don’t crowd into each other. A random layout of the same graph is a lot harder to interpret.
Finding a nice-looking layout for a given graph is a notoriously difficult problem. There is no known solution that reliably does this for arbitrary graphs, and large, densely connected graphs are especially hard. But for some specific types of graphs, for example, planar ones (which can be drawn without edges crossing each other), effective approaches exist.
To lay out a small graph (say, up to 200 nodes) that isn’t too tangled, we can apply an approach called force-directed graph layout. This runs a simplified physics simulation on the nodes of the graph, treating edges as if they are springs and having the nodes themselves repel each other as if electrically charged.
In this chapter we’ll implement a force-directed graph layout system and observe its performance. We can run such a simulation by repeatedly computing the forces that act on each node and moving the nodes around in response to those forces. Performance of such a program is important since it might take a lot of iterations to reach a good-looking layout and each iteration computes a lot of forces.
3. Defining a Graph
We can represent a graph layout as an array of GraphNode objects, each of which carries its current position and an array of the nodes to which it has edges. We randomize their starting positions.
class GraphNode { constructor() {
this.pos = new Vec(Math.random() * 1000, Math.random() * 1000);
this.edges = [];
}
connect(other) { this.edges.push(other); other.edges.push(this);
}
hasEdge(other) {
return this.edges.includes(other);
}
}
This uses the familiar Vec class from previous chapters to represent positions and forces.
The connect method is used to connect a node to another node when building up a graph. To find out whether two nodes are connected, we’ll call the hasEdge method.
To build up graphs to test our programs, we’ll use a function called treeGraph. It takes two parameters that specify the depth of the tree and the number of branches to create at each split, and it recursively constructs a tree-shaped graph with the specified shape.
function treeGraph(depth, branches) {
let graph = [new GraphNode()];
if (depth > 1) {
for (let i = 0; i < branches; i++) {
let subGraph = treeGraph(depth – 1, branches);
graph[0].connect(subGraph[0]);
graph = graph.concat(subGraph);
}
}
return graph;
}
Tree-shaped graphs don’t contain cycles, which makes them relatively easy to lay out and allows even the unsophisticated program we build in this chapter to produce good-looking shapes.
The graph created by treeGraph(3, 5) would be a tree of depth 3, with five branches.
To allow us to inspect the layouts produced by our code, I’ve defined a drawGraph function that draws the graph onto a canvas. This function is defined in the code at eloquentjavascript.net/code/draw_layout.js and is available in the online sandbox.
4. Force-Directed Layout
We’ll move nodes one at a time, computing the forces that act on the current node and immediately moving that node in the direction of the sum of these forces.
The force that an (idealized) spring applies can be approximated with Hooke’s law, which says that this force is proportional to the difference between the spring’s resting length and its current length. The binding springLength defines the resting length of our edge springs. The rigidity of the springs is defined by springStrength, which we’ll multiply by the length difference to determine the resulting force.
const springLength = 40;
const springStrength = 0.1;
To model the repulsion between nodes, we use another physical formula—Coulomb’s law—which says that the repulsion between two electrically charged particles is inversely proportional to the square of the distance between them. When two nodes are almost on top of each other, the squared distance is tiny, and the resulting force is gigantic. As the nodes move further apart, the squared distance grows rapidly so that the repelling force quickly weakens.
We’ll again multiply by an experimentally determined constant, repulsionStrength, which controls the strength with which nodes repel each other.
const repulsionStrength = 1500;
The force that acts on a given node is computed by looping over all other nodes and applying the repelling force for each of them. When another node shares an edge with the current node, the force caused by the spring is also applied.
Both of these forces depend on the distance between the two nodes.
For each pair of nodes, our function will compute a vector named apart that represents the path from the current node to the other node. The function then takes the length of the vector to find the actual distance. When the distance is less than one, we set it to one to prevent dividing by zero or by very small numbers because that will produce NaN values or forces so gigantic they catapult the node into outer space.
Using this distance, we can compute the magnitude of the force that acts between these two given nodes. To go from a magnitude to a force vector, we must multiply the magnitude by a normalized version of the apart vector. Normalizing a vector means creating a vector with the same direction but with a length of one. We can do that by dividing the vector by its own length.
function forceDirected_simple(graph) {
for (let node of graph) {
for (let other of graph) {
if (other == node) continue;
let apart = other.pos.minus(node.pos);
let distance = Math.max(1, apart.length);
let forceSize = -repulsionStrength / (distance * distance);
if (node.hasEdge(other)) {
forceSize += (distance – springLength) * springStrength;
}
let normalized = apart.times(1 / distance);
node.pos = node.pos.plus(normalized.times(forceSize));
}
}
}
We will use the following function to test a given implementation of our graph layout system. It runs the model for 4,000 steps and tracks the time this takes. To give us something to look at while the code runs, it draws the current layout of the graph after every 100 steps.
function runLayout(implementation, graph) {
function run(steps, time) {
let startTime = Date.now();
for (let i = 0; i < 100; i++) {
implementation(graph);
}
time += Date.now() – startTime; drawGraph(graph);
if (steps == 0) console.log(time);
else requestAnimationFrame(() => run(steps – 100, time));
run(4000, 0);
}
We could now run this first implementation and see how much time it takes.
<script>
runLayout(forceDirected_simple, treeGraph(4, 4));
</script>
On my machine, using version 58 of the Firefox browser, those 4,000 iterations took a little more than two seconds, so that’s two iterations per millisecond. That’s a lot. Let’s see whether we can do better.
Source: Haverbeke Marijn (2018), Eloquent JavaScript: A Modern Introduction to Programming, No Starch Press; 3rd edition.