Optimizing an Algorithm That’s Quadratic by Design

What the engine is doing

WhatChord is an app that watches the notes you play on a MIDI keyboard and names the chord as you play it. Press C-E-G together and it shows C major. That sounds like a dictionary lookup, and for that example it nearly is. The trouble is that real playing is rarely so tidy: the same notes can carry several legitimate names depending on the surrounding music, players leave notes out and add color tones, and a chord can get spread across both hands. So the engine does not look chords up. It treats naming as a ranking problem: list every plausible interpretation, score how well each one fits, then put them in the order a musician would expect to read.

Two terms worth explaining:

A voicing is the specific set of notes being played, including which one is lowest (the bass). “C-E-G” and “E-G, then C an octave up” are two voicings of the same chord. A candidate is one possible name for a voicing. The four notes C-E-G-A can be read as C6 or Am7, among others, so the engine produces many candidates per voicing and has to choose and order them.

This article is about the last step in the process, the ranking. When we built a reproducible benchmark and measured where the engine spends its time on a cache miss, the answer was lopsided: ranking is roughly 99% of it; scoring is about 1%. An uncached analysis of a common seventh chord takes a few milliseconds, and nearly all of that time goes toward putting the already-scored candidates in order.

Why ranking can’t use an ordinary sort

To sort a list, you hand the language a comparator: a function that takes two items and reports which should come first. Every general-purpose sort assumes that function describes a consistent ordering, and in particular that it is transitive: if A belongs before B, and B before C, then A must belong before C. Violate that and the sort’s result is undefined.

It will not usually crash, but it can drop items in nonsensical positions.

WhatChord’s comparator is deliberately not transitive. Most of the time it ranks two candidates by their fit score, but two kinds of musical override can outrank the score:

Hard rules are structural overrides for the cases where the higher score is simply the wrong name (preferring, say, an altered dominant chord over a diminished-slash respelling that fits the raw notes but reads worse). A hard rule can promote a lower-scoring reading over a higher-scoring one no matter how wide the gap. Tie-breakers apply only when two candidates score within a small window of each other (0.20 points, a constant the code calls nearTieWindow), capturing musical heuristics that a single number can’t.

Because a hard rule ignores the size of the score gap, you can end up with a cycle: A beats B, B beats C, and C beats A. No single ordering satisfies all three at once, so there is nothing coherent for a sort to return. Hand a cyclic comparator to a general sort and the outcome can depend on the candidates’ starting order.

So the engine does not sort. It linearizes the relation, turning the web of pairwise preferences into one ordered list:

// beats[i][j] == true => candidate i should rank above j. // The relation may contain cycles: a > b > c > a. List<Candidate> linearize(List<Candidate> cands, List<List<bool>> beats) { final result = <Candidate>[]; final remaining = { ...allIndices }; while (remaining.isNotEmpty) { // Prefer a maximal element: one beaten by nothing still remaining. var pick = firstUnbeaten(remaining, beats); // No maximal element means a cycle. Break it by Copeland win-count: // how many of the others this candidate beats. Global over remaining. pick ??= mostWins(remaining, beats); result.add(cands[pick]); remaining.remove(pick); } return result; }

Two important points.

First, to know whether a candidate is “beaten by nothing remaining,” you need the full matrix of pairwise results: every beats[i][j] combination. Building that matrix is n² calls to the comparator, where n is the number of candidates. Second, when a cycle blocks progress, the tie-break borrows Copeland’s method from voting theory: count how many of the others each candidate beats, and take the one that beats the most. That count is global, summed over every remaining candidate. That global count is why several appealing shortcuts are unsafe.

The cost is real, and it grows with the chord

The engine builds a candidate for every reasonable pairing of a root note with a chord shape it can find in the voicing, so the candidate count climbs steeply as you add notes:

Voicing Notes Candidates C major triad 3 25 Cmaj7 4 43 Cm7 4 46 C7 4 48 Cmaj9 5 67 Six-note voicing 6 90 Seven-note dense 7 131

Even a plain three-note triad produces 25 candidates. We keep a test set of deliberately adversarial, ambiguous voicings (an “oracle corpus,” so called because each case has a known-correct answer to check against), and there the count runs a median of about 75 candidates and a maximum of 143. Building the pairwise matrix for 75 candidates means over 5,000 calls to the comparator, a function the code calls _decide. Each call historically scanned all 21 hard rules before settling anything.

Because the matrix pits every candidate against every other, the work grows with the square of the candidate count: it is O(n²). That is where the time went.

The goal was to cut that cost without changing the output. The benchmark kept us honest by recording exact operation counts, such as how many candidates were built and how many comparisons were run. Those integers depend only on the input and the code, never on the hardware, so an accidental algorithm change would show up as a changed count instead of hiding inside noisy timings.

Win #1: gate the hard-rule scan

The first observation is that almost none of the 21 hard rules can possibly apply to a given pair. Each rule fires only for a specific structural pairing (an altered-fifth dominant against a remote spelling, a complete triad against a deficient inverted reading, and so on), and crucially that condition is candidate-local: it depends only on a single candidate’s quality, extensions, or precomputed features, never on the candidate it is being compared against.

So each rule gets a gate: a quick test on a single candidate that is guaranteed to say “yes” whenever the rule could possibly apply. Once per candidate, we precompute a bitmask, an integer whose bits flag which rules that candidate is eligible for. For a pair, the bitwise AND of their two masks is exactly the set of rules both are eligible for, and we check only those.

// Precompute once per candidate: O(n * rules), not O(n^2). final gateMasks = [for (final c in cands) gateMaskFor(c)];

// A rule needs one operand in each role, so it can only fire when // both candidates pass its gate. Skipped rules would return null. final shared = gateMasks[i] & gateMasks[j]; for (final rule in rulesIn(shared)) { ... }

A skipped rule would have returned null anyway, so this is provably output-identical, not just empirically validated.

Candidate generation and scoring are untouched, the generation counters stay byte-identical, and the ranking golden plus the cycle and hard-rule unit tests pass unchanged. A too-narrow gate would silently drop a real decision, so those test suites are the safety net.

Result: timing for uncached analysis of the adversarial corpus dropped about 27%, and everyday voicings sped up 1.2 to 1.7x. This is a constant-factor win: the same pairwise work, done faster. The algorithm is still O(n²).

What didn’t work, part 1: splitting the gate by role

That single combined gate is broad for rules whose “other” side is common, like “any slash chord” or “any seventh chord.” One refinement is to split each gate into two halves, a role A and a role B, and fire a rule for a pair only when the two candidates fill opposite roles: (maskA[i] & maskB[j]) | (maskB[i] & maskA[j]).

We implemented it across all 21 rules. It stayed output-identical, with unchanged counters and passing tests. It delivered 1 to 3% on typical voicings and roughly 0% on the dense corpus, inside benchmark noise. We reverted it.

The combined gate had already captured the big win: skipping pairs where neither candidate is eligible. Splitting roles only trims pairs where both candidates are eligible in the same role, a thin slice, and the second mask doubles the precompute. After the combined gate, the bottleneck is no longer the hard-rule scan. It is the O(n²) machinery itself: the pairwise matrix and the linearizing.

Why candidate reduction broke ranking

If 25 candidates for a triad feels wasteful, the direct move is to generate or keep fewer of them. Shrinking the candidate set attacks the n² term directly. Unfortunately, it is unsafe because the Copeland count is global.