Teorija

Atsakymas šeštai pamokai

Šeštos pamokos klausimas. Ta pati krūva, tas pats darbas — sudėk visus 10 000 ir ištuštink — dviem būdais.

$ algo pq -in s10k.jsonl -rounds 20
n = 10000, push-all then drain, 20 rounds

                              per round
  hand-written heap             1.469ms
  container/heap                2.395ms

  container/heap is 1.63x slower

Ir tvarkingai, testing.B, po penkis paleidimus:

$ go test -run XXX -bench 'Heap' -benchtime=20x -count=5

BenchmarkHeapMine-32      20    1194035 ns/op
BenchmarkHeapMine-32      20    1216500 ns/op
BenchmarkHeapMine-32      20    1184885 ns/op
BenchmarkHeapMine-32      20    1251305 ns/op
BenchmarkHeapMine-32      20    1172580 ns/op
BenchmarkHeapStdlib-32    20    1964010 ns/op
BenchmarkHeapStdlib-32    20    2018915 ns/op
BenchmarkHeapStdlib-32    20    2039655 ns/op
BenchmarkHeapStdlib-32    20    2015920 ns/op
BenchmarkHeapStdlib-32    20    2013920 ns/op

1.17–1.25 ms prieš 1.96–2.04 ms. Rėžiai nesiliečia. container/heap yra 1.66 karto lėtesnis.

Šeštoje pamokoje standartinė biblioteka laimėjo. Čia ji pralaimi, ir ne per plauką.

Bet KODĖL — štai kur pamoka

Šeštoje pamokoje priežastis buvo viena eilutė: uždarinys žinomas kompiliavimo metu, tad Go jį įterpia (inline) tiesiai į ciklą, ir po optimizacijos iškvietimo nebelieka.

Kas trukdo padaryti tą patį čia? Pažiūrėk į sąsajos parašus dar kartą:

func (s *stdItems) Push(x any)  { *s = append(*s, x.(Item)) }
func (s *stdItems) Pop() any    { ... }

any. Kiekvienas Item įpakuojamas į sąsajos reikšmę įeidamas ir išpakuojamas išeidamas. Item yra 56 baitai, o sąsajos reikšmė — 16, tad struktūra į ją netelpa: ji nukopijuojama į krūvą, o sąsajoje lieka rodyklė.

Kopijavimas į krūvą yra paskirstymas. Pridėk -benchmem:

$ go test -run XXX -bench 'HeapMine|HeapStdlib' -benchtime=20x -count=3 -benchmem

BenchmarkHeapMine-32      20   1256900 ns/op    565248 B/op        1 allocs/op
BenchmarkHeapStdlib-32    20   2026515 ns/op   3934086 B/op    20020 allocs/op

Vienas prieš 20 020

Tavo krūva: vienas paskirstymas. NewMinHeap(len(items)) iš karto paima visą reikalingą griežinį, ir daugiau atmintis neliečiama.

container/heap: 20 020. Iš jų

10 000 — kiekvienas Push, pakuojantis Item į any;
10 000 — kiekvienas Pop, grąžinantis any;
ir dar 19, kol griežinys auga nuo nulio (antros pamokos append, pamatuota ten pat).

Yra ir antras įtariamasis. Less ir Swap yra sąsajos metodai, kviečiami per lentelę: kompiliatorius nežino, kuris tipas atkeliaus, tad įterpti negali. Less yra vienas palyginimas, Swap — vienas sukeitimas. Tokio iškvietimo kaina yra tos pačios eilės kaip pats darbas, kurį jis apgaubia.

Taigi priežastys dvi — pakavimas ir iškvietimai — ir šis matavimas jų neatskiria, nes container/heap primeta abi vienu metu. Ketvirta pratybų užduotis jas atskiria, ir atsakymas aštresnis, nei atrodytų.

Kas iš tikrųjų skiriasi

	6 pamoka, `sort.Search`	13 pamoka, `container/heap`
kas paduodama	uždarinys, žinomas vietoje	tipas, slepiamas už sąsajos
ką daro kompiliatorius	įterpia — iškvietimo nelieka	negali; kviečia per lentelę
ar duomenys pakuojami	ne	taip, 20 000 kartų
rezultatas	abstrakcija nemokama	1.66 karto lėčiau

Šeštoje pamokoje buvo parašyta:

Yra taisyklė, kuri suderina abu atvejus, bet ji ne apie standartinę biblioteką. Ji apie tai, ką kompiliatorius gali permatyti. Toje pamokoje jis matė viską. Kitą kartą — nematys.

Štai tas kitas kartas. Taisyklė — septintame žingsnyje.

Ir dar viena skaitiklio riba

Pastebėk, ko šiame žingsnyje nebuvo nė karto: palyginimų.

Abi krūvos atlieka tiksliai tiek pat palyginimų — tai tas pats algoritmas. Skaitiklis parodytų lygiąsias ir būtų teisus. Visas 1.66 karto skirtumas guli 20 000 paskirstymų ir iškvietimų per lentelę, o palyginimų tarp jų nėra nė vieno.

pamoka	ko skaitiklis nematė
4	atminties
6	savęs paties — pakeitė matuojamą dydį
11	atminties išdėstymo — tie patys 5000.5, 4.5 karto skirtingas laikas
12	rotacijų — 23 % mažiau palyginimų, 1.65 karto lėčiau
13	pakavimo ir iškvietimų — vienodi palyginimai, 1.66 karto lėčiau

Penktas kartas. Ir kaskart ta pati išvada: skaitiklis matuoja algoritmą, laikrodis — programą. Reikia abiejų.