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

> Discover Fre's keyed reconciliation algorithm. Learn how diffing child fibers with four phases optimizes DOM updates, achieves O(1) lookups, and preserves component state.

- Repository: [frejs/fre](https://github.com/frejs/fre)
- Tags: internals
- Published: 2026-03-02

---

**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`](https://github.com/frejs/fre/blob/main/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`](https://github.com/frejs/fre/blob/main/src/reconcile.ts) (lines 97-104), the process begins:

```typescript
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`](https://github.com/frejs/fre/blob/main/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`](https://github.com/frejs/fre/blob/main/src/reconcile.ts) (lines 40-108) follows this pattern:

```typescript
// 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`](https://github.com/frejs/fre/blob/main/src/type.ts) (lines 16-24):

```typescript
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`](https://github.com/frejs/fre/blob/main/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:

```tsx
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`](https://github.com/frejs/fre/blob/main/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`](https://github.com/frejs/fre/blob/main/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.