Go Garbage Collector — concurrent tri-color incremental mark & sweep algorithm.

Доклад Рика Хадсона на конференции GopherCon 2015 о том, как в Go 1.5 удалось радикально уменьшить STW (Stop-The-World) задержки исполнения потоков программы (до наносекундных/субмиллисекундных показателей в последующих версиях, вплоть до крайних Go 1.8 и 1.9) благодаря применению гибридных алгоритмов многопоточной сборки мусора (GC) для программ написанных на языке Go.

https://www.youtube.com/watch?v=aiv1JOfMjm0

https://blog.golang.org/go15gc

Слайды:
https://talks.golang.org/2015/go-gc.pdf

Roadmap - на пути к версии 1.5:
http://golang.org/s/go14gc (https://docs.google.com/document/d/16Y4IsnNRCN43Mx0NZc5YXZLovrHvvLhK_h0KN8woTO4/edit)

Метрики:
https://github.com/bmhatfield/go-runtime-metrics

https://twitter.com/brianhatfield/status/900473287750365184

Статья с оценкой производительности и метрик сервиса Twitch в их блоге:
https://blog.twitch.tv/gos-march-to-low-latency-gc-a6fa96f06eb7

В версии языка и компилятора Go 1.5 был кардинально переработан код сборщика мусора (GC), до этой версии он был полностью переписан на самом Go методами автоматного (транс-компиляция с языка Си), а после и ручного программирования (коррекция) и были внедрены новые (вернее старые, но давно забытые) улучшения в алгоритмы многопоточной сборки мусора, благодаря чему данный GC стал лучшей программой в своём классе (субмиллисекундные задержки при освобождении памяти даже для оперативных in-memory хранилищ данных с размером кучи в 256 ГиБ (heap-size) для каждой ноды кластера!).

Эта разработка стала исторической вехой не только для языка Go, укрепившей его позиции в серверной разработке облачных инфраструктур, сетевых сервисов и демонов сетевых протоколов (server-side cloud infrastructure software development), но и большим прецедентом для доказательства работоспособности концепций (proof-of-concept) алгоритмов сборки мусора, разработанных ещё в 1970-х годах (tri-color, quad-color, incremental, mark & sweep algorithms).

Алгоритм сборки мусора, применённый в GC для программ на Go - это многопоточный трёхцветный (по фазам пометки указателей с последующим перемещением и освобождением блоков памяти) алгоритм коллектора (concurrent tri-color incremental mark & sweep collector), концепция которого была разработана известным датским математиком и инженером Эдсгером Дейкстра в 1978 году.

https://www.cs.utexas.edu/users/EWD/transcriptions/EWD05xx/EWD520.html

Но run-time (фаза исполнения) программ на Go был не первым проектом где был применён подобный алгоритм для коллектора памяти (GC).
Ранее Майк Пэлл (Mike Pall), автор знаменитого оптимизированного JIT копилятора Lua, применил подобный алгоритм в LuaJIT версий 1.x/2.0 для run-time фазы исполнения программ на языке Lua.
В LuaJIT будущей версии 3.0 автор планирует реализовать ещё более продвинутый четырёх-цветный оптимизированный алгоритм коллектора (Quad-Color Optimized Incremental Mark & Sweep GC).

http://wiki.luajit.org/New-Garbage-Collector

В run-time фазе исполнения программ оригинальным интерпретатором Lua версий 5.1/5.2 также используется трёхцветный алгоритм коллектора (Tri-Color Incremental Mark & Sweep GC). В более ранней версии Lua 5.0 использовался стандартный двухцветный алгоритм для коллектора памяти (Two-Color Mark & Sweep GC).

Отличная статья в блоге Майка Хёрна (Mike Hearn) о Go GC и вызовах современной компьютерной индустрии при создании гибридных алгоритмов коллекторов памяти:
https://blog.plan99.net/modern-garbage-collection-911ef4f8bd8e

Визуализация различных алгоритмов сборки мусора - https://t.me/technologique/958

#Go
#GC
#Lua
#ThrowbackTech

Ссылки:
https://t.me/technologique/721
https://t.me/technologique/722
https://t.me/technologique/750
https://t.me/technologique/1057

https://t.me/technologique/732
https://t.me/technologique/551
https://t.me/technologique/423

https://t.me/technologique/1157