Handwriting asm.js - как вы можете отслеживать объекты javascript в куче?

Ответ 1

Когда я прочитал спецификацию asm.js в http://asmjs.org/spec/latest/ и FAQ на http://asmjs.org/faq.html, короткий ответ заключается в том, что вы не можете хранить ссылки объектов JS в куче asmjs. Цитата из FAQ:

Q. Может ли asm.js служить в качестве виртуальной машины для управляемых языков, таких как JVM или CLR?

а. В настоящее время asm.js не имеет прямого доступа к собранным мусором данным; программа asm.js может косвенно косвенно взаимодействовать с внешними данными с помощью цифровых ручек. В будущих версиях мы намерены внедрить сбор мусора и структурированные данные на основе API структурированных двоичных данных ES6, что сделает asm.js еще лучшей целью для управляемых языков.

Таким образом, ваш текущий метод хранения внешней карты "от объекта к объекту", по-видимому, является рекомендуемым способом решения вашей проблемы до тех пор, пока вы заботитесь о экземплярах объекта, а не только о их содержимом. В противном случае, я думаю, идея состоит в том, что вы дематериализуете хранимые объекты: сохраняете полное содержимое каждого объекта в своем слоте в очереди приоритетов и возвращаете его обратно в истинный объект JS только тогда, когда он извлекается. Но это работает только в том случае, если ваши объекты безопасны для воссоздания по требованию.

Ответ 2

После прочтения спецификаций asm.js несколько раз и экспериментирования с ним в Firefox, я согласен с bks:

программа asm.js может косвенно взаимодействовать только с внешними данными с помощью цифровых ручек

Однако это не представляет серьезной проблемы. Поскольку asm.js является подмножеством JavaScript, вы не сможете использовать много JavaScript-конструкций в asm.js, включая:

• Объекты JavaScript
• Динамические массивы
• Функции более высокого порядка

Тем не менее, asm.js предоставляет способ вызова функций JavaScript с использованием интерфейса внешних функций (FFI). Это очень мощный механизм, поскольку он позволяет вам отменить JavaScript из asm.js(позволяя вам создавать процедуры, частично написанные в asm.js и частично написанные на JavaScript).

Важно различать, какие части вашего кода можно преобразовать в asm.js и будет извлечь выгоду из использования asm.js. Например, asm.js отлично подходит для обработки графики, поскольку для этого требуется множество вычислений. Однако это не подходит для струнных манипуляций. Для этой цели было бы лучше использовать обычный JavaScript.

Возвращаясь к теме, проблема, с которой вы сталкиваетесь, заключается в том, что вам нужно ссылаться на объекты JavaScript из кода asm.js. Поскольку единственный способ сделать это - использовать числовые дескрипторы (которые вам не нужны), есть только одно другое решение, которое я вижу:

Вместо ссылок на объекты JavaScript изнутри asm.js ссылайтесь на структуры asm.js из JavaScript.

Есть много причин, почему этот метод лучше:

• Так как JavaScript является надмножеством asm.js, вы уже можете использовать структуры asm.js в JavaScript как есть.
• Так как JavaScript более мощный, чем asm.js, проще сделать структуры asm.js похожими на объекты JavaScript.
• Импортируя структуры asm.js в JavaScript, ваш код asm.js становится более простым, более сплоченным и менее тесно связанным.

Достаточно говорить, давайте посмотрим пример. Возьмем алгоритм кратчайшего пути 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;
}

Я не буду подробно объяснять весь код, но требуется общее понимание:

• Первое, что нужно отметить, это предположить, что я создаю граф, состоящий из 4 вершин, тогда я создаю только массив из трех вершин. Последняя вершина не требуется.
• Далее, для каждой вершины я создаю новый массив (представляющий ребра) между двумя вершинами. Для графа с 4 вершинами:
  • Первая вершина имеет 3 ребра.
  • Вторая вершина имеет 2 новые ребра.
  • Третья вершина имеет 1 новый край.
  • Четвертая вершина имеет 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. Так мы ссылаемся на структуры данных asm.js из JavaScript.

Куча - это просто ArrayBuffer, и ее можно использовать либо как код asm.js, либо простой старый JavaScript. Это позволяет обмениваться структурами данных между кодом asm.js и JavaScript. На стороне JavaScript вы можете обернуть эту структуру данных в объекте и использовать геттеры и сеттеры для динамического обновления кучи. По моему скромному мнению, это лучше, чем использование числовых ручек.

Заключение:. Поскольку я уже ответил на ваш вопрос и продемонстрировал, как импортировать структуры данных asm.js в JavaScript, я бы сделал вывод, что этот ответ завершен. Тем не менее я хотел бы оставить рабочую демонстрацию в качестве доказательства концепции. Однако этот ответ уже становится слишком большим. Я напишу сообщение в блоге по этой теме и опубликую ссылку на него здесь как можно скорее.

JSFiddle для кратчайшего алгоритма алгоритма Dijkstra, реализованного в asm.js, скоро появится.

Ответ 3

Это кажется неправильным. Идея приведения int к строке для поиска в мире Javascript просто неверна. Одним из ключевых моментов написания внутрисетевых данных-структур в asm.js является предотвращение создания мусора.

Нет необходимости вводить int в строку здесь. У вас должен быть JS-массив, который сопоставляет индексы JS-объектам, а затем индексировать его с помощью целого числа, чтобы оптимизировать в JS-машинах прямое использование этого целого. Они будут знать, когда таблица поиска является массивом, а когда текущие значения являются целыми числами.

Вот как emscripten (в режиме вывода asm.js и в режиме вывода non-asm.js) обрабатывает такие вещи, как указатели на функции. У вас есть целочисленный идентификатор, и массив JS сопоставляет эти идентификаторы соответствующим объектам. Например,

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

позже вызванный с помощью

FUNCTION_TABLE[i]();

Важно, чтобы массив правильно оптимизировался, что в основном означает начало его значений в 0 и отсутствие отверстий. В противном случае он может быть реализован как словарь вместо быстрого плоского списка.

Ответ 4

Возможно, я не совсем понял ваш вопрос, но может быть возможно использовать очередь приоритетов из стандартной библиотеки С++, а затем скомпилировать ее с помощью emscripten для создания javascript-модуля asm.js.

Например, следующий код:

#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 вручную довольно сложно.