Как эффективно использовать типизированный массив с использованием общего буфера в JavaScript?

Question

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

После экспериментов и бенчмаркинга трехмерный массив оказался самым быстрым способом его реализации при использовании нетипизированных массивов:

var PixelCollection = function() {
    this.pixels = [];
};

PixelCollection.prototype = {
    add: function(x, y) {
        var pixels = this.pixels;
        if (pixels[y]) {
            pixels[y].push(x);
        } else {
            pixels[y] = [x];
        }
    },
    each: function(callback) {
        var pixels = this.pixels;
        for (var y = 0, m = pixels.length; y < m; y++) {
            var row = pixels[y];
            if (row) {
                for (var i = 0, mm = row.length; i < mm; i++) {
                    callback(row[i], y);
                }
            }
        }
    }
};

В некоторых ситуациях объект не достаточно быстрый, поэтому я попытался Uint8Array реализация, используя 2D массив:

var WIDTH = 255;
var HEIGHT = 160;

PixelCollection = function() {
    this.pixels = new Uint8Array(WIDTH * HEIGHT);
};

PixelCollection.prototype = {
    add: function(x, y) {
        this.pixels[WIDTH * y + x] = 1;
    },
    each: function(callback) {
        var pixels = this.pixels;
        for (var i = 0, m = pixels.length; i < m; i++) {
            if (pixels[i]) {
                callback(i % WIDTH, Math.floor(i / WIDTH));
            }
        }
    }
}

Это медленнее. Я думал, что это будет быстрее, потому что писать - и читать из Uint8arrays быстрее, но, поскольку я создаю огромный объект для каждого объекта PixelCollection, получение пикселей происходит намного медленнее, поскольку для итерации всех пикселей требуется больше времени. (Примечание: я также попробовал реализацию выше с нетипизированным массивом: это намного медленнее)

В PixelCollection обычно не установлены все пиксели. Однако ограничивающая рамка может охватывать весь холст, поэтому мне нужно создать массив с использованием такого большого буфера.

Хотя может быть способ обойти это. Я могу создать один большой общий буфер и использовать байтовое смещение для каждой коллекции PixelCollection. Так что когда PixelCollection P1 будет занимать 100 байт, а затем PixelCollection P2 будет начинаться со смещения байта 100. Это использует память более эффективно, но мне нужно будет отслеживать диапазон байтов, который использует каждый PixelCollection (это то, что C называет "указателями"?).

Раздражающая часть: когда P1Ограничительная коробка расширяется, мне нужно сместить P2 освободить место для P1, И мне нужно было бы установить безопасный размер буфера для общего буфера, поэтому мне нужно сделать безопасное предположение о том, сколько памяти ему нужно.

Реализация этого возможна, но это потребует много времени, проб и ошибок.

Итак, прежде чем начать это: кажется ли это хорошим способом сделать это? Есть ли лучшие или более простые способы сделать это? Вы знаете какие-нибудь примеры реализации, из которых я мог бы поучиться?

Изменить: я добавил jsperf на случай, если вы хотите попробовать свои силы в оптимизации.
Пожалуйста, добавьте к этому jsperf, если у вас есть блестящая идея для оптимизации.

Answer 1

Медленнее, я думаю, вы имеете в виду бег PixelCollection.each? Второй пример может быть медленнее, если не так много точек, для которых установлено значение 1, поскольку он по-прежнему проверяет все возможные местоположения, в то время как первый проходит только через добавленные точки. Если вы действительно хотите каждую возможную наносекунду любой ценой (в данном случае памяти), то вы можете предварительно выделить максимальный размер в два Uint8Arrayс и отдельно следить за размером.

var WIDTH = 255;
var HEIGHT = 160;

var PixelCollection = function() {
    this.pixels.length = 0;
    this.pixels.x = new Uint8Array(WIDTH * HEIGHT);
    this.pixels.y = new Uint8Array(WIDTH * HEIGHT);

};

PixelCollection.prototype = {
    add: function(x, y) {
        this.pixels.x[this.pixels.length] = x;
        this.pixels.y[this.pixels.length] = y;
        this.pixels.length++;
    },
    each: function(callback) {
        var pixels = this.pixels;
        for (var i = 0; i < this.pixels.length; i++) {
            callback(this.pixels.x[i], this.pixels.y[i]);

        }
    }
};

Если вы знаете ограничение на количество добавлений, которое будет иметь PixelCollection, вы можете уменьшить использование памяти. Вы даже можете объединить два массива в одну двойную длину, чередуя значения x и y.

Однако, если вы хотите иметь возможность удалять отдельные точки, этот метод становится сложным, и вряд ли он будет намного быстрее, чем ваш первый метод с изменением цикла @Pudge601.