手写asm.js - 如何跟踪堆中的javascript对象？

Question

我在Javascript 的asm.js子集中编写优先级队列和八叉树,以便从中榨取最后可能的性能.

但是,如何在asm.js函数的heap缓冲区中存储对Javascript对象的引用？

现在,我在堆中的结构必须有一个他们引用的Javascript对象的整数ID,我需要一个经典的Javascript对象作为这些int和Javascript对象之间的字典.

例如,我有一个asm.js八叉树,它公开了一个add函数,就像add(x1,y1,z1,x2,y2,z2,object_id)where object_id是整数一样.该find(x1,y1,z1,x2,y2,z2)函数返回一个包含在边界内的所有object_id的列表.这意味着我必须在Javascript中维护object_id的对象字典,以便我可以确定该框中的实际对象; object_ids到对象的映射.

这感觉不对.将int转换为字符串以在Javascript世界中进行查找的想法是错误的.在asm.js中编写内部循环数据结构的一个关键点是避免创建垃圾.

(我的目标是Chrome和Firefox一样;我希望asm.js严格的代码在两者上运行得更快.是的,我将进行分析.)

无论你有多少属性可以实现到asm.js堆 - 例如对象的位置和维度 - 你通常也需要将一些Javascript对象与项目关联起来; 字符串和webGL对象以及DOM对象等.

有没有更好的方法让asm.js堆包含指向Javascript对象的指针？如果使用整数ID映射,例如,使用数组或对象作为字典是否更好？

Answer 1

在多次阅读asm.js规范并在Firefox中进行实验后,我同意bks:

asm.js程序只能通过数字句柄与外部数据间接交互

然而,这并不构成重大问题.由于asm.js是JavaScript的子集,因此您无法在asm.js中使用大量JavaScript构造,包括:

1. JavaScript对象
2. 动态数组
3. 高阶函数

尽管如此,asm.js确实提供了一种使用外部函数接口(FFI)调用JavaScript函数的方法.这是一个非常强大的机制,因为它允许您从asm.js回调JavaScript(允许您创建部分用asm.js编写并部分用JavaScript编写的过程).

它区分你的代码的部分是很重要的可以被转换成asm.js并会使用asm.js.受益 例如,asm.js非常适合图形处理,因为它需要大量的计算.但是它不适合字符串操作.简单的JavaScript会更好地用于此目的.

回到主题,您面临的问题是您需要从asm.js代码中引用JavaScript对象.由于唯一的方法是使用数字句柄(你不想要),我看到的只有一个其他解决方案:

而不是从asm.js中引用JavaScript对象,而是从JavaScript中引用asm.js结构.

这种方法更好的原因有很多:

1. 由于JavaScript是asm.js的超集,因此您已经可以在JavaScript中使用asm.js结构.
2. 由于JavaScript比asm.js更强大,因此asm.js结构的行为更像JavaScript对象.
3. 通过将asm.js结构导入JavaScript,您的asm.js代码变得更简单,更具凝聚力并且不那么紧密耦合.

谈论足够,让我们看一个例子.我们来看看Dijkstra的最短路径算法.幸运的是我已经有了一个工作演示(我必须为大学任务实现Dijkstra的算法):

http://jsfiddle.net/3fsMn/

链接到上面的代码完全用普通的旧JavaScript实现.让我们将这段代码的一些部分转换为asm.js(请记住,数据结构将在asm.js中实现,然后导出到JavaScript).

从具体的东西开始,这就是我在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);

我们希望保持相同的界面.因此,首先要修改的是Graph构造函数.这是它目前的实现方式:

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;
}

我不打算深入解释所有代码,但需要一般性的理解:

1. 首先要注意的是假设我正在创建一个由4个顶点组成的图形,然后我只创建一个包含3个顶点的数组.最后一个顶点不是必需的.
2. 接下来,对于每个顶点,我在两个顶点之间创建一个新数组(表示边).对于具有4个顶点的图形:
   1. 第一个顶点有3条边.
   2. 第二个顶点有2个新边.
   3. 第三个顶点有1个新边.
   4. 第四个顶点有0个新边(这就是我们只需要3个顶点数组的原因).

通常,n顶点图具有n * (n - 1) / 2边.所以我们可以用表格格式表示图形如下(下表是上面演示中的图表):

+-----+-----+-----+-----+-----+-----+
|     |  f  |  e  |  d  |  c  |  b  |
+-----+-----+-----+-----+-----+-----+
|  a  |     |     |  14 |  9  |  7  |
+-----+-----+-----+-----+-----+-----+
|  b  |     |  15 |     |  10 |
+-----+-----+-----+-----+-----+
|  c  |     |  11 |  2  |
+-----+-----+-----+-----+
|  d  |  9  |     |
+-----+-----+-----+
|  e  |  6  |
+-----+-----+

这是我们需要在asm.js模块中实现的数据结构.现在我们知道了它的样子让我们开始实现它:

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));

正如您所看到的,我们的Graph构造函数变得更加复杂.除了v和vertices我们有两个新的公共属性,doubleArray并且graph,这些都要求分别暴露在asm.js模块的数据结构和数据操作.

的vertices属性是特别现在实现为对象,而不是一个数组,它使用的吸气剂,以暴露asm.js数据结构.这是我们从JavaScript中引用asm.js数据结构的方式.

堆只是一个ArrayBuffer,它可以通过asm.js代码或普通的旧JavaScript来操作.这允许您在asm.js代码和JavaScript之间共享数据结构.在JavaScript方面,您可以将此数据结构包装在一个对象中,并使用getter和setter来动态更新堆.我认为这比使用数字句柄更好.

结论: 既然我已经回答了你的问题,并演示了如何将asm.js数据结构导入JavaScript,我会得出结论,这个答案是完整的.不过,我想留下一个工作演示作为概念证明.然而,这个答案已经变得太大了.我会写一篇关于这个主题的博客文章,并尽快在这里发布一个链接.

JSFiddle for Dijkstra在asm.js中实现的最短算法路径算法即将推出.

Answer 2

当我读asm.js符合规范的http://asmjs.org/spec/latest/并在FAQ http://asmjs.org/faq.html,简单的答案是,你不能存储JS对象引用在asmjs堆中.引用常见问题解答:

问:asm.js可以作为托管语言的VM,比如JVM还是CLR？

A.现在,asm.js无法直接访问垃圾收集数据; asm.js程序只能通过数字句柄与外部数据间接交互.在未来的版本中,我们打算基于ES6结构化二进制数据API引入垃圾收集和结构化数据,这将使asm.js成为托管语言的更好目标.

因此,只要您关心对象实例而不仅仅是内容,您当前存储外部id-to-object映射的方法似乎是解决问题的当前推荐方法.否则,我认为您的想法是取消实现存储对象:将每个对象的完整内容存储在优先级队列中的插槽中,并仅在获取时将其转换回真正的JS对象.但这只适用于您的对象可以安全地按需重新创建的情况.