Iterate the Few, Not the Many

I was dragging an ellipse around the stage and dropping keyframes along the way. Somewhere between keyframe #10 and #15, the frame spike warning messages appeared:

Frame spike: 142.3ms
Frame spike: 128.7ms
Frame spike: 201.4ms

My editor had dropped to around 5 FPS. With only 15 keyframes!

My Assumption Turned Out to Be Incorrect

What I first suspected was that adding a keyframe had become expensive. Both addKeyframe() and setKeyframe() involved iterating through the whole array and inserting a new element, so maybe auto-keying or multiple F6 commands were causing the problem. The first step was to look inside the keyframe insertion code. I found addKeyframe() and setKeyframe(). The latter called hasKeyframeAt() before deciding whether to insert, and the former did its own linear scan to find the insertion point:

pub fn setKeyframe(self: *AnimationTrack, keyframe: Keyframe) !void {
    if (!self.hasKeyframeAt(keyframe.frame)) {
        try self.addKeyframe(keyframe);
    } else {
        for (self.keyframes.items) |*kf| {
            if (kf.frame == keyframe.frame) {
                kf.value = keyframe.value;
                break;
            }
        }
    }
}
 
pub fn addKeyframe(self: *AnimationTrack, keyframe: Keyframe) !void {
    var i: usize = 0;
    while (i < self.keyframes.items.len) : (i += 1) {
        if (self.keyframes.items[i].frame > keyframe.frame)
            break;
    }
    try self.keyframes.insert(i, keyframe);
}

Two inefficient scans in a row. Not great but still O(15). Certainly not 200ms.

Timing Changed the Approach

The final realization came with the exact timing of frame spikes. It turns out that it didn't happen when I added a keyframe. It kept happening on every single frame! In fact, even after I stopped working with the editor, it still rendered extremely slowly. So my problem became: Not: “adding a keyframe causes the editor to run slow” But: “having any keyframe causes the entire editor to be extremely slow.”

The Real Bottleneck

Every frame is redrawing the timeline. Every visible frame requires checking if a keyframe exists there to be able to draw the diamond:

var f: u32 = visible_start;
while (f < visible_end) : (f += 1) {
    if (!layer.hasAnyKeyframeAt(f)) continue;
    // ...
}

The hasAnyKeyframeAt() function calls hasKeyframeAt() for each animation track of the layer. That is also linear:

pub fn hasKeyframeAt(self: *const AnimationTrack, frame: u32) bool {
    for (self.keyframes.items) |kf| {
        if (kf.frame == frame) return true;
    }
    return false;
}

With the default zoom level, the timeline shows about 240 visible frames. There are usually more than ten animation tracks in each shape. And each track may have up to 15 keyframes. So we have: 240 × 10 tracks × 15 keyframes = 36,000 comparisons per layer row, per frame And that is just for the collapsed layer row (renderLayerAggregateFrames()). Expanding a layer adds shape rows and property track rows (`renderShapeAggregateFrames() and renderPropertyTrackFrames()), each performing its own iteration over visible frames. In a debug build, that is too much.

The Actual Fix: I Had the Loop Backwards

The insight was simple: I was iterating the dense set (frames) and probing the sparse one (keyframes). There are a large number of frames, but only some of them have keyframes. So the better approach would be: Not: "For each frame, check if it contains a keyframe." But: "For each keyframe, check if it is contained in any visible frame."

var visible_kf_frames: [MAX_VISIBLE_KF_FRAMES]u32 = undefined;
var kf_count: usize = 0;
collectVisibleKeyframeFrames(tracks, visible_start, visible_end,
    &visible_kf_frames, &kf_count);
 
for (visible_kf_frames[0..kf_count]) |f| {
    // ...
}

Instead of iterating over visible frames, we collect only those with keyframes and iterate over the keyframes themselves.

The Other Optimizations

As mentioned above, the main problem is the linear search for each keyframe in each animation track. So I fixed some related inefficiencies as well:

Binary search
Since keyframes are sorted by frame index, linear search in hasKeyframeAt() is unnecessary. Binary search reduces lookup complexity from O(n) to O(log n), meaning it takes about 4 comparisons to find a keyframe rather than 15. It was implemented for AnimationTrack, PathAnimationTrack, and MeshAnimationTrack.

Binary search for insertion
Similarly, linear scans in addKeyframe() were replaced with binary searches, so addKeyframe() now uses binary search as well. For setKeyframe(), I moved common code to findKeyframeIndex().

Double linear scan removed
The existingTrackValueAtFrame() function was doing two passes in one call: checking if there is a keyframe at the frame index and finding its value. Now it does that in one scan.

The Performance Improvements

Before: 120-200ms per frame, consistently, with just 15 keyframes in a single shape. After: The inner loop work became O(keyframes × log(keyframes)) instead of roughly O(visible_frames × tracks × keyframes_per_track). In practice: 15 keyframes × log2(15) ≈ 60 comparisons per frame instead of 36,000. A major improvement.

Why Debug Mode Helps Here

Another reason why this became apparent to me so easily: a debug build. Zig's debug mode includes additional safety checks. It performs additional checks on array accesses, skips optimizations such as inlining, and generally helps with debugging. Which makes inefficient algorithms hurt a lot more. Frankly speaking, I do not regret that. If the release build had smoothed over that, I probably would not have noticed the problem until there were hundreds of keyframes in a real project. And I would still have the same issue, but with much more noise.

Takeaways

Look at the timing carefully
The most useful information came from the timing of frame spikes. The consistent slowdown at each frame indicated a rendering issue.

Iterate the few, not the many
The takeaway I will probably remember is: when iterating between sparse and dense sets, make the loop iterate over the sparse set.

Keep things simple: sorted array + binary search goes a long way
The data model is simple here; keyframes are ordered by frames. Using a sorted array and binary search is sufficient.

Focus on the problem, not the symptoms
The keyframe insertion algorithm was wasteful, indeed. But it was not the cause of the performance issues.