Virtualization Isn't Enough: Making Long Lists Actually Fast

Imagine a chat with a hundred thousand messages. Twenty of them fit on the screen.

If you create a DOM element for every message, the browser has to keep track of all hundred thousand elements, even though the user sees only a small part of the history. Virtualization solves this problem: it keeps the visible messages and a small buffer around them in the DOM, and represents the rest of the space with an empty block called a spacer.

The screen still feels like a long history, but the browser doesn't have to render every message at once.

Virtualization doesn't solve every problem

To show the right messages, the component has to figure out which rows fall inside the viewport. If every row has the same height, that's easy:

const index = Math.floor(scrollTop / rowHeight)

But chat messages vary. One takes up two lines, another takes twenty. An image may load after the text, and resizing the window changes how lines wrap. A message's height isn't known precisely until it has been rendered.

So a virtual list has to solve three related but distinct problems:

1. Quickly find the row that corresponds to a given scroll position.
2. Update a row's height once its actual size becomes known.
3. Keep the message being read in place when the heights of rows above it change.

You can find rows quickly and still get scroll jumps. You can preserve the reading position and still spend too much time computing coordinates. A reliable list needs both solutions.

How virtualization works

A virtual list usually contains a full-height spacer and a separate container with the visible rows. The container is offset by the distance from the top of the list to the first rendered row.

History:  [ hidden rows ][──── viewport ────][ hidden rows ]

DOM:                     [visible + buffer]

Spacer:   ···············│                  │··············
                         ↑ window start

The visible range is often extended by a few rows above and below. This buffer is called overscan: it helps avoid blank areas during fast scrolling.

In simplified form, the markup might look like this:

<div style={{ height: totalHeight }}>
  <div style={{ transform: `translateY(${top}px)` }}>
    {visibleRows}
  </div>
</div>

Here, totalHeight is the combined height of the entire history, and top is the coordinate where the first rendered row begins. A real component also has to handle container positioning, row measurement, and size updates.

If every row's height is known and fixed, finding the window is easy. With variable heights, it gets harder: you need to quickly determine which row contains scrollTop, and then the coordinate where the window starts.

Let's start with a simple solution and add complexity only when we hit a concrete limitation.

Step 1. Linear scan: simple while the list is small

The most obvious approach is to add up message heights from the top of the list until the running total reaches scrollTop.

function findRowLinear(heights: number[], scrollTop: number) {
  let top = 0

  for (let i = 0; i < heights.length; i++) {
    const bottom = top + heights[i]

    if (bottom > scrollTop) {
      return { index: i, top }
    }

    top = bottom
  }

  // The list is empty, or the coordinate lies beyond the end of the list.
  return { index: -1, top }
}

The algorithm checks rows one by one. If the user is near the top of the list, the search finishes quickly. If they've scrolled almost to the end of the chat, it has to check nearly all hundred thousand messages.

In the worst case, lookup time is proportional to the number of rows: O(n).

Start of list                                        End
[1][2][3][4][5][6][7][8][9][10] ... [99991] ... [100000]
 └───────────────────────────────────────────────→ search

The problem isn't the number of DOM elements: virtualization has already capped that. The problem is that computing the visible window still walks the entire list to find a row.

You can cut some overhead by storing heights in a Float64Array, maintaining a running total height, and not recomputing the same values multiple times in a single pass. These are useful optimizations, but they don't change the asymptotic complexity: lookup still takes O(n).

Takeaway: a linear scan is a good simple starting implementation and a baseline for comparison. A large list needs a way to find a row without visiting every row before it.

Step 2. Prefix sums: fast lookup, expensive updates

A row's height is also the distance to the next row. If you add up the heights of all rows before row k, you get the coordinate of its top edge.

For example, for heights [40, 60, 30, 70], the boundary coordinates are:

Rows:        [   40   ][     60     ][  30  ][      70      ]
Boundaries:  0        40            100    130             200

Let's build a prefix sum array:

const heights = [40, 60, 30, 70]
const prefix = [0, 40, 100, 130, 200]

prefix[k] is the total height of the first k rows. So you can get the start coordinate of a row in O(1), and since the boundary coordinates are sorted, you can find a row with binary search in O(log n).

