# How Fre's Diff Algorithm Optimizes Head and Tail Matching

> Learn how Fre's diff algorithm optimizes head and tail matching to speed up reconciliation by comparing only the middle section of child fiber arrays.

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

---

**Fre's diff algorithm short-circuits reconciliation by matching identical nodes at the start (head) and end (tail) of child fiber arrays, reducing expensive comparison logic to only the unmatched middle section.**

Fre is a lightweight React alternative that implements a highly optimized reconciliation engine in [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts). By pruning common prefixes and suffixes before applying key-based diffing, Fre minimizes memory allocations and computational overhead during virtual DOM updates, achieving linear-time performance for common UI patterns.

## How Fre's Diff Algorithm Works

The core optimization resides in the `diff` function located at approximately line 240 in [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts). This implementation processes two fiber arrays—the current children (`aCh`) and the new children (`bCh`)—through a four-stage pipeline designed to eliminate unnecessary work on unchanged boundary nodes.

### Head Scanning

The algorithm begins by walking forward from index 0 while `aCh[i] === bCh[i]`. This comparison checks for reference equality between fibers. The scan increments a `head` pointer until encountering the first non-matching pair, effectively skipping all identical leading nodes without creating temporary data structures or performing key comparisons.

### Tail Scanning

After establishing the head boundary, the algorithm walks backward from the array ends (`aCh.length - 1` and `bCh.length - 1`) while fibers match. It maintains `tailA` and `tailB` pointers that decrement toward the head pointer until encountering a mismatch or until the pointers cross. This step eliminates identical trailing nodes from further processing.

### Middle Diff Processing

Only the slice between the head and tail pointers undergoes the expensive reconciliation logic. The algorithm extracts `middleA = aCh.slice(head, tailA + 1)` and `middleB = bCh.slice(head, tailB + 1)`, then applies a key-based mapping strategy to handle insertions, deletions, and moves within this reduced window.

## Implementation Details in src/reconcile.ts

The core logic follows this structure:

```typescript
function diff(aCh: Fiber[], bCh: Fiber[]) {
  let head = 0
  
  // Head matching
  while (head < aCh.length && head < bCh.length && aCh[head] === bCh[head]) {
    head++
  }

  // Early exit for identical arrays
  if (head === aCh.length && head === bCh.length) return []

  let tailA = aCh.length - 1
  let tailB = bCh.length - 1
  
  // Tail matching
  while (tailA >= head && tailB >= head && aCh[tailA] === bCh[tailB]) {
    tailA--
    tailB--
  }

  // Process only the unmatched middle
  const middleA = aCh.slice(head, tailA + 1)
  const middleB = bCh.slice(head, tailB + 1)
  
  return diffMiddle(middleA, middleB, head)
}

```

This approach ensures that when updating a list where only the middle changes, Fre avoids the O(n²) complexity of a naive diff for the entire array.

## Practical Code Examples

### Appending Items (Tail-Only Changes)

When adding elements to the end of a list:

```tsx
function List() {
  const [items, setItems] = useState([1, 2, 3])
  
  const add = () => setItems(prev => [...prev, prev.length + 1])

  return (
    <>
      {items.map(n => <div key={n}>Item {n}</div>)}
      <button onClick={add}>Add</button>
    </>
  )
}

```

The head scan matches the first three fibers. The tail scan finds no match for the new element, so the middle diff processes only the single new fiber, resulting in one insert action rather than re-examining the entire list.

### Prepending Items (Head-Only Changes)

Inserting at the beginning triggers the opposite optimization:

```tsx
const prepend = () => setItems(prev => [0, ...prev])

```

The head scan stops immediately at index 0, while the tail scan matches the remaining three nodes. The middle diff handles only the new head fiber, avoiding re-processing the stable tail section.

### Reordering Middle Elements

For changes confined to the middle of a list:

```tsx
const swapMiddle = () => setItems([1, 3, 2, 4, 5])

```

The head scan matches `1`, and the tail scan matches `4` and `5`. Only the slice `[2, 3]` versus `[3, 2]` enters the full diff logic, efficiently handling the swap without touching the stable boundaries.

## Key Source Files

- **[`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts)** – Contains the `diff` function implementing head-and-tail optimization (approximately line 240).
- **[`src/type.ts`](https://github.com/frejs/fre/blob/main/src/type.ts)** – Defines the `Fiber` interface used throughout the reconciliation process.
- **[`src/schedule.ts`](https://github.com/frejs/fre/blob/main/src/schedule.ts)** – Manages the execution of diff actions generated by the reconcile phase.
- **[`test/diff.tsx`](https://github.com/frejs/fre/blob/main/test/diff.tsx)** – Contains test cases validating head-and-tail matching behavior and edge cases.

## Summary

- Fre's diff algorithm uses **head and tail matching** to short-circuit reconciliation when child arrays share common prefixes or suffixes.
- The implementation in [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts) first scans forward for identical leading fibers, then backward for identical trailing fibers.
- Only the unmatched middle section undergoes expensive key-based diffing, reducing both time complexity and memory allocations.
- This optimization proves particularly effective for common UI patterns like appending to lists, prepending items, or editing middle elements without re-processing stable boundaries.

## Frequently Asked Questions

### How does Fre's diff algorithm differ from React's reconciliation?

Fre implements a similar head-and-tail optimization strategy to React, but focuses on minimal bundle size rather than concurrent rendering features. Both algorithms achieve O(n) best-case performance by pruning unchanged prefixes and suffixes, though Fre's implementation in [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts) uses a lighter-weight approach optimized for its smaller footprint.

### What is the time complexity of Fre's head-and-tail optimization?

The algorithm achieves **O(n)** linear time when arrays are identical or differ only at boundaries, requiring only a single forward and backward scan. When changes occur only at the head or tail, complexity remains O(n) for the scans plus O(m) for the small changed section, avoiding the O(m·n) complexity that would result from diffing full arrays.

### Does Fre support both keyed and non-keyed diffing?

Yes, the `diff` function in [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts) handles both keyed and non-keyed children. After the head-and-tail pruning phase, the middle section uses key-based mapping for fibers with explicit keys, while non-keyed children rely on positional indexing. The head-and-tail optimization benefits both modes by eliminating unchanged boundary nodes before the more expensive comparison logic executes.

### Where can I find the test cases for Fre's diff algorithm?

The test suite resides in [`test/diff.tsx`](https://github.com/frejs/fre/blob/main/test/diff.tsx) and covers various head-and-tail matching scenarios, including identical arrays, head-only changes, tail-only changes, and complex middle reorderings. These tests verify that the optimization correctly identifies stable prefixes and suffixes while accurately processing the variable middle region.