Kaip giliai — ir kas nutinka gale

Prijunk walk ir depth prie main.go. algo depth sukuria grandinę — aplanką aplanke aplanke, be šakojimosi — tad rekursijos gylis lygus n.

Spėk prieš skaitydamas

Go gijos stekas auga savaime: prasideda nuo maždaug 8 kilobaitų ir plečiasi, kai reikia. C gijoje stekas fiksuotas — dažniausiai 1–8 megabaitai — ir pasiekęs ribą tavo procesas krenta.

Kaip giliai, tavo manymu, nusileis Go rekursija? Užsirašyk skaičių prieš žiūrėdamas toliau.

Atsakymas

$ algo depth -n 1000000
recursive walk of a chain 1000000 deep: 1000000 items, 1000001 folders, 72ms

$ algo depth -n 8000000
recursive walk of a chain 8000000 deep: 8000000 items, 8000001 folders, 621ms

Aštuoni milijonai kadrų. Be jokių problemų, per 0,6 sekundės.

Jei spėjai tūkstančius ar dešimtis tūkstančių — taip būtų buvę C. Go stekas išauga, kiek reikia, iki numatytosios 1 gigabaito ribos.

Ir kur jis vis dėlto baigiasi

$ algo depth -n 16000000
runtime: goroutine stack exceeds 1000000000-byte limit
fatal error: stack overflow

main.WalkRecursive(0x0?, 0x2bd4e9b5fe28)
	.../walk.go:28 +0x45 fp=0x2bd4c9b61f98 sp=0x2bd4c9b61f58
main.WalkRecursive(0x0?, 0x2bd4e9b5fe28)
	.../walk.go:28 +0x45 fp=0x2bd4c9b61fd8 sp=0x2bd4c9b61f98
...8388426 frames elided...

Trys dalykai šitame pranešime verti dėmesio.

„fatal error", ne „panic". Šito negali pagauti su recover. Programa baigėsi. Tai vienintelė Go klaida, kurios neapdorosi.

Riba pasakyta tiksliai: 1 000 000 000 baitų.

Go pasako, kiek kadrų paslėpė: ...8388426 frames elided.... Iš to apskaičiuoji kadro dydį:

1 000 000 000 B ÷ 8 388 426 kadrų ≈ 119 baitų kadrui

Kiekvienas WalkRecursive iškvietimas kainuoja apie 119 baitų. Štai kiek kainuoja „paslėptas" stekas.

Tas pats darbas, tavo steku

$ algo depth -n 16000000 -iterative
iterative walk of a chain 16000000 deep: 16000000 items, 16000001 folders, 129ms

Tas pats gylis, kuris nužudė rekursiją. Ciklinė versija jį apeina per 129 milisekundes ir net nesuprakaituoja — nes jos stekas yra []*Folder paprastoje krūvoje (heap), o krūva neturi tos 1 GB ribos.

Ir ji greitesnė visur, ne tik ties riba: 72 ms prieš 8 ms ties milijonu. Funkcijos iškvietimas nėra nemokamas.