Windowing a long list

The idea

A browser does not care how many rows are in your array. It cares how many are in the document. Put a hundred thousand rows in and the page takes seconds to lay out, eats memory, and janks on every scroll.

But a screen only ever shows a dozen or so. So keep the rows in the array, and put only the visible slice in the document. Two numbers do the work: which row is at the top of the viewport, and which is at the bottom. Everything outside that range becomes empty padding, sized so the scrollbar still tells the truth about how long the list is.

Then one refinement makes it smooth: reuse the row components you already have instead of destroying and building them on every frame.

How it works

With one fixed row height, both ends of the window are arithmetic. No measuring, no layout read, no loop over the data.

def window(scroll_top, viewport_h, row_h, total, overscan=2):
    first = scroll_top // row_h
    last  = (scroll_top + viewport_h - 1) // row_h
    # overscan: render a little past each edge so a fast scroll never
    # exposes an unrendered gap for a frame
    start = max(0, first - overscan)
    end   = min(total - 1, last + overscan)
    return start, end, start * row_h, (total - 1 - end) * row_h
    #      ^ rows to render        ^ pad above     ^ pad below

When rows differ in height, first is no longer a division. Keep a prefix sum of heights, where offsets[i] is where row i starts, and binary search it for the largest i with offsets[i] <= scroll_top. That turns an O(n) walk into an O(log n) search, and the prefix array is the thing worth caching.

Cost

Watch out for

• The half-visible row at each edge. The last visible index is computed from scroll_top + viewport_h, and a row straddling the bottom edge is still visible. Using // on the bottom edge without the - 1, or forgetting to include the partial row at all, leaves a one-row gap that only appears at certain scroll positions.
• Padding that lies about the length. The spacer above and below is what gives the scrollbar its size. Get it wrong and the scrollbar shrinks as you scroll, or the list ends before the data does. Pad by exact row heights, never by a guess.
• No overscan, so fast scrolling flashes blank. Rendering exactly the visible range means a scroll event that outruns the next paint shows nothing. A margin of two or three rows on each side is cheap and removes the artifact.
• Recycled components keeping state. Reusing a component means its internal state comes with it. A row that was expanded, focused, or mid-edit will show that state on whatever data lands in it next unless the assignment resets it. Keying by data id rather than by slot is what makes this correct.
• Content that changes height above you. An image loading, or a row expanding, higher up the list shifts everything below it, and the row you were reading jumps. Anchoring means remembering which row was at the top and restoring the offset from it after the change, rather than restoring the raw pixel offset.

Worked example

A log viewer holds 100,000 lines at 26 pixels each: a document 2.6 million pixels tall. The viewport is 208 pixels, which is exactly eight rows, and the overscan is two rows at each end.

Scroll to pixel 500,000. That is not a row boundary. Row 19,230 begins at 499,980, so its last six pixels are still on screen and the window straddles a partial row at each end. first = 500000 // 26 = 19230 and last = (500000 + 207) // 26 = 19238, so nine rows are touched rather than eight. Add the overscan and the render range is 19,228 through 19,240: thirteen rows in the document. Pad 19,228 x 26 pixels above and the remaining rows below, and the scrollbar is still exactly where it should be.

The eight-versus-nine detail is the whole reason the bottom edge uses + viewport_h - 1. A viewport only shows a whole number of rows when it happens to be scrolled to a boundary, and the rest of the time it shows one more, partly.