Framtida förbättringar för Facett och Falsett
Utvärdera ett trädindex för träfftestning av kanter
Status: Uppskjutet enligt Andreas beslut 2026-10-04. Ingår inte i den pågående 29-stegsplanen. Den implementationen följer planens befintliga rutnätsindex med 64 enheter per cell.
Problem att undersöka
Ett nytt kantindex som lägger varje kant i alla rutnätsceller som dess begränsningsruta täcker kan lagra samma kant många gånger. Långa kanter och stora hubbgrafer kan då kräva mycket minne. Detta gäller ett implementationsförslag för den nya träfftestningen; det är inte ett påvisat fel i Falsetts ursprungliga rendering på main vid a367f9aa.
Möjlig lösning
Utvärdera ett hierarkiskt trädindex, exempelvis ett BVH (bounding volume hierarchy), över nodernas utbredning och kanternas kurvor. Ett sådant index kan lagra varje objekt en gång och ha minnesåtgång som växer linjärt med antalet objekt.
Det är ännu inte visat att detta förbättrar den totala prestandan. Trädet kostar tid att bygga och uppdatera. Många överlappande begränsningsrutor, exempelvis runt en hubb, kan fortfarande ge dyra sökningar.
Underlag före beslut
- Jämför med det index som faktiskt används efter att 29-stegsplanen är färdig.
- Mät minnesåtgång, antal indexposter, byggtid och kostnad för uppdateringar.
- Mät söktid och antal prövade kandidater för både träffar och missar.
- Använd vanliga DAG:ar, hubbgrafer, långa kanter och tätt överlappande kurvor, med ökande grafstorlek.
- Kontrollera att nodrutor, kurvor och träfftoleranser ger korrekta resultat vid olika zoomnivåer.
- Kontrollera att vanlig Falsett-rendering utan träfftestning inte får extra indexbyggen, minnesåtgång eller arbete per bildruta.
Bygg ändringen först efter separat beslut grundat på mätresultaten. Ingen prestandavinst är fastställd ännu.
Första referensmätning av den behållna implementationen
Planens träfftest kördes lokalt med 1 miljon noder och 1,6 miljoner kanter på Apple M2 Pro i debug-läge. En kantträff och en miss tog vardera cirka 71 ms eftersom samtliga kantbegränsningsrutor skannades. De rapporterade därefter en respektive noll kandidater till det mer precisa träfftestet. En nodträff hittades via rutnätsindexet på cirka 6,4 µs.
Detta är ett enda diagnostiskt körresultat, inte en jämförelse med ett trädindex eller ett löfte om dess prestanda. Fixtur, test och begränsningar finns i verifieringsanteckningarna. Uppskjutandet gäller fortfarande.