Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Garbage Collection

Avatar for Stefan Kanev Stefan Kanev
November 03, 2013
Programming
0
210

Garbage Collection

OpenFest 2013 talk about garbage collection

Avatar for Stefan Kanev

Stefan Kanev

November 03, 2013
Tweet

More Decks by Stefan Kanev

See All by Stefan Kanev
Въведение в (Machine|Deep) Learning
Avatar for Stefan Kanev skanev
0
88
GraphQL
Avatar for Stefan Kanev skanev
0
420
Automated Testing: Getting it Right
Avatar for Stefan Kanev skanev
1
67
From Novice to Expert
Avatar for Stefan Kanev skanev
0
430
Inbetween Code and Profession
Avatar for Stefan Kanev skanev
0
430
Clojure & ClojureScript
Avatar for Stefan Kanev skanev
2
120
Extreme Programming
Avatar for Stefan Kanev skanev
0
760
За смъртта на TDD
Avatar for Stefan Kanev skanev
0
590
Python 0 2014
Avatar for Stefan Kanev skanev
1
1.7k

Other Decks in Programming

See All in Programming
その面倒な作業、「Dart」にやらせませんか？ Flutter開発者のための業務効率化
Avatar for YomEngine yordgenome03
1
140
コードとあなたと私の距離 / The Distance Between Code, You, and I
Avatar for YAMAOKA Hiroyuki hiro_y
0
190
社会人になっても趣味開発を続けたい！ / traPavilion
Avatar for mazrean mazrean
1
100
AI駆動で0→1をやって見えた光と伸びしろ
Avatar for passion😎 passion0102
1
840
What's new in Spring Modulith?
Avatar for Oliver Drotbohm olivergierke
1
170
品質ワークショップをやってみた
Avatar for Nealle nealle
0
630
SODA - FACT BOOK（JP）
Avatar for SODA inc. sodainc
1
8.7k
Catch Up: Go Style Guide Update
Avatar for ANDPAD inc andpad
0
250
Google Opalで使える37のライブラリ
Avatar for MIKIO KUBO mickey_kubo
3
140
Migration to Signals, Resource API, and NgRx Signal Store
Avatar for Manfred Steyer manfredsteyer
PRO
0
110
Introduce Hono CLI
Avatar for Yusuke Wada yusukebe
6
3.1k
Ktorで簡単AIアプリケーション
Avatar for Keita Tsukamoto tsukakei
0
100

Featured

See All Featured
Designing Experiences People Love
Avatar for Jonathan Moore moore
142
24k
It's Worth the Effort
Avatar for 3n 3n
187
28k
[Rails World 2023 - Day 1 Closing Keynote] - The Magic of Rails
Avatar for Eileen M. Uchitelle eileencodes
37
2.6k
Scaling GitHub
Avatar for Zach Holman holman
463
140k
Designing for humans not robots
Avatar for Tammie Lister tammielis
254
26k
Agile that works and the tools we love
Avatar for Rasmus Luckow-Nielsen rasmusluckow
331
21k
XXLCSS - How to scale CSS and keep your sanity
Avatar for Zaharenia Atzitzikaki sugarenia
249
1.3M
Being A Developer After 40
Avatar for Adrian Kosmaczewski akosma
91
590k
Building a Modern Day 
E-commerce SEO Strategy
Avatar for Aleyda Solis aleyda
44
7.8k
Speed Design
Avatar for Sergey Chernyshev sergeychernyshev
32
1.2k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
Avatar for Vitaly Friedman smashingmag
253
22k
Improving Core Web Vitals using Speculation Rules API
Avatar for Sergey Chernyshev sergeychernyshev
21
1.2k

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

  9. None

  10. 2.0 & 2.1

  11. I ❤︎ LEGACY

  12. ?

  13. Garbage Collection

  14. None
  15. None

  16. “The undecidability of liveness is a corollary to the halting

    problem” — Garbage Collection, Jones et al
  17. None

  18. Stop-and-Copy 1 hour coding 6 hours debugging

  19. Garbage Collection

  20. None

  21. BG PUBLIC ENEMY №1

  22. -а/-ът

  23. None

  24. Ще деплойнем в пръдъкшън след като билда мине на кънтиниъс

    интегрейшъна. DISCLAIMER

  25. събирачи на смет свободни списъци пържоли корени

  26. <rant>

  27. Пълният член смуче!

  28. None

  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

  42. None

  43. ✔! алокацията е по-бърза от malloc()

  44. ✘ паузи по минута са възможни

  45. heap памет, където обекти се алокират в произволен ред mutator

    програмата (променя паметта) roots стека и регистрите live set паметта, достъпна от корените pointer “стрелка” от един обект към друг cells/objects парчета управлявана памет garbage недостижимата памет

  46. i = 0 while i < N: i += 1

    doSomething(i)

  47. Динамично алокиране

  48. None

  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. просто & лесно

  67. None
  68. None
  69. None

  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

  74. None

  75. weak-refs разни алгоритми

  76. чисто решение няма трябва tracing

  77. None

  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. Трябва помощ от компилатора

  118. None

  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!

  137. None

  138. 4

  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

  144. None
  145. None

  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

  151. None

  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

  155. None
  156. None
  157. None

  158. RGenGC

  159. None

  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!

  170. None

  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
  172. None