List virtualization (windowing)

Deep dive

How it works

In: scroll offset, viewport size, overscan, per-item heights (estimated, then measured) · Out: half-open index range [first, last) to render, each item's top offset, total scroll extent · State: item heights and their Fenwick tree, a pool of recycled views · Cost: O(1) fixed size, O(log N) variable size per lookup; O(visible) per frame

1. Hold only data: N and a height per item (estimate until measured). Total extent = sum of heights; give the scroll container that size with a spacer element or contentSize.
2. On scroll, map the offset to an index: floor(y / size) for fixed sizes, otherwise find the item whose cumulative range contains y (prefix sums; Fenwick descent in the code below).
3. Do the same for y + viewport - 1 for the last index, then widen by overscan items on both sides.
4. Diff against the rendered set: items leaving go to a pool, entering items take a pooled view of the same type and are bound to the new data (recycling) or are created fresh (create/destroy).
5. Position each item at offset_of(i): absolute translateY, or one padding/spacer block before the first rendered item and another after the last.
6. When an item is measured, store its real height, update the tree (O(log N)), and if it lies above the first visible item, shift scroll so the anchor keeps its screen y.
7. Key views by item identity, not slot, so state (input text, expansion, selection) follows the item.

Grids do this per axis: rows and columns each get a window (one tree per axis, or arithmetic if uniform), and the rendered cells are the cross product of the two ranges. Sticky headers are found by binary search over section start indices; the header of the section containing the first visible item is rendered and pinned even when its natural position is off-screen.

Code

/// Variable-height list: Fenwick tree over item heights (integer px, each >= 1).
pub struct VList {
    n: usize,
    h: Vec<i64>,    // current height of every item (measured or estimated)
    tree: Vec<i64>, // 1-based Fenwick tree of h
}

impl VList {
    pub fn new(n: usize, estimate: i64) -> Self {
        let mut tree = vec![0i64; n + 1];
        for i in 1..=n {
            tree[i] += estimate;
            let j = i + (i & i.wrapping_neg()); // parent in the Fenwick tree
            if j <= n { tree[j] += tree[i]; }   // O(N) build
        }
        VList { n, h: vec![estimate; n], tree }
    }

    /// Top edge of item i = sum of heights of items 0..i.
    pub fn offset_of(&self, i: usize) -> i64 {
        let (mut s, mut k) = (0, i);
        while k > 0 { s += self.tree[k]; k &= k - 1; }
        s
    }

    pub fn total(&self) -> i64 { self.offset_of(self.n) } // scroll-extent (spacer height)

    /// Index of the item containing y (clamped): binary lifting on the tree, O(log N).
    pub fn index_at(&self, y: i64) -> usize {
        let (mut pos, mut rem) = (0usize, y.max(0));
        let mut step = self.n.next_power_of_two();
        while step > 0 {
            let next = pos + step;
            if next <= self.n && self.tree[next] <= rem { pos = next; rem -= self.tree[next]; }
            step >>= 1;
        }
        pos.min(self.n - 1) // pos = number of items that end at or before y
    }

    /// Items to render for a viewport [scroll, scroll+viewport), plus `overscan` items each side.
    pub fn visible_range(&self, scroll: i64, viewport: i64, overscan: usize) -> (usize, usize) {
        let first = self.index_at(scroll);
        let last = self.index_at(scroll + viewport - 1);
        (first.saturating_sub(overscan), (last + overscan + 1).min(self.n)) // half-open
    }

    /// An item was measured: O(log N) update. Returns the height delta.
    pub fn set_height(&mut self, i: usize, new_h: i64) -> i64 {
        let d = new_h - self.h[i];
        self.h[i] = new_h;
        let mut k = i + 1;
        while k <= self.n { self.tree[k] += d; k += k & k.wrapping_neg(); }
        d
    }

