Essentials of Garbage Collectors
4.4 (53 ratings)
Course Ratings are calculated from individual students’ ratings and a variety of other signals, like age of rating and reliability, to ensure that they reflect course quality fairly and accurately.
642 students enrolled

Essentials of Garbage Collectors

Automatic memory management techniques
4.4 (53 ratings)
Course Ratings are calculated from individual students’ ratings and a variety of other signals, like age of rating and reliability, to ensure that they reflect course quality fairly and accurately.
642 students enrolled
Created by Dmitry Soshnikov
Last updated 9/2019
English
English
Current price: $14.99 Original price: $154.99 Discount: 90% off
30-Day Money-Back Guarantee
This course includes
  • 2 hours on-demand video
  • Full lifetime access
  • Access on mobile and TV
  • Certificate of Completion
Training 5 or more people?

Get your team access to 4,000+ top Udemy courses anytime, anywhere.

Try Udemy for Business
What you'll learn
  • Algorithms and data structures behind Automatic Memory Management in computer programs.
  • Memory management history: Static, Stack, Heap allocations
  • Virtual memory and Memory Layout
  • Tracing vs. Direct collectors
  • Semantic vs. Syntactic garbage
  • Mark-Sweep garbage collector
  • Mark-Compact collector
  • Reference counting collector
  • Copying collector
  • Generational collector
  • Parallel, Incremental, Concurrent collectors
  • Tri-color abstraction and marking
  • GC Barriers
Requirements
  • Basic data structures and algorithms (trees, graphs, linked lists, etc)
  • Basic knowledge about computer memory (bytes, addresses, pointers)
Description

Essentials of Garbage Collectors

Memory leaks and dangling pointers are the main issues of the manual memory management. You delete a parent node in a linked list, forgetting to delete all its children first — and your memory is leaking. You delete an object chain in correct order — but suddenly your program crashes since you forgot about second owner of this resource, which now tries to dereference a null-pointer.

To avoid these issues, most of the modern high-level programming languages implement automatic memory management. You allocate objects manually, however don’t bother with their deallocation: a special program, garbage collector, knows how to automatically deallocate them correctly, and reclaim for future reuse.

In the Essentials of Garbage Collectors class we study all different techniques and algorithms related to the automatic memory management, which are used today on practice.


Who this class is for?

First of all, for compiler engineers.

In implementing your programming language, there is a very high chance you’ll need to implement a garbage collector. Even languages which initially were positioned as “memory-safe”, such as Rust, eventual implemented automatic reference counting (ARC) and other collectors.

To reiterate: in most of the modern high-level programming languages, a garbage collector module (or multiple GC modules, like in Java) is pretty much a requirement today.


What if I don't implement programming languages every day?

If you are not a compiler engineer, then the class can still be interesting for you. Implementing a garbage collector or a memory manager in general, is a pretty advanced engineering task. It's a simple trick: you take some complex project (such as a garbage collector, compiler, interpreter, etc), and while building it, you learn all different data structures and algorithms. And then come back to "every-day programming", improved as a better engineer, with the transferable generic knowledge of complex systems.


Do I need C or C++ for this project?

Not really! Of course, C and C++ are probably the best languages for raw memory manipulations and fit well here, however in the course we study generic design algorithms and focus mainly on theoretical aspects of garbage collectors and memory allocators. This means you can implement them in any language you want. For example, you can allocate an `ArrayBuffer` in JavaScript for a virtual heap, or similarly `bytearray` in Python, Rust, etc.

Most of the algorithms in the course are described in generic pseudo-code, so you can port them to any language.


What's specific in this class?

The main things of these lectures are:

  • Concise and straight to the point. Each lecture is self-sufficient, concise, and describes information directly related to the topic, not distracting on unrelated materials or talks.

  • Animated presentation combined with live-editing notes. This makes understanding of the topics easier, and shows how (and when at time) the object structures are connected. Static slides simply don’t work for a complex content.


Reading materials

As further reading and additional literature for this course the following books are recommended:

  • The Garbage Collection Handbook: The Art of Automatic Memory Management by Antony Hosking, Eliot Moss, and Richard Jones

  • The Compiler Design Handbook: Optimizations and Machine Code generation by Y.N. Srikant, Priti Shankar

Who this course is for:
  • Compiler engineers
  • All curious engineers, willing to implement a complex project to learn different memory management algorithms (generic knowledge is transferable to other systems)
Course content
Expand all 17 lectures 02:13:03
+ Memory management
7 lectures 39:30

