Schnell machen

Mein core.logic-Fork, Teil 3 von 9. Übersicht · ← Kein nicht unterstütztes Verhalten · Vektoren →

Als die Relationen in jedem Modus korrekt waren, habe ich jede davon mit Map-Größen 10, 100 und 1000 gemessen. Manche waren in Ordnung. Manche nicht:

Operation, n = 1000	Vorher	Nachher
n × `geto` baut eine unbekannte Map auf	33 s	8.2 ms
`valso` mit gegebener Werteliste	faktoriell: bei n = 10 nicht fertig	0.4 ms
`mergeo m m`	465 ms	0.5 ms
`==` mit unbekanntem Schlüssel in eine große Map	97 ms	1.5 ms
`geto` zählt alle Schlüssel auf	49 ms	2.3 ms
`geto` mit bekanntem Schlüssel	0.26 ms	0.013 ms, konstant in n
`geto` mit fehlendem Schlüssel	0.31 ms	0.05 ms
`selectso`, 5 Schlüssel	1.4 ms	0.17 ms
Kette aus 1000 `assoco` (`run-nc`)	267 ms	35–38 ms

Keiner der Fixes hat geändert, was die Relationen bedeuten. Jeder ist ein Fall, in dem der Code das Allgemeine tat, obwohl etwas Billigeres und genauso Exaktes verfügbar war.

Constraints, die sich auftürmten

Jedes geto auf einer unbekannten Map fügt ihrem offenen Teil einen Schlüssel hinzu, und der neue Rest darf keinen der bisherigen Schlüssel enthalten. Die erste Version hängte pro Schlüssel ein Constraint an jeden Rest. Nach n Lookups sind das O(n²) Constraints, und jedes wird beim Binden neu geprüft: insgesamt kubisch, und 33 Sekunden bei n = 1000.

Jetzt trägt jede Variable höchstens ein Lacks-Constraint, das eine persistente Menge von Schlüsseln hält. Ein neuer Rest übernimmt die Menge und fügt einen Schlüssel hinzu, also bleibt der Constraint-Store linear.

Fakultät, wo es linear sein sollte

valso sagt "das sind die Werte, in beliebiger Reihenfolge", und die naheliegende relationale Definition ist permuteo. Bei gegebener Werteliste durchsucht permuteo Reihenfolgen: faktoriell in der Länge. Das nackte permuteo braucht bei zehn Elementen 1,5 s, und das erste valso darauf wurde nicht fertig.

Wenn alles bekannt ist, lautet die Frage nur "gleiche Multimenge?", eine Häufigkeitszählung. Wenn einige Elemente unbekannt sind, entfernt man sie eins nach dem anderen und verzweigt nur dort, wo ein Element unbekannt ist. permuteo bleibt für den einen Fall, der es braucht: Die Werteliste selbst ist unbekannt, und jede Reihenfolge ist eine eigene Antwort.

Nicht berechnen, wonach keiner gefragt hat

geto war über ein allgemeines "pick"-Primitiv definiert: m ist m' plus k → v. Das baut m', die Map ohne k. geto wirft m' weg. Bei n = 1000 ist das eine Kopie mit 1000 Einträgen pro Lookup. Jetzt nimmt das Primitiv "kein Rest gewünscht" entgegen und überspringt ihn, und ein bekannter Schlüssel in einer gewöhnlichen Map ist einfach ein Hash-Lookup.

Das Aufteilen einer Map in bekannte Einträge und Rest kopierte jedes Mal die Einträge. Jetzt gibt es die bestehende Map zurück, wenn sich nichts ändert, und mergt sonst die kleinere Seite in die größere. mergeo zweier vollständig bekannter Maps ist jetzt ein einfaches merge. Unifikation mit unbekannten Schlüsseln gleicht alle bekannten Schlüssel in einem Durchgang ab und sucht nur über die unbekannten.

Ketten

Der letzte Fall war der interessanteste. Wächst eine offene Map Schlüssel um Schlüssel, entsteht eine Kette:

m → (lmap {:k0 0} | r1)
r1 → (lmap {:k1 1} | r2)
r2 → (lmap {:k2 2} | r3)
...

Jeder spätere Lookup auf m läuft die ganze Kette ab, um alle Schlüssel zu sehen. n Lookups, von denen jeder bis zu n Glieder abläuft, sind quadratisch: 176 ms bei n = 1000.

Das ist Pfadkompression, der alte Union-Find-Trick. Wenn ein Lookup eine Kette mit mehr als einem Glied abläuft, bindet er m neu an die flache Map, die er gerade berechnet hat: m → (lmap {:k0 0 :k1 1 ... :kn n} | rn). Das ist kein neues Faktum, die beiden Terme sind unter der aktuellen Substitution gleich, also muss kein Constraint neu laufen. Der nächste Lookup läuft ein Glied und einen neuen Eintrag ab. Aus 176 ms wurden 8.2 ms, und das Wachstum ist wieder linear.

Die Zwischen-Reste bleiben gebunden wie zuvor, also sieht alles andere, was auf r1 verweist, weiterhin dieselbe Map.

Was Upstream-Code bezahlt

Nichts Messbares. Programme, die nie Maps benutzen, erreichen den Code der Relationen nicht, und die Upstream-Benchmarks liegen im Rauschen. Das Huckepack auf dem Occurs-Check aus Teil 2 kostet zwei Zählerzugriffe pro Bindung, wenn der Occurs-Check an ist.

Weiter: Vektoren.