How does Elm Virtual DOM reconciliation handle massive nested lists with keys?

Answer first

With stable, cheap keys Elm can reconcile a reordered massive nested list with moves instead of delete/add pairs, and each nesting level is reconciled independently in linear time per level. The measurable cost is the key map build plus key computation per item, not a free optimization. Without keys Elm falls back to index-based comparison, which causes unnecessary teardown and recreation when items shift, especially harmful for deep sub-trees that hold focus, scroll or timers.

Confirmed facts

• Elm 0.19 Virtual DOM diff first matches by tag name, then by key when a keyed node is used. Keyed nodes are created via Html.Keyed.node / Html.Keyed.map. The runtime builds a map from old keys to indices and reconciles in O(n) per list where n is the number of items in that list.
• Each nesting level runs its own reconciliation pass. Total work is the sum of work at each depth, i.e., proportional to total element count across all nesting levels.
• Without keys Elm uses positional comparison. Reordering therefore produces delete then insert pairs for the moved range.
• Keys must be comparable and stable across renders. The key function is evaluated on every render for every item in the list.

Likely explanation and uncertainty

The question mentions Html.mapList with a keys function. That API does not exist in Elm 0.19. The closest pattern is manual keyed nodes. Assuming you mean keyed nodes, the performance impact is two sided.

Likely overhead:

• Map construction and key lookup per list level adds constant work per item.
• If the key function is cheap, e.g., returning an Int id, the overhead is small and the benefit of avoiding subtree recreation dominates on reorders.
• If the key function traverses nested data or allocates, cost becomes O(n * k) where k is key computation time, which can dominate reconciliation for massive lists.

Uncertainty: Elm provides no built-in virtual DOM profiling. Exact frame time impact can only be measured externally. The linear-time guarantee assumes pure, cheap keys with no side effects.

Steps needed for this case

1. Confirm you are using keyed nodes, not index-based lists. Verify the key is stable and constant-time.
2. Benchmark a representative tree: top list N items, each with sub-list M items. Toggle a reorder and measure frame duration with window.performance.now for keyed vs unkeyed.
3. Observe DOM mutations with a MutationObserver or Elements panel. Keyed reorders should show moves; unkeyed should show removals and insertions.
4. Replace the key function with a constant-time id and then with an expensive computation to isolate key cost.

One missing diagnostic detail that changes the recommendation: what does your key function compute and is it stable across renders? If it derives from deep nested fields or allocates, manual key management may hurt more than help.