Virtualized list

Rendering a list with 100,000 items is impossible naively — the frame budget is 16ms and iterating every row would blow past that on even a warm cache. The trick is to render only the items you can see, which on a 40-row viewport is 10–50 out of 100,000. The hard part is mapping a scroll offset to “which row is at the top” when every row may have a different height.

VirtualizedList is another surface where the intelligence layer is visible to app authors. It solves this with two data structures:

• A Fenwick tree (binary indexed tree) gives O(log n) queries for prefix sums of row heights. Scroll offset → item index becomes a single search.
• A Bayesian height predictor with conformal bounds fills in heights for items you have not measured yet. It provides a 95%-confidence interval for each unknown height, so you can allocate realistic space without having touched the row.

Together they let the widget render only the visible rows, even when heights are variable and most rows have never been measured.

The math behind the height predictor is covered on bayesian-inference / height-prediction. This page focuses on the widget itself.

Source: virtualized.rs:45 (3,400+ lines).

Why the obvious approach fails

A naive list:

for item in &items {
    if in_viewport(item, scroll) {
        draw(item);
    }
}

is O(n) and scans every item even though most are off-screen. With 100K items and a 40-row viewport that is 99,960 wasted comparisons per frame, times 60 FPS, times whatever layout cost each measurement has. You cannot afford it.

Fenwick tree for O(log n) scroll mapping

A Fenwick tree indexes the list by cumulative height. Querying the cumulative height up to index i is O(log n). Inverting — “given a Y coordinate, which index is at that row?” — is also O(log n) via binary search on the tree structure.

Source: fenwick.rs.

The tree supports:

• update(i, new_height) — O(log n). Called when an item’s measured height changes.
• prefix_sum(i) — O(log n). Sum of heights [0, i).
• find_by_prefix(y) — O(log n). Smallest i such that prefix_sum(i) > y.

That last operation is the workhorse. Each frame, the widget calls find_by_prefix(scroll_offset) to decide which item starts at the top of the viewport, then walks forward drawing until the cumulative height exceeds viewport height.

For the variable-height version — used when most rows need measurement on first display — see VariableHeightsFenwick.

Bayesian height predictor

Not every row has a real measurement. A freshly-loaded list of 100K has measurements for the 50 rows currently visible and nothing else. The Fenwick tree still needs a height for every entry.

The height predictor (height_predictor.rs) maintains the empirical distribution of measured heights (mean, variance) and returns predictions for unmeasured rows plus a 95%-confidence interval:

The interval is a conformal bound — it is calibrated from recent measurements rather than assuming any parametric distribution.

Concretely, when a row is first loaded:

1. Predictor returns (mean, lo, hi).
2. Fenwick tree stores mean for that row.
3. The moment the row becomes visible, real measurement replaces the estimate.
4. Predictor updates with the new sample.

The state

Source: virtualized.rs:1689.

pub struct VirtualizedListState {
    pub scroll_offset: usize,    // item index at top of viewport
    pub selected: Option<usize>, // currently selected item, if any
    pub overscan: usize,         // extra items to render above/below viewport
    pub item_height: ItemHeight, // Fixed | Variable | VariableFenwick
    pub visible_range: Option<Range<usize>>,  // cached for this frame
}

• scroll_offset is expressed in item index, not pixels. The Fenwick tree converts as needed.
• overscan renders a few items just outside the viewport so a scroll event of one step doesn’t momentarily paint blank rows.
• item_height picks a strategy:
  • Fixed(h) — all rows are the same height; no Fenwick needed.
  • Variable — uses a naive prefix-sum cache, O(n) worst case.
  • VariableFenwick — the full machinery.

Render path

Each frame the widget:

Worked example

A log viewer over a 200,000-row log file. Rows may wrap; heights vary from 1 to 6 rows.

use ftui_widgets::virtualized::{VirtualizedList, VirtualizedListState, ItemHeight};
 
pub struct Model {
    pub rows: Vec<LogRow>,
    pub list_state: VirtualizedListState,
}
 
impl Default for Model {
    fn default() -> Self {
        Self {
            rows: Vec::new(),
            list_state: VirtualizedListState {
                scroll_offset: 0,
                selected: None,
                overscan: 3,
                item_height: ItemHeight::VariableFenwick,
                visible_range: None,
            },
        }
    }
}
 
fn view(&self, frame: &mut ftui_render::frame::Frame) {
    use ftui_widgets::StatefulWidget;
    let area = frame.buffer.bounds();
    let list = VirtualizedList::new(&self.rows)
        .render_item(|row, area, frame| draw_log_row(row, area, frame));
    StatefulWidget::render(&list, area, frame, &mut self.list_state);
}

Memory-wise, you are carrying 200K rows of data plus a 200K-entry Fenwick tree (≈ 1.6 MB for u64 heights). Render time is constant in list size.

Performance targets

On a modern laptop CPU the widget hits:

• 100,000-row list, 40-row viewport, mixed heights: < 2 ms per frame
• Scroll by one row: amortised O(log n)
• Full resize to a new viewport height: O(visible)

The dominant cost is the render closure itself, not the virtualization machinery.

Pitfalls

• Using Variable instead of VariableFenwick for large lists. The naive prefix cache is O(n) worst case; it will bite you somewhere past a few thousand rows.
• Changing row heights after render. The Fenwick tree is updated during render. Mutating heights in update() leaves the tree stale until the next render. Keep height derivation inside the item’s own render closure if possible.
• Forgetting to clamp scroll_offset externally. If your update() sets scroll_offset past the end, the next render will clamp it — correct, but the user sees one frame of “stuck at end”.
• Not resetting visible_range when the list changes. If your data grew by 1,000 rows, the cached visible range from last frame may be stale. Set visible_range = None whenever the underlying data changes length.
• Trying to scroll by pixel. scroll_offset is in item units; the Fenwick tree handles pixel conversion. Mixing units is the most common source of off-by-one bugs.

Where next