Fre Keyed Reconciliation Algorithm: How Fre Diffs and Optimizes the Virtual DOM

Fre’s keyed reconciliation algorithm minimizes DOM updates by diffing two flat arrays of child fibers using a four-phase approach—head-to-head matching, tail-to-tail matching, key-map building, and a main loop—enabling O(1) lookups for moves and inserts while preserving component state through cloning.

The frejs/fre repository implements a high-performance virtual DOM reconciler that treats keyed children as stable identifiers. By comparing previous and next fiber arrays in src/reconcile.ts, the algorithm generates a minimal set of actions to update the real DOM without reconstructing unchanged nodes.

How Fre’s Keyed Reconciliation Works

Fre’s reconciler operates on two flat arrays: aCh (previous children) and bCh (next children). When reconcileChildren is invoked, it normalizes the input through arrayfy and delegates to the diff function to compute the transformation needed.

In src/reconcile.ts (lines 97-104), the process begins:

let aCh = fiber.kids || [],
    bCh = (fiber.kids = arrayfy(children));
const actions = diff(aCh, bCh);

The diff function returns an ordered list of actions (INSERT, UPDATE, MOVE, REMOVE), which commit in src/commit.ts (lines 22-43) later applies to manipulate the DOM.

The Four-Phase Diff Strategy

The diff function executes four distinct phases to minimize computational work:

Phase 1: Head-to-Head Matching The algorithm walks from the start of both arrays while fibers are identical according to the same(a, b) predicate. Matching fibers are cloned, marked with TAG.UPDATE, and appended to the actions list.

Phase 2: Tail-to-Tail Matching Working backward from the end of both arrays, the reconciler identifies unchanged trailing nodes. These are collected in a temporary array to preserve order without interleaving with later insertions.

Phase 3: Key-Map Building For the remaining unprocessed middle section of bCh, Fre constructs a hash map bMap that maps key values to their indices. Only keyed children are stored, enabling constant-time lookups during the main reconciliation loop.

Phase 4: Main Reconciliation Loop The algorithm processes the remaining aCh and bCh slices simultaneously, handling four cases:

• Null old element → skip
• Exhausted new list → REMOVE
• Exhausted old list → INSERT
• Same type and key → UPDATE (via cloning)
• Key found elsewhere → INSERT (if new location precedes old) or MOVE (if it appears later)

The core implementation in src/reconcile.ts (lines 40-108) follows this pattern:

// Head-to-head comparison
while (aHead <= aTail && bHead <= bTail) {
  if (!same(aCh[aHead], bCh[bHead])) break
  clone(aCh[aHead], bCh[bHead])
  actions.push({ op: TAG.UPDATE })
  aHead++; bHead++
}

// Tail-to-tail comparison
while (aHead <= aTail && bHead <= bTail) {
  if (!same(aCh[aTail], bCh[bTail])) break
  clone(aCh[aTail], bCh[bTail])
  temp.push({ op: TAG.UPDATE })
  aTail--; bTail--
}

// Build key map for remaining new children
for (let i = bHead; i <= bTail; i++) {
  if (bCh[i].key) bMap[bCh[i].key] = i
}

Core Optimizations in Fre’s Reconciler

Fre incorporates several performance optimizations that distinguish its keyed reconciliation algorithm from naive implementations.

Early Exit on Identical Heads and Tails Two while loops compare fibers from both ends before constructing the key map. This optimization skips expensive hash map creation and inner-loop processing for large unchanged blocks at the beginning or end of lists.

Fiber Cloning Instead of Recreation The clone(a, b) function copies hooks, refs, DOM nodes, and children from the old fiber to the new one, marking the old fiber with TAG.REPLACE. The new fiber maintains a reference to its predecessor via the alternate property, preserving component state and avoiding DOM node reconstruction.

O(1) Key-Based Lookup The bMap structure stores only keyed children (if (bCh[i].key) bMap[bCh[i].key] = i), allowing constant-time detection of moves and inserts. This eliminates the O(n²) complexity typical of pairwise comparison algorithms.

Batched Update Actions Tail updates collected during phase 2 are stored in the temp array and appended after the main loop completes. This batching prevents interleaving of inserts and moves with tail updates, ensuring the final actions list requires only a single pass during the commit phase.

