Seven Minutes to Parse a Menu

Medium

· Backend

Incident

SEV-2

BUG-LOADTIME

Priority: High · reported by performance

Time to fix: 20 min

Failing checks on the shipped build

  • parsing stays linear

    work must be linear, saw 9541921 reads for 3089 chars: expected a truthy value but got false

How to work this incident

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

Inspired by

GTA Online · 2021

Modelled on the GTA Online load-time investigation (2021): a player traced six-minute loads to a JSON parser that called sscanf on a 10 MB buffer for every one of its 63,000 items. sscanf measures the whole string first, so each item cost a full scan — a one-line fix cut load times by 70%.

catalog.js has the same shape: a helper re-walks the entire payload on every item.

Fix parseItems so the total work is linear in the payload length.

Code map

var counter = require("./counter");

// Returns the length of the payload, counting every character it touches.
function measure(payload) {
  var n = 0;
  while (n < payload.length) {
    counter.charRead();
    n++;
  }
  return n;
}

exports.parseItems = function (payload) {
  var items = [];
  var current = "";
  for (var i = 0; i < payload.length; i++) {
    // Re-measures the whole payload on every single character.
    var total = measure(payload);
    if (i >= total) break;
    var c = payload.charAt(i);
    if (c === ",") {
      items.push(current);
      current = "";
    } else {
      current += c;
    }
  }
  if (current.length > 0) items.push(current);
  return items;
};

Sign in to edit the file, run the tests and submit a fix

A free account — no card, no trial clock. You come straight back here.

Seven Minutes to Parse a Menu — JavaScript Bug Hunt

Modelled on the GTA Online load-time investigation (2021): a player traced six-minute loads to a JSON parser that called sscanf on a 10 MB buffer for every…

  • Language: JavaScript
  • Layer: Backend
  • Difficulty: Medium
  • Concepts: Performance, Complexity
  • Modelled on: GTA Online · 2021
  • Visible tests: splits a small payload correctly; parsing stays linear
  • Reward: 50 XP for a complete fix

Incident

  • Severity: SEV-2 (priority: High)
  • Ticket: BUG-LOADTIME
  • Reported by: performance
  • Time to fix: 20 minutes, the target for a medium incident

Failing checks on the shipped build

  • parsing stays linear — work must be linear, saw 9541921 reads for 3089 chars: expected a truthy value but got false

How to work this incident

  1. Read the report: write down the expected behaviour and the actual one in a sentence each.
  2. Reproduce it: run the visible tests and find the failing check that matches the report.
  3. Read the logs and the failing checks for the first value that is wrong — the earliest wrong value is nearer the cause than the loudest error.
  4. Follow the request through the handler, the validation and the service it calls; find the first step whose output disagrees with the report.
  5. Fix the cause rather than the symptom, run the visible tests again, and submit against the hidden ones — then write the root cause down.

Briefing

Modelled on the GTA Online load-time investigation (2021): a player traced six-minute loads to a JSON parser that called sscanf on a 10 MB buffer for every one of its 63,000 items. sscanf measures the whole string first, so each item cost a full scan — a one-line fix cut load times by 70%.

catalog.js has the same shape: a helper re-walks the entire payload on every item.

Fix parseItems so the total work is linear in the payload length.

Bug report

BUG-LOADTIME · Priority: High · Reported by: performance

parseItems(payload) splits a comma-separated payload into trimmed item names.

Observed: parsing is quadratic. With a payload of 2,000 items the helper reads about 4,000,000 characters. The instrumented counter proves it.

Logs

[catalog] parsed 63000 items in 383s
[catalog] charReads=3968072 for a 1994-char payload

The code as shipped

src/catalog/catalog.js (editable)

var counter = require("./counter");

// Returns the length of the payload, counting every character it touches.
function measure(payload) {
  var n = 0;
  while (n < payload.length) {
    counter.charRead();
    n++;
  }
  return n;
}

exports.parseItems = function (payload) {
  var items = [];
  var current = "";
  for (var i = 0; i < payload.length; i++) {
    // Re-measures the whole payload on every single character.
    var total = measure(payload);
    if (i >= total) break;
    var c = payload.charAt(i);
    if (c === ",") {
      items.push(current);
      current = "";
    } else {
      current += c;
    }
  }
  if (current.length > 0) items.push(current);
  return items;
};

Read-only context: src/catalog/counter.js.

Open the hunt to start the incident clock, edit the files, run the visible tests and submit against the hidden ones, then write the root cause down. More JavaScript bug hunts.