What is the most efficient way to implement multidimensional arrays in JavaScript?
UPDATE Experiments for numeric.js, cwise and ndarray-ops added
To run the experiment in node, just do:
node experiment.js If you want to try it in your browser, you can install beefy by typing:
npm install -g beefy Then running
beefy experiment.js --open These are the results of running the experiment in the latest version of Chrome V8.
With:
- Core i7 @ 2.3 GHz. 8GB RAM
- Mac OS X 10.8.3
- Google Chrome 27
- cwise 0.3.3
- ndarray 1.0.4
- ndarray-ops 1.1.0
- numeric 1.2.6
Running experiment with dimensions = 16 x 16 x 16 experiment.js:30 Proposal #1 raw native array Total Init = 0ms Execution = 8ms Proposal #2 raw typed array Total Init = 0ms Execution = 9ms Proposal #3 object with array accessor Total Init = 0ms Execution = 15ms Proposal #4 object with flat accessor Total Init = 0ms Execution = 10ms Proposal #5 object with flat accessor, no offset Total Init = 1ms Execution = 11ms Proposal #6 array of native arrays Total Init = 1ms Execution = 25ms Proposal #7 array of native arrays (fast init) Total Init = 1ms Execution = 5ms Proposal #8 array of typed arrays Total Init = 0ms Execution = 9ms Proposal #9 array of contiguous typed arrays Total Init = 1ms Execution = 9ms Proposal #10 numeric.js simple Total Init = 0ms Execution = 47ms Proposal #11 numeric.js pointwise() Total Init = 0ms Execution = 64ms Proposal #12 ndarray-raw Total Init = 4ms Execution = 8ms Proposal #13 ndarray-ops Total Init = 0ms Execution = 52ms Proposal #14 cwise Total Init = 0ms Execution = 9ms Running experiment with dimensions = 64 x 64 x 64 experiment.js:30 Proposal #1 raw native array Total Init = 57ms Execution = 660ms Proposal #2 raw typed array Total Init = 0ms Execution = 471ms Proposal #3 object with array accessor Total Init = 1ms Execution = 732ms Proposal #4 object with flat accessor Total Init = 1ms Execution = 470ms Proposal #5 object with flat accessor, no offset Total Init = 1ms Execution = 464ms Proposal #6 array of native arrays Total Init = 3ms Execution = 1516ms Proposal #7 array of native arrays (fast init) Total Init = 22ms Execution = 244ms Proposal #8 array of typed arrays Total Init = 7ms Execution = 462ms Proposal #9 array of contiguous typed arrays Total Init = 4ms Execution = 556ms Proposal #10 numeric.js simple Total Init = 9ms Execution = 11902ms Proposal #11 numeric.js pointwise() Total Init = 5ms Execution = 3399ms Proposal #12 ndarray-raw Total Init = 1ms Execution = 256ms Proposal #13 ndarray-ops Total Init = 3ms Execution = 770ms Proposal #14 cwise Total Init = 0ms Execution = 201ms Running experiment with dimensions = 512 x 512 x 4 experiment.js:30 Proposal #1 raw native array Total Init = 199ms Execution = 1130ms Proposal #2 raw typed array Total Init = 4ms Execution = 1857ms Proposal #3 object with array accessor Total Init = 5ms Execution = 3025ms Proposal #4 object with flat accessor Total Init = 5ms Execution = 1895ms Proposal #5 object with flat accessor, no offset Total Init = 1ms Execution = 1853ms Proposal #6 array of native arrays Total Init = 162ms Execution = 6221ms Proposal #7 array of native arrays (fast init) Total Init = 138ms Execution = 1147ms Proposal #8 array of typed arrays Total Init = 543ms Execution = 1975ms Proposal #9 array of contiguous typed arrays Total Init = 395ms Execution = 1921ms Proposal #10 numeric.js simple Total Init = 81ms Execution = 59890ms Proposal #11 numeric.js pointwise() Total Init = 81ms Execution = 17571ms Proposal #12 ndarray-raw Total Init = 3ms Execution = 1172ms Proposal #13 ndarray-ops Total Init = 3ms Execution = 3799ms Proposal #14 cwise Total Init = 3ms Execution = 940ms Running experiment with dimensions = 512 x 4 x 512 experiment.js:30 Proposal #1 raw native array Total Init = 228ms Execution = 1841ms Proposal #2 raw typed array Total Init = 1ms Execution = 1856ms Proposal #3 object with array accessor Total Init = 1ms Execution = 2886ms Proposal #4 object with flat accessor Total Init = 1ms Execution = 1871ms Proposal #5 object with flat accessor, no offset Total Init = 1ms Execution = 1869ms Proposal #6 array of native arrays Total Init = 34ms Execution = 6015ms Proposal #7 array of native arrays (fast init) Total Init = 25ms Execution = 741ms Proposal #8 array of typed arrays Total Init = 6ms Execution = 1875ms Proposal #9 array of contiguous typed arrays Total Init = 4ms Execution = 1891ms Proposal #10 numeric.js simple Total Init = 31ms Execution = 45547ms Proposal #11 numeric.js pointwise() Total Init = 15ms Execution = 13322ms Proposal #12 ndarray-raw Total Init = 3ms Execution = 1003ms Proposal #13 ndarray-ops Total Init = 5ms Execution = 2766ms Proposal #14 cwise Total Init = 3ms Execution = 767ms Running experiment with dimensions = 4 x 512 x 512 experiment.js:30 Proposal #1 raw native array Total Init = 208ms Execution = 2232ms Proposal #2 raw typed array Total Init = 1ms Execution = 1885ms Proposal #3 object with array accessor Total Init = 1ms Execution = 2907ms Proposal #4 object with flat accessor Total Init = 1ms Execution = 1884ms Proposal #5 object with flat accessor, no offset Total Init = 1ms Execution = 1870ms Proposal #6 array of native arrays Total Init = 37ms Execution = 5959ms Proposal #7 array of native arrays (fast init) Total Init = 26ms Execution = 762ms Proposal #8 array of typed arrays Total Init = 6ms Execution = 1883ms Proposal #9 array of contiguous typed arrays Total Init = 4ms Execution = 1912ms Proposal #10 numeric.js simple Total Init = 23ms Execution = 39231ms Proposal #11 numeric.js pointwise() Total Init = 16ms Execution = 13258ms Proposal #12 ndarray-raw Total Init = 3ms Execution = 1002ms Proposal #13 ndarray-ops Total Init = 5ms Execution = 2773ms Proposal #14 cwise Total Init = 3ms Execution = 770ms Running experiment with dimensions = 2 x 2 x 2048 experiment.js:30 Proposal #1 raw native array Total Init = 0ms Execution = 16ms Proposal #2 raw typed array Total Init = 0ms Execution = 16ms Proposal #3 object with array accessor Total Init = 0ms Execution = 26ms Proposal #4 object with flat accessor Total Init = 0ms Execution = 17ms Proposal #5 object with flat accessor, no offset Total Init = 0ms Execution = 17ms Proposal #6 array of native arrays Total Init = 0ms Execution = 49ms Proposal #7 array of native arrays (fast init) Total Init = 0ms Execution = 7ms Proposal #8 array of typed arrays Total Init = 0ms Execution = 16ms Proposal #9 array of contiguous typed arrays Total Init = 0ms Execution = 16ms Proposal #10 numeric.js simple Total Init = 0ms Execution = 230ms Proposal #11 numeric.js pointwise() Total Init = 1ms Execution = 139ms Proposal #12 ndarray-raw Total Init = 0ms Execution = 8ms Proposal #13 ndarray-ops Total Init = 0ms Execution = 49ms Proposal #14 cwise Total Init = 0ms Execution = 9ms Running experiment with dimensions = 2048 x 2 x 2 experiment.js:30 Proposal #1 raw native array Total Init = 1ms Execution = 15ms Proposal #2 raw typed array Total Init = 0ms Execution = 15ms Proposal #3 object with array accessor Total Init = 0ms Execution = 34ms Proposal #4 object with flat accessor Total Init = 0ms Execution = 25ms Proposal #5 object with flat accessor, no offset Total Init = 0ms Execution = 23ms Proposal #6 array of native arrays Total Init = 1ms Execution = 51ms Proposal #7 array of native arrays (fast init) Total Init = 2ms Execution = 17ms Proposal #8 array of typed arrays Total Init = 7ms Execution = 20ms Proposal #9 array of contiguous typed arrays Total Init = 6ms Execution = 19ms Proposal #10 numeric.js simple Total Init = 21ms Execution = 458ms Proposal #11 numeric.js pointwise() Total Init = 2ms Execution = 303ms Proposal #12 ndarray-raw Total Init = 0ms Execution = 17ms Proposal #13 ndarray-ops Total Init = 0ms Execution = 83ms Proposal #14 cwise Total Init = 0ms Execution = 18ms Interesting things to note:
- v8 can optimize arrays of native arrays very well, providing that they are initialized in the right way very carefully.
- The downside to using native arrays though is that you can't do constant time transposing and slicing, so ndarrays may still be preferable for this reason.
- While it isn't as fast as using cwise, directly accessing ndarrays performs pretty well providing you iterate in the order of the stride of the ndarray.
- Obviously 1D typed arrays are best performance
- Using
get([i,j,k])for indexing is terrible.get(i,j,k)is more than 10x faster. - Similarly, it is pointless to store a separate offset field. That can be handled using the the subarray() method from a typed array.
- Wrapped objects nearly match the performance of typed arrays, within a factor <2
- Arrays-of-arrays are 5-100x slower than objects, but have the advantage of interoperating with other libraries.
- Contiguous typed array allocation is strictly faster by a small margin (~5%), so if you are going down that route might as well do it.
- For arrays of arrays, it is a trade off by between typed arrays and native arrays. Native arrays are faster if the last dimension is small, while typed arrays are faster if it is large.
Excluding obviously stupid things,
-
Flat typed array, with manual index
- Very fast
- But also messy, requires repeating certain patterns everywhere
- Does not carry semantic information like array shape
- Higher dimensional
subarraynot supported, can only slice along first axis.
-
Array-of-native arrays
- Simple, JS/idiomatic access pattern
- Complete representation of shape data
- Compatible with numeric.js
- Good for images or situations where last component is relatively small
- Bad when last component list large
- Need to convert to typed array when interfaced with WebGL
- Hard to ensure validity. (eg, checking all rows are actually rows)
-
Array-of-typed-arrays
- Same access pattern as array-of-arrays
- Complete representation of shape data
- Compatible with numeric.js
- Good when last component is large (eg volume data)
- Bad when last component is small
- With contiguous allocation, can support direct WebGL uploads
- Even harder to validate; need to check if array is contiguous and all types match
-
Custom multidimensional array object
- Near optimal performance
- Semantically complete
- Easy/simple validation
- Can be directly uploaded to GPU
- Awkward/non-standard interface, will require libraries standardize on convention
Based on performance considerations, I am currently leaning toward option 4, but dissenting opinions are welcome.
- numeric.js is internally built using the array-of-native-arrays approach, and so it is naturally slower than using a typed array
- Also, the implementation of numeric_simple.js uses mul() which returns a copy (and so it is much slower)
- ndarray-ops uses cwise internally, and so it is generally speaking slower than cwise, but may still be useful for some simple operations (like array copying/assignment/basic pointwise operations)
- cwise uses macro expansion to inline functions and unroll loops, and reaches performance which is comparable to a native 1D typed array, with some small overhead due to unboxing primitives.