Knowing your garbage collector
Castaño, Francisco Fernández
Francisco Fernández Castaño - Knowing your garbage collector As Python programmers we're used to program without taking care about allocating memory for our objects and later on freeing them, Python garbage collector takes care of this task automatically for us. Garbage collection is one of the most challenging topics in computer science, there are a lot of research around the topic and different ways to tackle the problem. Knowing how our language does this process give us a better understanding of underlying interpreter and allow us to know why problems like cycles can happen in CPython interpreters. So, this talk aims to be and introduction to the topic and a walkaround through different approaches followed in CPython and PyPy: * Generational Reference counting with cycles detector on CPython. * Incremental version of the MiniMark GC on PyPy.
 So, hi, thank you for coming. I'm Francisco Fernandez. Here you have my tour of handle if you want to ask me something during the talk or whatever. Also you have some questions during the talk. Don't doubt about interacting with me. So, okay, let's start. Today I'm going to talk about a garbage collection on Python. Here we have the agenda of this today's talk. In first place I'll do an introduction that includes the motivation why I think this talk could be interesting for a Python developer. Some non-problems, some manual memory management, some definitions on garbage collection from academia that I think is also quite interesting to know about. And also every solution has some trade-offs, so we will explore them. Later on we will see how C Python implements a garbage collection. We need to know something a little bit about the C implementation, so there will be a little bit about C, or good C. Then I'll explain the algorithm itself, and finally the cycle detector. And if I have enough time, I'll try to do a high overview of how PyPy approach garbage collection. So, let's start. Okay, what's the motivation in knowing more about garbage collection or memory management? We don't need to take care most of the time about memory in Python. We are some kind of lucky. Most of the time we are working on a business logic layer, because probably most of us we are developers, not Python core developers, so we don't do native extensions. So, we use a lot of exceptions that the language give to us without knowing more. For example, we use a lot dictionaries and we don't know, and we don't need to take care about how dictionaries are implemented or the layer between the operating system and the standard library. And also memory is another abstraction that we have, and sometimes it's useful to know about. So, we'll know more today. I hope that you know more about how memory is managed in Python. Okay. But managing memory manually is hard. How many of you are familiar with C or C++? So you know probably how difficult sometimes is managing memory manually. There is a lot of problems that I tried to list here. The most known is memory leaks, that basically is that we allocate memory for some resource and after using it we don't have to allocate it. We do that most of the time by accident, no purpose. Another problem that we have is the Omnistip. Let's say for example, like in this snippet of code, this is some kind of library. This library allocates memory on the heap. And it returns a pointer. Okay. So, we don't have to do that in Python, but who is responsible on freeing this resource? The library should do, I do the free, free this resource. This leads to the problem of double freeze. What happens if I free the resource and again the library somehow had the pointer and finally tried to free. We end up with a segmentation fault in the best of the cases. Another problem that you can have is dangling pointers. For example, this is another snippet of code. We are allocating here a variable on the stack and returning the reference. And once we are out of the scope, this address is not valid anymore. So, again, we will end up with strange behaviors. Segmentation fault will be the best of the cases because you know that something is wrong. Values that are not correct is the difficult one. Some languages propose some solutions, sort patterns, for example, C++, they try to apply as much as possible right pattern. They also introduce some tools on a standard library like unique pointer and serve pointer. And also there are other approaches like in Rust that they try to make language safe on compile time. There is a lot of solutions. I don't know if you see you have much tools to deal with that. But we cannot have garbage collection in every scenario. There are some scenarios where it is mandatory to have full control of memory. One of them could be embedded systems where we have very limited resources and we need to carefully deal with memory. So for example, we have very demanding applications like a video game can be where, for example, we need to know very carefully how the memory layout is to try to avoid cache misses and so on. And also applications that need determination because most of the algorithms, as far as I know, on garbage collection, we don't know for sure when a resource is located. So there are scenarios where garbage collection works and others don't. But what is all this about garbage collection? Probably most of you know what is. But I would like to introduce you a little bit about history. Here we have a picture of Mr. John McCarthy playing chess with a computer. And he was kind of the inventor of garbage collection. In this paper from the 1960s, the first mention to garbage collection on recursive function of symbolic expressions and computation on my machine. And it's kind of funny because he described the whole process. He described Mark and Swipe algorithm there. And as a food note, he says, okay, I've been naming this process garbage collection, but I know that academia is a bit sticky and I want to use. Finally, academia uses garbage collection. So kind of funny. So what's the formal definition of garbage collection? garbage collection is basically automatic memory management. Well, the emulator runs, it's originally allocates memory from the heap. If more memory than available is needed, the collector reclaimed and use memory and return it to the heap. This sounds too formal, but it's quite simple. The emulator, you have the definition, but basically it's our business logic. The heap is where the memory is allocated. And the collector is the garbage collection algorithm itself. In our case, Python virtual machine is the one that takes care of collecting and use resources. If you want to dig deeper into this topic, more in the academic side, this is a quite good book. It's quite extensive, but it's not so formal. So I recommend you to take a look. But as I told you before, every solution has some trade-offs. Nothing is perfect. So if we decide we are a language implementator and we decide to have a garbage collector language, we have to know that probably we'll need more resources. We will have performance impacts because the algorithm has to run. So we are losing CPU cycles there. And on some algorithms, we don't know for sure when resources will be free. So now we will start looking into how C Python implements a garbage collection. It implements a reference counting algorithm. But before, we need to know a little bit about how it's implemented in C. This is the main object that is supposed mostly for us as a user all the time. This is a py object that is basically a stack with two members. One of them is py size t that basically is for us an integer. Name of ref count. This member holds the number of incoming references that an object has. So for example, if this is an instance B and object A has a reference to B, the count is one because it has one incoming reference. And the other member is just a pointer to the type. This allows us to have dynamic typing. So let's see a simple example. For the purpose of this talk, I want to be educational, we will only take care about instances. We know that full class is also an object. But for simplifying, we only deal with instances. So how does this look graphically? Main is the main module. And it holds two references, one for full and another one for my list. So those contests that I told you before are both one. Because only main is referencing full and my list. But let's make this more interesting. Let's append full to my list. Now full will have two references. We can see graphically like this. Now full has both main and also my list, referencing him. That's happened. But who takes care about this counter? Presumably it's the C Python implementation. So here we have a snippet of the standard library, the list object. This function, what it does is, given the list itself, it happens the object B. In our case, full on my list. And take a look into this line. By in ref from B. This is the point where we are incrementing by one the counter. Because now the list itself in this case has a reference to B. In this line it sets in the last position the element. How does this PyIncref looks like? Like in a lot of places in C Python is a macro. What it does is it does a custom op and increment by one. The ref count. You see? But what happens when an object is not referenced by another one anymore? Well, presumably the counter will be decremented by one. So we end up with this case in the same picture as before. Because now my list on index zero that before had full inside now has none. Now we end up again with the same picture. Because my list is not holding a reference to full anymore. So full again as an over count of one. And how does it look like on C Python level? Again this is part of the list of the file that implements the list on C Python. And again we have very much like the inverse operation on the all item. Basically it's the one that we are not interested anymore. What happens there in that macro? Basically the counter is decremented by one. But it also happens one check. If this counter is equal to zero, we know for sure that no other element, no other object in the system running is interested in that object anymore. So we can safely dialogue that object. This is what happened here. That's the check here. If it's greater than zero, okay. That's some checks. Another case it's located. Okay. It's clear. Till now. Okay. And well, let's reproduce this case in our little example. Now we say to the module, okay, I'm not interested in full anymore. Delete all the references there. So ref count reaches value zero. So we allocate it. Well, we, the Caravage Collector, okay. And the interesting thing is that once we know for sure that no other object references full, we can allocate. We don't need to wait till collection like in other algorithms. Okay. Collection phase. But do you notice any problem that this approach can have? Any clue? Probably most of you know what happens. What's that? Cycles. What happens with cycles? This approach don't work for cycles. Okay. Like this. Now let's imagine the full has a reference to list. And we create a cycle. Full has a reference to my list and my list to full. Like this. Okay. Now both objects live in main modules. So no problem. They are there. But what happens if we don't take care anymore about full on my list? We end up with a cycle and those objects are not the allocated because both objects have a reference count of one. And it's not possible that anyone reference it again because we don't have reference on our system. We delete from the module main. So we end up with a memory leak. And I told you before that one of the problems with manual memory management is memory leaks. And we also have here memory leaks. So what was the pro of having Garage Collection? Well, we are lucky and in C Python implementation, they implemented the cycle detector. Well, this is another topology that we can have. More complex cycles. This is a, those are very, very simple examples, but in the real world, they are more complex. But yeah, what happened if we have a cycle? We'll explore how C Python implement algorithm to check if there is cycles. To do that, Garage collectors should know more or less all the objects that are allocated on the runtime. And this is keep track on this double link list. This is a node of a double link list that lives in GC module with this signature. And for performance reasons, there are three generations on implementation because doing a whole scan or looking for cycles on the old living objects is quite costly. So what they do is they divide into three generations, from the youngest one to the oldest ones. And we do step by step. So we don't need to check for the whole living objects. Okay. And, well, this is some C tricks to, this is a union. Don't worry about it. It's just some details. So let's represent our example like the one before. We have those three generations and we have four on my list. Both of them probably you can see in the back. Both of them has the value one on GC refs. And what's the key idea of the cycle detection algorithm on C Python? The key idea is that we know the object that belongs to a generation. So what we can do is extract all the internal references on that generation and those objects with a number of references bigger than zero, they have references from other generation objects. I don't know if I explain better. But the idea is that we keep track only on, we subtract all the internal references in the same generation. I'll do a step by step trying to explain better. To do that, types on internal on C Python implementation has this method that extract how to traverse all the references on objects. For example, I implemented this as a Python to do it more clear. So for example, the extract traversing all the references basically as iterating over the key and value and applying some function, a list basically iterate over all elements and apply a function. This is a utility that we have for this kind of problems like cycle detection. So those tools help to implement the algorithm. So let's start, let's think that we only have foo on my list on my generation zero, to simplify things as much as possible. So I start iterating over the first element that in this case is the one marking red foo. What I do is using these functions, depending on the type, I iterate over all the references that these objects have. In this case, it's only my list. And I apply one function. This function, what it does is check that the number of references is greater than zero and decrement by one. So with this way, we are breaking the cycles, okay? Because all the internal references are decremented. So if we have a case like this one, we are breaking it. We are marking as unreachable. So this is the first step. Foo only has a reference to my list, decrement by one, now the reference is zero, okay? The next step we have my list as the next object in the generation zero. And again, we decrement by one. So now we know that those objects could be unreachable outside of my generation. Okay? The next step is moving those objects to a new list called unreachable. And one step that we have to take care is we need to check on objects that are reachable, all the references because there can be cases where some object get a value of zero, but there is some kind of topology like one cycle, like the one that we were seeing before, and two other references. This end up having zero on those two objects, but they are still reachable by these two objects. So we have to check for that also. After that, we move to an unreachable list. Those objects that are reachable are moved to the next generation because they can live more. But I prepared a little demo in Python before I did this using GDB, but it was too much. So let's take a look. I have time, I think. Can you see the code over there? Yeah? Well, I tried to represent more or less the implementation on Python to make it easier to understand. Do you remember this tovelink list? This is one of the represented notes on how the garbage collector takes tracks on all the allocated objects. These are some helper methods that implement the traversal methods to know how to iterate over the references. One list. Some examples. We will run an example now. Okay? Here we have the garbage collector object. It has, in this case, two generations with two thresholds that I didn't mention before. But we don't do a cycle detection each time that we allocate an object. There is some threshold that they study. If we allocate more objects than that threshold, cycle detection is fired. Okay? Here we have this logic. Let's say that I want to instance it in class. What I do is I append to my first generation this object on this link list and I check this threshold. Okay? Is my generation greater than the threshold? Yes? I collect. I do a collection. How is this collect cycle? Okay. We get some references for being more comfortable programming. The first step is we need to update the references because on the notes, this note, don't have the most updated reference count. Because as I told you before, we don't run the cycle detection all the time. So it can have a value that is older. Okay? So the first step is we iterate over all the generations that we're interested in and we update the reference count with the pie of the one. Okay? The next step is this one of breaking cycles, just subtracting one on the internal references. Okay? So let's take a look at this. What we do is again, we iterate over the whole list of this generation and using this helper method that extracts how to iterate over all the references, we pass a function as an argument. Okay? And this function basically, what it does is it checks that the references are greater than zero and decrement by one. This is a helper method. Don't worry about it. So we end up with the... After this step, I will run one example. Oops. Do you know how to evaluate all the cells on the Python? Okay. I'm pretty new to notebooks. Sorry. Okay. We'll do like a step by step to see it clearly. Okay? We allocate one list. We are trying to replicate our sample. We have a list and an instance of an object and we are creating a cycle. Okay? We allocate... I don't know. We'll explore line manually. I don't know what's happening. Demo. Okay. After this step on our example, we will get those two objects with an account of zero. So the next step is just check those edge cases where we can get some object with an account of zero but some other object can't reference them. So what we do is, in first place, we use, again, TP traverse and we use another callback. That basically what it does is if we find one object that has an account zero, this is a false positive as an reachable. So we need to keep track that is still reachable. In other case, we just check that refs are greater than zero. And after that, we have those two lists, the unreachable object and the young ones. So we know that these ones can be deleted but it's not so simple. So we move the reachable object in this generation to the older one. And I'll explain later what we need to do with weak references and finalizers and we finally delete all the garbage. There are some edge cases that I'll try to explain now. But did you understand more or less the algorithm? Should I explain something more or is it clear? But as I told you before, there are some problems with this approach. We need to take care about finalizers. I mean, underscore and underscore deal. There are two kinds of finalizers. One is kind of legacy. Those cannot be delegated safely. So we end up having memory leaks if we have legacy finalizers. We deal with underscore and underscore deal. It also has to take care of a lot of edge cases. So please don't use finalizers. And finally, we have to take care also about weak references. What it does is check the ones that are reachable and execute the callback that they have associated. So what makes the emoji happy? That is incremental. This algorithm is incremental. So as it works, it frees memory. We don't need to wait to cycle to recover memory. And emoji is worried because as you can see detecting cycles is kind of hard. Not algorithm itself, but there is a lot of edge cases that I didn't mention that is kind of complex. And we also have some size overhead on objects that this OV ref count. And as a personal opinion, also in C Python, garbage collection is two-to-coupled to the model so that we have a counter in the main object of the interpreter. So we cannot change the model easily. So that's a sign note. I have little time now. Like five minutes, I'll try to do an overview of how PyPy handle garbage collection and memory. So probably most of you are familiar with PyPy. It's an alternative implementation of Python. It's written in our Python. And regarding to garbage collection, it has some points that are quite interesting. One is that it's kind of agnostic to the garbage collection algorithm. So during translation time, that is how do you get the interpreter at the end? You can, if I'm not wrong, you can change the model of garbage collection, the algorithm that you want to use. So this allows PyPy developers to experiment over time with different approaches that I think is a good thing not to be tied to one implementation. And the algorithm by default nowadays is in Minimug. And let's explore a little bit about PyPy. One of the things that PyPy developers notice is that we allocate a lot of... We interpret it, allocate a lot of objects with a short lifetime. So for example, we have some examples here, like for comprehension, we are allocating objects that will live very, very shortly. Even when we are calling a method on a class, we are creating a new object, a bounded method with a very, very short life. So those objects will be allocated in a performant way. So they end up with this kind of memory model. They divide it into two areas. One for the general objects, this one that lives early. The general area is divided into two areas, the nursery that has a fixed size. Another area where all the objects that don't fit in the realm of area go there. And also some arenas to hold the objects that are older than the young ones. So how does it work? It performs what they call minor and major collection. Minor collection is performed on the young area. So it's fast because we don't need to transfer to the old life objects. Objects are moved only once to the old area. And also major collection is done incrementally. At the end, they implement kind of mark and sweep algorithm. This are the phases that they implemented. In the first place, they do a scan phase, then mark, then sweep. And finally, they execute finalizer because we have the same problems as in CPython. Here we have some schema of how mark and sweep works. In general, this is the same schema as in the paper of McCarthy. Finally what we do, we know for sure the root of the main objects and we traverse the graph of memory. And we mark on this traversal which ones are reachable. Once we know which ones are reachable, we take it over the whole list and we sweep, we allocate the ones that were not marked. And yeah, that's it. Quite simple and elegant. Mark and sweep can collect cycles because we basically are doing a graph traversal. But type implementation can be more complex to understand than CPython because at least for me. And on full collection, we stop the work. I mean that we cannot, as well as when we are detecting cycles on CPython, we cannot perform other operations. So yeah, questions? Start up front if there are any. There are a few at the back. Hi. Thanks for the explanation of these algorithms. What I would be interested in as a Python developer is to anything I should take care about in my code so that I enable the garbage collector to do his work most efficiently. I try to avoid the underscore, underscore build methods. For example, because there are a lot of edge cases that interpreter has to take care of. So that's one off. With PyPy, you say there is a possibility of the stop the world issue on garbage collection. Is there a way to, in future implementation or theoretically to circumvent the circumstance? For example, splitting memory and garbage collecting different. They do that approach, so the stops. As far as I know, they're not so long. But it could be interesting having, again, the JVN where you have parallel strategies and so on. It could be interesting. What about threads? All the, you cannot have parallel code running because they global interpreter lock. As far as I know. But I don't get your question. Can you elaborate more? If I run more than one thread, then each thread allocates and then it has to be garbage collected. Is the garbage collector specific for a thread or is it global? It's global. As far as I know, it's in Python. PyPy, I'm not sure. Can you force the garbage collector to run or is it free also to ignore it if you can, if you call it? Can you repeat the question? I didn't hear you. Can you force the garbage collector to run and if it does, is it free to ignore it? Yes. You can force a cycle on GC module. At least on C Python, you can import GC. You can force a collection, a cycle detection because on reference counting, resources are free when they are not used anymore. You can force a cycle detection. But you have an API to manage a garbage collector. Could an object be resurrected by its finalizer? I didn't hear you. Can you repeat the question? Can an object be resurrected by its finalizer? Yeah. That's one of the HKSs that you have to handle. That's why it's not good practice. Is the garbage collector the one that collects cycles gathering and is statistics? Can I inspect and see some statistics? Yeah. You have through this API on GC module, you can check. As far as I can remember, number of retrieval objects. Let me check. What do you have over here? Document somewhere. It's a check for statistics. It's called the time. So, importing GC, you can access to some of them. Yeah. Definitely. Does it run with a certain frequency or how often? On C Python, it depends on this threshold. So, it's time that an object is allocated. It's appended to the younger generation list. Once we reach this threshold, a cycle detection cycle algorithm is done. Last question. We'll have time for more. So do you know about some user friendly tools to detect memory leaks before you deploy your application? I think there are some, but I don't know. In the worst case, you can use Valkyrie, but not so user friendly. And you have to know the internals. But probably there are some that I'm not aware of. Sorry. Great presentation. Thank you very much, everyone. Please. Thank you.
 So, hi, thank you for coming.  I'm Francisco Fernandez.  Here you have my tour of handle if you want to ask me something during the talk or whatever.  Also you have some questions during the talk.  Don't doubt about interacting with me.  So, okay, let's start.  Today I'm going to talk about a garbage collection on Python.  Here we have the agenda of this today's talk.  In first place I'll do an introduction that includes the motivation why I think this talk  could be interesting for a Python developer.  Some non-problems, some manual memory management, some definitions on garbage collection from  academia that I think is also quite interesting to know about.  And also every solution has some trade-offs, so we will explore them.  Later on we will see how C Python implements a garbage collection.  We need to know something a little bit about the C implementation, so there will be a little  bit about C, or good C.  Then I'll explain the algorithm itself, and finally the cycle detector.  And if I have enough time, I'll try to do a high overview of how PyPy approach garbage  collection.  So, let's start.  Okay, what's the motivation in knowing more about garbage collection or memory management?  We don't need to take care most of the time about memory in Python.  We are some kind of lucky.  Most of the time we are working on a business logic layer, because probably most of us we  are developers, not Python core developers, so we don't do native extensions.  So, we use a lot of exceptions that the language give to us without knowing more.  For example, we use a lot dictionaries and we don't know, and we don't need to take  care about how dictionaries are implemented or the layer between the operating system  and the standard library.  And also memory is another abstraction that we have, and sometimes it's useful to know  about.  So, we'll know more today.  I hope that you know more about how memory is managed in Python.  Okay.  But managing memory manually is hard.  How many of you are familiar with C or C++?  So you know probably how difficult sometimes is managing memory manually.  There is a lot of problems that I tried to list here.  The most known is memory leaks, that basically is that we allocate memory for some resource  and after using it we don't have to allocate it.  We do that most of the time by accident, no purpose.  Another problem that we have is the Omnistip.  Let's say for example, like in this snippet of code, this is some kind of library.  This library allocates memory on the heap.  And it returns a pointer.  Okay.  So, we don't have to do that in Python, but who is responsible on freeing this resource?  The library should do, I do the free, free this resource.  This leads to the problem of double freeze.  What happens if I free the resource and again the library somehow had the pointer and finally  tried to free.  We end up with a segmentation fault in the best of the cases.  Another problem that you can have is dangling pointers.  For example, this is another snippet of code.  We are allocating here a variable on the stack and returning the reference.  And once we are out of the scope, this address is not valid anymore.  So, again, we will end up with strange behaviors.  Segmentation fault will be the best of the cases because you know that something is wrong.  Values that are not correct is the difficult one.  Some languages propose some solutions, sort patterns, for example, C++, they try to apply  as much as possible right pattern.  They also introduce some tools on a standard library like unique pointer and serve pointer.  And also there are other approaches like in Rust that they try to make language safe  on compile time.  There is a lot of solutions.  I don't know if you see you have much tools to deal with that.  But we cannot have garbage collection in every scenario.  There are some scenarios where it is mandatory to have full control of memory.  One of them could be embedded systems where we have very limited resources and we need  to carefully deal with memory.  So for example, we have very demanding applications like a video game can be where, for example,  we need to know very carefully how the memory layout is to try to avoid cache misses and  so on.  And also applications that need determination because most of the algorithms, as far as I  know, on garbage collection, we don't know for sure when a resource is located.  So there are scenarios where garbage collection works and others don't.  But what is all this about garbage collection?  Probably most of you know what is.  But I would like to introduce you a little bit about history.  Here we have a picture of Mr. John McCarthy playing chess with a computer.  And he was kind of the inventor of garbage collection.  In this paper from the 1960s, the first mention to garbage collection on recursive function  of symbolic expressions and computation on my machine.  And it's kind of funny because he described the whole process.  He described Mark and Swipe algorithm there.  And as a food note, he says, okay, I've been naming this process garbage collection, but  I know that academia is a bit sticky and I want to use.  Finally, academia uses garbage collection.  So kind of funny.  So what's the formal definition of garbage collection?  garbage collection is basically automatic memory management.  Well, the emulator runs, it's originally allocates memory from the heap.  If more memory than available is needed, the collector reclaimed and use memory and return  it to the heap.  This sounds too formal, but it's quite simple.  The emulator, you have the definition, but basically it's our business logic.  The heap is where the memory is allocated.  And the collector is the garbage collection algorithm itself.  In our case, Python virtual machine is the one that takes care of collecting and use  resources.  If you want to dig deeper into this topic, more in the academic side, this is a quite  good book.  It's quite extensive, but it's not so formal.  So I recommend you to take a look.  But as I told you before, every solution has some trade-offs.  Nothing is perfect.  So if we decide we are a language implementator and we decide to have a garbage collector  language, we have to know that probably we'll need more resources.  We will have performance impacts because the algorithm has to run.  So we are losing CPU cycles there.  And on some algorithms, we don't know for sure when resources will be free.  So now we will start looking into how C Python implements a garbage collection.  It implements a reference counting algorithm.  But before, we need to know a little bit about how it's implemented in C. This is the main  object that is supposed mostly for us as a user all the time.  This is a py object that is basically a stack with two members.  One of them is py size t that basically is for us an integer.  Name of ref count.  This member holds the number of incoming references that an object has.  So for example, if this is an instance B and object A has a reference to B, the count is  one because it has one incoming reference.  And the other member is just a pointer to the type.  This allows us to have dynamic typing.  So let's see a simple example.  For the purpose of this talk, I want to be educational, we will only take care about instances.  We know that full class is also an object.  But for simplifying, we only deal with instances.  So how does this look graphically?  Main is the main module.  And it holds two references, one for full and another one for my list.  So those contests that I told you before are both one.  Because only main is referencing full and my list.  But let's make this more interesting.  Let's append full to my list.  Now full will have two references.  We can see graphically like this.  Now full has both main and also my list, referencing him.  That's happened.  But who takes care about this counter?  Presumably it's the C Python implementation.  So here we have a snippet of the standard library, the list object.  This function, what it does is, given the list itself, it happens the object B.  In our case, full on my list.  And take a look into this line.  By in ref from B.  This is the point where we are incrementing by one the counter.  Because now the list itself in this case has a reference to B.  In this line it sets in the last position the element.  How does this PyIncref looks like?  Like in a lot of places in C Python is a macro.  What it does is it does a custom op and increment by one.  The ref count.  You see?  But what happens when an object is not referenced by another one anymore?  Well, presumably the counter will be decremented by one.  So we end up with this case in the same picture as before.  Because now my list on index zero that before had full inside now has none.  Now we end up again with the same picture.  Because my list is not holding a reference to full anymore.  So full again as an over count of one.  And how does it look like on C Python level?  Again this is part of the list of the file that implements the list on C Python.  And again we have very much like the inverse operation on the all item.  Basically it's the one that we are not interested anymore.  What happens there in that macro?  Basically the counter is decremented by one.  But it also happens one check.  If this counter is equal to zero, we know for sure that no other element, no other object  in the system running is interested in that object anymore.  So we can safely dialogue that object.  This is what happened here.  That's the check here.  If it's greater than zero, okay.  That's some checks.  Another case it's located.  Okay.  It's clear.  Till now.  Okay.  And well, let's reproduce this case in our little example.  Now we say to the module, okay, I'm not interested in full anymore.  Delete all the references there.  So ref count reaches value zero.  So we allocate it.  Well, we, the Caravage Collector, okay.  And the interesting thing is that once we know for sure that no other object references  full, we can allocate.  We don't need to wait till collection like in other algorithms.  Okay.  Collection phase.  But do you notice any problem that this approach can have?  Any clue?  Probably most of you know what happens.  What's that?  Cycles.  What happens with cycles?  This approach don't work for cycles.  Okay.  Like this.  Now let's imagine the full has a reference to list.  And we create a cycle.  Full has a reference to my list and my list to full.  Like this.  Okay.  Now both objects live in main modules.  So no problem.  They are there.  But what happens if we don't take care anymore about full on my list?  We end up with a cycle and those objects are not the allocated because both objects have  a reference count of one.  And it's not possible that anyone reference it again because we don't have reference on  our system.  We delete from the module main.  So we end up with a memory leak.  And I told you before that one of the problems with manual memory management is memory leaks.  And we also have here memory leaks.  So what was the pro of having Garage Collection?  Well, we are lucky and in C Python implementation, they implemented the cycle detector.  Well, this is another topology that we can have.  More complex cycles.  This is a, those are very, very simple examples, but in the real world, they are more complex.  But yeah, what happened if we have a cycle?  We'll explore how C Python implement algorithm to check if there is cycles.  To do that, Garage collectors should know more or less all the objects that are allocated  on the runtime.  And this is keep track on this double link list.  This is a node of a double link list that lives in GC module with this signature.  And for performance reasons, there are three generations on implementation because doing  a whole scan or looking for cycles on the old living objects is quite costly.  So what they do is they divide into three generations, from the youngest one to the oldest ones.  And we do step by step.  So we don't need to check for the whole living objects.  Okay.  And, well, this is some C tricks to, this is a union.  Don't worry about it.  It's just some details.  So let's represent our example like the one before.  We have those three generations and we have four on my list.  Both of them probably you can see in the back.  Both of them has the value one on GC refs.  And what's the key idea of the cycle detection algorithm on C Python?  The key idea is that we know the object that belongs to a generation.  So what we can do is extract all the internal references on that generation and those objects  with a number of references bigger than zero, they have references from other generation  objects.  I don't know if I explain better.  But the idea is that we keep track only on, we subtract all the internal references in  the same generation.  I'll do a step by step trying to explain better.  To do that, types on internal on C Python implementation has this method that extract  how to traverse all the references on objects.  For example, I implemented this as a Python to do it more clear.  So for example, the extract traversing all the references basically as iterating over  the key and value and applying some function, a list basically iterate over all elements  and apply a function.  This is a utility that we have for this kind of problems like cycle detection.  So those tools help to implement the algorithm.  So let's start, let's think that we only have foo on my list on my generation zero, to  simplify things as much as possible.  So I start iterating over the first element that in this case is the one marking red foo.  What I do is using these functions, depending on the type, I iterate over all the references  that these objects have.  In this case, it's only my list.  And I apply one function.  This function, what it does is check that the number of references is greater than zero  and decrement by one.  So with this way, we are breaking the cycles, okay?  Because all the internal references are decremented.  So if we have a case like this one, we are breaking it.  We are marking as unreachable.  So this is the first step.  Foo only has a reference to my list, decrement by one, now the reference is zero, okay?  The next step we have my list as the next object in the generation zero.  And again, we decrement by one.  So now we know that those objects could be unreachable outside of my generation.  Okay?  The next step is moving those objects to a new list called unreachable.  And one step that we have to take care is we need to check on objects that are reachable,  all the references because there can be cases where some object get a value of zero, but  there is some kind of topology like one cycle, like the one that we were seeing before, and  two other references.  This end up having zero on those two objects, but they are still reachable by these two  objects.  So we have to check for that also.  After that, we move to an unreachable list.  Those objects that are reachable are moved to the next generation because they can live  more.  But I prepared a little demo in Python before I did this using GDB, but it was too much.  So let's take a look.  I have time, I think.  Can you see the code over there?  Yeah?  Well, I tried to represent more or less the implementation on Python to make it easier  to understand.  Do you remember this tovelink list?  This is one of the represented notes on how the garbage collector takes tracks on all  the allocated objects.  These are some helper methods that implement the traversal methods to know how to iterate  over the references.  One list.  Some examples.  We will run an example now.  Okay?  Here we have the garbage collector object.  It has, in this case, two generations with two thresholds that I didn't mention before.  But we don't do a cycle detection each time that we allocate an object.  There is some threshold that they study.  If we allocate more objects than that threshold, cycle detection is fired.  Okay?  Here we have this logic.  Let's say that I want to instance it in class.  What I do is I append to my first generation this object on this link list and I check this  threshold.  Okay?  Is my generation greater than the threshold?  Yes?  I collect.  I do a collection.  How is this collect cycle?  Okay.  We get some references for being more comfortable programming.  The first step is we need to update the references because on the notes, this note, don't have  the most updated reference count.  Because as I told you before, we don't run the cycle detection all the time.  So it can have a value that is older.  Okay?  So the first step is we iterate over all the generations that we're interested in and  we update the reference count with the pie of the one.  Okay?  The next step is this one of breaking cycles, just subtracting one on the internal references.  Okay?  So let's take a look at this.  What we do is again, we iterate over the whole list of this generation and using this helper  method that extracts how to iterate over all the references, we pass a function as an argument.  Okay?  And this function basically, what it does is it checks that the references are greater  than zero and decrement by one.  This is a helper method.  Don't worry about it.  So we end up with the...  After this step, I will run one example.  Oops.  Do you know how to evaluate all the cells on the Python?  Okay.  I'm pretty new to notebooks.  Sorry.  Okay.  We'll do like a step by step to see it clearly.  Okay?  We allocate one list.  We are trying to replicate our sample.  We have a list and an instance of an object and we are creating a cycle.  Okay?  We allocate...  I don't know.  We'll explore line manually.  I don't know what's happening.  Demo.  Okay.  After this step on our example, we will get those two objects with an account of zero.  So the next step is just check those edge cases where we can get some object with an  account of zero but some other object can't reference them.  So what we do is, in first place, we use, again, TP traverse and we use another callback.  That basically what it does is if we find one object that has an account zero, this  is a false positive as an reachable.  So we need to keep track that is still reachable.  In other case, we just check that refs are greater than zero.  And after that, we have those two lists, the unreachable object and the young ones.  So we know that these ones can be deleted but it's not so simple.  So we move the reachable object in this generation to the older one.  And I'll explain later what we need to do with weak references and finalizers and we  finally delete all the garbage.  There are some edge cases that I'll try to explain now.  But did you understand more or less the algorithm?  Should I explain something more or is it clear?  But as I told you before, there are some problems with this approach.  We need to take care about finalizers.  I mean, underscore and underscore deal.  There are two kinds of finalizers.  One is kind of legacy.  Those cannot be delegated safely.  So we end up having memory leaks if we have legacy finalizers.  We deal with underscore and underscore deal.  It also has to take care of a lot of edge cases.  So please don't use finalizers.  And finally, we have to take care also about weak references.  What it does is check the ones that are reachable and execute the callback that they have associated.  So what makes the emoji happy?  That is incremental.  This algorithm is incremental.  So as it works, it frees memory.  We don't need to wait to cycle to recover memory.  And emoji is worried because as you can see detecting cycles is kind of hard.  Not algorithm itself, but there is a lot of edge cases that I didn't mention that is kind  of complex.  And we also have some size overhead on objects that this OV ref count.  And as a personal opinion, also in C Python, garbage collection is two-to-coupled to the  model so that we have a counter in the main object of the interpreter.  So we cannot change the model easily.  So that's a sign note.  I have little time now.  Like five minutes, I'll try to do an overview of how PyPy handle garbage collection and  memory.  So probably most of you are familiar with PyPy.  It's an alternative implementation of Python.  It's written in our Python.  And regarding to garbage collection, it has some points that are quite interesting.  One is that it's kind of agnostic to the garbage collection algorithm.  So during translation time, that is how do you get the interpreter at the end?  You can, if I'm not wrong, you can change the model of garbage collection, the algorithm  that you want to use.  So this allows PyPy developers to experiment over time with different approaches that I  think is a good thing not to be tied to one implementation.  And the algorithm by default nowadays is in Minimug.  And let's explore a little bit about PyPy.  One of the things that PyPy developers notice is that we allocate a lot of...  We interpret it, allocate a lot of objects with a short lifetime.  So for example, we have some examples here, like for comprehension, we are allocating  objects that will live very, very shortly.  Even when we are calling a method on a class, we are creating a new object, a bounded method  with a very, very short life.  So those objects will be allocated in a performant way.  So they end up with this kind of memory model.  They divide it into two areas.  One for the general objects, this one that lives early.  The general area is divided into two areas, the nursery that has a fixed size.  Another area where all the objects that don't fit in the realm of area go there.  And also some arenas to hold the objects that are older than the young ones.  So how does it work?  It performs what they call minor and major collection.  Minor collection is performed on the young area.  So it's fast because we don't need to transfer to the old life objects.  Objects are moved only once to the old area.  And also major collection is done incrementally.  At the end, they implement kind of mark and sweep algorithm.  This are the phases that they implemented.  In the first place, they do a scan phase, then mark, then sweep.  And finally, they execute finalizer because we have the same problems as in CPython.  Here we have some schema of how mark and sweep works.  In general, this is the same schema as in the paper of McCarthy.  Finally what we do, we know for sure the root of the main objects and we traverse the graph  of memory.  And we mark on this traversal which ones are reachable.  Once we know which ones are reachable, we take it over the whole list and we sweep, we  allocate the ones that were not marked.  And yeah, that's it.  Quite simple and elegant.  Mark and sweep can collect cycles because we basically are doing a graph traversal.  But type implementation can be more complex to understand than CPython because at least  for me.  And on full collection, we stop the work.  I mean that we cannot, as well as when we are detecting cycles on CPython, we cannot  perform other operations.  So yeah, questions?  Start up front if there are any.  There are a few at the back.  Hi.  Thanks for the explanation of these algorithms.  What I would be interested in as a Python developer is to anything I should take care  about in my code so that I enable the garbage collector to do his work most efficiently.  I try to avoid the underscore, underscore build methods.  For example, because there are a lot of edge cases that interpreter has to take care of.  So that's one off.  With PyPy, you say there is a possibility of the stop the world issue on garbage collection.  Is there a way to, in future implementation or theoretically to circumvent the circumstance?  For example, splitting memory and garbage collecting different.  They do that approach, so the stops.  As far as I know, they're not so long.  But it could be interesting having, again, the JVN where you have parallel strategies  and so on.  It could be interesting.  What about threads?  All the, you cannot have parallel code running because they global interpreter lock.  As far as I know.  But I don't get your question.  Can you elaborate more?  If I run more than one thread, then each thread allocates and then it has to be garbage collected.  Is the garbage collector specific for a thread or is it global?  It's global.  As far as I know, it's in Python.  PyPy, I'm not sure.  Can you force the garbage collector to run or is it free also to ignore it if you can,  if you call it?  Can you repeat the question?  I didn't hear you.  Can you force the garbage collector to run and if it does, is it free to ignore it?  Yes.  You can force a cycle on GC module.  At least on C Python, you can import GC.  You can force a collection, a cycle detection because on reference counting, resources are  free when they are not used anymore.  You can force a cycle detection.  But you have an API to manage a garbage collector.  Could an object be resurrected by its finalizer?  I didn't hear you.  Can you repeat the question?  Can an object be resurrected by its finalizer?  Yeah.  That's one of the HKSs that you have to handle.  That's why it's not good practice.  Is the garbage collector the one that collects cycles gathering and is statistics?  Can I inspect and see some statistics?  Yeah.  You have through this API on GC module, you can check.  As far as I can remember, number of retrieval objects.  Let me check.  What do you have over here?  Document somewhere.  It's a check for statistics.  It's called the time.  So, importing GC, you can access to some of them.  Yeah.  Definitely.  Does it run with a certain frequency or how often?  On C Python, it depends on this threshold.  So, it's time that an object is allocated.  It's appended to the younger generation list.  Once we reach this threshold, a cycle detection cycle algorithm is done.  Last question.  We'll have time for more.  So do you know about some user friendly tools to detect memory leaks before you deploy your  application?  I think there are some, but I don't know.  In the worst case, you can use Valkyrie, but not so user friendly.  And you have to know the internals.  But probably there are some that I'm not aware of.  Sorry.  Great presentation.  Thank you very much, everyone.  Please.  Thank you.
Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_0_59.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_60_2099.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_2100_11015.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_11016_11207.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_11208_11819.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_11820_11879.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_11880_11927.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_11928_12107.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_12108_12263.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_12264_13283.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_13284_13907.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_13908_16127.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_16128_18827.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_18828_20915.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_20916_26915.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_26916_31463.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_31464_31715.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_31716_31763.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_31764_32579.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_32580_32819.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_32820_33635.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_33636_33683.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_33684_34355.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_34356_34439.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_34440_34763.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_34764_35111.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_35112_35483.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_35484_36659.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_36660_36719.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_36720_37199.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_37200_38243.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_38244_38423.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_38424_39119.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_39120_40835.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_40836_41003.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_41004_41759.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_41760_41927.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_41928_42503.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_42504_42647.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_42648_42875.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_42876_43463.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_43464_45419.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_45420_46139.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_46140_46343.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_46344_47795.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_47796_51407.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_51408_53567.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_53568_55307.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_55308_56663.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_56664_59339.png Francisco_Fernandez_Castano_-_Knowing_your_garbage_collector_59340_59349.png
So, hi, thank you for coming. I'm Francisco Fernandez. Here you have my tour of handle if you want to ask me something during the talk or whatever. Also you have some questions during the talk. Don't doubt about interacting with me. So, okay, let's start. Today I'm going to talk about a garbage collection on Python. Here we have the agenda of this today's talk. In first place I'll do an introduction that includes the motivation why I think this talk could be interesting for a Python developer. Some non-problems, some manual memory management, some definitions on garbage collection from academia that I think is also quite interesting to know about. And also every solution has some trade-offs, so we will explore them. Later on we will see how C Python implements a garbage collection. We need to know something a little bit about the C implementation, so there will be a little bit about C, or good C. Then I'll explain the algorithm itself, and finally the cycle detector. And if I have enough time, I'll try to do a high overview of how PyPy approach garbage collection. So, let's start. Okay, what's the motivation in knowing more about garbage collection or memory management? We don't need to take care most of the time about memory in Python. We are some kind of lucky. Most of the time we are working on a business logic layer, because probably most of us we are developers, not Python core developers, so we don't do native extensions. So, we use a lot of exceptions that the language give to us without knowing more. For example, we use a lot dictionaries and we don't know, and we don't need to take care about how dictionaries are implemented or the layer between the operating system and the standard library. And also memory is another abstraction that we have, and sometimes it's useful to know about. So, we'll know more today. I hope that you know more about how memory is managed in Python. Okay. But managing memory manually is hard. How many of you are familiar with C or C++? So you know probably how difficult sometimes is managing memory manually. There is a lot of problems that I tried to list here. The most known is memory leaks, that basically is that we allocate memory for some resource and after using it we don't have to allocate it. We do that most of the time by accident, no purpose. Another problem that we have is the Omnistip. Let's say for example, like in this snippet of code, this is some kind of library. This library allocates memory on the heap. And it returns a pointer. Okay. So, we don't have to do that in Python, but who is responsible on freeing this resource? The library should do, I do the free, free this resource. This leads to the problem of double freeze. What happens if I free the resource and again the library somehow had the pointer and finally tried to free. We end up with a segmentation fault in the best of the cases. Another problem that you can have is dangling pointers. For example, this is another snippet of code. We are allocating here a variable on the stack and returning the reference. And once we are out of the scope, this address is not valid anymore. So, again, we will end up with strange behaviors. Segmentation fault will be the best of the cases because you know that something is wrong. Values that are not correct is the difficult one. Some languages propose some solutions, sort patterns, for example, C++, they try to apply as much as possible right pattern. They also introduce some tools on a standard library like unique pointer and serve pointer. And also there are other approaches like in Rust that they try to make language safe on compile time. There is a lot of solutions. I don't know if you see you have much tools to deal with that. But we cannot have garbage collection in every scenario. There are some scenarios where it is mandatory to have full control of memory. One of them could be embedded systems where we have very limited resources and we need to carefully deal with memory. So for example, we have very demanding applications like a video game can be where, for example, we need to know very carefully how the memory layout is to try to avoid cache misses and so on. And also applications that need determination because most of the algorithms, as far as I know, on garbage collection, we don't know for sure when a resource is located. So there are scenarios where garbage collection works and others don't. But what is all this about garbage collection? Probably most of you know what is. But I would like to introduce you a little bit about history. Here we have a picture of Mr. John McCarthy playing chess with a computer. And he was kind of the inventor of garbage collection. In this paper from the 1960s, the first mention to garbage collection on recursive function of symbolic expressions and computation on my machine. And it's kind of funny because he described the whole process. He described Mark and Swipe algorithm there. And as a food note, he says, okay, I've been naming this process garbage collection, but I know that academia is a bit sticky and I want to use. Finally, academia uses garbage collection. So kind of funny. So what's the formal definition of garbage collection? garbage collection is basically automatic memory management. Well, the emulator runs, it's originally allocates memory from the heap. If more memory than available is needed, the collector reclaimed and use memory and return it to the heap. This sounds too formal, but it's quite simple. The emulator, you have the definition, but basically it's our business logic. The heap is where the memory is allocated. And the collector is the garbage collection algorithm itself. In our case, Python virtual machine is the one that takes care of collecting and use resources. If you want to dig deeper into this topic, more in the academic side, this is a quite good book. It's quite extensive, but it's not so formal. So I recommend you to take a look. But as I told you before, every solution has some trade-offs. Nothing is perfect. So if we decide we are a language implementator and we decide to have a garbage collector language, we have to know that probably we'll need more resources. We will have performance impacts because the algorithm has to run. So we are losing CPU cycles there. And on some algorithms, we don't know for sure when resources will be free. So now we will start looking into how C Python implements a garbage collection. It implements a reference counting algorithm. But before, we need to know a little bit about how it's implemented in C. This is the main object that is supposed mostly for us as a user all the time. This is a py object that is basically a stack with two members. One of them is py size t that basically is for us an integer. Name of ref count. This member holds the number of incoming references that an object has. So for example, if this is an instance B and object A has a reference to B, the count is one because it has one incoming reference. And the other member is just a pointer to the type. This allows us to have dynamic typing. So let's see a simple example. For the purpose of this talk, I want to be educational, we will only take care about instances. We know that full class is also an object. But for simplifying, we only deal with instances. So how does this look graphically? Main is the main module. And it holds two references, one for full and another one for my list. So those contests that I told you before are both one. Because only main is referencing full and my list. But let's make this more interesting. Let's append full to my list. Now full will have two references. We can see graphically like this. Now full has both main and also my list, referencing him. That's happened. But who takes care about this counter? Presumably it's the C Python implementation. So here we have a snippet of the standard library, the list object. This function, what it does is, given the list itself, it happens the object B. In our case, full on my list. And take a look into this line. By in ref from B. This is the point where we are incrementing by one the counter. Because now the list itself in this case has a reference to B. In this line it sets in the last position the element. How does this PyIncref looks like? Like in a lot of places in C Python is a macro. What it does is it does a custom op and increment by one. The ref count. You see? But what happens when an object is not referenced by another one anymore? Well, presumably the counter will be decremented by one. So we end up with this case in the same picture as before. Because now my list on index zero that before had full inside now has none. Now we end up again with the same picture. Because my list is not holding a reference to full anymore. So full again as an over count of one. And how does it look like on C Python level? Again this is part of the list of the file that implements the list on C Python. And again we have very much like the inverse operation on the all item. Basically it's the one that we are not interested anymore. What happens there in that macro? Basically the counter is decremented by one. But it also happens one check. If this counter is equal to zero, we know for sure that no other element, no other object in the system running is interested in that object anymore. So we can safely dialogue that object. This is what happened here. That's the check here. If it's greater than zero, okay. That's some checks. Another case it's located. Okay. It's clear. Till now. Okay. And well, let's reproduce this case in our little example. Now we say to the module, okay, I'm not interested in full anymore. Delete all the references there. So ref count reaches value zero. So we allocate it. Well, we, the Caravage Collector, okay. And the interesting thing is that once we know for sure that no other object references full, we can allocate. We don't need to wait till collection like in other algorithms. Okay. Collection phase. But do you notice any problem that this approach can have? Any clue? Probably most of you know what happens. What's that? Cycles. What happens with cycles? This approach don't work for cycles. Okay. Like this. Now let's imagine the full has a reference to list. And we create a cycle. Full has a reference to my list and my list to full. Like this. Okay. Now both objects live in main modules. So no problem. They are there. But what happens if we don't take care anymore about full on my list? We end up with a cycle and those objects are not the allocated because both objects have a reference count of one. And it's not possible that anyone reference it again because we don't have reference on our system. We delete from the module main. So we end up with a memory leak. And I told you before that one of the problems with manual memory management is memory leaks. And we also have here memory leaks. So what was the pro of having Garage Collection? Well, we are lucky and in C Python implementation, they implemented the cycle detector. Well, this is another topology that we can have. More complex cycles. This is a, those are very, very simple examples, but in the real world, they are more complex. But yeah, what happened if we have a cycle? We'll explore how C Python implement algorithm to check if there is cycles. To do that, Garage collectors should know more or less all the objects that are allocated on the runtime. And this is keep track on this double link list. This is a node of a double link list that lives in GC module with this signature. And for performance reasons, there are three generations on implementation because doing a whole scan or looking for cycles on the old living objects is quite costly. So what they do is they divide into three generations, from the youngest one to the oldest ones. And we do step by step. So we don't need to check for the whole living objects. Okay. And, well, this is some C tricks to, this is a union. Don't worry about it. It's just some details. So let's represent our example like the one before. We have those three generations and we have four on my list. Both of them probably you can see in the back. Both of them has the value one on GC refs. And what's the key idea of the cycle detection algorithm on C Python? The key idea is that we know the object that belongs to a generation. So what we can do is extract all the internal references on that generation and those objects with a number of references bigger than zero, they have references from other generation objects. I don't know if I explain better. But the idea is that we keep track only on, we subtract all the internal references in the same generation. I'll do a step by step trying to explain better. To do that, types on internal on C Python implementation has this method that extract how to traverse all the references on objects. For example, I implemented this as a Python to do it more clear. So for example, the extract traversing all the references basically as iterating over the key and value and applying some function, a list basically iterate over all elements and apply a function. This is a utility that we have for this kind of problems like cycle detection. So those tools help to implement the algorithm. So let's start, let's think that we only have foo on my list on my generation zero, to simplify things as much as possible. So I start iterating over the first element that in this case is the one marking red foo. What I do is using these functions, depending on the type, I iterate over all the references that these objects have. In this case, it's only my list. And I apply one function. This function, what it does is check that the number of references is greater than zero and decrement by one. So with this way, we are breaking the cycles, okay? Because all the internal references are decremented. So if we have a case like this one, we are breaking it. We are marking as unreachable. So this is the first step. Foo only has a reference to my list, decrement by one, now the reference is zero, okay? The next step we have my list as the next object in the generation zero. And again, we decrement by one. So now we know that those objects could be unreachable outside of my generation. Okay? The next step is moving those objects to a new list called unreachable. And one step that we have to take care is we need to check on objects that are reachable, all the references because there can be cases where some object get a value of zero, but there is some kind of topology like one cycle, like the one that we were seeing before, and two other references. This end up having zero on those two objects, but they are still reachable by these two objects. So we have to check for that also. After that, we move to an unreachable list. Those objects that are reachable are moved to the next generation because they can live more. But I prepared a little demo in Python before I did this using GDB, but it was too much. So let's take a look. I have time, I think. Can you see the code over there? Yeah? Well, I tried to represent more or less the implementation on Python to make it easier to understand. Do you remember this tovelink list? This is one of the represented notes on how the garbage collector takes tracks on all the allocated objects. These are some helper methods that implement the traversal methods to know how to iterate over the references. One list. Some examples. We will run an example now. Okay? Here we have the garbage collector object. It has, in this case, two generations with two thresholds that I didn't mention before. But we don't do a cycle detection each time that we allocate an object. There is some threshold that they study. If we allocate more objects than that threshold, cycle detection is fired. Okay? Here we have this logic. Let's say that I want to instance it in class. What I do is I append to my first generation this object on this link list and I check this threshold. Okay? Is my generation greater than the threshold? Yes? I collect. I do a collection. How is this collect cycle? Okay. We get some references for being more comfortable programming. The first step is we need to update the references because on the notes, this note, don't have the most updated reference count. Because as I told you before, we don't run the cycle detection all the time. So it can have a value that is older. Okay? So the first step is we iterate over all the generations that we're interested in and we update the reference count with the pie of the one. Okay? The next step is this one of breaking cycles, just subtracting one on the internal references. Okay? So let's take a look at this. What we do is again, we iterate over the whole list of this generation and using this helper method that extracts how to iterate over all the references, we pass a function as an argument. Okay? And this function basically, what it does is it checks that the references are greater than zero and decrement by one. This is a helper method. Don't worry about it. So we end up with the... After this step, I will run one example. Oops. Do you know how to evaluate all the cells on the Python? Okay. I'm pretty new to notebooks. Sorry. Okay. We'll do like a step by step to see it clearly. Okay? We allocate one list. We are trying to replicate our sample. We have a list and an instance of an object and we are creating a cycle. Okay? We allocate... I don't know. We'll explore line manually. I don't know what's happening. Demo. Okay. After this step on our example, we will get those two objects with an account of zero. So the next step is just check those edge cases where we can get some object with an account of zero but some other object can't reference them. So what we do is, in first place, we use, again, TP traverse and we use another callback. That basically what it does is if we find one object that has an account zero, this is a false positive as an reachable. So we need to keep track that is still reachable. In other case, we just check that refs are greater than zero. And after that, we have those two lists, the unreachable object and the young ones. So we know that these ones can be deleted but it's not so simple. So we move the reachable object in this generation to the older one. And I'll explain later what we need to do with weak references and finalizers and we finally delete all the garbage. There are some edge cases that I'll try to explain now. But did you understand more or less the algorithm? Should I explain something more or is it clear? But as I told you before, there are some problems with this approach. We need to take care about finalizers. I mean, underscore and underscore deal. There are two kinds of finalizers. One is kind of legacy. Those cannot be delegated safely. So we end up having memory leaks if we have legacy finalizers. We deal with underscore and underscore deal. It also has to take care of a lot of edge cases. So please don't use finalizers. And finally, we have to take care also about weak references. What it does is check the ones that are reachable and execute the callback that they have associated. So what makes the emoji happy? That is incremental. This algorithm is incremental. So as it works, it frees memory. We don't need to wait to cycle to recover memory. And emoji is worried because as you can see detecting cycles is kind of hard. Not algorithm itself, but there is a lot of edge cases that I didn't mention that is kind of complex. And we also have some size overhead on objects that this OV ref count. And as a personal opinion, also in C Python, garbage collection is two-to-coupled to the model so that we have a counter in the main object of the interpreter. So we cannot change the model easily. So that's a sign note. I have little time now. Like five minutes, I'll try to do an overview of how PyPy handle garbage collection and memory. So probably most of you are familiar with PyPy. It's an alternative implementation of Python. It's written in our Python. And regarding to garbage collection, it has some points that are quite interesting. One is that it's kind of agnostic to the garbage collection algorithm. So during translation time, that is how do you get the interpreter at the end? You can, if I'm not wrong, you can change the model of garbage collection, the algorithm that you want to use. So this allows PyPy developers to experiment over time with different approaches that I think is a good thing not to be tied to one implementation. And the algorithm by default nowadays is in Minimug. And let's explore a little bit about PyPy. One of the things that PyPy developers notice is that we allocate a lot of... We interpret it, allocate a lot of objects with a short lifetime. So for example, we have some examples here, like for comprehension, we are allocating objects that will live very, very shortly. Even when we are calling a method on a class, we are creating a new object, a bounded method with a very, very short life. So those objects will be allocated in a performant way. So they end up with this kind of memory model. They divide it into two areas. One for the general objects, this one that lives early. The general area is divided into two areas, the nursery that has a fixed size. Another area where all the objects that don't fit in the realm of area go there. And also some arenas to hold the objects that are older than the young ones. So how does it work? It performs what they call minor and major collection. Minor collection is performed on the young area. So it's fast because we don't need to transfer to the old life objects. Objects are moved only once to the old area. And also major collection is done incrementally. At the end, they implement kind of mark and sweep algorithm. This are the phases that they implemented. In the first place, they do a scan phase, then mark, then sweep. And finally, they execute finalizer because we have the same problems as in CPython. Here we have some schema of how mark and sweep works. In general, this is the same schema as in the paper of McCarthy. Finally what we do, we know for sure the root of the main objects and we traverse the graph of memory. And we mark on this traversal which ones are reachable. Once we know which ones are reachable, we take it over the whole list and we sweep, we allocate the ones that were not marked. And yeah, that's it. Quite simple and elegant. Mark and sweep can collect cycles because we basically are doing a graph traversal. But type implementation can be more complex to understand than CPython because at least for me. And on full collection, we stop the work. I mean that we cannot, as well as when we are detecting cycles on CPython, we cannot perform other operations. So yeah, questions? Start up front if there are any. There are a few at the back. Hi. Thanks for the explanation of these algorithms. What I would be interested in as a Python developer is to anything I should take care about in my code so that I enable the garbage collector to do his work most efficiently. I try to avoid the underscore, underscore build methods. For example, because there are a lot of edge cases that interpreter has to take care of. So that's one off. With PyPy, you say there is a possibility of the stop the world issue on garbage collection. Is there a way to, in future implementation or theoretically to circumvent the circumstance? For example, splitting memory and garbage collecting different. They do that approach, so the stops. As far as I know, they're not so long. But it could be interesting having, again, the JVN where you have parallel strategies and so on. It could be interesting. What about threads? All the, you cannot have parallel code running because they global interpreter lock. As far as I know. But I don't get your question. Can you elaborate more? If I run more than one thread, then each thread allocates and then it has to be garbage collected. Is the garbage collector specific for a thread or is it global? It's global. As far as I know, it's in Python. PyPy, I'm not sure. Can you force the garbage collector to run or is it free also to ignore it if you can, if you call it? Can you repeat the question? I didn't hear you. Can you force the garbage collector to run and if it does, is it free to ignore it? Yes. You can force a cycle on GC module. At least on C Python, you can import GC. You can force a collection, a cycle detection because on reference counting, resources are free when they are not used anymore. You can force a cycle detection. But you have an API to manage a garbage collector. Could an object be resurrected by its finalizer? I didn't hear you. Can you repeat the question? Can an object be resurrected by its finalizer? Yeah. That's one of the HKSs that you have to handle. That's why it's not good practice. Is the garbage collector the one that collects cycles gathering and is statistics? Can I inspect and see some statistics? Yeah. You have through this API on GC module, you can check. As far as I can remember, number of retrieval objects. Let me check. What do you have over here? Document somewhere. It's a check for statistics. It's called the time. So, importing GC, you can access to some of them. Yeah. Definitely. Does it run with a certain frequency or how often? On C Python, it depends on this threshold. So, it's time that an object is allocated. It's appended to the younger generation list. Once we reach this threshold, a cycle detection cycle algorithm is done. Last question. We'll have time for more. So do you know about some user friendly tools to detect memory leaks before you deploy your application? I think there are some, but I don't know. In the worst case, you can use Valkyrie, but not so user friendly. And you have to know the internals. But probably there are some that I'm not aware of. Sorry. Great presentation. Thank you very much, everyone. Please. Thank you.
why I think this talk could be interesting for a overview of how PyPy approach garbage collection. of exceptions that the language give to us to take care about how dictionaries are responsible on freeing this resource? The library This leads to the problem of double freeze. What to know very carefully how the memory layout is been naming this process garbage collection, but machine is the one that takes care of collecting with cycles? This approach don't work for cycles. kind of problems like cycle detection. So those remember this tovelink list? This is one of the don't have the most updated reference count. opinion, also in C Python, garbage collection is time with different approaches that I think is a allocating objects that will live very, very example, because there are a lot of edge cases garbage collector to run and if it does, is it through this API on GC module, you can check. As