Say scrollTop = 115. The largest boundary that doesn't exceed 115 is 100. So the visible area starts in the third row (counting from one), 15 pixels below its top edge.

But now imagine that, once measured, the first row turns out to be 10 pixels taller than estimated:

Before: [0, 40, 100, 130, 200]
After:  [0, 50, 110, 140, 210]
             └── every later boundary shifted

To update the prefix array, you have to change every value after it. In the worst case, a single measurement costs O(n).

Chat message heights are refined after rendering and can change again when an image loads or the window is resized. So updates aren't an exception — they're a normal part of the component's work.

Takeaway: prefix sums work well when data rarely changes. A list with frequent measurements needs a structure that updates only the affected sums.

Step 3. Fenwick tree: fast queries and point updates

A Fenwick tree doesn't store every prefix sum; it stores a set of partial sums. Each node covers a specific range of elements. To get the sum of the first k rows, you add up just a few of these ranges.

For eight rows, the node ranges look like this. Tree indices start at one:

Node:      1     2      3      4       5      6       7       8
Range:    [1]  [1–2]   [3]   [1–4]    [5]   [5–6]    [7]   [1–8]

For example, to get the sum of the first seven rows, you only need nodes 7, 6, and 4:

7 → 6 → 4 → 0

[7] + [5–6] + [1–4] = sum of rows [1–7]

Instead of seven additions, you do three. For larger arrays, the number of steps grows logarithmically.

Why do the jumps work this way? The length of node i's range is i & -i — the value of the lowest set bit of i. For example, 6 in binary is 110, and its lowest set bit is 2. So node 6 stores the sum of elements 5 and 6.

Updating the height of a single row

If row 6's height changes, you only need to update the nodes whose ranges include that row. For eight elements, the update path looks like this:

Update row 6:
6 → 8 → done

We store the raw heights separately so we can compute the difference between the new and old values.

function prefixSum(count: number) {
  let sum = 0

  for (let i = count; i > 0; i -= i & -i) {
    sum += tree[i]
  }

  return sum
}

function setHeight(index: number, nextHeight: number) {
  const delta = nextHeight - heights[index]
  heights[index] = nextHeight

  for (let i = index + 1; i <= heights.length; i += i & -i) {
    tree[i] += delta
  }
}

Here, index is the zero-based row index, while the tree's internal indices start at one. The code assumes tree has already been built and holds correct partial sums.

Both the prefix query and the point update take O(log n). Unlike a prefix sum array, a Fenwick tree doesn't require updating every subsequent prefix sum when a row's height changes.

Finding a row by coordinate

Finding the sum of the first k elements and finding an index for a given sum are different problems. For the second one, you can do a binary lifting search over the Fenwick tree: check powers of two from largest to smallest, and take the next range if its sum fits into the remaining offset.

function findByOffset(offset: number) {
  if (heights.length === 0) return -1

  const total = prefixSum(heights.length)
  if (offset >= total) return heights.length - 1
  if (offset <= 0) return 0

  let position = 0
  let remaining = offset
  let step = 1

  while (step * 2 <= heights.length) step *= 2

  for (; step > 0; step >>= 1) {
    const next = position + step

    if (next <= heights.length && tree[next] <= remaining) {
      position = next
      remaining -= tree[next]
    }
  }

  // position is the number of rows lying entirely before offset.
  // With positive heights, this is the zero-based row index.
  return Math.min(position, heights.length - 1)
}

This search assumes heights are non-negative, the tree is built correctly, and offset is given in list coordinates. In a production component, the boundaries need to match your chosen semantics: for example, which row counts as active when the coordinate lands exactly on a row's bottom edge. An empty list and coordinates near the end also need explicit handling.

Where a Fenwick tree stops being convenient

A Fenwick tree is great when heights are updated one at a time. But suppose the app switches display modes and needs to add the same amount to the height of an entire range of rows at once.

If you perform a hundred thousand individual updates, the total work is O(n log n). The plain Fenwick tree in this implementation can't apply a single operation to an arbitrary range in O(log n).

