ndarrays – Multidimensional Arrays are really useful – Ways to implement multidimensional arrays

View Github Repository Open presentation in a new window

mikolalysenko

See all presentation from mikolalysenko

ndarrays – Multidimensional Arrays are really useful – Ways to implement multidimensional arrays

0 2

ndarray-presentation

Presentation on ndarrays

On Github mikolalysenko / ndarray-presentation

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(nd-1) extra space
  • O(d nd) traversal, cache incoherent*
  • O(nd) 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(nd / B) traversal
  • O(nd / B) slicing*

Con: Fixed size, slicing expensive

*Can be less for special kinds of slices

Strided arrays

"Affine map from ℤn 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(nd / 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

Other fun stuff

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: