Fast scrolling and long lists

Until now, I reserved a 2 MB block of the PSRAM for the music index and copied the whole thing into it at boot. That doesn't work with large collections, so let's improve it.

This problem is tied to the fast scrolling one. Until now I had two scrolling speeds: one row per click, and one page per click when the wheel spins fast. On laaaaarge lists, it took ages to scroll all the way down. Let's fix that on the way, and make the index structure handle fast scrolling well.

The short version:

• The index is now one file on the SD card, opentone/index.pack. The firmware reads it 4 KB at a time, when it needs it, and keeps the recent pages in PSRAM. The library is bounded by the card, not by the PSRAM.
• Boot no longer copies anything: 3.1 s with 100,000 tracks, against 5.6 s with 6,000 before.
• Fast scrolling now jumps from letter to letter, with gears: a sustained fast turn shifts up to bigger jumps, and once in a gear you go through the letters at your own pace. Pausing shifts back down. Three quick turns cross my whole library, A to Z.
• The bench did most of the work: the AI drove the device over serial, measured, and found two bottlenecks I would never have guessed.

The old index

• One file per map: Artist->Album, Album->Tracks, Track->Path, etc.
• One file for the trie (the search structure).
• All files copied into PSRAM at startup, one after the other.
• Nothing checked the end of the 2 MB region. Past 8 MB, the chip's addresses wrap around onto the audio buffer.

Sizes depending on the collection size

On my real library (1,658 tracks, 28 GB of music), the index takes 568 KB: about 340 bytes per track. The search trie is 60% of it, the paths 20%:

File	Size
music_index.bin (search trie)	343 KB
path_index.bin	118 KB
track_index.bin (titles)	46 KB
relations, durations, track→album/artist…	61 KB

On the generated bench dataset (npm run bench -- prepare --tracks N), I get:

Tracks	Index	Search trie	Paths	Titles	Fits in 2 MB?
1,658 (my library)	568 KB	343 KB	118 KB	46 KB	✅
20,000	5.5 MB	2.7 MB	1.6 MB	0.6 MB	❌
100,000	25.1 MB	11.2 MB	8.0 MB	3.1 MB	❌

So the 2 MB region held about 7,300 tracks. A 128 GB card of 4-minute MP3s is around 21,000 tracks. And the boot time grew with the library: 13.9 s at 20,000 tracks, just to copy the index.

The new index

One pack file

The syncer now writes every table, and the trie, as sections of a single file:

"OPIX" | u16 version | u16 0 | u32 count | {u32 id, u32 offset, u32 length} * count
then the sections, 16-byte aligned

The podcast tables get their own podcasts.pack, since they're rebuilt separately. At boot, the firmware only opens the pack and reads its section table. Nothing is copied.

While I was at it, the tables changed to be cheap to read from the card:

• Ids are dense (0..count, already in alphabetical order), so the tables are indexed by id directly. The old string tables had an array of ids that was always 0, 1, 2… and every name lookup did a 15-step binary search in it. Gone.
• Relations store where each source's targets start, instead of how many there are. To find artist #3,000's tracks, the old code added up the counts of the 2,999 artists before it: thousands of reads.
• New letter tables: for the full lists (artists, albums, genres, tracks), where each 1-, 2- and 3-letter prefix starts. That's for the fast scrolling, below. They're tiny: 13 KB for 100,000 tracks.

The pack ends up a bit smaller than the old files: 562 KB for my library, 24.2 MB at 100k tracks (from 25.1).

A page cache in PSRAM

The firmware reads the pack through a cache (src/storage/PageStore.h):

• The 2 MB region now holds the podcast listening state (128 KB) and 480 slots of 4 KB.
• A page is a 4 KB block of the pack file, so small sections share pages.
• Each page can only go into one set of 4 slots (4-way set associative). That way there's no hash table to keep in RAM: the whole cache bookkeeping is 2.1 KB of RAM, and the RAM is the scarce resource (3.5 KB free at runtime).
• Within a set, eviction is CLOCK (second chance): a page used since the hand last passed it stays.
• A miss reads the page from the card in one go, then calls audioYield(), so a cold read never starves the audio fifo.