Takeaway: if the main workload is coordinate lookups and individual height changes, a Fenwick tree offers a good balance of speed and simplicity. If you need frequent updates to whole ranges, consider a segment tree.

Step 4. Segment tree: range updates in O(log n)

A segment tree divides an array into ranges. The root represents the whole list, its children represent the left and right halves, and the leaves represent individual rows. Each node stores the total height of its range.

                        [1–8]
                 sum of all eight rows
                    /             \
                 [1–4]             [5–8]
                /     \           /     \
             [1–2]   [3–4]      [5–6]   [7–8]

To find the row at a given coordinate, compare the coordinate with the total height of the left subtree. If it's smaller, the target row is on the left. Otherwise, subtract the left half's sum and go right. Each step halves the range, so lookup takes O(log n).

Lazy updates

Now imagine you need to add 5 pixels to the height of every row in the range [1–8].

A naive approach would update all eight leaves. But the root already represents the entire range. It's enough to increase its sum by 8 × 5 and record the addition in a pending field to propagate later.

Before:                After adding +5:

       [1–8]                  [1–8, pending +5]
      /     \                 /               \
  [1–4]   [5–8]           children not updated yet

This technique is called lazy propagation. The node's sum already reflects the change, but its children haven't been updated yet. When the algorithm needs to descend to the children, it first pushes the accumulated addition down to them.

In simplified form, applying a change looks like this:

function apply(node: number, left: number, right: number, delta: number) {
  sum[node] += (right - left + 1) * delta
  pending[node] += delta
}

A range update follows three rules:

1. If the node doesn't overlap the target range, skip it.
2. If the node lies entirely inside the range, update its sum and pending addition without descending to the leaves.
3. If the node is only partially covered, push the pending addition down to its children, update the relevant subranges, and recompute the node's sum.

function addRange(
  node: number,
  left: number,
  right: number,
  from: number,
  to: number,
  delta: number
) {
  if (to < left || right < from) return

  if (from <= left && right <= to) {
    apply(node, left, right, delta)
    return
  }

  push(node, left, right)

  const middle = Math.floor((left + right) / 2)

  addRange(node * 2, left, middle, from, to, delta)
  addRange(node * 2 + 1, middle + 1, right, from, to, delta)

  sum[node] = sum[node * 2] + sum[node * 2 + 1]
}

This snippet illustrates the core idea. A full implementation should also include building the tree, bounds checking, handling an empty list, and a push function that passes the pending change down to the children and resets the current node's pending.

A key invariant: sum[node] already accounts for pending[node], but the children's sums may not include that addition yet. If you forget to push it down before descending, queries will start returning wrong sums.

For any range, the tree visits only a bounded number of nodes per level, so adding to a range takes O(log n). A point height update also takes O(log n).

There's an important caveat, though: this advantage applies only when a single operation can be applied uniformly across the range — for example, adding the same amount to every row. If resizing the window makes each message wrap differently and end up with its own new height, the tree doesn't spare you from measuring those rows. It speeds up storing and updating the values, but it doesn't eliminate the work needed to obtain them.

Takeaway: a segment tree is justified when the app genuinely needs frequent range updates. If only individual rows change, a Fenwick tree is usually simpler.

Comparing the structures on the same set of operations

Let's put the properties of these solutions into a single table. Here, "find a row by coordinate" means locating a row at a given coordinate while accounting for heights, and "add a value to a range" means applying the same addition to every row in a range.

Structure	Find a row by coordinate	Update a single height	Add a value to a range
Height array with linear scan	O(n)	O(1)	O(n)
Prefix sum array	O(log n)	O(n)	O(n)
Fenwick tree	O(log n)	O(log n)	O(n log n) via individual updates
Segment tree with lazy propagation	O(log n)	O(log n)	O(log n)

These complexities describe algorithmic work, not guaranteed time in milliseconds. On a real device, results depend on the implementation, available memory, the browser, the number of measurements, and the work performed by the UI itself.

What the measurements show

