Teorija

transit: kaip renkamasi indeksą

transit — Vilniaus viešojo transporto maršrutų paieškos serveris — turi tą patį klausimą, kurį ką tik sprendei: kaip indeksuoti 1 531 stotelę. Jis atsakė du kartus, skirtingiems klausimams, ir vienas iš atsakymų yra klaidingas lietuviškai — sąmoningai, amžinai ir su testais, kurie neleidžia to pataisyti.

Antraštė: baitai nėra raidės

Prisimeni struktūrinio programavimo kurso septintą pamoką? len("ąžuolas") = 9, nors raidžių 7. Tai buvo to kurso centrinė spąstų vieta. Štai kas atsitinka, kai ta pati klaida patenka į paieškos indeksą.

Stotelių paieška privalo tenkinti tris reikalavimus:

įvedus "zirmunu"  turi rasti "Žirmūnų"   (diakritikų į paieškos laukelį niekas neveda)
įvedus "žirmūnų"  turi rasti "Žirmūnų"   (bet jei įveda — irgi turi veikti)
įvedus "ŽIRMŪNŲ"  turi rasti "Žirmūnų"   (registras nesvarbus abiem kryptimis)

Pirmas bandymas — įprastas C stiliaus ciklas per baitus:

func foldBytes(s string) string {
	b := []byte(s)
	for i := 0; i < len(b); i++ {
		if b[i] >= 'A' && b[i] <= 'Z' {
			b[i] += 'a' - 'A'
		}
	}
	return string(b)
}

Ir kas iš to išeina:

"Ž"  baitai C5 BD  runos 1  ilgis 2
"ž"  baitai C5 BE  runos 1  ilgis 2

"Katedros"  foldBytes -> "katedros"     Fold -> "katedros"
"Žirmūnų"   foldBytes -> "Žirmūnų"      Fold -> "zirmunu"
"ŽIRMŪNŲ"   foldBytes -> "ŽirmŪnŲ"      Fold -> "zirmunu"

Įsižiūrėk į "ŽirmŪnŲ". Latiniškos raidės sumažėjo, lietuviškos ne. Ne todėl, kad kažkas buvo pamiršta, o todėl, kad Ž nėra baitas: tai C5 BD, o ž yra C5 BE. Jie skiriasi tik antruoju baitu, tad b[i] >= 'A' && b[i] <= 'Z' jų niekada nesujungs — jokiu pataisymu, jokia papildoma sąlyga.

Antra bėda ta pati, kitoje vietoje. Medis (trie) šakojasi kiekvienam baitui:

"Žirmūnų": 10 baitų, 7 runos -> baitų medis yra 10 lygių gylio, runų medis 7
mazgas 1 lygyje laiko baitą 0xC5, o tokios raidės niekas neįvedė

Trys papildomi lygiai, o kas trečiame — pusė UTF-8 sekos. Ne raidė. Ne kažkas, ką vartotojas galėtų parašyti.

Angliškuose duomenyse abi versijos elgiasi vienodai — būtent todėl klaida išgyvena testavimą. "Katedros" per abi funkcijas eina teisingai. Studentas lietuviškai įveda „žirmūnai" ir negauna nieko.

Taisymas — iteruoti runomis, nes for _, r := range s dekoduoja UTF-8:

for _, r := range s {          // runų iteracija
	r = unicode.ToLower(r) // Unicode-aware: 'Ž' -> 'ž', ne tuščias veiksmas
	if f, ok := ltFold[r]; ok {
		r = f
	}
	b.WriteRune(r)
}

Kaip `transit` neleidžia to „pataisyti"

Sugadinta versija repozitorijoje lieka visam laikui, nes ji yra pamokos pirmoji pusė. Bet ji negali netyčia patekti į veikiantį serverį — ji gyvena faile search_bytetrie_demo_test.go, o Go _test.go failus kompiliuoja tik go test. Serveris, CLI ar bet kokia būsima diagnostika negali jos net paminėti: kompiliacija nulūžtų.

Tai kompiliavimo meto garantija, o ne pavadinimų susitarimas ar kodo peržiūros taisyklė.

Ir du testai reikalauja, kad ji liktų sugedusi:

$ go test ./internal/store/ -run 'TestByteTrieFailsOnRealFeed|TestFoldBytesIsBrokenOnLithuanian' -v
=== RUN   TestFoldBytesIsBrokenOnLithuanian
--- PASS: TestFoldBytesIsBrokenOnLithuanian (0.00s)
=== RUN   TestByteTrieFailsOnRealFeed
    search_realfeed_test.go:99: byte trie nodes=4850, rune trie nodes=4173
