Fixing a 15-second graph freeze with an indexed lookup

My graph-performance case study records a plot-matching improvement from 15.5 seconds to 14 milliseconds on 1,600 elements. Those are historical figures carried from my résumé into this portfolio’s approved metrics registry. They describe plot matching, not total graph rendering or end-to-end page responsiveness.

The public repository does not include the original profile, dataset, hardware details or repeated-run measurements. I cannot reproduce that exact result from this repository. What I can show is the algorithmic problem and a synthetic demonstration of the same class of fix.

The shape of the problem

Suppose incoming records need to be merged by ID while preserving their first-seen order. A simple implementation searches the output accumulated so far for each incoming record:

type GraphItem = { id: string; x: number; y: number };

function mergeByScan(elements: readonly GraphItem[]): GraphItem[] {
  const plotted: GraphItem[] = [];
  for (const incoming of elements) {
    const index = plotted.findIndex((p) => p.id === incoming.id);
    if (index === -1) plotted.push({ ...incoming });
    else plotted[index] = { ...plotted[index], ...incoming };
  }
  return plotted;
}

These are standalone teaching examples, not production source code. They contain no customer data or product-specific graph logic.

For n distinct IDs, the scans perform 0 + 1 + … + (n − 1) comparisons, or n(n − 1)/2. That is quadratic work. Doubling a sufficiently large, mostly unique input roughly quadruples the comparison count, not necessarily elapsed time. Duplicates, object sizes, JIT compilation and garbage collection affect timings.

Build an index while merging

Store each ID’s output position as it is first encountered:

function mergeByIndex(elements: readonly GraphItem[]): GraphItem[] {
  const plotted: GraphItem[] = [];
  const indexById = new Map<string, number>();
  for (const incoming of elements) {
    const index = indexById.get(incoming.id);
    if (index === undefined) {
      indexById.set(incoming.id, plotted.length);
      plotted.push({ ...incoming });
    } else {
      plotted[index] = { ...plotted[index], ...incoming };
    }
  }
  return plotted;
}

Check index === undefined, not !index: zero is a valid position. Both versions retain first-seen ID order and let later records replace earlier field values. They make shallow copies and do not mutate the input records.

With expected constant-time Map access and fixed-size records, this is expected linear work, using additional memory proportional to the number of distinct IDs. JavaScript requires average sublinear access for a Map, not a universal worst-case O(1) guarantee; see the Map reference.

This is an index local to one operation, not React useMemo. If the output is reordered, spliced or kept across calls, its positions can become stale. Rebuild or maintain the index when those assumptions change.

Profile before replacing loops

The historical case study attributes the bottleneck to plot matching. The general debugging habit is to measure the expensive phase first, then inspect repeated searches or copies inside its loops. A nested findIndex is a useful lead, not proof that it dominates the application.

A related trap is rebuilding an object with a spread on every iteration:

const byId = items.reduce((acc, item) => ({ ...acc, [item.id]: item }), {});

For distinct keys, each step copies an increasingly large accumulator. A local Map avoids that repeated copy and safely accommodates arbitrary string keys:

const byId = new Map<string, GraphItem>();
for (const item of items) byId.set(item.id, item);

This changes the result type from an object to a Map, so callers must use get rather than property access. Mutation of a newly created local accumulator is different from mutating shared application state.

What the live demo measures

Fix 01 on the homepage generates deterministic synthetic nodes with some duplicate IDs. Both implementations merge the same records. Timings wrap the merge function; they exclude node generation and canvas drawing.

Normally, the demo calibrates the record count toward roughly 1–2 seconds of work for the slow version. The count is bounded, and the target is approximate. With reduced motion enabled, it skips calibration and uses 1,600 records. The displayed count and timings belong to that browser session. They are not a reproduction of the historical 15.5-second result or a promise that the fast path always finishes within a particular frame budget. The Break control deliberately runs blocking work.

To compare the public algorithms, use the same seed and record count for both, verify equal outputs, warm up both paths, and collect several samples while alternating their order. Report the environment, input size and timing spread. Keep input generation and rendering outside the measured merge phase.

The repository’s plot tests check equal output, duplicate handling, order and input preservation. Those are correctness checks. Timing comparisons are environment-sensitive and cannot validate the historical production result. The transferable lesson is to remove repeated work after profiling, while preserving the behavior users depend on.