In the original experiment with 100,000 rows, finding the window near the end of the history took about 50 ms with the naive scan and about 3–4 µs with the indexed structures. Updating the height of a row near the start of the history took about 387 µs with prefix sums and about 2 µs with either the Fenwick tree or the segment tree. Adding a value to the entire range took about 7.6 ms with the Fenwick tree and about 2 µs with the segment tree.

These are results from a specific microbenchmark, not universal properties of the data structures. Before publishing numbers like these, you should include the benchmark code and specify the runtime environment, the number of iterations, the warm-up method, and how the final values were calculated. Without that information, the numbers are hard to verify independently.

A separate scrolling run in headless Chrome with a 6× CPU slowdown produced the following results:

Step	p95 frame time	Frames over 20 ms
Naive scan	248 ms	28 of 29
Height array	24 ms	28 of 312
Prefix sums	18 ms	0 of 455
Fenwick tree	18 ms	5 of 425
Segment tree	18 ms	6 of 448

These numbers are also specific to the test environment. They show that switching from a linear search to an indexed data structure significantly improved performance in this run, while switching between indexed structures had little effect on the p95 frame time.

Why? Once one bottleneck is removed, another part of the UI can become the limiting factor: row measurement, React component updates, layout, or painting. Speeding up the data structure doesn't necessarily speed up the whole frame by the same factor.

Practical takeaway from the benchmark: choose a more complex structure for the operations it actually speeds up. Don't adopt a segment tree just hoping it will automatically make scrolling smoother.

Correct sums don't guarantee correct scrolling

Even with a fast height index, a virtual list still has another problem: the height of an off-screen row may be unknown.

Until a row is rendered, the component uses an estimate. When the row appears, ResizeObserver lets you get its actual size and update the height index.

But if a row above the viewport becomes 12 pixels taller, the coordinates of every row after it also increase by 12 pixels. Without compensation, the user sees a jump: the message they were reading moves.

Height of a row above viewport:  +12 px
Scroll position:                 +12 px
Visible message:                 stays in place

If the height of a row above the anchor grows by delta and the reading position must be preserved, the scroll position is usually adjusted by the same amount. Keep the sign in mind: if the row got shorter, the adjustment is negative.

Preserve an anchor, not just a pixel count

For reliable compensation, it helps to remember the first visible row and the offset within it. After heights change, the component recomputes that row's coordinate and restores the previous offset within it.

This is more robust than blindly adding every change to scrollTop: several rows may change during a single cycle, the user may scroll manually, and measurements may arrive in a different order from the one in which they were requested.

The same principle applies when loading older messages at the top. If rows are prepended before the current history, you need to keep the anchor message in place. First update the total height calculation and the spacer size, and only then restore the scroll position. Otherwise, the new scrollTop value may exceed the old content height, and the browser will clamp it.

The browser may also try to preserve the scroll position automatically through scroll anchoring. If your component manages the anchor itself, check how it interacts with the CSS overflow-anchor property so the browser and the app don't both compensate for the same change.

There's also a special case: the user is at the bottom of the chat. In that case, you usually want to keep the view anchored to the bottom rather than preserve the position of a specific message — provided that this matches your product's intended behavior. If the user is reading older messages, new messages shouldn't force them back to the bottom.

A practical sequence of steps

Don't start with the most complex structure. Evolve the solution as real limitations surface.

1. Implement virtualization. Render only the visible rows and a small buffer around them.
2. Start with a simple height model. Verify that coordinates and edge cases are correct.
3. Measure performance. Make sure that row lookup or height updates are actually the bottleneck.
4. Choose a structure that fits your update pattern. Prefix sums suit data that rarely changes, a Fenwick tree suits frequent point updates, and a segment tree suits frequent range updates.
5. Solve scroll jumps separately. Keep a reading anchor and compensate for height changes correctly.
6. Measure again. Compare not only the data-structure microbenchmark but also the behavior of the full UI.

A good virtual list is more than just a small number of DOM nodes. It computes coordinates quickly, handles variable heights correctly, and keeps the reader's place when content changes.

The most complex structure isn't always the most useful one. The best solution is the one that removes the measured bottleneck, keeps the UI behaving correctly, and doesn't add unnecessary complexity.

Code for this article: godfreyd/virtual-list-fenwick.