Memoization Short-Circuiting When a component carries the memo flag and shouldUpdate returns false, the isMemo check short-circuits diffing entirely. This optimization avoids unnecessary work for pure function components whose props remain unchanged.

WeakMap Suspense Handling For asynchronous operations, Fre uses a WeakMap to associate pending promises with their awaiting fibers. This ensures reconciliation resumes only when suspended promises resolve, reducing wasted computation during async loading states.

Implementation Details in the Source Code

The action types driving the reconciliation are defined as bitwise flags in src/type.ts (lines 16-24):

export const enum TAG {
  UPDATE   = 1 << 1,
  INSERT   = 1 << 2,
  REMOVE   = 1 << 3,
  SVG      = 1 << 4,
  DIRTY    = 1 << 5,
  MOVE     = 1 << 6,
  REPLACE  = 1 << 7,
}

These flags indicate the operation type for each fiber during the commit phase. The commit function in src/commit.ts interprets these flags to perform the actual DOM manipulations—inserting new nodes, updating attributes, moving existing elements, or removing deleted items.

Working Example: Keyed Lists in Practice

Consider a component rendering a dynamic list:

function TodoList({ todos }) {
  return (
    <ul>
      {todos.map(t => (
        <li key={t.id}>{t.text}</li>
      ))}
    </ul>
  );
}

When the list changes from [{id:1}, {id:2}, {id:3}] to [{id:2}, {id:1}, {id:4}], Fre’s algorithm executes as follows:

1. Head-to-head: No match (1 ≠ 2)
2. Tail-to-tail: No match (3 ≠ 4)
3. Key-map: Builds {2: 0, 1: 1, 4: 2}
4. Main loop:
   • id:1 found at index 1 → MOVE to position 0
   • id:2 found at index 0 → MOVE to position 1 (or remains if optimized)
   • id:3 not found → REMOVE
   • id:4 not in old list → INSERT

The resulting DOM operations preserve the existing <li> elements for keys 1 and 2, maintaining focus state and event listeners while only creating a new node for id:4 and removing id:3.

Summary

• Fre’s keyed reconciliation algorithm in src/reconcile.ts diffs two flat fiber arrays (aCh and bCh) using a four-phase strategy to minimize DOM updates.
• The algorithm uses head-to-head and tail-to-tail matching to quickly skip unchanged blocks, then builds a key map for O(1) lookups during the main reconciliation loop.
• Actions (UPDATE, INSERT, MOVE, REMOVE) are generated based on key comparisons and executed by commit in src/commit.ts to manipulate the real DOM.
• Fiber cloning preserves component state (hooks and refs) by copying data from old fibers to new ones rather than recreating DOM nodes.
• Optimizations include memoization short-circuiting, batched tail updates, and WeakMap-based suspense handling to avoid unnecessary computation.

Frequently Asked Questions

How does Fre handle reordering of list items with keys?

When list items are reordered, Fre detects the new positions of keyed fibers using the bMap constructed during the key-map building phase. If a key from the old list exists in the new list but at a different position, the algorithm generates a MOVE action rather than destroying and recreating the DOM node. This preserves internal component state, focus, and event listeners attached to the moved elements.

What is the difference between UPDATE and REPLACE actions in Fre?

UPDATE indicates that a fiber’s properties or children have changed but the DOM node can be reused, allowing Fre to apply patches to the existing element. REPLACE (set during the clone operation) marks the old fiber as superseded while the new fiber retains a reference via alternate. This distinction enables Fre to preserve hooks and refs while ensuring the commit phase knows which fibers have been superseded in the tree.

Why does Fre use a WeakMap for Suspense implementation?

Fre uses a WeakMap to store pending promises keyed to their associated fibers. This allows the reconciler to resume work exactly where it paused when an async dependency resolves, without retaining references to completed work that could cause memory leaks. The weak references ensure that fibers can be garbage collected once no longer needed, even if promises remain in flight.

How does Fre’s keyed algorithm compare to React’s reconciler?

Both Fre and React use keyed reconciliation to minimize DOM updates, but Fre implements a simplified four-phase diff that prioritizes minimal code size alongside performance. Fre’s approach of cloning fibers and using explicit action flags (TAG.UPDATE, TAG.MOVE, etc.) differs from React’s more complex fiber architecture, yet achieves similar O(n) complexity for most list operations through the same fundamental optimization: treating keys as stable identifiers for DOM node reuse.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}