You will learn:

  • Static, Stack, Heap allocations

  • Compile vs. Runtime allocation

  • Fixed size vs. Dynamic size allocation

  • Recursion

  • Stack frame

  • Stack overflow

  • Memory leaks, dangling pointers

Preview 05:06

You will learn:

  • Memory leaks: forget to deallocate

  • Dangling pointers: deallocate too early

  • Human factor in memory management

Preview 03:55

You will learn:

  • Memory alignment

  • Object header

  • Collector meta-information

Object header
03:19

You will learn:

  • Virtual address space

  • Kernel space vs. User space

  • Code segment, data segment

  • Stack and stack pointer

  • Heap and break pointer

  • Memory mapping

  • Memory management unit (MMU)

  • Translation lookaside buffer (TLB)

Virtual memory and Memory layout
08:57

You will learn:

  • Life cycle of a GC'ed program

  • Mutator: user program

  • Allocator: memory allocation

  • Collector: garbage collector

  • Mutator vs. Collector object graph view

  • "Stop the World" state

  • System calls to invoke GC from Mutator

Mutator, Allocator, Collector
04:35

You will learn:

  • Sequential (aka "Bump") allocator

  • Free-list allocator

  • First fit, Next-fit, Best-fit searches

  • Segregated list

  • Blocks coalescing and splitting

  • Lab session to implement `malloc` and `free`

Lab session and example of implementation: http://dmitrysoshnikov.com/compilers/writing-a-memory-allocator/

Allocators: Free-list vs. Sequential
08:56

You will learn:

  • Semantic: objects that will not be reached

  • Syntactic: object that cannot be reached

  • Example of Stack structure

  • Example of invalidated cache

Semantic vs. Syntactic garbage
04:42
+ Garbage Collectors
5 lectures 44:54

You will learn:

  • Tracing: trace for alive objects

  • Direct: directly identify the garbage

  • Main four collection algorithms

Tracing vs. Direct collectors
06:09

You will learn:

  • Mark phase: objects trace

  • Sweep phase: reclamation

  • Detailed algorithm description with code example

  • Non-moving collector

  • Free-list allocation

  • Heap fragmentation

Example of implementing a Mark-Sweep GC in C++: http://dmitrysoshnikov.com/compilers/writing-a-mark-sweep-garbage-collector/

Preview 07:42

You will learn:

  • Mark phase: objects trace

  • Compact phase: objects relocation

  • Fixing fragmentation issue

  • Moving collector

  • Forwarding address

  • Lisp 2 algorithm detailed description

  • Sequential allocator

Mark-Compact collector
10:16

You will learn:

  • Semi-space collector

  • Heap reservation

  • Forwarding address

  • Objects evacuation

  • Fixing child pointers

  • Bump-allocator

  • Detailed algorithm description with code example

Copying collector
11:01

You will learn:

  • Directly identify the garbage

  • Strong vs. Weak references

  • Deeply integrated into Mutator

  • Barrier pointer operations

  • Pauses on deep nested structures removal

  • Cyclic references

  • Detailed algorithm description with code example

Reference counting collector
09:46
+ Advance topics
5 lectures 48:39

You will learn:

  • Heap partitioning

  • Young vs. Old generations

  • Minor vs. Major collection cycles

  • Objects promotion

  • Intergenerational pointers

  • Write barrier

Generational collector
08:37

You will learn:

  • Mark-Region collector

  • Mark-Sweep + Copying + Heap partitioning

  • Immix collector

  • Heap segregation: Blocks and Lines

  • Free, Recyclable, Occupied blocks

  • Bump-allocation in recyclable blocks

  • Sweep-to-region technique

  • Heap defragmentation

  • Evacuation from Source to Destination blocks

Mark-Region GC: Immix collector
12:58

You will learn:

  • "Stop the World" state

  • Multiple collection threads

  • Collector interruption by Mutator

  • Concurrently running collection thread

  • Synchronization barriers

Parallel, Incremental, Concurrent GC
07:21

You will learn:

  • Black, Gray, and White objects

  • Collection time slices

  • Illegal BW-pointers

  • Legal BW-pointers

  • GC barriers

Tri-color abstraction
07:31

You will learn:

  • Illegal BW-pointers

  • Read and Write barriers

  • Snapshot-at-Beginning

  • Incremental update (Dijkstra and Steel's)

  • Baker's Copying method

  • Brook's method

  • Final notes

GC barriers
12:12