--- PASS: TestByteTrieFailsOnRealFeed (13.31s)

Ta pati forma, kaip septintos pamokos atrankinis rikiavimas ir aštuntos quicksort: trūkumas įtvirtinamas testu, kad liktų matomas.

Kur maišos lentelė iš tikrųjų laimėjo

Dabar — pati struktūra. Kiek verta maišos lentelė vietoj tiesinio stotelių sąrašo? Izoliuotai (mūsų matavimas, docs/reference/transit-benchmarks.md):

vienos stotelės paieška, n = 1 531	mūsų matavimas
tiesinė	1.22 µs
maiša	7.02 ns
santykis	174×

174 kartai atrodo įtikinamai. Ir vis dėlto to neužtenka, ir transit repozitorija tai pasako pati: ir 1.22 µs, ir 7 ns žmogui yra nulis. Vienam paieškos veiksmui šis skirtumas nepastebimas.

Argumentas yra kitas. Kraunant maršrutų duomenis, kiekvienas stop_time įvykis turi išsiaiškinti savo stotelę — apie 207 000 paieškų vieno paleidimo metu. Ten skirtumas matomas:

viso duomenų įkėlimo trukmė	mūsų matavimas (3 paleidimai)
tiesinis indeksas	1549 ms
maišos indeksas	1200 ms
skirtumas	~350 ms

Trečdalis sekundės kiekvieną kartą paleidžiant serverį. transit README skelbia 468 ms; mūsų kompiuteryje išėjo ~25 % mažiau, o trijų matavimų sklaida yra 165 ms, tad tikslesnio skaičiaus nei „maždaug trečdalis sekundės" čia nė nereikia bandyti.

Struktūrą pateisino ne izoliuotas santykis, o kur ji naudojama.

Kitas indeksas kitam klausimui

Yra ir antra struktūra: prefiksų medis (trie), kuris atsako į kitą klausimą. Maišos lentelė moka „ar yra tokia stotelė"; medis moka „kokios stotelės prasideda šiomis raidėmis" — o būtent tai daro paieškos laukelis, kai vartotojas rašo.

Jo nestatysi. Bet verta pamatyti, kaip priimamas sprendimas jo nenaudoti.

Autoįvedimo užklausai medis laimi aiškiai — nuo 7.9× (3 raidės) iki 22× (8 raidės). Bet vartotojas neužduoda vienos užklausos: jis rašo, ir kiekvienas paspaudimas yra nauja užklausa. Visai „zirmunai" rašymo sesijai (8 paspaudimai):

„zirmunai" sesija	`transit` kompiuteris	mūsų kompiuteris
tiesinis	130 µs	~135 µs
runų medis	250 µs	~42 µs
laimėtojas	tiesinis	medis, ~3.2×

Atsakymas apsivertė. Jų mašinoje medis sesiją pralaimėjo ~120 µs; mūsų — laimėjo ~93 µs. Skiriasi ne dydis, o kryptis.

Ir vis dėlto išvada abiem atvejais ta pati, nes argumentas niekada nebuvo santykis:

ten medis kainuoja ~120 µs, čia sutaupo ~93 µs;
abu skaičiai yra dešimtoji milisekundės dalis;
rašymo sesija žmogui trunka ~160 ms, o įdiegtoje programoje dar prisideda tinklo kelionė;
vadinasi, visas ginčas vyksta trys eilės žemiau už tai, su kuo lyginamas.

O medis kainuoja 777 KB prieš 113 KB atminties (6.9×) ir 3.1× ilgesnį pastatymą. Tai atlyginimo reikalavimas už skaičių, kurio nė vienoje mašinoje neįmanoma pajusti.

Teisinga struktūra tam klausimui — ir vis tiek neverta šiame dydyje.

Palygink tai su šeštąja pamoka

Šeštoje pamokoje matavimas taip pat priklausė nuo mašinos: tiesinės ir dvejetainės paieškos persikirtimo taškas juda. Bet ten jis keičia sprendimą, nes matavimas vyksta ties pačia riba.

Čia matavimas irgi juda, netgi apsiverčia — ir sprendimas nesikeičia, nes skirtumas yra tris eiles nuo bet kokios ribos.

Skirti šiuos du atvejus ir yra įgūdis:

Klausk ne „ar mano skaičius sutampa su kito", o „ar mano skaičius yra arti sprendimo ribos". Jei taip — matuok savo mašinoje. Jei ne — svetimas matavimas gali visai nesutapti su tavo, ir tai nieko nekeičia.