A divide per pixel

Last post got the SPI panel off the critical path: DMA the blit, stop streaming a framebuffer to a viewer that no longer exists, and run the cart fullscreen. By the end of it the panel was at about 41fps and, more to the point, the frame was made of exactly one thing. blit, prep, transport: all about zero. Whatever time was left was Solais running its own _update60 and _draw.

That is a good problem to have. It means the next bit of speed is not hiding in my plumbing any more. It is in the cart, or in the code the cart calls. The bottleneck moved house.

The cart that would not run

Before any of that mattered, the cart had to actually run, and it kept falling over with this:

lua _update60 error: cart:ld: attempt to call a nil value (global 'sub')

sub is PICO-8's substring function, sub(str, i, j). My Lua prelude defines the maths and table helpers a cart expects as bare globals (flr, sin, add, del, ...), because PICO-8 carts call those as globals, not math.floor. But I had never added the string ones. So the moment Solais's ld routine reached for sub, the call hit a nil and _update60 threw.

Three lines fixed it:

function sub(s,i,j) return string.sub(s,i,j) end
function tonum(x) return tonumber(x) end
function tostr(x) return tostring(x) end

The part I liked: this also closed a bug I had filed separately. Trampolines in the dungeon were not bouncing the player. I had assumed a physics or collision problem and left myself a note to look at it later. It was the same sub. The error threw partway through _update60, so every line after the ld call, including the trampoline physics, silently never ran. One missing builtin, two bugs, and the second one looked nothing like the first.

Which draw call?

Now the frame was all cart, and in the dungeon it was about 17ms, call it 50fps. To hold 60 I needed it under 16.7ms. The honest way to find 3ms is to measure, so I leaned on a per-primitive profiler that was already in the firmware: every draw binding bumps a counter, and once a second the totals get dumped over the debug link.

draw us [spr,map,sspr,tline,rfill,cfill,line,print]
        =[15472, 57135, 435380, 153868, 749, 0, 2423, 0]

There it is. sspr, stretched sprite, at 435ms of every second of draw time. Two thirds of the budget in one call. About 960 calls a second at roughly 450us each.

This is worth dwelling on, because a plan I had been handed said to optimise tline, the textured-line call, fourth in that list. It was a reasonable guess. tline is the textured-wall workhorse and it is the biggest call on the title screen. But on the title screen, not in the dungeon. The dungeon's hog is sspr, and it is not close. If I had taken the guess I would have spent a day shaving the wrong call. The profiler does not care what is plausible.

What costs 450 microseconds

sspr scales a rectangle of the sprite sheet to an arbitrary destination size. The old loop did nearest-neighbour sampling the textbook way: for each destination pixel, work out which source pixel it maps back to.

for j in 0..dh {
    let ssy = sy + j * sh / dh;
    for i in 0..dw {
        let ssx = sx + i * sw / dw;   // this line, every pixel
        ...
    }
}

i * sw / dw. An integer divide, in the inner loop, once per pixel.

The Cortex-M7 has a hardware divider, but it is not pipelined. The core stalls for the duration, a handful of cycles it cannot overlap with anything else. Do that on every pixel of a large scaled sprite, times a couple of dozen sprites a frame, and it adds up to the 10ms I was staring at.

I wanted to be sure it was the divide and not something subtler, like the framebuffer and sprite sheet thrashing the data cache. So I tried the cheap experiment first: I moved both into DTCM, the core-coupled RAM that is zero-wait-state and not cached at all. If the cost were cache misses, that would have helped. It did nothing. sspr stayed at 450us a call. Compute, not memory. The divide was the whole story.

Stepping without dividing

You do not need a divide per pixel to walk i * sw / dw. The value climbs by sw/dw each step, and that is a fixed rate, exactly the thing Bresenham's line algorithm tracks with an integer accumulator and a compare.

let mut ssx = sx + i_lo * sw / dw;  // one divide, at the start of the row
let mut acc = i_lo * sw % dw;
for i in i_lo..i_hi {
    // ... sample at ssx, write the pixel ...
    acc += sw;
    while acc >= dw { ssx += 1; acc -= dw; }   // add and compare, no divide
}

The sampled coordinate comes out bit-identical to sx + i * sw / dw. It is the same number, computed without the divide. While I was in there I did the rest of the hot-loop hygiene the plain sprite blitter already had: clip the destination rectangle to the screen once, up front, instead of testing every pixel; hoist the row pointers; inline the 4bpp sheet read.

sspr per call:   451us -> 54us
dungeon draw:    ~17ms -> ~10ms
dungeon fps:     42-50 -> 54-58

Eight times faster, from deleting one divide. The scaled art is pixel-for-pixel the same. I checked, on the glass, because exact-match-by-construction is a claim right up until you look at it.

Where it went

So the dungeon plays at 54 to 58 now, up from the 14 I started the day at. And the bottleneck has moved again. With the cart down to about 12ms a frame, the thing setting the pace is no longer Solais. It is the panel, converting and pushing 32KB of pixels out the SPI bus every frame. The convert and the DMA happen one after the other, and there is a double buffer sitting right there to overlap them. That is the next swing, and the smart move is to instrument it before touching it, because the convert is CPU work and "overlap" could just shove the cost back onto Lua.

The whole day was one shape, repeated. The slow part was never where it felt like it should be. It was the USB stream, then the blocking blit, then a missing builtin, then a divide I would never have guessed at. Every time the fix was small and the finding was the hard part. Measure the thing. The profiler is smarter than the plan.