ndarrays

Mikola Lysenko

University of Wisconsin-Madison

twitter @mikolalysenko | github @mikolalysenko | blog: 0fps.net

Multidimensional Arrays are really useful

Image processing

σ:

Visualization

DSP

Stretch Factor

Scientific Computing

...and more

Ways to implement multidimensional arrays

Arrays-of-arrays

"Arrays of nested arrays"

          var array = [ [ 1, 0, 0 ], 
                        [ 0, 1, 0 ],
                        [ 0, 0, 1 ] ]
          var x = array[1][2]

Performance summary

O(d) indirect memory reads/array accss
O(n^d-1) extra space
O(d n^d) traversal, cache incoherent^*
O(n^d) slicing

^*Sometimes optimized by v8 in special cases

Implicit arrays

"Lexicographic ordering"

  var array = [ 1, 0, 0, 0, 1, 0, 0, 0, 1 ]
  var x = array[ 1*3 + 2 ]

Performance summary

O(1) indirect memory reads/array accss
No extra space!
O(n^d / B) traversal
O(n^d / B) slicing^*

Con: Fixed size, slicing expensive

^*Can be less for special kinds of slices

Strided arrays

"Affine map from ℤⁿ to ℤ"

var stride = [3, 1]
var offset = 0
var array = [ 1, 0, 0, 0, 1, 0, 0, 0, 1 ]
var x = array[stride[0]*1+stride[1]*2+offset]

Performance summary

O(1) indirect memory reads/array accss
O(d) extra space
O(n^d / B) traversal
O(d) slicing

Getting to know ndarrays

Philosophy

Minimal core
Add functionality through modules
Browserify and npm
Strided array layout
Explicit memory management
WebGL interoperability

Constructor

Require

var ndarray = require("ndarray")

Create

var array = ndarray(data,shape,stride,offset)

data is the underlying 1D array
shape gives the dimensions of the ndarray
stride is the linear part of the map
offset is the translation part of the map

Accessors

Update an element

array.set(i0,i1,v)

Translates to

data[stride[0]*i0+stride[1]*i1+offset]=v

Other accessors: .get(), .set(), .index()

Slicing

Methods

.hi(x0,x1,...): Changes the shape to [x0,x1,...]
.lo(x0,x1,...): Moves (x0,x1,...) to (0,0,...)
.transpose(x0,x1,...): Permutes indices
.step(x0,x1,...): Changes striding, skips elements
.pick(x0,x1,...): Selects a subarray

Can be chained and takes O(dimension) time

Slicing Visualized

Data:

Slice:

Props:

Shape:

Stride:

Offset:

            array.lo(222,215).hi(40,40) //Edit me!

Custom datatypes

data can be any array-like object or data structure with .get/.set

Example:

    var hash = {}
    var hashStore = {
      get: function(i) {
        return +hash[i]
      },
      set: function(i,v) {
        return hash[i]=v
      },
      length: Infinity
    }
    var array = ndarray(hashStore, [1000,1000,1000])

Useful for implementing sparse arrays, interfacing to other data structures

ndarray modules

ndarray-ops

Require:

var ops = require("ndarray-ops")

Example:

ops.mulseq(a, 2.0)

Operation name
Scalar flag
In place update flag

Operators: assign,random,add,sub,mul,div,mod,...

cwise

Engine behind ndarray-ops.

Generates cache efficient array operations

Very fast

gl-modules

Thin, modular WebGL wrappers using ndarrays

glslify: Module system for shaders
gl-texture2d: Upload ndarrays to textures on the GPU
gl-buffer: Upload ndarrays to array/vertex buffers
gl-vao: Manage vertex array objects
gl-fbo: Manage frame buffer objects

utilities

ndarray-pack: Convert array-of-arrays to ndarrays
ndarray-unpack: Convert ndarray to array-of-arrays
ndarray-fill: Initialize ndarray with a function
typedarray-pool: Memory pooling for typedarrays
ndarray-scratch: Helper for ndarray/typedarrays
save-pixels: Writes a 2D ndarray to a file
get-pixels: Reads an image into an ndarray
ndarray-imshow: Displays an ndarray as an image
ndarray-string: Converts a string to an ndarray

Other fun stuff

ndarray-fft: Fast Fourier transform
ndarray-sort: Sorts arrays
binary-search-bounds: Supports ndarrays
distance-transform: Distance transforms
ndgemm: General matrix multiplication
voxelize: Voxelizes a mesh to an ndarray
ndarray-bit: Bitmap ndarrays
ndarray-hash: Hash table backed sparse ndarrays
ndarray-segment: Sparse, run-length-encoded ndarrays
ndarray-prefix-sum: Computes partial sums/integral images/rank queries
surface-nets: Extracts contours from images
...and much more!

Worked examples

Burrows-Wheeler Transform

Step 1: Input string

var str="BANANA"+"\0"

Step 2: Generate matrix of rotations

00000
10101
00110

var ndstring = require("ndarray-string")
var n = str.length
var x = ndstring(str+str,[n,n],[1,1])

Step 3: Sort rows

00000
10101
00110

var ndsort = require("ndarray-sort")
var scratch = require("ndarray-scratch")
var y = ndsort(scratch.clone(x))

Step 4: Return last column

foo

var result = ndstring.toString(y.pick(-1, n-1))
scratch.free(y)

Inverse transform

Step 1: Input string

var x = ndstring("", [n,n], [1,0])

Step 2: Sort columns

var y = scratch.clone(x)
for(var i=n-1; i>=0; --i) {
  ndsort(y.lo(0, i))
}

Step 3: Return top row

var result = ndstring.toString(y.pick(0).lo(1))
scratch.free(y)
return result

Conclusion

Future work

Linear algebra
Sparse array support
Tensor operations
Debugging tools
Outreach

Lots more work to do!

More info

Acknowledgements

The following (incomplete) set of people/organizations helped out with ndarrays, or contributed otherwise useful stuff: