Optimizing an Algorithm That’s Quadratic by Design | WhatChord

What the engine is doing

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

Two terms worth explaining:

A voicing is the specific set of notes being<br>played, including which one is lowest (the bass). “C, E, G” and<br>“E, G, then C an octave up” are two voicings of the same chord.

A candidate is one possible name for a voicing.<br>The four notes C, E, G, A can be read as<br>C6 or Am7,<br>among others, so the engine produces many candidates per voicing<br>and has to choose and order them.

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

Why ranking can’t use an ordinary sort

To sort a list, you hand the language a comparator: a<br>function that takes two items and reports which should come first.<br>Every general-purpose sort assumes that function describes a<br>consistent ordering, and in particular that it is<br>transitive: if A belongs before B, and B before C, then A must belong before<br>C. Violate that and the sort’s result is undefined. It will not<br>usually crash, but it can drop items in nonsensical positions.

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

Hard rules are structural overrides for the cases<br>where the higher score is simply the wrong name (preferring, say,<br>an altered dominant chord over a diminished-slash respelling that<br>fits the raw notes but reads worse). A hard rule can promote a<br>lower-scoring reading over a higher-scoring one no matter how wide<br>the gap.

Tie-breakers apply only when two candidates score<br>within a small window of each other (0.20 points, a constant the<br>code calls nearTieWindow), capturing musical<br>heuristics that a single number can’t.

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

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

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

Two important points. First, to know whether a candidate is “beaten<br>by nothing remaining,” you need the full matrix of pairwise results:<br>every beats[i][j] combination. Building that matrix is<br>n² calls to the comparator, where n is the<br>number of candidates. Second, when a cycle blocks progress, the<br>tie-break borrows<br>Copeland’s method<br>from voting theory: count how many of the others each candidate<br>beats, and take the one that beats the most. That count is<br>global , summed over every remaining candidate. That<br>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<br>note with a chord shape it can find in the voicing, so the candidate<br>count climbs steeply as you add notes:

Voicing<br>Notes<br>Candidates

C major triad<br>25

Cmaj7<br>43

Cm7<br>46

C7<br>48

Cmaj9<br>67

Six-note voicing<br>90

Seven-note dense<br>131

Even a plain three-note triad produces 25 candidates. We keep a test<br>set of deliberately adversarial, ambiguous voicings (an “oracle<br>corpus,” so called because each case has a known-correct answer to<br>check against), and there the count runs a median of about 75<br>candidates and a maximum of 143....