How do I use a typed array using a shared buffer efficiently in JavaScript?

Question

In my code I have an object that contains a series of pixel coordinates. Performance of this object is critical because it's being used in a 60fps game where the output cannot always be cached.

After experimentation and benchmarking, a 3D array proved to be the fastest way of implementing it when using untyped arrays:

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

In some situations, the object is not fast enough, so I tried a Uint8Array implementation, using a 2D array:

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

This is slower. I thought it would be faster because writing to - and reading from Uint8arrays is faster, but since I'm creating a huge object for every PixelCollection object, retrieving pixels is way slower because it takes longer to iterate over all pixels. (Note: I also tried the implementation above with an untyped array: it is a lot slower)

A PixelCollection typically does not have all pixels set. However, the bounding box may span the entire canvas so I do need to create the array using a buffer this big.

There may be a way around that though. I can create one big shared buffer and use a byte offset for every PixelCollection. So when PixelCollection P1 would take up 100 bytes, then PixelCollection P2 would start at byte offset 100. This uses memory more efficiently, but I would need to keep track of the range of bytes every PixelCollection uses (is this what C calls "pointers"?).

Annoying part: when P1's bounding box expands, I need to shift P2 to make space for P1. And I would need to set a safe buffer size for the shared buffer, so I need to make a safe guesstimation of how much memory it needs.

Implementing this is possible, but it would require lots of time, trial and error.

So before start on this: does it seem a good way to do it? Are there better or simpler ways to do this? Do you know any example implementations I could learn from?

Edit: I added a jsperf in case you want to try your hand at an optimization.
Please add to this jsperf if you have a brilliant idea for an optimization.

Answer 1

By slower I guess you mean running PixelCollection.each? The second example might be slower if there aren't that many points that are set to 1, as it still checks all possible locations whilst the first only runs through added points. If you really want every possible nanosecond at any cost (in this case memory), then you can pre-allocate the maximum size in two Uint8Arrays and separately keep track of the size.

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

        }
    }
};

If you know a limit to the number of additions the PixelCollection will have then you can reduce the memory usage. You could even combine the two arrays into one double length alternating x and y values.

However, if you want to be able to remove individual points this method gets tricky, also it's unlikely to be much faster than your first method with @Pudge601's loop change.