Progress Update: Timeline Model

I've just finished adding a couple major pieces of infrastructure to the Lapis data model. The biggest is the timeline, which is really the central structure around which playback and media export will revolve. This is decoupled from cue sequences, which contain all the tempo/meter information for a cue and all the events programmed into that cue.

Here's a brief summary of some of the technical details, in case they're of interest to anybody doing similar work.

Assumptions

• Events on the timeline occupy a range of time
• A typical timeline might have on the order of 1,000 events (including bar/beat counter changes)
• Looking up events by time needs to be fast
• Populating the event list can take slightly longer
• Playback may happen in multiple passes
• Within one pass, playback always progresses forward in time; i.e., each successive lookup will happen at a time slightly later than the previous lookup

Approach

This is an area where I pretty routinely ran into problems with Streamers, because the concepts of cue sequences and timelines were tightly coupled, and playback was driven directly off the cue sequence; although this seems like a reasonable structure at first glance -- it certainly mirrors how timelines are usually presented in user interfaces -- it turned out to result in a bunch of unnecessary complexity. It also made it much harder to figure out multi-cue playback and media export, because each cue had its own distinct timeline. Thus, as mentioned above, Lapis takes a decoupled approach, compiling a simple timeline of events that has no knowledge of tempo or meter information.

There are two new model types supporting this aspect of playback: Timeline and TimelineSlice. Timeline is the fundamental data model that contains all the events currently scheduled for playback at any point in time on the entire timeline. TimelineSlice instance are created once per playback pass, and are similar to the concept of array slices in some programming languages, in that it deals only with a subset of the full collection. It also has no ability to mutate the timeline events.

A TimelineSlice keeps track of a playhead, and uses that to advance along an array of scheduled events. It also keeps a running list of currently active events -- those that were scheduled to start before the playhead but have not yet ended -- so that it can figure out which events are still active after advancing the playhead, without having to look at every past event in the sequence. (This is needed because each event occupies a range of times, some of which may span a substantial duration. It's possible for the first event in the timeline to be active even as the playhead is on, say, the 1,000th event.)

Initial results

Here are some test measurements on a 2015 MacBook Pro:

• Compile timeline events from a fairly complex tempo/meter map: 13 ms average
• Measurements on a randomly-generated 1,000-event timeline:
  • Create TimelineSlice and look up events near beginning: 0.15 ms average
  • Create TimelineSlice and look up events near end: 6 ms average
  • Look up events while incrementally advancing (mimicking normal playback): 0.37 ms average

Lessons Learned

I've been trying to embrace the idea of unit tests, and interestingly, this was the first case I've found where a test has unexpectedly unearthed a latent bug. The bug was that lookups starting in the middle of a timeline would be missing events, but only sometimes. I had created a test that used a manually hard-coded set of predefined events on a timeline, and started playback from around halfway through. If I ran the test individually, it would always pass, but if I ran all tests together, this one test would usually (but not always) fail. Which I thought was weird, since it was behaving like a race condition, but I was specifically avoiding any situation that could cause mutable state to be shared across threads.

The problem turned out to stem from the fact that timelines store events in a dictionary (keyed by a UUID for each event), and also store an array of UUIDs sorted by event start time. When creating a TimelineSlice, I was inadvertently enumerating over the unsorted dictionary rather than the sorted array. Somehow, when running the test individually, the dictionary was apparently maintaining the entries in the order they were created (which happened to be ordered by start time), so the test was erroneously passing! Something about the fact that Xcode runs multiple tests in parallel when possible caused that ordering to be lost.

I guess the moral of the story is that unit tests are actually better than doing random manual spot checks? Or maybe it's that unit tests on their own actually aren't that much better, unless they get run in less controlled conditions? In any case, running all tests together did provide a more realistic scenario, and saved me from the trouble of having to track down this bug much later, when it would inevitably have caused problems during playback.