• Game 'o Life

    I found an article by Chris Wellons describing a Game of Life simulation that runs on the GPU and I wanted to try it myself. I wrote my version of it in Skew (which turned out to be a pleasure to use) and it works pretty well. On my laptop it runs fine with grids of 16 million cells.

    If your browser supports WebGL, you should see a small demo below. Click here to see a full page demo and here to see the code.

  • W00T (Without Operational Transformation)

    Oster, Gérald, et al. "Real time group editors without operational transformation."

    This paper describes a method of building online collaborative systems that is far simpler than OT. A few years ago I would have dismissed it as a hack (a key to its implementation strategy is that it never deletes characters from the document). But a few years of experience in software engineering have taught me to appreciate it's simplicity in implementation. Simple implementation and "good enough" feature set is sometimes the right move.

    It's pretty easy reading as far as academic papers go. It's full of examples to make sure that you really know the edge cases of the algorithm by the time you're done reading.

    Below is a gif of my own (toy) implementation. The code is on Github here.

  • More than you want to know about @synchronized

    If you've done any concurrent programming in Objective-C, then you've seen the @synchronized construct. The @synchronized construct does just what a lock does: it prevents different threads from executing the same code at the same time. But it's more convenient and more readible in some cases compared to allocating, locking and unlocking an NSLock.

    If you've never used @synchronized before, below is an example of how to use it. The meat of this article will talk about a short investigation that I made into how @synchronized is implemented.

  • An Intro to OT

    I've been reading about real-time collaborative editing. One popular approach is OT (operational transformation). Most OT resources online reference this old paper on the Jupiter Collaboration system. It's one of the first to introduce OT as a technique for building collaborative editors and while it's easy to read, it's light on details and spends more time than I'd like describing what real-time collaboration is (I guess you couldn't take that for granted in 1995).

    If you're interested in OT, I'd recommend starting instead with this article by Daniel Spiewak. It describes OT at a high level and gets into some of the complexities of using it to build a server/client pair.

    When I was done with Spiewak's article, I still didn't have a solid idea of how to implement OT on text or XML or any particular datatype. He directs to you to the Google Wave whitepapers to find out more, but I found the ot.py implementation to be a better explanation. It's pretty small and easy to read in entirety. There are more implementations at that link (js, Haskell, lua) but I haven't dug into them. If you find one that you think is great, let me know!

  • Parallelograms
    If you draw any quad and join its midpoints with lines, you get a parallelogram! That's pretty neat. The animation below repeatedly draws a (not quite) random quad and joins its midpoints with lines.