Garbage Collection with Mark and Sweep

Toby and Huiqi talk about the full garbage collection mechanism that is used in the most popular programming languages like JavaScript, Java, C# and more. We introduce the mark and sweep algorithm. We also compare it to ARC (Automatic Reference Counting) languages like Python, Swift, and Objective-C.

Transcript

The following transcript was automatically generated by an algorithm.

00:00 : i'm just gonna talk about the concept of
00:02 : garbage collection
00:03 : let's have a stack and the heap and
00:07 : let's have like a top level view let's
00:09 : say you got a bunch of objects in the
00:11 : heap
00:12 : and some of the objects are referencing
00:15 : some of the other objects
00:17 : all right and then on the stack
00:20 : you have these frames with variables
00:23 : some of the variables are like pointing
00:25 : to these
00:26 : heap objects so maybe you have something
00:28 : like this going on
00:30 : so what we're gonna talk about is we
00:32 : called it fo
00:33 : gc last time uh another term for
00:38 : is tracing gc what is train
00:42 : tracing gc both of these terms
00:45 : i'm using to mean the same thing and the
00:47 : reason it's called tracing gc is because
00:50 : it the algorithm used to do the gc
00:53 : do the garbage collection is a tracing
00:56 : algorithm and it
00:59 : actually comes directly from graph
01:01 : theory
01:02 : there's a part of computer science that
01:04 : is graph theory
01:05 : there's a bunch of research in graph
01:08 : theory
01:09 : algorithms a graph is represented by a
01:11 : bunch of notes which look like little
01:13 : circles
01:14 : the circles are notes uh and you can
01:18 : have connections between the circles if
01:20 : these are
01:21 : called edges so the little arrows
01:24 : they're called edges
01:28 : and the edges can either be
01:30 : unidirectional
01:31 : which in this case it is or they can be
01:33 : bi-directional
01:35 : if it goes both ways if it's
01:38 : bi-directional
01:39 : usually you don't even bother writing
01:41 : the arrow because it's implied
01:43 : it's both ways in our scenario it is
01:46 : going to be unidirectional
01:48 : because a reference is a unidirectional
01:52 : like this variable points to this heap
01:54 : object this heap object does not point
01:56 : back to the
01:56 : variable the heap object knows nothing
01:58 : about this variable
02:00 : so this algorithm that does this garbage
02:03 : collection
02:04 : comes straight out of the graph theory
02:07 : repertoire
02:08 : and it's it's the reachability problem
02:11 : the reachability problem is this if i
02:14 : start from this
02:15 : note is it possible to reach this note
02:18 : by
02:18 : traveling the edges so you might imagine
02:22 : a more complex graph is it possible to
02:24 : reach this
02:25 : note here from this note in this case
02:28 : yes because i can go
02:29 : blah blah blah and i reach this note
02:33 : um is it possible to reach
02:36 : this node from this node
02:39 : no because this node has no outgoing
02:42 : edges it can't go anywhere
02:44 : so do you have to travel the graph in
02:46 : order to
02:47 : calculate whether you can reach a note
02:49 : or yes or other ways to do it
02:52 : yeah that's what you do i i believe
02:53 : you're familiar with binary tree
02:55 : traversal
02:56 : right or just tree traversal in general
02:59 : a graph traversal
03:00 : is not really any different from a tree
03:03 : traversal
03:04 : you have a way of accessing your
03:07 : children
03:08 : or the neighbors that you're able to
03:10 : reach that are direct neighbors
03:12 : and you just go to them to recursively
03:15 : traverse the whole graph
03:17 : until you either find that you reach the
03:19 : thing you're
03:20 : wanting to reach or you don't so yeah
03:22 : basically that's what you do
03:24 : you you you recurs just pretend this was
03:27 : a tree
03:28 : like this is a tree actually in this
03:30 : case
03:32 : the one difference between trees and
03:35 : graphs is
03:36 : graphs are allowed to have cycles so
03:39 : if i add a cycle in this graph or two
03:42 : cycles
03:43 : this is not a valid tree anymore because
03:46 : trees must not have cycles but a graph
03:49 : is allowed to have cycles so basically
03:52 : this
03:53 : reachability algorithm is what is used
03:56 : uh to do garbage collection for
04:00 : a situation like this with a stack and
04:03 : the heap
04:03 : the most famous algorithm for garbage
04:06 : collection
04:06 : is called mark and sweep step one of
04:10 : mark and suite for each heap
04:12 : object as unvisited
04:15 : this is the initialization step and then
04:18 : we're gonna
04:19 : traverse it and then mark stuff as
04:22 : visited as we go and then we're gonna
04:24 : for each global variable
04:26 : or variable on the stack
04:29 : start a graph traversal
04:32 : marking each visited node
04:36 : as visited so for example we're going to
04:38 : start from
04:40 : a var and b var and start traversing the
04:43 : graph right
04:44 : each one as you visit it we're gonna
04:46 : mark that node as visited
04:48 : and then finally the third step is
04:51 : for each unvisited node
04:55 : or i should say heap object that's what
04:57 : the nodes are
04:58 : you can free the memory so that other
05:01 : things can use that memory now
05:03 : so for any object in the heap if nothing
05:07 : refer to it and it cannot be reached by
05:11 : this
05:11 : algorithm so then we can just free it
05:14 : exactly so let's do it on this graph
05:17 : first
05:18 : we're gonna do step one which is mark
05:20 : each one
05:21 : as unvisited i'm gonna put a little
05:24 : parenthesis
05:25 : and put a u next to each one right for
05:27 : unvisited
05:28 : and then for each global variable uh we
05:31 : don't have a
05:31 : global stack but i could maybe this one
05:34 : is a global stack
05:36 : and the global variables go on the
05:37 : global stack i don't know or the global
05:39 : variable could go on a different place
05:41 : than the stack it doesn't matter uh but
05:44 : we're just gonna
05:45 : work with these two variables that are
05:47 : on the stack
05:48 : so start with avar we're gonna traverse
05:52 : to this guy and then because we were
05:55 : able to reach this guy
05:56 : this becomes visited we're here and we
06:00 : need to visit its two neighbors
06:02 : so we visited this neighbor here
06:06 : and this guy becomes visited and then
06:09 : depends on if you're doing a depth first
06:11 : or a breath first
06:12 : you might visit this in a different
06:14 : order but
06:15 : here let's do a depth first and then
06:17 : we're going to follow this edge here
06:20 : and then so we visit this one and this
06:22 : becomes visited
06:23 : we already visited everything so maybe
06:25 : this example
06:27 : weren't super great but the next thing
06:29 : we're going to do is do the same thing
06:30 : starting from b
06:31 : var we're we're gonna first see this guy
06:34 : and bivar is gonna see that it's already
06:37 : been visited
06:38 : and just jump out because because
06:41 : if it was visited then it would have
06:43 : visited its neighbors as well
06:45 : in the previous round so there's nothing
06:48 : for for this one to do since we haven't
06:52 : seen a case where there's actually
06:55 : dangling
06:56 : objects let's let's make an example
06:58 : where
06:59 : like in this case yeah in this case
07:02 : everything was visited like so step
07:05 : three has nothing to do
07:07 : there are no unvisited heap objects
07:09 : let's make a separate example
07:11 : so um in this case if we did this
07:14 : it will still visit everything but let's
07:17 : say
07:17 : b we got done with this function call
07:20 : and this frame got destroyed
07:23 : okay b doesn't exist anymore
07:26 : so now if we do this algorithm we're
07:28 : gonna
07:30 : mark every object unvisited uh and then
07:33 : we're gonna start with a
07:35 : and visit this one so this one is gonna
07:38 : be
07:38 : v v and u i'm writing them very very
07:42 : similarly
07:43 : maybe i'll put like a underline under
07:46 : the use
07:47 : okay and now we're gonna visit this one
07:49 : and then this
07:50 : is gonna become a v and that's it so
07:53 : these
07:54 : two ended up being unvisited and we're
07:56 : gonna
07:57 : we're gonna free up their resources
08:01 : and and then if this frame also gets
08:04 : destroyed
08:06 : then you can see that we don't have
08:08 : longer have any
08:09 : variable starting point so these are
08:11 : going to get unvisited and
08:13 : they'll get reclaimed the memory get
08:15 : reclaimed for other uses also
08:18 : do you re execute this this algorithm
08:22 : is that like every time you a function
08:24 : returns you you
08:26 : just do it that's a great question uh
08:28 : before
08:29 : going there though what's the big o of
08:31 : this algorithm
08:32 : um by big o we mean like more stuff in
08:35 : the stack
08:36 : or like oh okay
08:40 : here let's state there's n
08:43 : heap objects in here maybe
08:46 : m m variables
08:49 : on the stack what do you think the big o
08:52 : of this mark and sweep algorithm so the
08:55 : worst case is so each time
09:00 : m at uh there's another m
09:03 : there's gonna be the mode n
09:06 : to the power of n
09:10 : because you you don't know how this and
09:13 : how these heap objects are referencing
09:15 : each other
09:17 : so one thing to remember though
09:20 : is that if you visit
09:23 : something that's already been visited
09:26 : once you can actually stop
09:28 : the execution there and you no longer
09:31 : need to go further
09:33 : oh so to the most everything will only
09:36 : be visited
09:37 : visited once like you mark this
09:40 : you mark this maybe there's multiple
09:42 : variables that will end up visiting
09:44 : these
09:45 : but once they visit it they don't have
09:47 : to do the traversal uh
09:50 : that's related to them anymore maybe
09:52 : because you marked this one
09:54 : you also mark this one so you visit this
09:57 : guy
09:57 : and then you don't have to do this
09:59 : traversal to
10:01 : to visit this one anymore wait so that
10:04 : means that's just m
10:05 : n m times n yeah
10:09 : it's not even m times n let's say
10:13 : m was 100 they
10:16 : have a stack that has a lot of variables
10:18 : on it and
10:19 : n was 10. um i think
10:22 : m would have very little impact on the
10:26 : performance
10:28 : and the n has more impact because
10:31 : at the end of the day you're you're
10:32 : traversing those 10
10:34 : objects and these 100 variables
10:37 : most of them are going to go back to the
10:39 : same objects over and over again
10:41 : right and and the first time they hit
10:43 : something
10:44 : that you already visited it's stopping
10:46 : so even though there's
10:48 : many of these they're not doing that
10:51 : much
10:51 : once once the notes have already been
10:53 : visited
10:55 : so i actually think it's it's mostly big
10:58 : o of n
10:58 : you visit this one cross cross
11:01 : and then the next one is the guy oh it's
11:03 : the same one
11:05 : visit this one again and then oh you
11:07 : visit this one again and maybe the next
11:08 : one goes here
11:10 : and then visit this one again this one
11:12 : again like most of the hundred is gonna
11:15 : be spent just seeing that you already
11:17 : visited that one
11:19 : ah sure yeah so i think yeah that makes
11:21 : sense i actually think it's big of
11:23 : n and and yeah and this this does matter
11:27 : it matters less maybe it's like a
11:30 : m times some constant but maybe maybe
11:33 : it's like this
11:35 : maybe it's like this it's m times some
11:38 : constant plus
11:39 : n times some constant but in any case
11:42 : i'm not sure if i'm totally right on
11:44 : this so somebody you can if i'm wrong
11:46 : please correct me
11:48 : let's just say that it is big o of n it
11:51 : is at least big o of n
11:53 : that means if you have a lot of heap
11:56 : objects allocated it could potentially
11:59 : get expensive
12:00 : right which leads us to the second
12:03 : question when
12:03 : does this process kick in what do you
12:07 : think
12:08 : i can tell you javascript does this java
12:10 : does this
12:11 : we talk about when a function returns
12:13 : right
12:14 : we need to relate okay when this
12:17 : function returns
12:19 : it doesn't do it that often because like
12:22 : if they did it every time a function
12:24 : returns
12:24 : it'll be doing that all the time it'll
12:27 : severely
12:28 : penalize your your program because this
12:31 : is a big of n
12:32 : operation that's happening all the time
12:34 : i mean a lot of times your program
12:36 : is still keeping a lot of the objects so
12:39 : you're just visiting those
12:41 : objects over and over again
12:44 : and only reclaiming a small percentage
12:47 : of the objects
12:49 : and you're doing that all the time that
12:51 : that's
12:52 : that's not good they're very lazy about
12:55 : uh doing this process as i understand it
12:59 : they
12:59 : only do this when they have to when do
13:03 : they determine that they have to do it
13:05 : when they try to request for
13:08 : more memory but the system is not
13:11 : willing to give
13:12 : give us more memory oh god
13:18 : i think i ran up against the
13:21 : memory limit for chrome one time
13:25 : and when that happens your environment
13:29 : it might be your operating system or
13:31 : your browser in this case if you're
13:32 : doing javascript
13:34 : in the browser that's chrome that's
13:36 : making decisions
13:37 : about how much memory is too much to get
13:40 : but but there's
13:41 : a there's a threshold it's not
13:44 : necessarily
13:45 : how much memory your computer physically
13:48 : has
13:49 : that's because of something called
13:51 : virtual memory
13:53 : i'm not going to try to dive into that
13:55 : because that's a whole separate topic
13:57 : but in short virtual memory
14:00 : is the computer is making your program
14:03 : think there's more available memory
14:07 : than there there is it's giving your
14:10 : program the impression that it has a lot
14:13 : of memory
14:14 : even bigger than the amount of physical
14:16 : memory you have
14:18 : why do that why does it do that um just
14:21 : make the programmer's job easier your
14:24 : program
14:25 : is not the only program that's running
14:27 : on the computer
14:29 : if the computer was like
14:33 : i only have one gigabyte of physical
14:35 : memory
14:37 : and i have to run 20 programs therefore
14:40 : i'm gonna divide up
14:41 : my physical memory by 20 and give each
14:45 : program only that much only
14:48 : you know one over 20 of the
14:51 : of the one gigabyte that i have then
14:54 : it's all programmed but
14:56 : yeah so you know the program doesn't
14:58 : have to worry about
15:00 : oh how much physical memory do i
15:02 : actually have
15:03 : and then does it have to you know do
15:06 : things differently
15:07 : based on how much actual memory because
15:09 : if you're basing
15:10 : on physical memory then when the
15:12 : physical memory is
15:14 : used up you actually can't continue
15:17 : there's actually no way
15:18 : to add more memory if you're basing it
15:21 : on physical memory
15:22 : so virtual memory allows your program to
15:26 : ask
15:26 : for you know more than its share
15:30 : that way the program doesn't have to
15:32 : worry
15:33 : about the physical limitations of this
15:35 : machine because you want to write a
15:37 : program that can
15:38 : work on a lot of machines right not just
15:41 : the machines that have a lot of memory
15:43 : right it's like the air company like
15:45 : oversell the air tech
15:47 : yes okay yeah
15:51 : uh it's not exactly like that
15:54 : um maybe we could do another session
15:56 : about virtual memory
15:58 : in in the future but um sure but that's
16:01 : the short version of it
16:02 : but then even even despite that
16:05 : the operating system still you know
16:08 : places a limit
16:10 : on how much memory you can have i
16:13 : actually don't know what that threshold
16:16 : is
16:16 : maybe i should read more about this at
16:19 : some point
16:20 : if you ask for too much um your
16:22 : operating system is gonna say
16:24 : no you can't have it and basically at
16:26 : that point
16:27 : the garbage collector is time for it to
16:30 : kick
16:30 : in to hopefully reclaim some of the
16:34 : memory
16:34 : that you currently own so that
16:38 : these these objects that we can x out
16:41 : and we're going to recycle them for use
16:44 : by your own program
16:46 : sure before i forget last time i should
16:49 : have talked about this but i forgot
16:51 : and that is one drawback of the arc
16:56 : which the the mark and sweep scheme
16:59 : fixes this drawback your object graph
17:02 : has a cycle in
17:03 : it right so when the field assignment
17:05 : happened
17:07 : remember we're supposed to increase the
17:09 : reference count right
17:11 : this guy's reference count is 2 because
17:14 : it's
17:15 : this arrow plus this arrow right from
17:18 : the stack
17:19 : and then this guy's reference count is
17:21 : also one
17:23 : so now this stack frame got destroyed
17:26 : because that function is done
17:28 : we're gonna decrease this guy to one and
17:31 : now
17:32 : all the reference counts are one but
17:36 : these three objects are unreachable
17:39 : from the stack
17:43 : they're mutually pointing to each other
17:46 : so how does it
17:47 : how does the program that use arc or the
17:50 : language that use arc resolve this
17:52 : um good question one way
17:56 : is they prevent you from doing this in
17:59 : the first place that's one that's one
18:01 : strategy
18:02 : um there's another strategy called
18:05 : weak pointers which is a pointer
18:08 : that points to the object without
18:11 : increasing its reference count
18:15 : in the igma script didn't know there's a
18:18 : thing called the weak map
18:20 : in uh yeah i heard about yeah there's
18:23 : there's a ecmascript
18:24 : weak map which um it's just like a map
18:28 : except the keys are weak references
18:33 : if you do new weak map so my my map
18:36 : is a new weak map and then uh
18:40 : first of all in a map you can use
18:42 : objects
18:43 : as keys that's number one if you've been
18:46 : using just
18:46 : object literals for your dictionary
18:49 : you might not be used to that but it is
18:52 : possible
18:53 : to use um use the object as a key
18:58 : so that's the key and then maybe like a
19:01 : value i'll just put a number
19:03 : right say the key has to be the same
19:06 : reference
19:06 : on the same object it can be like a copy
19:09 : or something right
19:10 : it has to be the object yeah that has
19:14 : that's like the object it is the object
19:17 : that is the key of this map like
19:19 : internally this is a hash table
19:21 : it probably looks up the object's memory
19:24 : location
19:24 : it probably uses that as the key and
19:27 : then it might
19:28 : transform it using a hash function so
19:30 : this is possible with
19:32 : both the map and the weak map the
19:35 : difference between the weak map
19:36 : and the map is with the map if it were
19:40 : an arc system which
19:41 : javascript is not but but if it were
19:45 : then with the map
19:46 : it'll like plus one on the reference
19:48 : count on
19:49 : that object with a weak map it will not
19:51 : plus one that's the difference so the
19:53 : key is a weak reference so the weak map
19:55 : means
19:56 : keys are weakly referenced
19:59 : since javascript is not a reference
20:01 : counted
20:02 : language i'm gonna draw it like a graph
20:04 : so let's say this
20:06 : is map this is the map that we have here
20:09 : and i have opt here and maybe
20:13 : there's other objects all of this is the
20:16 : heap
20:17 : and then we have the stack which may
20:19 : have some pointers
20:21 : to objects over here um
20:24 : if this was a normal map not a weak map
20:28 : then for each key that you use with the
20:31 : map there would be a pointer
20:33 : to the objects which means if you if you
20:36 : run
20:36 : the mark and sweep algorithm there
20:39 : should be a pointer to this map
20:40 : as long as the algorithm reaches this
20:43 : map it'll also reach
20:45 : all the key objects that are used within
20:47 : the map so
20:48 : basically all the other objects that are
20:51 : keys
20:52 : in this map are retained by this map
20:55 : because the map point to them however if
20:58 : this were
20:58 : a weak map that is not true
21:01 : if it was a weak map then the system
21:04 : do not track the references that the map
21:08 : has
21:08 : to these objects which means if this
21:11 : object gets
21:12 : cleaned up maybe this pointer got
21:14 : removed
21:15 : somehow this object will get cleaned up
21:18 : even though this object is a key in this
21:21 : map
21:22 : it's gone and that means implicitly the
21:25 : entry in the map is also gone
21:27 : which does not break the program because
21:29 : there isn't another place in the program
21:31 : that has this reference
21:33 : to be able to ask your map for this key
21:36 : again
21:36 : okay so how does it keep track of
21:40 : whether there is another part of the app
21:43 : that's asking for this key
21:45 : after the that thing is destroyed
21:48 : now it doesn't keep track of it it
21:50 : doesn't keep track of it it's just
21:52 : impossible if this object got reclaimed
21:56 : that's because there are no longer
21:58 : variables
21:59 : on the stack or or from any other object
22:02 : that's referencing this one anymore okay
22:06 : so basically the process of having a map
22:09 : that have like the which is not a weak
22:12 : map that was redundant
22:13 : to begin with because if it's
22:15 : technically impossible
22:17 : right so uh oh i see
22:20 : you're saying why even why would you
22:23 : ever use
22:24 : a not a weak map exactly
22:28 : there is a reason to use a non-weak map
22:31 : which is you can actually um iterate the
22:34 : entries of the map
22:36 : oh god shot so weak map cannot do that
22:39 : correct elite map cannot iterate through
22:41 : the entries of a map
22:44 : okay that makes sense interesting i
22:47 : wanna
22:47 : wrap up by just saying if you have this
22:50 : psycho situation
22:52 : in a mark and sweep algorithm okay so
22:55 : what we're gonna do
22:56 : is uh well if if we did the mark and
22:59 : sweep at this point
23:00 : then all of these guys would be visited
23:03 : obviously the problem
23:04 : is if this function was
23:07 : terminated and we destroyed this frame
23:10 : this pointer is
23:11 : gone what what would the mark and sweep
23:13 : algorithm do
23:15 : well it would mark each one of these as
23:19 : unvisited so these are unvisited for
23:21 : each variable that's on the stack we're
23:23 : gonna start the traversal
23:24 : well there's no variable to start the
23:27 : traversal
23:27 : with our stack is empty so none of these
23:30 : guys get traversed
23:32 : and therefore all of them stay unvisited
23:34 : and we're gonna
23:35 : loop through the untraversed ones and
23:37 : then destroy each one
23:39 : so basically um the mark and sweep
23:41 : solves this problem
23:43 : so in in a mark and sweep garbage
23:45 : collected programming language
23:46 : you don't you don't have to worry about
23:47 : having cycles in your objects
23:51 : that's kind of a big drawback of the arc
23:54 : approach
23:54 : however i have read recently that
23:58 : python is an arc based language
24:01 : however it has some algorithm in there
24:04 : that it uses to remove this kind of
24:06 : cycles
24:07 : automatically so i want to dig into that
24:09 : i i want to understand how that works
24:11 : okay so python is actually using arc
24:15 : yeah python yeah python uses arc which
24:19 : is surprising to me
24:20 : honestly because it doesn't feel like an
24:22 : arc language because i looked at
24:24 : arc languages before like swift
24:27 : uh rust objective c and all of them have
24:30 : these
24:31 : extra extra stuff that they introduced
24:34 : to cope with
24:35 : this problem and python doesn't have
24:37 : that