Garbage Collection Theory: Tracing vs Reference Counting Explained

[00:00:00]okay so a little bit about me um I'm a former computer science educator I'm currently a quote unquote professional programmer honestly um I got interested in garbage collection because I use Ruby professionally for a long time and that's yeah that's kind of a joke but also um and yeah also I want to say like to what our what the um what our friend the CTO said if you're not interested in computers then you know this isn't the right place for you but um I am and I hope most of you are it seems like the set's really cool um so yeah I used RW professionally I had a lot of problems with that I started studying it and then I wanted to give a talk where I taught um a you know a conference where the people as much as I could about what garbage collection is how it works um what they can you know what they can do to learn more about it and and the you know the idea was that people should people who use Ruby in particular should understand how garbage collection Works in order to write better Ruby code write faster Ruby code or understand the reasons why their code was uh behaving the way that it was performance- wise um particularly so I got really into it um and this paper out of all the papers that are read in studying the subject a few dozen um is is my favorite um and yeah this meat up is basically my dream come true because not only because I'm speaking and I love to hear myself speak but because um but because it's such a [ __ ] awesome idea you know and uh I wish that something like this was around 10 years ago open to the public uh because then you know I would be 10 years uh in the more advanced than I am now which is not very Advanced um so yeah that's a that's I think that's enough about me um the paper is unified theory of garbage collection it was published by bacon Chan and ran in 2004 um these are three guys that work in MIT and IBM excuse me and um it's a fantastic paper so I'm going to give you a little bit of an outline of what the rest of this talk is going to look like um I'm going to speak for about 30 minutes total hopefully um maybe a little bit more maybe a little bit less and then I hope that we can have some discussion it seems like a bunch of you have read this paper um and hopefully you have some questions or some things to say about it and and we can chat about it um you know being invited to be the first speaker to meet up like this is interesting we're kind of still playing it bye in terms of what this thing should look like but hopefully we can you know I know that there's some opinionated people in the audience um don't act surprise um so yeah so I'm going to talk I'm going to give a little bit of background about garbage collection as a subject area I'm going to highlight what I think are this paper's contributions to the field I'm going to talk about what my favorite parts of the paper are and then I hope that we can talk about all that at the end or some of it so as a show of hands um who has studied garbage collection like in any capacity before reading this paper included okay way up let's raise your hands okay good nice okay that's a good number all right so how many of you have read the paper again okay good pretty good red read the paper you got to read it a few times before you read it first you have to read it and then you're like do I want to read it and then you read it and then you're like did I read it or did I read it okay uh that's that's you know I think that's another thing that I'd like everyone in here to take away from this Meetup is that you know papers like this that are published by the you know prominent computer scientists that are doctorates and work at big company these these people do research for a living right so you're not going to understand all of it right but the beauty of a lot of papers and this paper in particular is that you'll understand a some of it right and and you'll understand some and then a little more and then a little more and you'll get the basic idea and that's really cool like read the abstract read the conclusion look at the sections read the you know read the bibliography if any of those papers sound interesting to you do the same thing over and over again recursively walk that biblography and that's how you you know that's how I learn anyway um yeah I don't normally recommend that people do things the way that I do but I think that's pretty good so how many of you get hacked on a garbage collector in any capacity before a few okay I think actually that more of you have than you know like probably some of you have hacked on a garbage collection like algorithm before and you haven't you don't really you might not know that and that's another lesson that this paper has for you for us um and how many of you are just here for the beer and pizza and I me cuz I'm so like handsome and charm no no other at Okay cool so first let's start with garbage collection um this is John McCarthy one of the greatest photographs of all time here he is in the early 60s or so playing chess against a computer he wrote the he wrote the program that the computer is running to play chess and I I mean let's all just look at this picture for a minut look expression I want to look at a computer that way one day you know normally I typically have much more scornful look on my face but if anyone here knows chat I mean this looks like it's kind of earling on in the match I don't know who one but anyway it's cool there's robots in the background so he's on slide because he's one of the inventors of garbage collection as a concept right um I have a joke where I say that 1960 was a great year for garbage collectors that's because that's the year that both of them were invented right and and that's actually that's an interesting idea that is sort of born out in this paper and refuted a little bit of this paper but the the two major algorithms that we'll be discussing were both invented in papers in the same year sort of been auspiciously neither of them are titled like yo I invented garbage collection right or this whole other thing but these algorithms fell out of that so and plus like I said it's really good picture so let's talk about garbage collection as a background in order to do that this is the list of terminology that I think is important to to understand so garbage collection is on this list that's kind of silly but we have to know what it is right in order to give a good definition of garbage collection I think we need to have pretty good definitions for all the other terms terms that are on this list okay so um what's a heap who wants to help me out anyone else anyone have a good definition for what a heap is sort of tree structure it's a it's a data structure that you have access to that you can allocate from and deallocate to it's a big it's a big pool of blogs that you do stuff with right I mean it's a tree structure as Brandon says okay does anyone not does anyone have no idea what a he is and is really confused when I talk about heaps you know so most of you are okay with that subject okay so it's like a big pool of memory that you have access to in this paper and for the purposes of this discussion we're going to assume that this heap of memory that you have access to you only allocate and deallocate fixed size chunks from this Heap right it's a big bag full of marbles when you need a marble you take a marble out right when you're out of marbles you're in trouble right and when you're done with the marble you put it back in the bag okay marbles that's basically how computers work okay what about a mutator okay so a mutator is is specific to garbage collection terminology I would say that a mutator is the mutator is the part of your program that does does the stuff right the mutator is the thing that takes marbles out and puts marbles back polishes some marbles you know annotates them in some way okay so if you have a big pool of memory and you want to say this the memory is an integer the integer one this this bit of memory is the value true this bit of memory is you know the head of a list and then it points to the tail of the list and that list contains a function structure all that stuff whoever's doing that work in your program is is the mutator of the program it's kind of abstract that's one of the beauties of this paper right because what it does is it takes something that's typically considered quite concrete and makes it into an abstract system and I hope to hope to demonstrate that more okay okay any questions yes would it be reasonable to say the mutator is mutating the heat the mutator is mutating the heat yes that's for sure true anyone else so is the collector well right right okay so is the collector so let's talk about the collector okay so and in some cases like we'll see the line between the mutator and The Collector is kind of blurry right who's mutating who's collecting whatever like I said it's a computer you know you know kind of all bets are off but um so the collector is the part of the program that is specific to bookkeeping the you know the memory in that heat right so that's the The Collector has to know what's going on uh with all your available memory what you can do what has been done it typically keeps track of things for you right and and and as you'll see we'll drill a little bit deep more deeply into that okay so that's heat mutator and collector any questions about that if you don't really understand those on a basic level then you know the rest of the the top might be a little bit challenging for you so since this is a discussion you know anyone any questions no anyone UNC you can like wink you don't have to I like being Wim that anyway so all right let's keep going yeah did you skip garbage collection on purpose I did Skip garbage collection on purpose because you're going to have to know the ones below it and I give a nice definition of garbage collection on the next slide and I remember that because it's right in front of me um so Roots roots are interesting right roots are sort of uh specific to specific implementations of garbage collection but what I call roots are roots are areas of your HEAP that can be reached without asking other areas of the Heap how to reach them right so roots are something that are sort of inherent to heaps they are your entry points into those heaps um in Dynamic languages in Dynamic object-oriented languages there a really there's a really good thing to point to for the Heap and the or for roots and like an example in Ruby for example of what a root object is in the Heap is like the definition of the object class is a root in the Ruby Heap right because you have to be able to get to object in order to be able to find everything else in that Heap it's a very Ruby specific example does anyone else have any contribution program stack right so that's another thing that would typically be in The Roots right you don't have to ask you know when when the program loads where the program starts right and how to access the data that comprises the actual program will typically be reachable for the roots as well all right and then barriers are um a little bit more complicated and we're going to talk about them a little bit more in detail but barriers are types a barrier is a mechanism by which the mutator can it sorry it is through barriers that your mutator can inform the collector of certain things that are happening inside your program and we're going to that's a little bit big I'm okay with that okay barriers are important yes I have a question about I'm still like very into this topic but um I was wondering is there a reason why heat is the data structure in a garbage collector and not like another sure so I know the answer to that okay uh Heap is a a misnomer and it's historical uh so I joked saying it was a tree structure because um uh a heap is a sorted tree but it's also the first implementation that was used for like malok and free implantations and so uh malok free sort of style systems came before garbage collectors and over time the bag of dynamically allocated and free memory was traditionally called the heat because it was a heap and it has not been true in 60 70 years so the question was why is it a heap and the answer is it's not okay it's going to make it a lot clearer that's true I mean these things were invented in 1960 and things are different then and now you just use the word e right it's just that thing it's there with that we would be in trouble so um going to talk a little bit more about barriers they don't really need to be on this list because actually the definition I'm going to show you doesn't have the word barrier in it but I want you to like look at that word okay so there you go all right so now here's my garbage collection a definition for this is like my there's another definition that has none of that other terminology in it that I wanted to show you the the terminology and show you so garbage collection is automatic memory management while the mutator runs and routinely allocates memory from the Heap if more memory than available is needed the collector reclaims unused memory and returns it to the heat that's General that's kind of implementation specific in certain ways but I like I'm happy with this okay so any questions about this this is garbage collection this pretty good definition of garbage collection if you've never heard a definition of garbage collection before I'd throw this on the table right the garbage collection was initially invented because people that were right programs thought hey wouldn't it be cool if we could write a program that used more memory than was physically available on the machine that it was using right so that's kind of hilarious to think about right but if you only have 10 marbles right and you want to pull 10 of them out at a time you got to be kind of tricky to like you know you got to keep nine in the air you might be juggling them or something I don't know that was a terrible mix metaphor but um does anyone not like this definition or want to argue with me about it or or tell me how great it is okay let's look at it I think this is pretty garbage collection is automatic memory management that's why we're all here that's why it's important while the mutator runs it routinely allocates memory from the Heap if more memory than available as needed the collector reclaims unused memory and returns it to the unused maybe isn't the greatest word unimportant memory or something like that so um the two there are two there are two big algorithms that were invented for garbage collection in in the' 60s in the early' 60s and here's a comparison from them this is the first time we're dipping into the paper a little bit here and this this table that uh the authors's offer was really it's one of the first things that so this is my this is my copy of this paper um and I've been I we've been friends for a long time it's heavily highlighted and annotated and you know I have stars next to things and everything and I really like this table it's on the second page and the first time that I saw it it really it was striking to me because I was like wow okay you know first of all these are two algorithms that are typically considered very different from each other right there you don't when you're writing in a garbage collector you're not like ah I'm either going to use that one or this one right no we no like they were considered very different and for very different purposes so just the idea that there were the same number of rows for each like alone I was like okay like there was a lot of thought put into this table in particular and and the idea in general that these algorithms have a lot in common so let's look at them the two kinds of algorithms are are called Mark and sweep typically but the authors call them tracing algorithms and on the other side there are reference counting algorithms so let's let's go down this table and just we can talk about each of the rows in this table okay so we have tracing reference counting the collection style okay in what style is memory reclaimed uh and used Again by the system that is doing the GC so in tracing it's a batch style and in reference counting it's incremental so incremental means that you know each time something happens there is a little bit of that of that happening and batch means that you know you offer things up and wait for a certain limit to be reached typically and then do it all at once so it's the difference between a little bit a little bit a little bit a little bit a little bit and nothing nothing nothing a lot nothing nothing nothing a lot okay so cost per mutation okay so every time the mutator does something does the garbage collector um have any overhead for that particular operation and tracing there is classically none okay uh and tracing a market sweep you mutate to your heart's uh content and and that's it and you'll find out what happens afterwards next right and reference counting the cost per mutation is high so every time you mutate you pay that cost of reference counting typically and this is this table is in the naive implementations of these algorithms which are the initial implementations of them that's that's the starting point and that's the point that really informed people's opinions about the applications and performance profile these algorithms so throughput and tracing is high and in reference counting is low pause times in tracing are long so Ruby which is a mar has a mark and sweep um garbage collector for example one of the problems that I was initially chasing down was these long pause times they suck okay they're in the jbm to they're all over the place pause times are bad um and we'll talk a little bit more about that soon pause times are long and tracing short and reference counting so there's you see there's a high long for throughput and pause times and low short right there there's a relationship between those columns up to those rows so real time this is a this is a bit of a confusing bit of terminology real time no for tracing and yes for reference counting so all real time me real time doesn't mean you know real time has a lot of different meanings okay in this particular context what it means is that in reference counted garbage collection algorithms you are capable of conforming to a particular SLA as to the amount of time that you will take to do work that the garbage collection algorithm will take to do work and in tracing algorithms that there's a sort of non-determinism that is inherent to that particular kind of implementation that's a little bit much you don't really have to know about the Real Time stuff now if you are interested in real time garbage collection I have a pretty I think a pretty good explanation of uh the issues involved in that on my blog that you can check out and if you want to ask me any questions about real time or you want to discuss it at the end we can but tracing typically no and reference counting typically yes and then na of implementation and tracing uh can collect cycles and reference counting uh classically cannot Cycles are uh items in the Heap which refer either refer to themselves directly or refer to something that refers back themselves so we're going to talk a little bit more about what that means right now okay so let's talk about just a little mistified by throughput okay what does that mean in this context so throughput means the that's a good question throughput would mean the amount of memory that you could allocate and well it's sort of meant to be it's sort of meant to be a uh performance characterization of how much overhead you pay so you you know when you your mutator will have a high throughput when it doesn't have to pay a cost per mutation and your throughput will your reference counting will have a lower throughput because it does pay that cost per mutation so it can allocate it can do more allocations in a more predictable amount of time so reference counting will do less more predictably and Market we will do more less predictably is that does that work for you okay it's a little bit tricky right it's I would say if you were thinking about it it would be the amount of stuff you can allocate and deallocate and how quickly you can do that and and throughput might actually be more a characterization of the mutator than the collector in this particular case um we can talk more about performance stuff too okay so let's start with reference counting so reference counting is basically the idea that that when you're running a program um each time you want to access some area of memory a heap you will keep track of the references to that particular area of memory so every time you make a change you're doing that bookkeeping as you make those changes so it's reference counting it counts the references to areas in memory in your heat okay and let's talk about um this is a quote from the paper about the naive implementation of reference counting and it says the incremental nature of reference counting is generally considered to be its fundamental advantage however the cost of updating reference counts every time a new pointer is loaded into a register is typically much uh much too high I miss know much too high for high performance applications okay so this kind of tries to tell you what the pros and cons of this particular kind of algorithm uh is so the good thing about it is that it's incremental right every time you do a little bit of work you know that your memory is uh is at the best state in its bookkeeping that it could possibly be right so at the end of each mutation when the reference counts are done and the memory is allocated and deallocated there's there's no extra work to do so that's what makes it suitable for Real Time application specifically right you can say I know that this algorithm will never pause for more than n microsc or milliseconds or wherever you're at um because you know that that book that bookkeeping will be done and you have a few more knobs to turn in that regard right and so uh that's that's cool right so let's look at that and then let's look at what what's really great that these authors have to say about it is that as a result of that issue right some form of deferred reference counting is typically used so the result is delayed collection floating garbage and longer pauses which are the typical characteristics of tracing collectors right so what the authors are showing you is that reference counting is awesome except for when it isn't right and that the changes that are typically made to reference counting garbage collectors in order to um optimize them make them look more like tracing collectors that's that's pretty interesting yes are there any are there any well-known examples of systems using reference counting uh yeah python python see python uses reference counting I've heard of iOS yeah um so there are some languages that so so in reality in reality no right we're going to hear about that like nothing really uses pure reference counting and that that's kind of one of the that's one of the cool Parts about this paper so I'm you know these are you know these are sort of surfacy definitions of these algorithms because I want to get to the heart what's most interesting about this paper in a lot of ways isn't about garbage collection right there there's there's higher uh higher planes at play here there's more interesting stuff going on so that's why it's okay just to talk this much about reference counting and Market to because there's a lot of literature about what those things are and what they look like in the real world so let's talk about Market sweep for a second so Market sweep is the idea that as you are accessing your keep right you will mutate and allocate and allocate and allocate until you can no longer allocate anymore and then some other part of your program some other thread or some other unit of execution in your program will do that bookkeeping all at once so as opposed to the incremental nature of reference counting where every time an operation is executed you pay that cost in a tracing Mark and sweep algorithm you allocate allocate allocate allocate and then stop everything to do the deallocation where it's necessary so that you can then continue okay so its fundamental Advantage advantages are the lack of permutation overhead and the natural collection of CID garbage however a fundamental disadvantage of tracing is that freeing of dead objects is delayed resulting in long pause time so and this was the issue that I was experiencing with MRI Ruby and how do you optimize this kind of algorithm well it's funny you should ask because um one of the first optimizations that is typically applied is generational collection um which you know it General generational collection is 1990s uh technology that is finally making its way to Ruby in 2014 which is actually good it's making it a lot faster which is cool um so generational flection this reduces the average pause time but also introduces permutation overhead thus it takes on both some of the positive and negative aspects of reference counting collection okay so in order to make Market sweep algorithms faster you typically do something called create a generational garbage collector where you have one area of your HEAP that's allocated from more often and another area of your HEAP that is allocated from less often or maybe you divide your heat by the size of the objects but in any event you need to use a barrier going back to that word in order to optimize a generational uh Market sup garbage collector into a generational collector and once you have a right barrier you have permutation overhead and permutation overhead and right barriers are fundamental uh characteristics of reference counted garbage flection algorithms okay so that's crazy right it's really interesting because it's this idea I'm going to get more into that soon because I'm taking a lot more time than I want to so this paper structur so let's talk about just the just these are the number sections of this paper that I have just copied so so it has a qualitative comparison that we've just gone through right a similar kind of treatment of these two very different algorithms uh the authors then introduced this idea of algorithmic duel right where they say that garbage collection in the forms of reference counting and Market sweep are typically considered very different from each other but in fact they are what the authors and I believe this is a novel term that they coin in this paper in specific and I have not found many other references to the idea of an algorithmic duel elsewhere although I'm going to ask you guys questions about that at the end um they're like okay actually they're kind of the same thing right especially in their real world implementations then they talk about hybrid collectors and show us that almost all production garbage collection algorithms are hybrids of tracing and uh reference C and that's kind of what those optimization slide quotes that I showed you show right they say that okay reference counting works until the performance isn't good enough and then you make them look more like tracing algorithms and then tracing algorithms are great but then the pause times get too long and you want generation garbage collection so then you end up introducing barriers which make them look more like reference cting so then they go through uh cycle collection which we talked a little bit about they talk about multitud collectors and then they discuss the cost analysis and SpaceTime tradeoffs of these different algorithms and the cost analysis is probably one of the most applicable and beneficial components of the entire paper where they actually create a fix point for ation which is like a math thing I guess and um so basically they make a they take these two algorithms that were considered like diametric opposites of each other and they create a mathematical framework through which you can measure the SpaceTime costs of any garbage collection algorithm okay which is incredible and like I cannot do a Justice you're going to have to read it like a bunch and then you're going to read it right I finally am pretty confident with that material and it took a really long time um yeah and I'm not very intelligent so you know any of you will probably have a lot better time with you than that okay so then they talk about the SpaceTime tradeoffs and that's really interesting too so I feel like these this paper's main contributions are that it creates this formal framework for considering any garbage collection algorithm implementation any right as long as Z garbage collection algorithm is basically you know graph traversal and manipulation of these kind of heat like data structures you can apply this cost analysis framework to them which is incredible right um that is the main that's the main meat of what they're doing it breaks down cargo culted beliefs right it takes this idea that you choose one or the other and it says well actually right what you do is you design your garbage collection algorithm around the workload that your application needs to uh perform right so they don't you don't just choose one or the other you you you are going to end up choosing a combination of the characteristics of those two and either you can do so intelligently through the framework that they present or you can start with one and then like beat it with a bat until it looks like the other one and you're not going to be that happy with that result right and they say that that nearly all and it's really like just cuz I knew someone in here was going to bust my chops if I said all I there are no production garbage collection algorithms that are one or the other there just aren't you're not going to you know there I don't know unless you know of any like your toy implementation that you do in computer science class will be one or the other right for very simple virtual machine implementations that's great but when you're talking about optimizing you will end up doing one or more of these things specifically in the current state of like 2014 computer architecture that's typically what will end up happening and then they make real design recommendations that's the other really cool thing about this paper is that they say for people who are designing garbage collectors you can be doing so more methodically and and to me that was really powerful because it was uh it this paper came out of people that had implemented many garbage collectors right so after implementing reference County garbage collection collectors and optimizing them and implementing ref uh tracing uh collectors and optimizing them they stared at that for so long that they started to see these similarities between these two things and for me that is the that is the most powerful type of insight that you can have in the field of computer science right the the best most uh for me most visceral and awesome mindblowing computer science are these crazy abstract connections between things that are so that seem so uh sort of you know um profane and like real world right like they're in the flesh right but if you stare at them for long enough you can start to see these deep connections and they like to use that word like deep connections algorithmic du right what does that even mean right okay and that's really powerful this is the most important uh aspect of that so they said that um our firsthand experience of and frustration with the convergence of optimized forms of reference counting and tracing collectors led directly to a deeper study of the algorithms in the hope of of finding fundamental similarities that seem to be appearing in practice so they were like okay here's a hypothesis they're similar and then they proved that they are right this is not this is someone's opinion right okay if you believe in you know formal mathematics and proofs you'll I consider this truth it is a it is a fact that these algorithms are duels of each other and that's not refutable unless another proof comes out that refutes that right okay not so I like this I like this quote and then so here's the here's this is like the this is like the up really late smoking dope version where they're like tracing operates on live objects or matter while reference counting operates on dead objects or antimatter for every operation performed by the tracing collector there is a precisely corresponding anti- operation performed by the reference calendar collector who dude as a do right okay so then so so all of that all of that is Gospel right now we can re look at that that table that I showed you that compares the naive implementations of reference counting and tracing and here's the like the 21st century version um tracing and reference counting have uh starting points right uh in tracing you start from the roots and in reference counting you start from the anti- roots and the graph last what's that say what an anti-root is yeah so so I can I can um yeah so in reference counting the idea is that you start with an overestimation of the number of references that are that exist to a given area in memory and you decrement them until they get down to the true Count and then once you know that true Count you know whether or not you actually need need that area of memory hanging around right so you are like starting with what you don't need and figuring out what you need from what you don't need and that's why it's hard to explain sort of because kind I haven't read it a few times but you know the forward from The Roots thing is like it's an implicit component of Mark and algorithms right that's always how they work you walk through the Heap and you're amusing you amusing you amusing you and then you know all right so if you have like I said if you have 10 marbles right and the algorithm the program that you're running is using one two and three right you just mark one mark two and Mark three and then during the sweep phase right you you know that there's 10 so you go through Z through nine and you say am I using you yes am I using you yes am I using you yes am I using you no no no no no no no I don't need this area I can allocate from this area right so in tracing you start from what is known to be being used and reference counting you start from you know what's left of that right um that's as good as I'm going to do right now so um in object reversal uh and tracing you trace what's live and in reference counting you trace what's dead the initial reference count in tracing is low and the initial reference count in reference counting is high oh [ __ ] I got that part right okay um and in reference count Rec construction you add to that low number and so you get to the accurate number and in uh reference count reconstruction on the reference counting side you subtract ract from that over estimate until you get to the actual estimate and then in uh and then this last line which we didn't really discuss refers to those specific optimizations that tend to be applied where in the extra iteration the extra work that you need to do because there's always extra work that needs to be done uh in the in tracing algorithms that's during that sweep phase where you actually do that deallocation and in reference counting they call something called trial deltion which is basically a different formulation of that idea I don't know I kind of bailed on the slide a little bit but that's all right okay so another awesome contribution of these paper is these awesome diagrams okay and these are the really simple ones right but okay if you just look at these four whatever they are right they're four things okay they look really similar to each other right okay they're really simple um on the left the left bars are the roots or the anti roots in a in a given algorithm right and C stands for counting and T stands for tracing so in pure in pure tracing you use tracing to count from the roots to the Heap and also within the Heap and in pure reference counting you use counting to keep track of what's going from the anti- roots to the Heap and then also from within the Heap right and then the next line uh is is that uh is that first level of optimization where the first thing you will do to optimize your tracing algorithm is to uh use counting to keep track of the um what's what's being referred to from the roots to the Heap and then use tracing within the Heap and then the first uh optimization that you will tend to do to reference counting algorithms is to use tracing to keep track of what's from going being referred to from the anti roots to the Heap and then use counting within that heat right so they did all of that work and all of that formal basis just to be able to sort of graphically depict that you just pull from the other side in order to optimize the particular algorithm that you started with and they characterize some very complex algorithms using this system and those of you who have read the paper or started reading the paper if you just flip through you'll see that even the most complicated you know distributed garbage collection algorithms whatever it is can be expressed using these kinds of diagrams okay so just a little bit more about why I love it um and then I'm going to finish up so I love this paper because it emphasizes tradeoffs not not garbage collection tradeoffs but it emphasizes tradeoffs just in general it says that in order to choose the right garbage collector you need need to think about the workload that your application uh what it's doing right and they give some really interesting examples where they say that you know they they talk about for example some some optimizations to reference counting that would typically be a terrible idea unless right you were working with a I think it's like a log log structured file system right so if you know if the allocation and deallocation that you're doing has to be written to dis right each time you do it that would probably significantly change the picture of which algorithm you would choose right so you're right I don't know if that makes much sense to everyone but like in other words through this framework they can show that what matters is what kind of work your program is doing not like what is the fashionable algorithm to use or which one you have heard is the right one to use the right one to use is the one that applies to your workload and that's I think something not only in garbage collection but in general it's really easy to overlook as Engineers you know you just want to I don't know what you want to do you don't want to think about it you want to do this or do that or use an algorithm just borrow from someone and all that it's great but when it comes down to it what you really need to do is consider the space time trade-offs and whatever it is that you're implementing or choosing to use it also specifies areas of focus for design um it goes through um it goes through a bunch of properties where you know in reality you're not choosing between reference counting and tracing you're choosing between whether or not you're you will partition your HEAP or you won't and you're choosing between you know do you need things to be fast or do you need them to take up a small amount of space there are other things that you're actually considering when you're choosing which garbage flesh and algorithm will be appropriate for your workload and finally it's just a really neat and novel paper where two very different kinds of algorithms are shown to be very closely related to each other in a way that really just it really just like kind of blew my mind the first time that I really understood what these uh authors were communicating where you can take you can use math as a sort of intermediate representation of these code algorithms and then you know once you have these and once you have this formula that uh which you can use to express the trade-offs that are inherent in those choices that you can make intelligent scientific decisions about that implementation and that's something that is very hard to do and like I said I feel like that kind of insight is really uh As Good As It Gets uh in computer science um and that's not that's you know that's not a derogatory thing to say um Okay cool so we can I think we can have a little hopefully have a little bit of discussion now I've been speaking for over 44 minutes so here's here's some some thoughts some potential discussion points maybe I'll just go drink more beer those Concepts fine with me too um so are there other algorithmic DS can anyone think of anything that works in that way yeah so I think I think that um vocabulary comes from optimization um because for every you call like your optimization problem you come up up with is called the Primal problem and then there's a corresponding dual problem so one of them the Primal problem is like you know what do I buy to SP to get the most value while spending my Target and the Dual problem is like you know what do I how much can I get for my money how do I how do I you know fit things there's a there's a whole there's a very like rigorous way you can switch between the two formulations of the problem and there's a relative bound where when you solve one that tells you a bound on the other okay cool did everyone hear that so it comes from optimization comes from optimization theory is that is that a way to I toer for you to speak about is that what I'm heing I'd love to see you have any references for that they don't they don't cite anything specific to that language um search for the word Primal duel Primal duel Primal duel okay so this is one of those scenarios where like you know my lack of Academia is showing and that's good I'm comfortable with that so true of every graduate student ever have some old dude who's like no yeah here I have I have I I have an idea I don't I don't think this is this does definitely not fit um your case but one one one framework that I've sort of thought about in similar contexts um and if you read the blog post that I wrote about this I think I mentioned at the end one thing that I like to think about in a similar context is like the relationship between relationship between functional programming and object-oriented programming right where they're not algorithmic RS of each other in any sense right but if you take one and you take the other right and you know there's a whole bunch of people that think they're inherently different right and and then you read like The Art of the Met meta object protocol or something like that or you read a more like Brian marrick's functional programming for the objectoriented programmer you see that you can take a purely functional language and and Implement objects in it right or you can or what so we're talk about this more next time yeah okay so so that's so so that so so that's one thing that's that's as much as that's as far as I was like that that made sense to me yeah so this isn't from computer science but I can't help but think that this sounds a lot like and deconstruction where they take like two things that you think are completely opposite and they indicate that they're on a Continuum and then are able to like theoretically draw that out yeah so there's like postmodern theory that has nothing to do with which is my background I have a I have a philosophy I studied philosophy so maybe that's why I like this where you know making abstract Frameworks out of things and then in the in dared sense right deconstruction is this idea deconstruction is this idea that you can just no I mean that's that's really good I like that that's great were you g to say something oh you you wreck my mind with jedo okay so there's in the in the world of real things there is particles and waves okay and frequency analysis versus time series analysis okay could you elaborate on that at all or well is it a particle or is it a way is it a particle or is it a way yes it's supposed to be one or the other but it's both at the same time okay where you observe it from that's good that's great and there are some there are some problems that are solved more easily in the frequency domain versus the time domain and when you're having trouble in the frequency domain you can switch over to the time domain yeah like I try to do that what do you have the fix I have it I can we can talk about it yeah so so we can talk about the details of the fix Point formulation that's that's another thing that's like kind of intense but we can talk about it um we can talk about these tradeoffs partition and traversal and then we can also potentially discuss this automatically to gc's idea where what they say toward the end of the paper is that they have like a sentence on it at the end it's awesome but they're like oh by the way maybe this means that people can actually have automatically uh tuned garbage reflection algorithms and maybe the jbm doesn't have to have you know 7,000 knobs in order to achieve optimization maybe you could start from a certain point and Hint it and tell it hey I might be doing this workload or it can listen to how that workload changes over time and I know there are those things kind of exist they don't really exist um especially not in you know mainstream application right we're talking about uh special Hardware instruction style garbage collection algorithms have some of those properties where they say maybe you could start with one and the garbage collector should just know what to do based on the workload that it's processing okay so yeah any questions or does anyone want to we could talk about the fix Point formulation should I bring that up you want talk about part but I'm a math geek a little bit too so a little bit yeah yeah I think it's really cool I I can show that anyone else have any questions or well yeah maybe this relates to that you mentioned that they use some real mathematics to to show this Duality or whatever is that what you're referring to yeah yeah that's part yeah yeah let's take a look at it okay yeah's let's do that so um here it is this this is proof that I read it right here purple oh you can't see it what the look it's purple know that means I Okay cool so let's see I like that it's name is bacon garbage bacon garbage yeah like that yeah bacon garbage okay so um basically what they do is so let's let's take a look here take a look here this is cool this is like these are two pseudo code implementations uh one of tracing and one of reference cting and you can kind of see similar to similar to that table where they had the same number of rows like they're lined up they look a lot life right don't don't worry about what they say just just squint and it makes sense the same um applies to everything that I'm saying so right here this is cool stuff