After reading the asm.js specs several times over and experimenting with it in Firefox I agree with bks:
an asm.js program can only interact indirectly with external data via numeric handles
However this doesn't pose a major problem. Since asm.js is a subset of JavaScript you will not be able to use a lot of JavaScript constructs in asm.js, including:
- JavaScript Objects
- Dynamic Arrays
- Higher Order Functions
Nevertheless, asm.js does provide a way to call JavaScript functions using the Foreign Function Interface (FFI). This is a very powerful mechanism as it allows you to callback JavaScript from asm.js (allowing you to create procedures partially written in asm.js and partially written in JavaScript).
It's important to distinguish which parts of your code can be converted to asm.js and will benefit from using asm.js. For example asm.js is great for graphics processing since its requires a lot of calculations. However it's not suitable for string manipulation. Plain JavaScript would be better for that purpose.
Getting back to the topic, the problem you're facing is that you need to reference JavaScript objects from within asm.js code. Since the only way to do this is to use numeric handles (which you don't want), there's only one other solution I see:
Instead of referencing JavaScript objects from within asm.js, reference asm.js structures from within JavaScript.
There are many reasons why this method is better:
- Since JavaScript is a superset of asm.js you can already use asm.js structures in JavaScript as is.
- Since JavaScript is more powerful than asm.js it's easier to make asm.js structures behave like JavaScript objects.
- By importing asm.js structures into JavaScript your asm.js code becomes simpler, more cohesive and less tightly coupled.
Enough of talk, let's see an example. Let's take Dijkstra's shortest path algorithm. Luckily I already have a working demo (I had to implement Dijkstra's algorithm for a college assignment):
http://jsfiddle.net/3fsMn/
The code linked to above is fully implemented in plain old JavaScript. Let's take some parts of this code and convert it to asm.js (keeping in mind that the data structures will be implemented in asm.js and then exported to JavaScript).
To start with something concrete, this is the way I'm creating a graph in JavaScript:
var graph = new Graph(6)
.addEdge(0, 1, 7)
.addEdge(0, 2, 9)
.addEdge(0, 3, 14)
.addEdge(1, 2, 10)
.addEdge(1, 4, 15)
.addEdge(2, 3, 2)
.addEdge(2, 4, 11)
.addEdge(3, 5, 9)
.addEdge(4, 5, 6);
We want to keep the same interface. Hence the first thing to modify is the Graph
constructor. This is how it's currently implemented:
function Graph(v) {
this.v = --v;
var vertices = new Array(v);
for (var i = 0, e; e = v - i; i++) {
var edges = new Array(e);
for (var j = 0; j < e; j++)
edges[j] = Infinity;
vertices[i] = edges;
}
this.vertices = vertices;
}
I won't bother explaining all the code in depth, but a general understanding is required:
- The first thing to note is that suppose I'm creating a graph consisting of 4 vertices, then I only create an array of 3 vertices. The last vertex is not required.
- Next, for each vertex I create a new array (representing the edges) between two vertices. For a graph with 4 vertices:
- The first vertex has 3 edges.
- The second vertex has 2 new edges.
- The third vertex has 1 new edge.
- The fourth vertex has 0 new edges (which is the reason we only need an array of 3 vertices).
In general a graph of n
vertices has n * (n - 1) / 2
edges. So we can represent the graph in a tabular format as follows (the table below is for the graph in the demo above):
+-----+-----+-----+-----+-----+-----+
| | f | e | d | c | b |
+-----+-----+-----+-----+-----+-----+
| a | | | 14 | 9 | 7 |
+-----+-----+-----+-----+-----+-----+
| b | | 15 | | 10 |
+-----+-----+-----+-----+-----+
| c | | 11 | 2 |
+-----+-----+-----+-----+
| d | 9 | |
+-----+-----+-----+
| e | 6 |
+-----+-----+
This is the data structure we need to implement in the asm.js module. Now that we know what it looks like let's get down to implementing it:
var Graph = (function (constant) {
function Graph(stdlib, foreign, heap) { /* asm.js module implementation */ }
return function (v) {
this.v = --v;
var heap = new ArrayBuffer(4096);
var doubleArray = this.doubleArray = new Float62Array(heap);
var graph = this.graph = Graph(window, {}, heap);
graph.init(v);
var vertices = { length: v };
for (var i = 0, index = 0, e; e = v - i; i++) {
var edges = { length: e };
for (var j = 0; j < e; j++) Object.defineProperty(edges, j, {
get: element(index++)
});
Object.defineProperty(vertices, i, {
get: constant(edges)
});
}
this.vertices = vertices;
function element(i) {
return function () {
return doubleArray[i];
};
}
};
}(constant));
As you can see our Graph
constructor has become a lot more complicated. In addition to v
and vertices
we have two new public properties, doubleArray
and graph
, which are required to expose the data structure and the data operations from the asm.js module respectively.
The vertices
property is particular is now implemented as an object instead of an array, and it uses getters to expose the asm.js data structure. This is how we reference asm.js data structures from within JavaScript.
The heap is simply an ArrayBuffer
and it can be operated on by either asm.js code or plain old JavaScript. This allows you to share data structures between asm.js code and JavaScript. On the JavaScript side you can wrap up this data structure in an object and use getters and setters to dynamically update the heap. In my humble opinion this is better than using numeric handles.
Conclusion: Since I've already answered your question and demonstrated how to import asm.js data structures into JavaScript I would conclude that this answer is complete. Nevertheless I would like to leave behind a working demo as a proof of concept. However this answer is already getting too big. I'll write a blog post on this topic and post a link to it here as soon as possible.
JSFiddle for Dijkstra's shortest algorithm path algorithm implemented in asm.js coming up soon.