An old card (indexed by a previous syncer) shows "Library needs a re-sync".

What a page miss costs

That's where the bench was precious. The first version used 8 KB pages, read 512 bytes at a time through a stack buffer. On the device:

Version	One page miss	Slowest search keystroke (cold)
8 KB pages, 512-byte reads	26 ms	564 ms
+ 4 KB reads (borrowed buffer)	22 ms	469 ms
+ pack written contiguous	13 ms	340 ms
4 KB pages, one read each	6.5 ms	179 ms

Three things were going on:

1. Each SD read has a fixed cost. 16 reads of 512 bytes cost much more than one of 8 KB. I have no RAM left for a big buffer, but the audio buffer already has a 4 KB one for its SD → PSRAM chunks. Both only use it within one call of their own, so the page cache borrows it.
2. The pack was fragmented on the card. The syncer rewrote it in place, so the filesystem first reused the old file's clusters, then went elsewhere. Every seek then walks the cluster chain: 9 ms of a 22 ms miss. Now the syncer writes a new file and renames it over the old one. The firmware warns at boot when the pack isn't contiguous.
3. A search touches pages all over the pack: trie nodes, results, then the names and artists of up to 100 hits. It reads a few bytes from each page, so smaller pages are cheaper.

With the 26 ms misses, a cold keystroke took ~550 ms. Typing a few of them in a row right after a track started drained the audio buffer: 1,515 underruns in the search scenario. Now it's 0.

New fast scrolling

The idea is to jump from letter to letter. At the fastest level, a click jumps from first letter to first letter. A bit slower, from 2-letter prefix to 2-letter prefix (AB → AC). Then 3 letters (ABA → ABB). Then back to row by row. And the overlay shows the letters you're jumping by.

Getting the jumps right was the easy part. Making it usable ===> haard, specially I think because I'm just a mere programmer, not a UX guy.

First version: speed picks the tier

I started by trying to measure how fast people are scrolling and deduce the scrolling speed from it by measuring how many scroll events I get in a certain timeframe.

Problem 1: the speed depended on the UI load

On the main menu where there is nothing to update, I would get a looot of events on one revolution, but on the Tracks menu, with the overhard of loading the Tracks as I scroll, I would get much less for the same revolution, with my thumb runing around the wheel at the same speed ====> baaaad.

Two fixes:

