# How Fre's diff() Algorithm Handles Keyed Reconciliation in the Virtual DOM

> Discover how Fre's diff() algorithm achieves O(N) keyed reconciliation. Learn about its double-ended pointers and key-index map for efficient DOM mutations like insert, move, update, and remove.

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

---

**Fre's `diff()` function in [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts) implements an O(N) keyed reconciliation strategy that uses double-ended pointers and a key-index map to generate minimal DOM mutation actions—insert, move, update, and remove—between two fiber child lists.**

Fre is a lightweight React-like library that achieves high performance through an optimized virtual DOM reconciliation engine. At the heart of this system lies the `diff()` algorithm, which efficiently computes the difference between previous and new component trees while preserving component state through stable keys. This deep dive examines the implementation from lines 40-108 of [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts) to reveal how Fre minimizes expensive DOM operations.

## Algorithm Structure and Initialization

The `diff()` function accepts two arrays of fiber nodes: **`aCh`** (previous children) and **`bCh`** (new children). It returns an ordered list of `Action` objects that instruct the commit phase how to transform the DOM.

### Double-Ended Pointer Strategy

Fre employs a classic optimization using four index pointers to narrow down the differential region before performing heavy key comparisons:

- **`aHead`** and **`aTail`** track the unconsumed boundaries of the old list
- **`bHead`** and **`bTail`** track the unconsumed boundaries of the new list

```typescript
// From src/reconcile.ts#L40-L44
let aHead = 0, bHead = 0, aTail = aCh.length - 1, bTail = bCh.length - 1;

```

The algorithm first synchronizes from the **right (tail)** using a `while` loop that checks if the tail nodes of both lists are identical via the `same()` function. When matched, it clones the old fiber onto the new one (reusing the DOM node) and records an `UPDATE` action. Both `aTail` and `bTail` decrement inward until a mismatch occurs【L49-L55】.

Next, it performs the same optimization from the **left (head)**, incrementing `aHead` and `bHead` while nodes match【L57-L63】. These fast-path checks handle common patterns like appending to the end of a list or prepending to the beginning without requiring key map construction.

### Key Index Map Construction

After the fast-path synchronization, Fre builds a lookup table for the remaining new children that possess keys:

```typescript
// From src/reconcile.ts#L65-L67
for (let i = bHead; i <= bTail; i++) {
  if (bCh[i].key) bMap[bCh[i].key] = i;
}

```

This **`bMap`** object enables O(1) retrieval of a new child's index by its key, transforming the reconciliation from an O(N²) search into an O(N) operation for keyed lists. Elements without keys fall back to positional comparison during the core loop.

## Core Reconciliation Loop and Operations

The main reconciliation logic resides in a `while` loop that processes the unmatched middle region between `aHead…aTail` and `bHead…bTail`【L69-L101】. During each iteration, the algorithm determines whether to remove, insert, move, or update a fiber based on key presence and position.

### REMOVE Operations

When the current old element `aElm` has no corresponding key in `bMap` (`foundB == null`), the algorithm immediately schedules a removal:

```typescript
// From src/reconcile.ts#L87-L90
removeElement(aElm);
aHead++;

```

This occurs when a keyed element is deleted from the list or when an unkeyed element no longer aligns positionally with any new child.

### INSERT and MOVE Handling

The algorithm distinguishes between **insertion** (creating a new DOM node) and **moving** (repositioning an existing node) using the key map:

- **INSERT**: Triggered when the old list is exhausted (`aTail + 1 <= aHead`) or when `foundB` exists ahead of the current `bHead`. The action includes a reference node for proper insertion placement【L76-L79】【L91-L94】.

- **MOVE**: Occurs when `foundB` exists behind the current `bHead` (`foundB < bHead`). The element is already rendered elsewhere in the tree, so Fre clones the old fiber to preserve its DOM node and records a `MOVE` action to reposition it before the current `aHead` reference【L95-L99】.

### UPDATE Actions

