24

我正在 JavaScript 的asm.js子集中编写优先级队列和八叉树,以便从它们中挤出最后可能的性能。

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

现在,我在堆中的结构必须具有它们所引用的 Javascript 对象的整数 ID,并且我需要一个经典的 Javascript 对象来充当这些整数和 Javascript 对象之间的字典。

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

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

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

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

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

4

4 回答 4

15

在多次阅读 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构造函数变得更加复杂。除了vvertices我们还有两个新的公共属性doubleArraygraph,它们分别用于公开来自 asm.js 模块的数据结构和数据操作。

vertices属性是特别的,现在实现为对象而不是数组,它使用 getter 来公开 asm.js 数据结构。这就是我们在 JavaScript 中引用 asm.js 数据结构的方式。

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

结论: 由于我已经回答了您的问题并演示了如何将 asm.js 数据结构导入 JavaScript,因此我认为这个答案是完整的。尽管如此,我还是想留下一个工作演示作为概念证明。然而,这个答案已经变得太大了。我会写一篇关于这个主题的博客文章,并尽快在此处发布指向它的链接。

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

于 2013-07-20T06:45:14.273 回答
9

当我阅读 http://asmjs.org/spec/latest/ 上的 asm.js 规范和http://asmjs.org/faq.html的常见问题解答时,简短的回答是您不能存储 JS 对象引用在 asmjs 堆中。引用常见问题解答:

问:asm.js 能否用作托管语言(如 JVM 或 CLR)的 VM?

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

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

于 2013-07-14T17:13:37.193 回答
4

这感觉不对。将 int 转换为字符串以在 Javascript 世界中进行查找的想法是错误的。在 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 开始并且没有孔。否则,它可以实现为字典而不是快速平面列表。

于 2013-10-12T21:51:16.693 回答
0

可能我还没有完全理解你的问题,但是可以使用 C++ 标准库中的优先级队列,然后用 emscripten 编译它来创建一个 asm.js javascript 模块。

例如下面的代码:

#include <queue>
#include <iostream>

class MyClass {
    private:
        int priority;
        int someData;
    public:
        MyClass():priority(0), someData(0){}
        MyClass(int priority, int data):priority(priority), someData(data){}
        int getPriority() const { return this->priority;}
        int getData() const { return this->someData;}
        void setData(int data){ this->someData = data;}
        inline bool operator<(const MyClass & other) const{
            return this->getPriority() < other.getPriority();
        }
};

int main(){

    std::priority_queue<MyClass> q;
    q.push(MyClass(50, 500));
    q.push(MyClass(25, 250));
    q.push(MyClass(75, 750));
    q.push(MyClass(10, 100));

    std::cout << "Popping elements: " << std::endl;
    while(!q.empty()){
        std::cout << q.top().getData() << std::endl;
        q.pop();
    }
    std::cout << "Queue empty" << std::endl;

    return 0;
};

编译如下:

emcc queue.cpp -s ASM_JS=1 -O2 -o queue.js

然后可以使用 nodejs 执行,产生以下输出:

$ nodejs queue.js 
Popping elements: 
750
500
250
100
Queue empty

也可以编译它以创建一个 html 文件并将其加载到浏览器中,例如:

$ emcc queue.cpp -s ASM_JS=1 -O2 -o queue.html

不知道这是否适合您,但是手动编写 asmjs 代码非常复杂。

于 2013-07-12T21:39:36.657 回答