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

Question

我在Javascript的asm.js子集中编写优先级队列和octree，以便从它们中挤出最后可能的性能。

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

现在，堆中的结构必须有它们所引用的Javascript对象的整数ID，并且我需要一个经典的Javascript对象作为这些in和Javascript对象之间的dict。

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

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

(我对Chrome的关注和火狐一样多；我希望asm.js严格的代码能在这两种浏览器上运行得更快。是的，我会分析一下。)

无论您可以在asm.js堆中实现多少属性(例如，一个对象的位置和尺寸)，您通常也需要将一些Javascript对象与该项相关联；字符串、webGL对象和DOM对象等等。

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

Answer 1

当我在asm.js上阅读http://asmjs.org/spec/latest/规范和在http://asmjs.org/faq.html上阅读FAQ时，简单的回答是，您不能将JS对象引用存储在asmjs堆中。引用FAQ的话：

问: asm.js是否可以作为托管语言的VM，如JVM或CLR？ 答:现在，asm.js无法直接访问垃圾收集的数据；asm.js程序只能通过数字句柄间接地与外部数据交互。在未来的版本中，我们打算引入基于ES6结构化二进制数据API的垃圾收集和结构化数据，这将使asm.js成为托管语言更好的目标。

因此，您当前存储外部id-对象映射的方法似乎是解决问题的当前推荐方法，只要您关心对象实例，而不仅仅是它们的内容。否则，我认为您的想法是对存储的对象进行非物质化:将每个对象的完整内容存储在优先级队列中的时隙中，并仅在获取对象时才将其转换回真正的JS对象。但是，只有当您的对象安全地按需重新创建时，这才有效。

Answer 2

在多次阅读asm.js规范并在火狐中进行实验之后，我同意bks的观点：

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

然而，这并不构成重大问题。由于asm.js是JavaScript的一个子集，所以您将无法在asm.js中使用大量的JavaScript构造，包括：

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

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

区分代码的哪些部分(可以将转换为asm.js )非常重要，而将从使用asm.js中获益。例如，asm.js非常适合图形处理，因为它需要大量的计算。但是，它不适用于字符串操作。为此目的，普通的JavaScript会更好。

回到主题，您面临的问题是您需要在JavaScript代码中引用asm.js对象。因为这样做的唯一方法是使用数字句柄(您不想要)，所以我只看到了另一个解决方案：

，而不是在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's shortest path algorithm为例。幸运的是，我已经有了一个工作演示(我必须为大学作业实现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. 第一顶点有三个边。
   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属性现在被实现为对象而不是数组，它使用getter公开asm.js数据结构。这是我们如何从JavaScript.内部引用asm.js数据结构的方法。

堆只是一个ArrayBuffer，可以通过asm.js代码或普通的旧JavaScript对其进行操作。这允许您在asm.js代码和JavaScript之间共享数据结构。在JavaScript方面，您可以将此数据结构封装在对象中，并使用getter和setter动态更新堆。在我看来，这比使用数字手柄要好。

结论:既然我已经回答了您的问题并演示了如何将asm.js数据结构导入JavaScript，那么我将得出这样的结论:这个答案已经完成。尽管如此，我想留下一个工作演示作为概念的证明。然而，这个答案已经变得太大了。我会写一篇关于这个话题的博客文章，并尽快在这里发布一个链接。

Dijkstra的最短路径算法JSFiddle即将在asm.js上实现。

Answer 3

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

这里不需要将int转换为字符串。您应该有一个JS数组，该数组将索引映射到JS对象，然后应该在JS引擎中优化用整数索引它，以便直接使用该整数。它们将知道什么时候查找表是数组，什么时候流入的值是整数。

这就是emscripten (在asm.js输出模式和非asm.js输出模式下)处理函数指针之类的事情的方式。您有一个整数ID，并且有一个JS数组将这些ID映射到相关对象。例如,

var FUNCTION_TABLE = [function zero() {}, function one() {}];

后来调用了

FUNCTION_TABLE[i]();

保持数组的适当优化是很重要的，这基本上意味着它的值从0开始，而不是有洞。否则，可以将其实现为字典而不是快速平面列表。