A resizable TypedArray

One of the most powerful features of Lager is our flexible data parsing engine, called Regal (yes, that is “Lager” in reverse). As data flows in from your device under test, Regal can easily parse, format, and graph it. Since Regal allows you to redefine your data structure definition on the fly, it’s not enough to simply parse the data as it arrives — we also need to store the raw bytes in a Uint8Array, in case you want to redefine your structure and re-parse everything. There’s only one problem — an instance of Uint8Array, unlike an instance of Array, can’t grow, so appending data isn’t possible! Let’s fix that…

@fictivekin/growable-uint8-array is a small utility library that manages a "resizable" Uint8Array buffer. "Resizable" is in quotes because instances of Uint8Array (like all TypedArrayspecies) have a fixed size determined at object construction time. The only way to append data to an existing Uint8Array is to allocate a new Uint8Array of the necessary size, copy in the old data, and then copy in the new data. This isn't terribly difficult to manage with a simple function:

However, if you’re doing lots of small appends, this approach is not very efficient, since you’ll be allocating O(n) Uint8Array’s and copying O(n²)bytes. For example, if you start with an empty array, and append 1 byte at a time 1000 times:

You’ll end up copying 500k of memory! The first call to appendToUint8Array copies 1 byte, the second copies 2 bytes, all the way up to the last which copies 1000 bytes, for a grand total of over 500,000 bytes copied.

So, how can we do better?

Our solution was to create a class GrowableUint8Array that wraps an instance of Uint8Array, automatically reallocating a larger buffer when necessary, but using an exponentially increasing size for the buffer, drastically reducing the number of allocations and copies necessary. Unfortunately we can't subclass Uint8Array itself, because the underlying ArrayBuffer instance variable itself is read-only.

GrowableUint8Array delegates all of the TypedArray prototype methods (map, filter, every, etc - see https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/TypedArray) and adds a few new methods:

1. extend(newData) — Appends array-like newData in-place to an existing GrowableUint8Array. If the underlying buffer is large enough to hold the new data, no allocations are needed and only the new data is copied. If the underlying buffer is not large enough, a new buffer is transparently allocated and copied from the old.
2. unwrap() — returns a new Uint8Array whose buffer is either shared (default) or copied from the GrowableUint8Array's buffer, with appropriate bounds set. For example, if you have a GrowableUint8Array with a 1000-element buffer, but only 500 are "in use", unwrap() will return a 500-element Uint8Array
3. getElement(n) and setElement(n, value) — get or set the nth element of the array. Attempting to set a value beyond the end of the array is a no-op, just as with a TypedArray.

Putting that together, we have:

We get the same result as before, but this time with only 7 Uint8Array allocations and 2,008 bytes copied.

So, we now have a class that mostly behaves like a resizable Uint8Array, with one major exception: We can't do Array-style indexing! For example, we can't do growableArray[0] - we need to use the utility methods getElement and setElement — e.g. growableArray.getElement(0). This is undesirable for at least 2 reasons - it's more typing, which is never fun, but more importantly, it means that instances of GrowableUint8Array can't be passed to functions which expect to do array-style indexing. for...of loops will work fine, since GrowableUint8Array.prototype[@@iterator] is implemented, but old-fashioned for (let i = 0; i < arr.length; i++) loops will not work if they ever try to access or set arr[i].

One possible solution is to call unwrap() and pass the result into the function in question. This will work if the function does not hold a reference to the passed-in array. If the function does hold a reference, then you may not always get the results you expect, as the following contrived example shows:

The problem is that the call to extend allocated a new Uint8Array, so the unwrapped version initially passed to doesItContain42Maker is "out of date" - subsequent updates, such as those made by calls to fill, are changing a different buffer.

So how do we solve this problem? In our next blog post we’ll talk about the magic of ES6 Proxies.

A Fictive Kin company