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
200
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
75
GraphQL
skanev
0
360
Automated Testing: Getting it Right
skanev
1
49
From Novice to Expert
skanev
0
420
Inbetween Code and Profession
skanev
0
370
Clojure & ClojureScript
skanev
2
100
Extreme Programming
skanev
0
600
За смъртта на TDD
skanev
0
500
Python 0 2014
skanev
1
1.6k
Other Decks in Programming
See All in Programming
ヤプリ新卒SREの オンボーディング
masaki12
0
130
AWS Lambdaから始まった Serverlessの「熱」とキャリアパス / It started with AWS Lambda Serverless “fever” and career path
seike460
PRO
1
260
TypeScript Graph でコードレビューの心理的障壁を乗り越える
ysk8hori
3
1.2k
シェーダーで魅せるMapLibreの動的ラスタータイル
satoshi7190
1
480
Outline View in SwiftUI
1024jp
1
340
受け取る人から提供する人になるということ
little_rubyist
0
250
EMになってからチームの成果を最大化するために取り組んだこと/ Maximize team performance as EM
nashiusagi
0
100
みんなでプロポーザルを書いてみた
yuriko1211
0
280
とにかくAWS GameDay!AWSは世界の共通言語! / Anyway, AWS GameDay! AWS is the world's lingua franca!
seike460
PRO
1
910
What’s New in Compose Multiplatform - A Live Tour (droidcon London 2024)
zsmb
1
480
Pinia Colada が実現するスマートな非同期処理
naokihaba
4
230
Macとオーディオ再生 2024/11/02
yusukeito
0
380
Featured
See All Featured
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
47
2.1k
Rails Girls Zürich Keynote
gr2m
94
13k
Designing the Hi-DPI Web
ddemaree
280
34k
Adopting Sorbet at Scale
ufuk
73
9.1k
Code Reviewing Like a Champion
maltzj
520
39k
Optimising Largest Contentful Paint
csswizardry
33
2.9k
For a Future-Friendly Web
brad_frost
175
9.4k
Learning to Love Humans: Emotional Interface Design
aarron
273
40k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
250
21k
Site-Speed That Sticks
csswizardry
0
33
Building an army of robots
kneath
302
43k
Six Lessons from altMBA
skipperchong
27
3.5k
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