• Each scroll event carries the time of the wheel sample its clicks were read in, and the speed is computed on that. A turn at 30 clicks/s reads 30 whether the wheel is read every click, or 3 clicks every 100 ms (there's even a test for it).
• The speed window is an angle, not a time: Compute the speed over a global angle, not over a period of time. I average over the last 12 clicks, wich is half a turn.

Problem 2: impossible to control

So I was using the current angular speed to determine the scrolling speed, which makes it feel like wearing ski boots while driving a car. Accelerates too fast, breaks abrutly, hard to go on the paste I want, impossible to scroll where I want. Tried different fine tuning, even designed a page for it, to tweak the gear speed changes, nothing worked.

I had some ideas:

• Acceleration to shift up? Even Wooorse
• Reset only when the finger lifts? Anooyyying
• Drop a tier when turning slowly for a while? Bad bad bad

Final version of the gearbox

So the right move is to use angular speed to switch gears up, and then let the user go at its own paste at this gear. Then to go switch a gear down, just measure the inactivity time and switch them back down one by one.

	How
Shift up	the average over the next half turn reaches the next gear's speed
In a gear	one click = one jump at that level, at any speed, both ways
Shift down	hold still: one gear down (finer prefix)
Back to rows	lift the finger

• One gear at a time, and each shift starts the half-turn window over. First letters take three deliberate half turns, and a flick only reaches the first gear.
• Turning back keeps the gear: you overshot to M, you step back to K letter by letter.
• Holding still switches a gear down: spin to get close, pause, step through the letters, pause, step through the 2-letter prefixes… The overlay shows each shift.
• Short lists have fewer gears: under 150 items only first letters, under 1,500 up to 2 letters. Under 3 screens, rows only (magic hat numbers)

The settings I ended up with, after tuning them using the page I built before:

Setting	Value
1st gear (3 letters)	16 clicks/s
2nd gear (2 letters)	28 clicks/s
3rd gear (first letters)	40 clicks/s
Speed window	12 clicks (half a turn)
Hold still to shift down	520 ms

The Scroll Tuning page

Tuning by flashing firmware would have been painful, so there's a page for it: Scroll tuning. It talks to the board running the bench firmware over Web Serial and sets everything live with #scrollcfg:

• a gauge of the wheel's speed with the three thresholds, and the last 10 seconds of scrolls colored by gear, so you see when you shift;
• a slider per setting, sent to the board as you move it;
• the wheel events as they come (touch, scroll, each gear and shift down), to check the real wheel and not only the remote;
• the values are remembered in the browser (the board forgets them on reboot), and "Copy as C++" gives the line to paste in fast_scroll.cpp.

Without a board, ?demo runs a model of the wheel and of the gears in the browser.

The jumps

Every list is in alphabetical order (the syncer sorts the ids the ICU way: case and accents ignored, spaces and punctuation before letters), so a prefix is one contiguous block. For the full lists, the next block's start comes from the letter tables. For scoped lists (an artist's albums, an album's tracks), the firmware reads names: it gallops forward (+1, +2, +4…) until the prefix changes, then bisects. That's a dozen reads even in a 5,000-row block.

The prefix ("key") of a title is computed the same way on both sides, by scroll_key in the syncer and fastScrollKey in the firmware, with shared test cases:

• a title that doesn't start with a letter is # (they all sort first)
• then letters uppercased, and anything else a space: A Day → A D

On the device

On my library (1,666 tracks, so all three gears), turning the wheel from the top of Tracks:

Turn	Speed	Result
1 turn in 3 s	8 clicks/s	24 rows
1 turn in 1.2 s	20 clicks/s	rows for half a turn, then 3-letter jumps, to "Ah…"
1 turn in 0.7 s	34 clicks/s	same: one turn only reaches the 1st gear
2 turns in 0.8 s	60 clicks/s	3, 2 then 1 letter, to "D…"
3 turns in 1.2 s	60 clicks/s	through to "Z…", the end of the list

Usage of the new benchmark capabilities

It has been super useful! I can let the AI take full control of the device: it flashes the firmware, drives the wheel with the virtual finger over serial, and measures at the same time. That gives reliable comparisons between versions, and makes it very easy to see the bottlenecks. The page miss table above is one afternoon of it.

New serial commands:

• #scrollcfg tunes the fast-scroll gears (s1= s2= s3= win= dwell=).
• #cache gives the page cache counters (hits, misses, time spent reading the card).
• #state now shows the overlay's letters and the highlighted row's key.
• Every scroll is echoed with its gear as #ev fast l=<letters> v=<clicks/s>, and so is each shift down (v=0).

The e2e tests check the gears too: a steady turn reaches 3-letter jumps, a fast spin shifts up gear by gear onto the start of a first-letter block, turning back slowly keeps the gear, holding still shifts down one, and a new touch starts over at rows.

Along the way it also found two bugs in the bench itself:

• The output the board prints while nobody reads the port loses bytes. An answer could then end up glued to a truncated log line (…max20#ok state …), and the host never saw it.
• The bench answered a button gesture as soon as its last keyframe played, about 20 ms before the wheel's debounce reported the release. So the tests saw a down without its up.

Results

The 100,000-track card against the previous run (6,000 tracks, everything in PSRAM):

	Before (6k tracks)	Now (100k tracks)
Boot to ready	5.6 s	3.1 s
Library index load	2.4 s	0.17 s
Search index load	2.0 s	0.008 s
Fast scroll burst (p95)	67 ms	39 ms
Underruns, all scenarios	0	0
Slowest search keystroke (cold)	45 ms	179 ms
Open a list (p95)	865 ms	1.0 s
Scroll one row (p95)	63 ms	76 ms

The last three are the price of reading from the card: the first time you type a letter or open a list, its pages come from the SD. The next step is to load the most used parts of the index (artist and album names, the letter tables, the top of the trie) into the cache while the device is idle after boot.