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

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, 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 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:

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:

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.

// 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 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, 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.

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