When the `same()` function confirms that old and new elements are identical (either by key match or by reference), Fre clones the old fiber onto the new one to preserve the underlying DOM node and component state. An `UPDATE` action is pushed to the queue, and both `aHead` and `bHead` advance【L78-L84】.

## Action Pipeline and Commit Integration

After the core loop completes, Fre appends any updates collected from the initial right-side synchronization. These are stored temporarily in a `temp` array and reversed before concatenation to ensure proper execution order【L104-L106】:

```typescript
for (let i = temp.length - 1; i >= 0; i--) {
  actions.push(temp[i]);
}
return actions; // L107-L108

```

The returned `actions` array contains objects with an `op` property referencing the **`TAG`** enum defined in [`src/type.ts`](https://github.com/frejs/fre/blob/main/src/type.ts) (lines 16-24). The `reconcileChildren` caller attaches these actions to each child fiber (`child.action = actions[i]`), which the commit phase ([`src/commit.ts`](https://github.com/frejs/fre/blob/main/src/commit.ts)) consumes to perform actual DOM mutations.

## Practical Example: Keyed List Reordering

Consider a component rendering a dynamic list where each item has a stable identifier:

```tsx
import { h } from 'fre'

function List({ items }: { items: { id: string; text: string }[] }) {
  return (
    <ul>
      {items.map(item => (
        <li key={item.id}>{item.text}</li>
      ))}
    </ul>
  )
}

```

When the `items` array reorders, Fre's `diff()` algorithm:

1. Detects that each `<li>` retains the same `key` (`item.id`) via the `bMap` lookup
2. Issues **MOVE** actions to reposition existing DOM nodes rather than destroying and recreating them
3. Preserves component state and input focus across the reorder operation

Without keys, the algorithm would fall back to positional comparison, likely resulting in unnecessary removals and insertions.

## Summary

- **Fre's `diff()`** implements an O(N) keyed reconciliation algorithm in [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts) using double-ended pointers (`aHead`, `aTail`, `bHead`, `bTail`) to optimize list diffing.

- The algorithm builds a **`bMap`** key index for the new children to achieve constant-time lookups, enabling efficient detection of moved elements versus new insertions.

- Four operation types drive the commit phase: **UPDATE** (reuse DOM node), **MOVE** (reposition existing node), **INSERT** (create new node), and **REMOVE** (destroy node).

- Actions are batched and ordered to ensure DOM mutations execute correctly, with tail-side updates reversed and appended after the core reconciliation loop.

- The **TAG** enum in [`src/type.ts`](https://github.com/frejs/fre/blob/main/src/type.ts) defines operation codes consumed by [`src/commit.ts`](https://github.com/frejs/fre/blob/main/src/commit.ts) to apply the computed differences to the actual DOM.

## Frequently Asked Questions

### What makes Fre's diff algorithm "keyed"?

Keyed reconciliation relies on the optional `key` property assigned to elements in arrays. When children possess stable keys, Fre builds an index map (`bMap`) of the new children's positions, allowing the algorithm to identify which existing DOM nodes can be reused and moved versus which need creation. This prevents unnecessary destruction of component state when lists reorder.

### How does Fre handle unkeyed children during reconciliation?

For elements without keys, Fre falls back to positional comparison using the double-ended pointer strategy. If the fast-path head/tail synchronization fails to match nodes, the algorithm treats mismatches as removals and insertions rather than moves, which is less efficient but maintains correctness for dynamic content.

### What is the time complexity of Fre's diff() function?

The algorithm operates in **O(N)** time complexity where N is the total number of children in both lists. The initial pointer sweeps run in linear time, the key map construction is linear, and the core reconciliation loop processes each node exactly once thanks to the `bMap` providing O(1) key lookups.

### How does the diff algorithm interact with Fre's commit phase?

After `diff()` returns the `actions` array, the `reconcileChildren` function attaches each action to its corresponding fiber. During the commit phase ([`src/commit.ts`](https://github.com/frejs/fre/blob/main/src/commit.ts)), the system iterates these fibers and executes the DOM mutations encoded in `action.op` (INSERT, MOVE, UPDATE, or REMOVE), ensuring the browser reflects the new virtual DOM state.