Vijf vormen van MOAD-0001

MOAD-0001 komt voor in vijf gedocumenteerde vormen in meer dan 60 software-ecosystemen. De structuur: een membership-test met een sequentiële container, genest in een lus over dezelfde of een gerelateerde collectie.

De vijf vormen

Alle vijf delen dezelfde structuur: een lidmaatschapstest genest in een lus, met een container die een lineaire scan vereist om de lidmaatschapsvraag te beantwoorden.

De Scanning Keyword List

Auditen op MOAD-0001 betekent greppen naar lidmaatschapstest-trefwoorden binnen lussen:

- Python: in met een list-variabele, .count(), list.index()

- Java: ArrayList.contains(), List.contains(), LinkedList.contains()

- JavaScript: Array.includes(), Array.indexOf(), Array.find()

- C++: std::vector::find(), handmatige lus met == vergelijking

- Go: slices.Contains(), handmatige lus over een slice

De oplossing in elk geval: vervang de sequentiële container door een hash-container. list → set. ArrayList → HashSet. Array → Set. vector → unordered_set. slice → map[T]struct{}.

Eén sleutelwoord. Eén substitutie. Nul gedragsverandering. 1.000× versnelling bij N=1.000.

Codefragment controleren

Pas MOAD-0001 patroonherkenning toe op een echt codefragment.

Eén Regel, Vier Talen

De oplossing voor MOAD-0001 in vier talen:

# Python
visited = []       # VOOR: O(N) lidmaatschap
visited = set()    # AFTER:  O(1) membership

// Java
List<Node> visited = new ArrayList<>();    // BEFORE
Set<Node> visited = new HashSet<>();       // AFTER

// JavaScript
const visited = [];      // VOOR: Array.includes() O(N)
const visited = new Set(); // NA: Set.has() O(1)
// visited.push(n) → visited.add(n)
// visited.includes(n) → visited.has(n)

// Go
visited := []NodeID{}              // VOOR: slices.Contains() O(N)
visited := make(map[NodeID]struct{}) // NA: map lookup O(1)
// _, ok := visited[n]  voor lidmaatschapcontrole
// visited[n] = struct{}{}  voor invoegen

In elk geval: hetzelfde gedrag, dezelfde output, dezelfde tests slagen. Alleen de groeisnelheid verandert.

Wat de Fix NIET Verandert

- Het logische gedrag van het algoritme: depth-first blijft depth-first

- Correctheid van de uitvoer: dezelfde knopen worden in dezelfde volgorde bezocht (binnen DFS)

- Testresultaten: alle tests die correctheid controleren blijven slagen

Wat de fix WEL verandert

- Lidmaatschapstest: O(N) → O(1)

- Totale looptijd: O(N²) → O(N)

- Bij N=1.000: 1.000× sneller

- Bij N=10.000: 10.000× sneller

Eén beperking: volgorde

Hash-containers (set, HashSet, unordered_set) bewaren de invoegvolgorde niet. In Python 3.7+ bewaart dict de invoegvolgorde; een gewone set doet dat niet. In Java bewaart HashSet geen volgorde; LinkedHashSet wel.

Als volgorde belangrijk is naast lidmaatschap: onderhoud twee structuren. Een set (of HashSet) voor O(1)-lidmaatschapstests. Een aparte list (of ArrayList) voor geordende doorloop. Of gebruik LinkedHashSet in Java, die beide biedt.

Voor MOAD-0001 bij grafen-doorloop: visited beantwoordt een binaire vraag (is deze knoop al gezien?). Volgorde doet er niet toe voor de lidmaatschapsvraag. De doorloopvolgorde komt van de stack of queue, niet van visited.

Lidmaatschap versus Volgorde

In Tarjan’s algoritme voor sterk samenhangende componenten houdt onStack bij welke knopen nog op de huidige DFS-call-stack staan. Het moet twee vragen beantwoorden: (1) lidmaatschap — staat deze knoop momenteel op de stack? (2) aan het einde van een DFS-pad knopen in volgorde van de stack halen tot deze knoop verschijnt.

Een naïeve implementatie gebruikt een List voor onStack en beantwoordt de lidmaatschapsvraag met contains() — O(N) per controle, O(N²) totaal voor grote grafen.

Waarom dit een disclosure is, geen patch

MOAD-0001 komt voor op meer dan 1.000 geverifieerde locaties in meer dan 60 software-ecosystemen. Grafentraversie in build-tools, route-deduplicatie in netwerkrouting-daemons, botsingsdetectie in game-engines, resource-toewijzing in besturingssysteem-schedulers.

Elke locatie: correcte code. Elke locatie: O(N²)-groei die wacht tot N een drempel overschrijdt.

Het disclosure-proces

Een patch zonder upstream-disclosure lost één locatie op. Het patroon keert terug in de volgende versie, de volgende bibliotheek, de volgende taalport. Disclosure: benoem het patroon, documenteer het als CWE-407 (Algorithmic Complexity: Inefficient Algorithmic Complexity), publiceer de herkenningsheuristieken en de éénregelige fix. Dan kan elke ontwikkelaar die de disclosure leest zijn eigen instantie herkennen en oplossen.

Hamming noemde dit 'een vis geven versus leren vissen.' De patch geeft een vis. De disclosure — MOAD-0001 benoemd, patroon gedocumenteerd, fix gegeneraliseerd — leert de heuristiek.

De Permacomputer-extensie

Hamming werkte aan puntoplossingen: repareer dit filter, verbeter deze code. Unhamming voegt de disclosure-laag toe: benoem het patroon, publiceer de heuristiek en geef het aan de commons.

Het compound-knowledge-principe geldt hier op ecosysteemschaal. Eén onderzoeker benoemt een patroon. Honderd ontwikkelaars herkennen het in hun eigen codebases. Duizend regels O(N²)-code worden O(N). De infrastructuur wordt sneller voor iedereen die erop bouwt.

Dit is de draak die groeit: hetzelfde vuur (werk aan belangrijke problemen, compound knowledge, systems thinking), andere vlucht (open disclosure, commons-eigendom, geen patron vereist).