Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Garbage Collection
Search
Stefan Kanev
November 03, 2013
Programming
0
210
Garbage Collection
OpenFest 2013 talk about garbage collection
Stefan Kanev
November 03, 2013
Tweet
Share
More Decks by Stefan Kanev
See All by Stefan Kanev
Въведение в (Machine|Deep) Learning
skanev
0
87
GraphQL
skanev
0
410
Automated Testing: Getting it Right
skanev
1
64
From Novice to Expert
skanev
0
430
Inbetween Code and Profession
skanev
0
430
Clojure & ClojureScript
skanev
2
120
Extreme Programming
skanev
0
740
За смъртта на TDD
skanev
0
590
Python 0 2014
skanev
1
1.7k
Other Decks in Programming
See All in Programming
Your Perfect Project Setup for Angular @BASTA! 2025 in Mainz
manfredsteyer
PRO
0
120
メモリ不足との戦い〜大量データを扱うアプリでの実践例〜
kwzr
1
780
プログラミングどうやる? ~テスト駆動開発から学ぶ達人の型~
a_okui
0
190
私達はmodernize packageに夢を見るか feat. go/analysis, go/ast / Go Conference 2025
kaorumuta
2
470
ポスターセッション: 「まっすぐ行って、右!」って言ってラズパイカーを動かしたい 〜生成AI × Raspberry Pi Pico × Gradioの試作メモ〜
komofr
0
930
複雑化したリポジトリをなんとかした話 pipenvからuvによるモノレポ構成への移行
satoshi256kbyte
1
750
明日から始めるリファクタリング
ryounasso
0
110
クラシルを支える技術と組織
rakutek
0
190
ソフトウェア設計の実践的な考え方
masuda220
PRO
3
420
Catch Up: Go Style Guide Update
andpad
0
110
高度なUI/UXこそHotwireで作ろう Kaigi on Rails 2025
naofumi
4
3.3k
開発者への寄付をアプリ内課金として実装する時の気の使いどころ
ski
0
340
Featured
See All Featured
Fashionably flexible responsive web design (full day workshop)
malarkey
407
66k
Visualization
eitanlees
148
16k
Documentation Writing (for coders)
carmenintech
75
5k
Done Done
chrislema
185
16k
The Myth of the Modular Monolith - Day 2 Keynote - Rails World 2024
eileencodes
26
3.1k
We Have a Design System, Now What?
morganepeng
53
7.8k
Build your cross-platform service in a week with App Engine
jlugia
232
18k
Writing Fast Ruby
sferik
629
62k
Typedesign – Prime Four
hannesfritz
42
2.8k
Measuring & Analyzing Core Web Vitals
bluesmoon
9
610
Distributed Sagas: A Protocol for Coordinating Microservices
caitiem20
333
22k
Imperfection Machines: The Place of Print at Facebook
scottboms
269
13k
Transcript
Garbage Collection Стефан Кънев http://skanev.com/ @skanev OpenFest 3 ноември 2013
София
Здравейте, аз съм Стефан
DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS
twitter @skanev github skanev blog http://skanev.com/
Всеки път
03.11.2013
I ❤︎ LEGACY
@current_year = 2011 ‑︎ @current_year = 2012
None
2.0 & 2.1
I ❤︎ LEGACY
?
Garbage Collection
None
None
“The undecidability of liveness is a corollary to the halting
problem” — Garbage Collection, Jones et al
None
Stop-and-Copy 1 hour coding 6 hours debugging
Garbage Collection
None
BG PUBLIC ENEMY №1
-а/-ът
None
Ще деплойнем в пръдъкшън след като билда мине на кънтиниъс
интегрейшъна. DISCLAIMER
събирачи на смет свободни списъци пържоли корени
<rant>
Пълният член смуче!
None
ЦСКА vs. Левски
ЦСКА vs. Балкан Ботевград
Долу пълния член!
#ътставка
</rant>
i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
Автоматично освобождаване на неизползваната памет, без баене от страна на
програмиста
това включва и Reference counting
Не целя: kernel developer-и с Garbage Collector web developer-и с
malloc()
Целя: kernel developer-и с Garbage Collector web developer-и с malloc()
Целя: Да добиете някаква представа за collector-ите и особеностите им
Common misconceptions
None
✔! алокацията е по-бърза от malloc()
✘ паузи по минута са възможни
heap памет, където обекти се алокират в произволен ред mutator
програмата (променя паметта) roots стека и регистрите live set паметта, достъпна от корените pointer “стрелка” от един обект към друг cells/objects парчета управлявана памет garbage недостижимата памет
i = 0 while i < N: i += 1
doSomething(i)
Динамично алокиране
None
<=>
O(nlgn)
cnlgn
CPU cache virtual memory*
различни приложения, различни pattern-и на работа
сложен инженерен проблем
i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
REFERENCE COUNTING MARK & SWEEP MARK & COMPACT COPY
Reference Counting
1. Всеки обект има брояч 2. Всеки указател увеличава брояча
3. Триенето на указател намалява 4. free() когато брояча е нула Outline
roots 1 1 REFERENCE COUNTING
roots 1 2 REFERENCE COUNTING
roots 1 1 REFERENCE COUNTING
roots 1 1 1 REFERENCE COUNTING
roots 1 0 1 REFERENCE COUNTING
roots 0 1 REFERENCE COUNTING
roots 1 REFERENCE COUNTING
просто & лесно
None
None
None
roots 1 1 REFERENCE COUNTING
roots 2 2 REFERENCE COUNTING
roots 1 2 REFERENCE COUNTING
roots 1 1 Memory Leak REFERENCE COUNTING
None
weak-refs разни алгоритми
чисто решение няма трябва tracing
None
roots 1 1 1 1 1 1 1 1 1
детерминизъм vs. паузи при големи обекти
✔; Проста имплементация ✔; Детерминистичност ✘ Инкрементации/декрементации ✘ Допълнителна памет
✘ Паузи при големи обекти* ✘ Не освобождава цикли ✔; Повече по-късно
Reference Counting има много варианти
<aside>
x = [] y = [] id(x) == id(y) =>
False id([]) == id([]) => True
a = [] a = id(a) b = [] b
= id(b) a == b
#lolpython
Mark & Sweep
малко интро
header header header heaps
header off-heap storage ✘
Free list Heap Heap MARK/SWEEP
1. Започваме от root-овете 2. Рекурсивно маркираме всичко, до което
може да стигнем 3. Трием немаркираното Outline
roots MARK/SWEEP
roots roots Garbage MARK/SWEEP
Heap MARK/SWEEP
Heap Fragmentation MARK/SWEEP
✔; Събира цикли ✔; По-икономичен (памет и процесор) ✘ Пауза
за обхождане и събиране* ✘ Повече cache misses ✘ Недетерминистичен ✘ Нужда от свободна памет ✘ Линеен на спрямо heap-а
Mark & Compact
1. Маркираме всичко 2. Местим обекти в дупките 3. Обновяваме
указателите Outline
MARK/COMPACT
MARK/COMPACT
STALE POINTERS MARK/COMPACT Active Memory Forwarding Adresses
✔; Евтина алокация ✔; Дефрагментира паметта ✘ Линейно на heap-а
✘ Копирането е бавно ✘ Няма свободни pointer-и (мести)
Copy
1. Разделяме heap-а на две 2. Алокираме в едната половина
3. Копираме достижимото в другата Outline
From space To space COPY
From space To space COPY
From space To space COPY
✔; Евтина алокация ✔; Дефрагментира паметта ✔; Линейно на живите
обекти ✘ 50% място разхищение ✘ Трябва да мести обекти
i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
STOP-THE-WORLD vs. INCREMENTAL vs. PARALLEL vs. CONCURRENT
STOP-THE-WORLD collector mutator
INCREMENTAL sweep mutator mark ✔! Разпределени кратки паузи ✘ Overhead
при алокация
PARALLEL collector mutator
CONCURRENT collector mutator ✔! Не спира света ✘ Overhead за
синхронизация
MOSTLY CONCURRENT collector mutator ✘ Мутатора и колектора се гонят
CONSERVATIVE vs. PRECISE
Трябва помощ от компилатора
None
Weak generational hypothesis: Most objects die young
1. Разделяме heap-а на млади и стари 2. Събираме основно
младите (minor) 3. От време на време събираме старата генерация (major cycle) Outline
Old Generation New Generation roots
Old Generation New Generation roots roots
Old Generation New Generation roots roots
Old Generation New Generation roots roots BUG ☢
WRITE BARRIER
old ˠ young
roots Old Generation New Generation remembered set
i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
Reference counting No cycle detection ;(
Reference counting Full cycle detection
Reference counting Almost full cycle detection
__del__ finalizers
gc.garbage
trololothon
Mark and sweep Incremental, conservative (...)
Java!
None
4
1 SerialGC Stop-the-world copy for young generation Stop-the-world mark/compact for
old generation
2 ParallelGC Stop-the-world copy for young generation Stop-the-world mark/compact for
old generation
3 ConcMarkSweepGC Stop-the-world copy for young generation Mostly concurrent, non-compacting
mark- sweep for older generation Fallback to stop-the-world compacting full collection
4 G1GC Stop-the-world copy for young generation Mostly concurrent marking
old generation Stop-the-world, mostly incremental compacting for old generation Fallback to stop-the-world compaction
HotSpot JRockit IBM J9 Azul Zing
None
None
C C++
Boehm-Demers Collector http://www.hpl.hp.com/personal/Hans_Boehm/gc/
malloc ! GC_MALLOC realloc ! GC_REALLOC
scan the stack find all pointers mark/sweep
detect memory leaks
None
i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
2.0 & 2.1
CoW friendly ‐︎ copy-on-write
None
None
None
RGenGC
None
RARRAY_PTR(obj)
#define RARRAY_PTR(a) \ ((RBASIC(a)->flags & RARRAY_EMBED_FLAG) ? \ RARRAY(a)->as.ary :
\ RARRAY(a)->as.heap.ptr)
break lots of C extensions vs. non-generational GC
Shady Sunny
Shady objects, - go into the remembered set when shaded
- do not get promoted in the old generation
#define RARRAY_PTR(a) \ ((VALUE *) \ RARRAY_CONST_PTR(RGENGC_WB_PROTECTED_ARRAY ?\ OBJ_WB_UNPROTECT((VALUE)a) :
\ ((VALUE)a)))
incrementally update the C extensions
incrementally update the virtual machine
I ❤︎ LEGACY
Books!
None
DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS
DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS
None