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

Question

In my code, I have an object containing a series of pixel coordinates. The performance of this object is crucial because it is used in the game at 60 frames per second, where the output cannot always be cached.

After experiments and benchmarking, the 3D array turned out to be the fastest way to implement it 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 implementing the Uint8Array 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)); } } } } 

It is slower. I thought it would be faster because writing - and reading from Uint8Array is faster, but since I create a huge object for each PixelCollection object, getting pixels is slower because it takes more time to repeat all the pixels. (Note: I also tried the implementation above with an untyped array: it is much slower)

A PixelCollection usually does not have all the pixels. However, the bounding box can span the entire canvas, so I need to create an array using a large buffer.

However, there may be such a way. I can create one large shared buffer and use a byte offset for each PixelCollection. So when the PixelCollection P1 will take up to 100 bytes, then the PixelCollection P2 will start at a byte offset of 100. This uses memory more efficiently, but I will need to keep track of the range of bytes used by each PixelCollection (is that what C calls "pointers"?) .

The annoying part: when the frame P1 expands, I need to move P2 to make a space for P1 . And I will need to set a safe buffer size for the shared buffer, so I need to make a safe estimate of how much memory it needs.

The implementation of this is possible, but it will take a lot of time, trial and error.

So, before you start with this: does this seem like a good way to do this? Are there any better or simpler ways to do this? Do you know any implementation examples that I could learn?

Edit: I added jsperf if you want to try your hand at optimization.
Add jsperf to this if you have a brilliant idea for optimization.

Answer 1

The slower I think you mean the launch of PixelCollection.each ? The second example can be slower if there are not so many points that are set to 1, since it still checks all possible locations, while the first only goes through the added points. If you really want every possible nanosecond at any cost (in this case, memory), you can pre-allocate a maximum size of two Uint8Array and separately track 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 the limit on the number of add-ons that PixelCollection will have, you can reduce memory usage. You can even combine two arrays into a single variable x and y with double length.

However, if you want to delete individual points, this method becomes complicated, and it is unlikely to be much faster than your first method with changing the @ Pudge601 loop.