Question

What is the most efficient way to implement multidimensional arrays in JavaScript?

UPDATE Experiments for numeric.js, cwise and ndarray-ops added

Experiment

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

Results:

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

UPDATE

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.

Generic Observations

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.

Reasonable Approaches to Arrays

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 subarray not 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.

UPDATE Observations about Libraries

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.

Name		Name	Last commit message	Last commit date
Latest commit History 27 Commits
.gitignore		.gitignore
LICENSE		LICENSE
README.md		README.md
cwise.js		cwise.js
experiment.js		experiment.js
multi_cont.js		multi_cont.js
multi_native.js		multi_native.js
multi_native_fast_init.js		multi_native_fast_init.js
multi_typed.js		multi_typed.js
native_1d.js		native_1d.js
ndarray-raw.js		ndarray-raw.js
ndarrayops.js		ndarrayops.js
numeric_pointwise.js		numeric_pointwise.js
numeric_simple.js		numeric_simple.js
object_array.js		object_array.js
object_flat.js		object_flat.js
object_flat_no_offset.js		object_flat_no_offset.js
package.json		package.json
typed_1d.js		typed_1d.js
typed_1d_get.js		typed_1d_get.js

License

mikolalysenko/ndarray-experiments

Folders and files

Latest commit

History

Repository files navigation

Question

Experiment

Results:

UPDATE

Generic Observations

Reasonable Approaches to Arrays

UPDATE Observations about Libraries

About

Resources

License

Stars

Watchers

Forks

Languages