# How Fre Uses a bMap in Its Diff Algorithm for Fast Key Lookup

> Discover how Fre uses a bMap for O(1) key lookup in its diff algorithm, optimizing keyed list reconciliation and avoiding slow O(n²) scans.

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

---

**Fre's reconciler builds a key-to-index map (bMap) of new children to achieve O(1) lookups during diffing, avoiding O(n²) scans when reconciling keyed lists.**

The **Fre** library is a lightweight alternative to React that implements a fiber-based virtual DOM. When reconciling children arrays in [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts), Fre leverages a **bMap** data structure to optimize keyed element lookups. This technique transforms the diff algorithm from a potentially quadratic operation into a linear one, making list reordering and updates significantly faster.

## What Is the Fre bMap Diff Algorithm?

In Fre's reconciler, the **bMap** (short for "before map" or "backup map") is a plain JavaScript object that maps element keys to their indices in the new children array (`bCh`). This map is constructed once at the beginning of the diff process and reused throughout the reconciliation loop.

### Building the bMap in src/reconcile.ts

The map creation occurs in [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts) during the initial phase of the `diff` function. As the algorithm iterates through the new children array from `bHead` to `bTail`, it populates the `bMap` object:

```typescript
for (let i = bHead; i <= bTail; i++) {
  if (bCh[i].key) bMap[bCh[i].key] = i   // ← bMap creation
}

```

This loop runs in **O(n)** time where *n* is the number of new children, creating a lookup table that stores only keyed elements.

### O(1) Key Lookup During Reconciliation

Once the `bMap` is constructed, the reconciler processes the old children array (`aCh`). For each old element (`aElm`), it checks for a corresponding key in the new list:

```typescript
const foundB = aElm.key ? bMap[aElm.key] : null   // ← key lookup via bMap

```

This lookup operates in **constant time O(1)**. If `foundB` returns a number, the algorithm knows exactly where the matching new element resides. If it returns `undefined` or `null`, the old element has no counterpart in the new list and is scheduled for removal.

## Performance Benefits of bMap in Fre

The `bMap` structure provides two critical optimizations that distinguish Fre's diff algorithm from naive implementations.

### Avoiding O(n²) Scans

Without a key map, the reconciler would need to scan the entire new children array for every old element to find matches. This results in **O(n × m)** complexity where *n* and *m* are the lengths of the old and new arrays. The `bMap` reduces this to **O(n + m)** by trading space (the map object) for time (linear scans).

### Supporting Keyed Reordering

When children are reordered (such as dragging list items or sorting), the `bMap` enables the diff to emit `MOVE` actions without expensive comparisons. The algorithm knows the old index and the new index (from `bMap`) immediately, allowing it to calculate the minimal DOM manipulation required.

## Practical Example: Keyed List Diff

Consider a component that renders a keyed list. When the order changes and items are added or removed, Fre's `bMap` handles the reconciliation efficiently.

```tsx
// Old render
const oldVtree = (
  <ul>
    <li key="a">A</li>
    <li key="b">B</li>
    <li key="c">C</li>
  </ul>
)

// New render – order changed, "b" removed, "d" added
const newVtree = (
  <ul>
    <li key="c">C</li>      // moved
    <li key="a">A</li>      // moved
    <li key="d">D</li>      // inserted
  </ul>
)

```

When `render(oldVtree, root)` is followed by `render(newVtree, root)`, Fre's diff performs the following steps using the `bMap`:

1. **Creates** `bMap = {c: 0, a: 1, d: 2}` while scanning the new list.
2. **Processes** old elements:
   - `a` → found at index `1` → emits `MOVE` action.
   - `b` → not found (`null`) → emits `REMOVE` action.
   - `c` → found at index `0` → emits `MOVE` action.

The resulting actions update the real DOM with the minimal number of mutations, avoiding unnecessary creation or destruction of DOM nodes.

## Summary

- **Fre's reconciler** in [`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts) implements a linear-time diff algorithm for keyed children using a `bMap` structure.
- **The bMap** is a key-to-index map built from the new children array (`bCh`), enabling O(1) lookups during reconciliation.
- **Performance gains** include avoiding O(n²) scans and efficiently handling list reordering through direct index comparisons.
- **Implementation** involves a single pass to build the map followed by constant-time key lookups for each old element to determine moves, updates, or removals.

## Frequently Asked Questions

### What does bMap stand for in Fre?

In Fre's source code, **bMap** refers to a lookup map built from the "before" or "backup" children array (conventionally named `bCh` in the reconciler). It maps element keys to their indices in the new children list, allowing the diff algorithm to locate keyed elements instantly rather than searching through the array.

### How does Fre's bMap improve diff performance?

Without the **bMap**, Fre would need to scan the entire new children array for every old element to find a matching key, resulting in O(n × m) complexity. By constructing the **bMap** once at the start of the diff (O(n) time), subsequent key lookups become O(1) operations. This reduces the overall reconciliation to linear time O(n + m) and makes keyed list reordering significantly faster.

### Where is the bMap logic located in Fre's source code?

The **bMap** implementation resides in **[`src/reconcile.ts`](https://github.com/frejs/fre/blob/main/src/reconcile.ts)**, specifically within the reconciler's diff function. The map is populated in a loop that iterates from `bHead` to `bTail` (the bounds of the new children array), and it is queried later when processing the old children array (`aCh`) to determine if keyed elements have moved, updated, or been removed.

### Does Fre's bMap handle duplicate keys?

Fre's reconciler assumes that keys are unique within a single render's children array. If duplicate keys exist in the **bMap** construction loop, later indices will overwrite earlier ones in the JavaScript object, meaning the diff algorithm will only "see" the last occurrence of that key. This behavior aligns with standard virtual DOM expectations where duplicate keys produce undefined behavior or warnings in development mode.