notes on coupled-oscillator-array morphogenesis

I thought this hack was going to be super simple to write, but it actually ended up taking me something like 6 hours, a lot of which was because of efficiency problems with <canvas>. In particular, running fillRect 1024 times on a displayed canvas seems to be rather alarmingly slow on all the platforms I tried it on. My eventual winning strategy was putImageData onto a <canvas> with one pixel per oscillator, scaled up to the right size using CSS. But it took me a couple of hours to figure that out. Rendering to a hidden canvas sped things up a bit, but not nearly as much as rendering to an ImageData, even before I reduced the pixel count.

I had written this APL-like or Matlab-like Vec class originally for a couple of the earlier hacks, first the augmented reality test and then the interactive canvas k-means thing, allowing me to write things like this:

    oscillators = oscillators.plus(3).minus(hSlowdowns).minus(vSlowdowns).bitand(255);
…
    var right = where(rawRight.greaterThan(maxValidIndex), maxValidIndex, rawRight)
      , sums = oscillators.prefixSum()
      , averages = sums.index(right).minus(sums.index(left)).dividedBy(right.minus(left))

The history is a bit confused — I’m intentionally duplicating code between the different hacks in order to not maintain each one once it’s finished, and I was writing this concurrently with the k-means code — but I added at least prefixSum, gradeDown, and index operations to Vec for this morphogenesis hack.

On one hand, Vec turns out to be a very handy way to experiment with numerical things, and it’s reasonably compact, at only about two pages of code. And it’s at least somewhat efficient. On the other hand, it does a lot of allocation, and its implementation using dynamic code generation led to profiler headaches with methods being described merely as “anonymous” until I learned about the displayName property in Firefox. And it still only supports one-dimensional computations, which forced some compromises here.

In theory, the abstraction provided by Vec should make it possible for the library to implement those calculations in a more optimized way. But I’m not sure the interface is the right interface.

The TensorFlow approach separates expression graph building from execution, as does Dan Amelang’s Nile, so the work of figuring out how to efficiently execute a particular expression graph can be shared across many executions, which probably would also help in this case. You could argue that with a multidimensional computation, time is just another dimension, and you could get that same benefit by doing a single execution on much larger arrays. This overlooks four things:

In this case, as in many of the things TensorFlow is designed for, the input for each execution comes in part from the output of the previous execution. This does not fit very well into the array-computation paradigm; although it is a sort of prefix sum operation, the well-known efficient parallel algorithms for prefix sum do not apply if the operation is not associative. While, in the abstract, you can decompose the time evolution of any deterministic system into the prefix sum of its elementary state transition function, which has been used to get big SIMD speedups on regular expression matching, this is only a computational speedup if you have reasonably compact descriptions of arbitrarily long parts of the system’s history, and in this case we don’t.
It’s desired in this case to display the individual frames of the oscillator array evolution as they are computed, interleaving the array computations with drawing operations. While you can certainly imagine an array system that supports that, I haven’t seen one.
Extra dimensions aren’t free. Vec doesn’t yet support extra dimensions at all, but even existing multidimensional array languages and libraries still run into trouble with them, both due to poorly-thought-out repertoires of operations and due to raggedness concerns. The ability to re-execute the same expression with different inputs solves both of these problems neatly.
You’d need to map the temporal dimension onto physical time to avoid the giant array using an enormous amount of memory.

Possible optimization opportunities for Vec include:

per-graph dynamic code generation: instead of evaluating each node in the expression into a concrete array in memory, compile the entire dataflow graph into a JS function, enabling at least loop fusion and deforestation; perhaps a function specialized for the particular data type and set of broadcasting operations along dimensions that are in use at a particular time. As an example of the “set of broadcasting operations”, the .where function in the current code already dispatches to one of five different manually-written inner loops in order to avoid checking on each iteration which arguments it needs to index into. Deforestation would be a pretty huge win: the current code generates 40 new Vecs per frame, almost all of which are temporary intermediates of 1024 elements, a total of 320 kibibytes. With deforestation, it would probably fit into L1.
In Firefox, the dynamic code generation could use asm.js, which would move not just the shape dispatch but also the atomic type dispatch to compile time. WASM is a cross-browser version of asm.js which is likely to be supported in Chromium.
Even without using asm.js, using TypedArrays would likely use much less space (1 byte per element instead of 8!) and might also provide JS compilers with more useful type information, allowing them to hoist type checks out of the inner loop. The only SIMD operations they support are copying and filling with a constant, but even that would actually be an improvement for what I’m doing.
Although WebCL looks like it might be dead in favor of WebGL ES compute shaders (ARB_compute_shader), it’s possible to do general-purpose computation with WebGL shaders. Getting this to speed things up instead of slowing them down may be quite a trick.
Finally, SIMD.js is a mapping of SSE and NEON into JS functions which is enabled in Firefox nightly, and is especially useful in asm.js. It has some warts (the .shuffle and .swizzle functions inexplicably don’t take vectors of indices) but it should be able to give a good speedup once the other things are taken care of.

Profiling in general on here was kind of a bear. Firebug’s profiler (Console main tab, Profile second-level tab, which for some reason I couldn’t find by myself until I dug up a tutorial), in addition to not being able to figure out what minus and greaterThan are called until I set .displayName on them, also slows the code down from some 7ms per frame up to 170ms per frame, so it’s unclear how closely related the profiler results are to the actual timing. And I don’t have any profiler available for anything that isn’t Firefox. A lot of my “profiling” to see what sped things up and what slowed them down was done with htop to see what percentage of CPU the browser was supposedly using at a fixed frame rate.

I ended up using requestAnimationFrame to drive the thing in the end, which should keep it from using more CPU than it can use or from using CPU when it’s not visible, and in theory maybe reduce its visual glitchiness. (It actually seems more glitchy than before; I suspect its frame rates are being quantized to 60, 30, 20, or 15, depending on how fast the browser is managing to execute it.)

Concurrent with all this, I also cleaned up the mobile layout stuff a bit; I needed a viewport meta tag, and my default stylesheet has these 7.48em (‽) margins on the left and right, which really don’t work very well at all when the screen is only 20 or 25 ems wide. So I added a media query to the stylesheet, which isn’t great but better than the alternative. So now these pages are fairly readable on smartphone screens.

This hack seems to have falsified a thing I thought about a certain kind of phosphene I get from pressing on my eyes, since it doesn't look the same way.

I thought I would have to add multidimensional support to Vec, or rewrite Vec with multidimensional support, for this. The current result is not exactly correct but it's not bad.