Garbage Collection

OpenFest 2013 talk about garbage collection

Transcript

1. Garbage Collection Стефан Кънев http://skanev.com/ @skanev OpenFest 3 ноември 2013 София
2. Здравейте, аз съм Стефан
3. DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS DEVELOPERS
4. twitter @skanev github skanev blog http://skanev.com/
5. Всеки път
6. 03.11.2013
7. I ❤︎ LEGACY
8. @current_year = 2011 ‑︎ @current_year = 2012
10. 2.0 & 2.1
11. I ❤︎ LEGACY
12. ?
13. Garbage Collection
16. “The undecidability of liveness is a corollary to the halting problem” — Garbage Collection, Jones et al
18. Stop-and-Copy 1 hour coding 6 hours debugging
19. Garbage Collection
21. BG PUBLIC ENEMY №1
22. -а/-ът
24. Ще деплойнем в пръдъкшън след като билда мине на кънтиниъс интегрейшъна. DISCLAIMER
25. събирачи на смет свободни списъци пържоли корени
26. <rant>
27. Пълният член смуче!
29. ЦСКА vs. Левски
30. ЦСКА vs. Балкан Ботевград
31. Долу пълния член!
32. #ътставка
33. </rant>
34. i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
35. i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
36. Автоматично освобождаване на неизползваната памет, без баене от страна на програмиста
37. това включва и Reference counting
38. Не целя: kernel developer-и с Garbage Collector web developer-и с malloc()
39. Целя: kernel developer-и с Garbage Collector web developer-и с malloc()
40. Целя: Да добиете някаква представа за collector-ите и особеностите им
41. Common misconceptions
43. ✔! алокацията е по-бърза от malloc()
44. ✘ паузи по минута са възможни
45. heap памет, където обекти се алокират в произволен ред mutator програмата (променя паметта) roots стека и регистрите live set паметта, достъпна от корените pointer “стрелка” от един обект към друг cells/objects парчета управлявана памет garbage недостижимата памет
46. i = 0 while i < N: i += 1 doSomething(i)
47. Динамично алокиране
49. <=>
50. O(nlgn)
51. cnlgn
52. CPU cache virtual memory*
53. различни приложения, различни pattern-и на работа
54. сложен инженерен проблем
55. i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
56. REFERENCE COUNTING MARK & SWEEP MARK & COMPACT COPY
57. Reference Counting
58. 1. Всеки обект има брояч 2. Всеки указател увеличава брояча 3. Триенето на указател намалява 4. free() когато брояча е нула Outline
59. roots 1 1 REFERENCE COUNTING
60. roots 1 2 REFERENCE COUNTING
61. roots 1 1 REFERENCE COUNTING
62. roots 1 1 1 REFERENCE COUNTING
63. roots 1 0 1 REFERENCE COUNTING
64. roots 0 1 REFERENCE COUNTING
65. roots 1 REFERENCE COUNTING
66. просто & лесно
70. roots 1 1 REFERENCE COUNTING
71. roots 2 2 REFERENCE COUNTING
72. roots 1 2 REFERENCE COUNTING
73. roots 1 1 Memory Leak REFERENCE COUNTING
75. weak-refs разни алгоритми
76. чисто решение няма трябва tracing
78. roots 1 1 1 1 1 1 1 1 1
79. детерминизъм vs. паузи при големи обекти
80. ✔; Проста имплементация ✔; Детерминистичност ✘ Инкрементации/декрементации ✘ Допълнителна памет ✘ Паузи при големи обекти* ✘ Не освобождава цикли ✔; Повече по-късно
81. Reference Counting има много варианти
82. <aside>
83. x = [] y = [] id(x) == id(y) => False id([]) == id([]) => True
84. a = [] a = id(a) b = [] b = id(b) a == b
85. #lolpython
86. Mark & Sweep
87. малко интро
88. header header header heaps
89. header off-heap storage ✘
90. Free list Heap Heap MARK/SWEEP
91. 1. Започваме от root-овете 2. Рекурсивно маркираме всичко, до което може да стигнем 3. Трием немаркираното Outline
92. roots MARK/SWEEP
93. roots roots Garbage MARK/SWEEP
94. Heap MARK/SWEEP
95. Heap Fragmentation MARK/SWEEP
96. ✔; Събира цикли ✔; По-икономичен (памет и процесор) ✘ Пауза за обхождане и събиране* ✘ Повече cache misses ✘ Недетерминистичен ✘ Нужда от свободна памет ✘ Линеен на спрямо heap-а
97. Mark & Compact
98. 1. Маркираме всичко 2. Местим обекти в дупките 3. Обновяваме указателите Outline
99. MARK/COMPACT
100. MARK/COMPACT
101. STALE POINTERS MARK/COMPACT Active Memory Forwarding Adresses
102. ✔; Евтина алокация ✔; Дефрагментира паметта ✘ Линейно на heap-а ✘ Копирането е бавно ✘ Няма свободни pointer-и (мести)
103. Copy
104. 1. Разделяме heap-а на две 2. Алокираме в едната половина 3. Копираме достижимото в другата Outline
105. From space To space COPY
106. From space To space COPY
107. From space To space COPY
108. ✔; Евтина алокация ✔; Дефрагментира паметта ✔; Линейно на живите обекти ✘ 50% място разхищение ✘ Трябва да мести обекти
109. i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
110. STOP-THE-WORLD vs. INCREMENTAL vs. PARALLEL vs. CONCURRENT
111. STOP-THE-WORLD collector mutator
112. INCREMENTAL sweep mutator mark ✔! Разпределени кратки паузи ✘ Overhead при алокация
113. PARALLEL collector mutator
114. CONCURRENT collector mutator ✔! Не спира света ✘ Overhead за синхронизация
115. MOSTLY CONCURRENT collector mutator ✘ Мутатора и колектора се гонят
116. CONSERVATIVE vs. PRECISE
117. Трябва помощ от компилатора
119. Weak generational hypothesis: Most objects die young
120. 1. Разделяме heap-а на млади и стари 2. Събираме основно младите (minor) 3. От време на време събираме старата генерация (major cycle) Outline
121. Old Generation New Generation roots
122. Old Generation New Generation roots roots
123. Old Generation New Generation roots roots
124. Old Generation New Generation roots roots BUG ☢
125. WRITE BARRIER
126. old ˠ young
127. roots Old Generation New Generation remembered set
128. i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
129. Reference counting No cycle detection ;(
130. Reference counting Full cycle detection
131. Reference counting Almost full cycle detection
132. __del__ finalizers
133. gc.garbage
134. trololothon
135. Mark and sweep Incremental, conservative (...)
136. Java!
139. 1 SerialGC Stop-the-world copy for young generation Stop-the-world mark/compact for old generation
140. 2 ParallelGC Stop-the-world copy for young generation Stop-the-world mark/compact for old generation
141. 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
142. 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
143. HotSpot JRockit IBM J9 Azul Zing
146. C C++
147. Boehm-Demers Collector http://www.hpl.hp.com/personal/Hans_Boehm/gc/
148. malloc ! GC_MALLOC realloc ! GC_REALLOC
149. scan the stack find all pointers mark/sweep
150. detect memory leaks
152. i.Garbage Collection ii.Algorithms iii.Classifications iv.Languages v.Ruby 2.0 & Ruby 2.1
153. 2.0 & 2.1
154. CoW friendly ‐︎ copy-on-write
158. RGenGC
160. RARRAY_PTR(obj)
161. #define RARRAY_PTR(a) \ ((RBASIC(a)->flags & RARRAY_EMBED_FLAG) ? \ RARRAY(a)->as.ary : \ RARRAY(a)->as.heap.ptr)
162. break lots of C extensions vs. non-generational GC
163. Shady Sunny
164. Shady objects, - go into the remembered set when shaded - do not get promoted in the old generation
165. #define RARRAY_PTR(a) \ ((VALUE *) \ RARRAY_CONST_PTR(RGENGC_WB_PROTECTED_ARRAY ?\ OBJ_WB_UNPROTECT((VALUE)a) : \ ((VALUE)a)))
166. incrementally update the C extensions
167. incrementally update the virtual machine
168. I ❤︎ LEGACY
169. Books!
171. 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