    /// Same, but keep the first visible item at the same screen y (scroll anchoring).
    pub fn set_height_anchored(&mut self, i: usize, new_h: i64, scroll: &mut i64) {
        let anchor = self.index_at(*scroll);
        let screen_y = self.offset_of(anchor) - *scroll;
        self.set_height(i, new_h);
        if i < anchor { *scroll = self.offset_of(anchor) - screen_y; }
        // i == anchor: its top edge does not move; i > anchor: nothing above changed
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn matches_linear_scan_and_covers_viewport() {
        let mut s = 12345u64;
        let mut rnd = move || { s ^= s << 13; s ^= s >> 7; s ^= s << 17; s };
        let n = 1000;
        let mut l = VList::new(n, 30);
        for _ in 0..2 * n { l.set_height(rnd() as usize % n, 1 + (rnd() % 200) as i64); }
        let total = l.total();
        for _ in 0..1000 {
            let y = (rnd() % total as u64) as i64;
            let mut acc = 0;
            let brute = l.h.iter().position(|&x| { acc += x; acc > y }).unwrap();
            assert_eq!(l.index_at(y), brute);
            let (a, b) = l.visible_range(y, 800, 3);
            assert!(l.offset_of(a) <= y && l.offset_of(b) >= (y + 800).min(total));
        }
        // anchoring: re-measuring an item above the first visible one must not move it on screen
        let mut scroll = total / 2;
        let first = l.index_at(scroll);
        let screen_y = l.offset_of(first) - scroll;
        l.set_height_anchored(first / 2, 500, &mut scroll);
        assert_eq!(l.index_at(scroll), first);
        assert_eq!(l.offset_of(first) - scroll, screen_y);
    }
}

index_at is the Fenwick binary-lifting descent: it counts the items whose bottom edge is at or above y without computing a prefix sum. Heights are integers, so updates never drift. The test compares against a linear scan, checks viewport coverage and anchoring.

Complexity and constants

• Build O(N); offset_of, index_at, set_height O(log N); visible_range is two descents.
• Memory here: 8 bytes per item for the tree plus 8 for the height array (u32 halves both).
• Measured on this Mac (Apple M4 Pro), release build, N = 1,000,000, random heights 20-99 px, random scroll positions, 900 px viewport, overscan 5: visible_range 140-190 ns (3 runs); set_height 24-34 ns; a single index_at 110-200 ns; a naive linear-scan index_at 133-158 µs. That is about 1000x. The tree is 8 MB; why visible_range (two descents) costs little more than one index_at was not profiled.
• Cost driver: not the lookup but creating, binding and laying out about viewport / avg_height + 2 * overscan items per frame.

Efficiency

• Cost: per frame, one range lookup (about 150 ns at N = 1M, measured above) plus bind and layout of the visible items; no work grows with N except the tree update on re-measure (about 30 ns, measured). Bound: view creation, binding and layout, not indexing.
• Levers:
  • view recycling / pooling — skips inflation and construction per scrolled-in row (RecyclerView docs: reuse "can drastically improve performance by skipping initial layout inflation or construction") — homogeneous row types
  • fixed or prototype item size — O(1) offset arithmetic and no re-measure jumps — uniform rows (Flutter ListView.builder takes itemExtent, prototypeItem)
  • overscan — hides blank flashes during fast scrolls at the price of more items per frame — tune to scroll speed and bind cost
  • content-visibility: auto — browser skips rendering of off-screen subtrees; web.dev's demo reports a 7x rendering boost on initial load — long static pages where DOM size is acceptable
• Naive → standard → state of the art:
  • render all N children · O(N) nodes, memory and layout on every change
  • fixed-size window with a spacer · O(1) lookup, O(visible) per frame
  • measured heights in a Fenwick tree, recycling, anchoring, overscan tuned to velocity · O(log N) lookup and update, O(visible) per frame, no scroll jumps

Implementation notes

• Position children absolutely (transform) rather than with margins: moving the window changes only offsets.
• Browsers cap the height of a scrollable element, so extents of millions of rows can exceed it (the limit differs per browser; from memory, not verified here); then map a smaller scrollbar range to the real offset.
• One pool per item type (header, row, ad).
• Measure after layout (ResizeObserver, onLayout) and batch height updates per frame.
• A width change invalidates every measured height; reset to estimates and re-measure lazily.

Pitfalls

• Wrong estimate: scrolling into unmeasured territory makes the thumb and content jump. Anchor, and estimate from the measured average.
• Blank gaps during flings: the window follows the scroll one frame late. Raise overscan, or render a cheap placeholder.
• Reused views keep old state: images, text fields, animations and expansion flags from the previous item flash up unless reset on bind or stored in the model keyed by item id.
• Accessibility and search: virtualized items are absent from the DOM or accessibility tree, so find-in-page misses them and screen readers announce a wrong list length. On the web set aria-setsize/aria-posinset or grid aria-rowcount/aria-rowindex and offer in-app search. MDN notes that content-visibility: auto keeps skipped content available to find-in-page, tab order and selection; hidden does not.
• Float heights drift in an incremental tree: store integers. Zero heights make a position ambiguous: clamp to at least 1.
• A focused element that scrolls out of the window is destroyed; keep its view alive.

Variants and alternatives

In production

• Android RecyclerView (view holders, scrap and recycled-view pool), iOS UITableView / UICollectionView (dequeueReusableCell), Flutter ListView.builder and slivers (builder called only for visible children; SliverList places offsets by "dead reckoning" because off-screen children are not materialized).
• Web: react-window, TanStack Virtual (headless; vertical, horizontal and grid), react-virtuoso.
• Data grids: AG Grid describes its DOM virtualisation as the way it keeps rendering fast on large row counts.

Implementations

Sources

• Peter M. Fenwick, A new data structure for cumulative frequency tables, Software: Practice and Experience 24(3), 1994. DOI 10.1002/spe.4380240306 (Crossref-verified; publisher link blocks scripted access).
• Android Developers, RecyclerView, API reference. docs
• Apple, dequeueReusableCell(withIdentifier:for:), UIKit. docs
• Flutter, ListView.builder constructor and SliverList class. ListView.builder · SliverList
• MDN, content-visibility. docs
• web.dev, content-visibility: the new CSS property that boosts your rendering performance. article
• AG Grid, DOM Virtualisation. docs
• TanStack Virtual docs · code; react-window code