JVM Garbage Collection: Algorithms & Shenandoah GC Explained

[00:00:00][Music] hello hi everyone um welcome to jvm roundabout so we're live on our youtube channel um this is our 22nd installment as you can see i'm joined by uh chris and roman tonight um so yeah we're we're obviously excited um for this one um it should be a great one we're gonna be talking about jbm garbage collect um so just um before we start obviously um for anyone who's a regular good to have you again but for anyone new welcome um my name is ben i work for a company called trg so i actually am a recruiter in this space and alongside that i run the event uh to give something back to the community um so we are trying to grow as a community so you'll be able to see we have a twitter handle um if you are putting anything online please just hashtag jbm roundabout that really helps us get more followers more people talking about it um so first up tonight is chris senior engineer company called diff blue who we're collaborating with tonight so um thanks to everyone from deep blue for your efforts tonight and helping to get it organized and then after that roman principal engineer at red hat uh he's also a java champion so we're obviously delighted to have him uh speak for us tonight as well um so what i'll do is i will now hand you over to chris who's going to start um and if you have any questions uh there is a comment section you can put them in there um and we will as long as there's not too many we we should get through them or if there's loads we will have to select some and um others will have to ask chris and roman after on our slack channel so i'll hand over to chris now thanks very much cool uh thank you so if i'm going to speak a little bit today about some general uh guard creation uh algorithms so these are effectively building blocks they're not real production jd map algorithms but they're they're the concepts that are used in most of the the real collection algorithms so what am i going to talk about basically some overviews i'm going to gloss over a lot of the very tedious detail that's involved in these apart from a few things which i find a kind of cute little tricks that are played um and i say these are not about specific real world jvms uh so i'm going to start with a little bit kind of terminology just to make sure we don't have a shared starting point so if i talk about an object i just mean a piece of data in memory now in java that's pretty much going to be an object in the gel sense but it could be any piece of data in memory i will also talk about pointers and references do the same thing they're just the address of some piece of memory um i'll talk about the heap the heap is just a section memory that's used for dynamic allocation so every time you do a new some class in java that's dynamic allocation it will appear on the heap um i will talk a little bit about stacks as well so a stack is just a lasting first out structure that stores the sort of per method local states i think that your local variables return addresses things like that uh i also talk about mutators which is the that's eventually the user program that's the thing that is putting stuff into memory deleting things remember etcetera uh and i'll talk about the allocator which is the thing that gives you a piece of memory so when you say new blah it's the allocator that basically gives you that chunk of memory i'll also talk a little bit about seeing a couple other concepts so one is the the age of an object this is a little bit odd in that when we talk about the age of an object we don't really care about wall clock timing this is this is about how much work has happened um so when we say an object is is a certain age that's the amount of allocation that's been performed memory allocation has been performed between the time the object was created and the time that object becomes dead um it's a slightly confusing concept but just think about it is the gc doesn't care about time it just cares about how much momentum pressure there is uh and then i'll talk about live objects which are an object that could possibly be used at some point in the program's lifetime and i'll talk about dead objects which are an object that can never be used ever again um i'll occasionally mention working sets by that i just mean all the live objects in the program at any instant time in in time um and i all the times mentioned the compiler now for java what i mean there is the jit compiler not the javascript compiler so i'm going to start with just a kind of key driving concept in in garbage tracing that's reachability now god perspective is not a time machine it doesn't know what your program is going to be doing in the future all you know is about is the current state of the program so what it cares about is reachability and that is the idea that if there's anywhere in the program you have a reference to an object then that object is is reachable so it must be considered life because it's always possible that you may use that again in the future the opposite of that is that if if you have no references to an object then it's absolutely impossible for your program to access that object again and therefore it's unreachable and it's dead and it's the unreachable objects that you're trying to find as a gold collector occasionally this gets referred to as liveness as well so it's another sort of interchangeable term to some degree so i'm going to start with what is arguably the simplest uh guard protecting algorithm and that's reference counting i'll work through this fairly fast because it's probably quite familiar to some people especially if you've done any kind of ios programming um okay thank all right um so if you imagine there's some program here um and we have a stack frame for this method that has the local variables x and y on it at the the first line in the program um or in this method you allocate some objects and what happens is you get a pointer in in this variable x on the stack points to somewhat gt memory and we stamp a number on that object which is how many references to those objects there are and this point it's just been created as anyone then next line okay now another that get another object that also gets stamped with a with a reference count and then in this line we've override or added a another reference to y into this field f1 so now this object here gets a reference counter too because it's now got two references into it and then you know maybe maybe we change what y points to some point something else so the reference count this object here goes back down to one because it's lost a reference um and then at some point in the future um in the return statement you'll find that the reference here we've lost the reference to this object so this reference account goes to zero now when adjustments count goes to zero that means there are no more references left in the program to it and it can be deleted so it's quite a kind of simple algorithm in terms of actually methods is how it works uh leftist counseling gc is typically maintain what's called a free list and free list is conceptually effectively just a linked list of pieces of memory that are available for allocation so they're free they're empty um and they can be used for new objects and the allocator will put basically just take the first thing off of that free list that is large enough to hold the object that you're trying to allocate and then when you have a dead object you just link it into the linked list so it's fairly sort of fast operation in that sense lessons accounts do need an extra object uh sorry an extra field in in every object and that field needs to be large enough to hold the maximum number of references that you could possibly have to an object so typically that's going to be effectively one whole word one one whole pointer size and he needs to perform an action every time references are modified and and that's done by what's called a right barrier and right there again is a general concept uh in gc so i'm going to talk a little bit about white barriers here now like i said right there is effectively just a piece of code that is executed every time a reference is updated by that we might mean a reference is added or it's removed or it's overwritten um and generally there's quite close cooperation between the protector and the git compiler so that uh normally you want to kind of inline the right values if you can or in line part of the right barriers for for performance reasons now because you're potentially in lining these everywhere a reference is updated um it's quite important to have white bows to be small and fast because they're going to end up in a lot of pieces of code that are executed a lot of times so you'll typically split them into a fast path and a slow path with the idea that the fast path is effectively a sort of condition gate of do i need to do any work at this reference update and a slow path which is yes i do need to do some work now do the work and then you'll typically do some like inline the fast path but don't inline this low pass so for reference counting what does the the right barrier look like so you have a fast pass um which looks something like this in pseudocode so if you imagine this right there is triggered for trying to write a reference to object into this variable var so the first thing you have to do is check whether the existing value invar is is a null or not if it's not then you need to remove the reference or decrement the reference count for that thing that he currently points to and if that thing has now gone to zero you need to free it otherwise you just overwrite the the variable within the mini value and then you update the reference account for that object that you just created a reference for that's the fast pass so we hope that happened that should be relatively fast in a slow pass you actually have to do some serious work because now you know that this object is dead and you need to collect it so when you do that you actually have to first go through all the references of that object contains to other objects and then effectively do the same as the the right variant and go and decrement the vectors cancel all those things it points to potentially having to go and free those as well and then eventually once you've done that for all the references in this object you then can add it to the free list that effectively is that object and anything it points to collected sort of kind of pros and cons with reference counting um so on the good side uh your gc work is actually kind of interleaved with the user program's work um sometimes that means you can make use of cash locality for performance uh improvements um you don't have sort of stop the world phases where where all your user program work seems to pause for some you know long period of time it's also relatively simple and sort of non-invasive and it can be quite successful on the downside uh you do have to increase your object sizes slightly and if you've got a lot of objects that can add up or if you're in kind of memory constrained situations the allocation routines can be a bit slow there's various kind of ways to manage free lists with sort of various improve performance improvements but in general they're not the fastest way of allocating um it has issues with memory fragmentation which i'll come back to later in the talk it also has kind of unpredictable performance around assignment operations so most programmers kind of expect assignment operations to be relatively constant time um modular whether it's a copy or not but with reference counting if you imagine you do an assignment that removes the last reference to a gigantic tree of objects then that's going to take quite a lot longer time while it goes and collects all those those objects that have now become garbage also the the reference counts actually need to be atomic as well so if you've got a multi-30 system you've got a whole bunch of atomic operations that have to be done to keep those those counts saying but probably the biggest killer is that it doesn't collect cyclic structures so if you imagine you have a a set of objects like this where you've got you know some objects around here and a reference into this object here if you remove that reference then that object's reference count goes down to one and now effectively all these three objects are actually garbage because they're not referenced by anything other than themselves but none of those reference counts ever go back down to zero so they never get collected so how do we deal with cycles um one of the ways we deal with them is what's known as tracing collectors and this is a broad range of different types of garbage collectors and i'm going to go into some examples here in fact all the best examples i'll go through in this talk are tracing collectors so the idea of chasing collectors is the effect you just do a tree walk from some roots which i'll explain in a second and anything that is reachable from those roots is still alive and everything else is dead um so in in java for instance the the roots are effectively your your global variables static fields things like that the stack because that's where your local variables are stored and potentially your cpu registers because your jet compiler may have done optimizations where references to objects are only in cpu registers for some period of time and then never make it back onto the stack for instance um and as i said the rest of the gt algorithms i'll talk about in this talk are all tracing collectors so i'm going to start by talking about an algorithm called mark sweep so if you imagine you have your your heap um in the middle here and you have a set of roots which are pointers into the heap and we've been doing some work and we've filled up our heap so now we need to do some some garbage connectivity so the first thing you have to do is stop the world so stop all the user threads so that while we're doing our gc work it doesn't change underneath our feed and then you do a mark phase and in the marketplace what you do is you look at each of the roots in turn in this case we've got the first food here let me look at this and you stamp that object with a mark to say it's still alive and then for each object filled the reference field within the corner in that object uh you go and mark each of those so this one fill for instance points this object so you mark that the o2 field let's say points to some other objects so you mark that uh that object has another object field oops so yes that object points back to something that's already been milled so we don't have to do any more work on that uh and let's say this final field here is some kind of primitive type so we don't have to do work for that field so at this point we've reached the sort of bottom of the tree walk from this route and everything that is reachable has been marked so you can move to the next route uh in this case we mark that one uh it has two primitive fields so nothing no more work to do there and their references to chase they want the next route do the same thing and then when you've hit the end of all your routes uh you've marked everything that is reachable from those routes and that's the end of the mark phase then you move on to a sweep phase so in a sweep phase you start with a effectively appointed to the first object in the heap and if it's a marked object you unmark it and then you move to the next object if that's an unmarked object again you unmark it move to next object if the next object is on is unmarked then that means it was a dead object it wasn't reached via tracing so you can add that to the free list then you move to next object on the market xlx unmark it x object this is an unmarked one so it goes on three list x objects unmark it and once you've hit the end of the the heap with your pointer you can start the world back up again and the users can carry running at this point you freed the things that were good so how does this kind of work in practice um so it uses a free list uh like reference counting uh in this case you don't actually need the right barrier because we're not tracking pointers as they're modified uh that's true for a stop the world mark sweep like this there are such things as concurrent marks we can algorithms where they don't stop the world um they do need a right barrier but i'm not going to cover that in this talk because they're fairly complicated you also need a little bit of space in objects to to mark them when they're doing the mark phase however you actually only need a single bit and you can kind of steal it most of the time so what do we mean by steel it so as far as gel etcetera said an object is just some kind of blob of memory there's no real structure in that memory um and the jvm also actually adds some of its own kind of invisible headers to objects as well so there might be things like locks and pointers to type information maybe thread ids things like that um and the fields are actually just offsets from the base address of the object so you know the type info in this example is it offset zero the lock is offset four etc now all of the reference fields in there are going to just be pointers and pointers are actually aligned addresses and what we mean by that is that they don't point to any possible byte in memory they typically point to any possible word in memory uh and that means the lower couple of bits of a pointer or reference are always zero so what you can do is you can still some of those bits to mark an object so for instance uh given that the jvm internal header is always at fixed locations we can use some of those those headers so for instance in this example we're going to store a bit out of type info so if you want to mark an object here what you do is you use the type info and you set the the lowest bit of that that reference and then when you want to clear it you just unset it and as long as the jvm doesn't need to access that field between you marking it and you're clearing it it's quite happy so that way you don't actually need to add any more memory space you can just still some bits pros and cons of mark sweep um on a good side you can collect cycling structures because you're doing a tree walk and a trace and you'll always reach everything that's live and if it's not reachable you won't reach it you pretty much have zero overhead in memory in terms of per object you don't need the right barrier the performance is fairly predictable and you don't need sort of atomic operations on the downside allocation is still can be a bit slow because it's free based and you still need to stop the world phase or you need to stop the oil phase rather so during the time you're doing gc no other work is going on you also end up traversing the heat twice at every gc which can be a bit of a performance problem depending on how your caching works so you basically have to traverse it once a marking and then again for sweeping and it's also a problem with memory fragmentation so what do we mean by memory fragmentation so if you imagine a heap like this let's say the program's been running for some time and we've got a mixture of some objects in heat which are in blue and then all the freeze space that we've collected in grey after time you'll find there's a lot of kind of grey holes in amongst your blue so when you want to allocate an object this new one here you suddenly find actually there are no single uh single contiguous piece of gray memory if you remember here that you can fit that into so although you have plenty of free memory in total you can't actually allocate the object you want to allocate and and the more gaps there are the more fragmented it's considered to be so how can we um uh deal with the memory fragmentation issue so one of the ways we do that is what's known as copying collectors also known as moving collectors so i'm just going to run through what's probably the simplest copying collector which is what's known as semi-space for semi-space you notionally split your heap into two halves uh you have a form space and you have a two space and you start off by allocating memory objects in your form space so you have a pointer that's your allocation pointer you create objects and the allocation pointer and then you move the allocation point onto the next piece of freeze space you keep doing this during your allocation from the point along allocation bump the point along and eventually you fill up your heap or that half of the heat i should say and that's the point we need to do as you see so you move your allocation pointer over to the two space again i should say this is a stock world connector so you stop the world and then you move the allocation point over to the t space and then you also add an additional pointer called the scan pointer which again points to the beginning of two space and then like the other tracing connectors you start with your roots and for each root you look at the object that's pointed to and you copy it across to the two space at the allocation point then you bump the allocation pointer you also write into the old location what's known as a forwarding address so i'm going to put that in this header here and that's basically the address of the copy of that object and then you go to your next route and you do the same again so you copied over leave behind a forwarding address and the next route copied over leaving find before the address once you've done see all the the routes i've had you then start looking at the scan pointer in this way yeah uh the scan pointer here and you look at this object here and you follow the references out of that object back into the the bomb space and all of those things you also need to copy over so let's take the first case here so let's say this object field here points to this class this object over here it has a forwarding address which means it's already been copied so all you do is you overwrite that field with the forwarding address which means effectively the point it does that and again you look at the next field in the object and that points to an object that hasn't yet been copied it's got no forwarding address so you copy it over leave them behind avoiding this and you update the field once you've done all the the fills in that object you bump the scan pointer to the next object and again this this particular green object here has two primitive fields so we'll assume there's no work to be done for that and let's say this one here has got two primitive fields no work to be done let's finally get to this object here that has two object fields so you look at each of these and say okay that one points to an object that's already been copied because it's got a folding pointer so you update that filter point to the copy look at the next field that's also already been copied so you update the pointer again and then bump the scan pointer forward at the point that the scan pointer uh meets the allocation pointer that means you trace the entire heap which means everything in the form space is garbage so you flip what's from space into space and start your your program offline again and start the world again and then you do your allocation in the the form space here so nuts and bolts of this the the allocation is is great it's what's known as bump point allocation and that's about the fastest uh method of doing allocation you can get it's small code is fast it can be inlined if you want uh freeing objects is basically free once you figure out what's what's dead you just throw away the entire memory space or literally overwrite it uh you don't need the right barrier um you do need some space uh in the objects to store forwarding address however you only need that space after you've already copied the object so typically what you do is you just reuse any existing field in the old version and overwrite it and then still a mark bit to say this one's been copied but actually you don't need any more space in the object in terms of pros and cons uh you don't need to maintain a free list um so that gives you a win in terms of of allocation speed you have fast one point allocation you don't have memory fragmentation anymore uh and you only traverse the heat once per gc because effectively you use your the your your two space where you're copying objects as your work cue unfortunately you do need twice as much memory as the size of the heap actually kind of twice as much as the size of your working set and basically you copy everything on every gc or everything that's live in a vtc so you if you have objects that hang around for a long time they'll get repeatedly copied to infer between form and two space um so we can deal with the repeated copying you get with what's known as generational collectors uh and this is driven by what's known as the weak generation hypothesis which is an observation by by dave unger in 1984 that most objects die young this actually holds across most types of languages so imperative functional object-oriented uh and the idea of generational duties is that you concentrate your work on the things that are most likely to be dead so the younger objects and this to a life extent devise most sort of modern uh gt algorithms most real world qc algorithms so the basic idea of a generational collector is that you a bit like semi-space you divide your memory into two regions you have a nursery region and you have an old region there are different names for these things but this is the sort of generic name as it were and you do your allocation in the nursery and it's just one point of allocation normally so you do some fantastic and you fill up your nursery at the point that you've filled up your nursery you do a collection just of the nursery and you do the normal thing of trace from the roots copy the things that are live into the old generation and you throw away and it's left in the nursery and then you can do some more allocation and you see another collection once the allocation is filled up the nursery now at this point as well as the routes that are sort of global you also have um routes that are references in the old generation into the nursery so the nursery collections we're only going to collect the nursery not the old generation so anything in the old generation that points to anything in the nursery has to be considered so again copy over anything that's that's either reference from roots or from things in the old generation copy those over and then you start away nursing and then you repeat this of decent collection it's allocation and eventually you get to the point where you filled up both your nursery and your old generation at which point you do a collection of the entire heap uh from the roots and this is a full heap collection of everything including your generation so that you end up with just the live objects in the generation this will be a a slower collection because you're collecting more memory uh the idea is that you'll do lots and lots of nursery collections before you ever have to do a full heat collection so a couple of nuts and bolts again it's one point to allocation which is fast um right barriers are needed this time because you need to somehow notice that there are pointers in the old generation into the nursery so you need to watch for pointers being updated so the white browser for generational collector they're fairly simple again if we have some target object that we want to write a reference to into some memory slots here then what we need to do is check that the target is in the nursery and that the slot is not in the nursery and if that's the case then we need to add this slot into the the roots so that we look at this slot when we do a collection now this is a little bit less than ideal because we're actually doing two branches in in this right barrier which is not great for performance so there's some tricks we can play here if you consider the memory layout of your heap if you lay out your nursery so it's at one end of the heap it doesn't really matter which end i'm going to use the lower end of the heap and if you set your nursery to be a power of two size so in this case two to the nursery bits when those two bits are 12 and you make sure that's aligned on that boundary then effectively the lower 12 bits in this case of the of an address of an object effectively telling you which that i'll cover all the the memory dresses in the nursery so what you can then do in your front your your right barrier is do a bit of bit shifting so that you take the target address in the slot address you effectively slice off a couple of lower bits so we effectively shrink it down to something that points to a region rather than an exact address and then you only have to compare whether the regions are ordered so if you have a if the target region is lower than the slots region then we have to remember that slot because it's across the boundary into the target there's a little bit of um fuzziness here in that this uh saves you a branch you only have to do one branch you do end up adding a few more slots to your uh roots that you ideally need but they're fast to deal with at gc time so it's a trade-off that's worth having because this white barrier we executed a lot um so it's a little trick that gets used quite often so pros and cons um the longest objects are only processed on full heat gcs the nursing pcs are not copied once they've been copied once they'll they'll stay in the old generation until you need to do it full heap your nursing will be smaller than your old generation so your gc pause times are fairly short because you only have to collect the nursery and you concentrate mostly work on the nursery where they're most likely to be dead objects on the downside you need to have a right barrier now so your your points your updates and things have a little bit of attacks on them um and you need some additional structures to track these old to young roots so what about real gcs well most gcs don't actually use one of these algorithms they use some kind of mix and match sort of hybrid approach so you get things like a mark compact collector where you do mark sweep but instead of sweeping you do a copying type collection to to reduce fragmentation or you get things like generational mark sweeps where you use copying from the nursery into the fall into the old generation and then in the full heap you do a marks reap or something like that when you get kind of multi-generational collectors so you have uh like an eden space which is sort of the nursery and then a survivor space which is things that survive the nursery collection and then an old generation which is things that survived multiple gcs so there's normally some kind of hybrid approach like that and that was all i wanted to kind of run through today very fast apology to that do we have any questions i think we have a few on the comments uh let's see so uh yeah you asked the are they runtimes e's reference counting gcs how to be history combat cycling left counts so there are a bunch of um versions of reference accounting that do kind of graph type operations to try and find cycles um reference campaigns work well if you don't generally produce cycles so for instance um most of apple's sdks for both macos and ios for a decent amount of time we're using reference counting for their api level um memory management so their underlying runtime didn't do gc it was automated via the apis surveillance accounting quite often is used in cases like that um let me see um and then listen we have another question here yeah the question should show up now start showing up well do you want me to cool i'm also worth the time and i don't want to come in i think the net the next question was what happens when compressed oops are enabled when when marks are stored cool so i don't actually know the answer to that i'll stop my head um in in the worst case i guess have to uh the jvm would effectively add some extra bits onto the the structures uh that's an implementation detail that yeah honestly i don't know the answer to um in the worst case you add an extra field around the metadata the jvm will always have metadata around objects so yeah cool um i think we will do another question um chris will be available for any questions after um yeah i'll point everyone to our slack group at the end um so we'll go with one more question which um should come up on the screen but i'll start reading it um from desmond ice that you said earlier here we go here we go uh yes yeah that's great yes apologies okay yep cool um chris thanks very much really appreciate it great talk um like i just mentioned to all the viewers um i will point you all in the direction of our slack group at the end um and obviously you can reach out but chris thank you and we'll get roman set up for the next the next presentation um thanks very much okay um roman that's uh hello right now i'm a champion i'll take it away hello thanks chris this was a nice talk um actually a great introduction into what i'm going to do um i want to talk about the shenandoah gc um which is one particular you see in the open jdk um and i will take a little bit deeper than what you've seen so far um so a little overview of what i'm going to talk about um i'll give you a little introduction into the shenandoah gc and then i will talk more about the concurrent evacuation and the concurrent routes and why we are doing all this stuff um [Music] so introduction um shenandoah is a garbage collector in the open jdk it is a concurrent gc so what chris talked about so far um all the collectors um stop the word she sees which means that whenever the uh gc kicks in it needs to stop all the java threads and then do its work and then resume java threads and this can easily take some time you probably remember from like 10 years ago so the dreaded gc process um but even today with large applications this can easily take up to several seconds and the the aim here is to solve this gc pose problem regardless of heap size regardless of tiny hardware or whatever constraint environment you have and shenandoah is also made to be universal in the sense that it has no restrictions on operating systems or hardware-wise or something like this to put this in context um of the other gcs that we have in the open jdk um we have the the simplest gc is probably the serials you see um which is a copying collector it has generations young and old and it does a copying collection in young generation and mark compact in the old generation all of this stuff is um stop the word this is the orange the meaning of the orange boxes here um and it's single threaded this is why it's called serial collector which means that if you have a large heap this is probably going to take a while the improvement on this is the parallel collector which works similar to the serial collector except that it uses several threads that to do that you see works which makes it just a little bit faster or much faster actually so um this is also called the performance gc if you need high throughput and don't care about latency and this is probably it then we have cms the concurrent mark and sweep collector the name says that all it's um mark and sweep collector it's mostly concurrent in the old generation it doesn't care about concurrency in the young generation because it's usually fast enough um problem here is that it tends to fragment the heap in the o generation and at some point especially if you have long running application it's probably fragmenting the heap and causing a full gc and at this point you are back to having a long gc pause here g1 um this stands for garbage first it's um kind of a hybrid model it's a compacting gc it does concurrent marking but compacting and young generation copying is still done while the world is stopped um the idea here is to to manage the amount of work that it does in the compact phase here by picking uh only those regions of the heap that have lots of garbage and hopefully a few live objects so that this doesn't take too long it's kind of a managing solution and then we have those new gcs um shenandoah gc and set you see which are concurrent all concurrent gcs um they do concurrent marking concurrent compacting but so far they are not generational um we have we are working on generational support for shenandoah um but it's not there yet so um how does it look like so we have just i i want to talk about um where these gc process come from and how we uh eliminate him in shenandoah so just to break it up a little bit what what's the the the um reason why we need to stop the gc so we have this marking phase here this is a stop to what you see right so it needs to mark all through the heap it needs to do the evacuation which is also called compacting and it also needs to update all the references and all this stuff is in the classic gc is done in while the world is stopped there's also the little boxes here which is the so-called roots um chris also already mentioned this so we have um the thread stacks and then we have all sorts of other stuff in the roots here which is basically internal to the jvm like jni handles we have code cache where we have all those constants that the compiler compiled into the code we have weak references class loader data and so on all these things need to be scanned and take away the um yeah pause time um overall it's basically um oh of n performance here proportional to the live data size here in those big phases plus the size of the roots that means if we have many threads or threads with large stacks this is going to take time away from your process if you use lots of jni handlers this is going to take time if you have lots of weak references then this is going to take away from your pause time so we need to address all those issues um shenandoah is um solving this in in several ways so we first of all um shenandoah is a regionalized collector which is similar to what g1 is doing so the heap is divided into regions each region is one of those boxes here the blue boxes are regions which have objects allocated and the grey ones are empty regions and um as long as the application is running node 2c is done we don't know what's in them we have lots of objects in them but we don't really know then we stop the word briefly here for some setup of data structures and scanning the roots and then we carry on with the application and while the application is running we do concurrent marking between ctc is marking through the heap here and figuring out which objects are live and which objects are unreachable the outcome is what you see here the green oops sorry the green ones here are um live data the yellow ones is um [Music] regions which are selected for collection so it's basically similar to what g1 does it picks regions with which have little live data and lots of garbage and selects them for further collection later at this point we stop the world again do some shuffling around of data structures and scan the routes for the initial evacuation and then we copy all those live objects that are remaining in those regions into a new one over here at which point those objects become unreachable um then we stop the word again and then we do concurrent updating of references which means that all the objects that previously pointed to uh objects in those regions need to be updated to now point to the new copy that we just made here after we're done with that we can reclaim all those regions here the yellow ones they become free now and are good for further allocation so um this is this this and this and this region this is the overview of how one one cycle of shenandoah collection works um let's start with the concurrent marking actually i don't go into this detail here because um this is already done in g1 gc we do it very similar to what g1 does um if you are interested in that um i suggest you um read this book the garbage collection handbook if you have any interest in in gc or memory management um this is the book to go to so this is a very uh the go-to resource for any information if you want to learn about garbage collection so this is the we use the snapshot at the beginning algorithm this is similar to g1 for concurrent marking so this is concurrent now let's see um i i make the concurrent faces green so let's address the other ones the evacuation phase and the update references phase especially the evacuation because this is interesting how to um move around objects while the application is running um this is the problem that chris described you don't want to move away objects under your feet while you are working with them so this is um what we do here is we copy all reachable objects out of the [Music] live regions that are in the collection set and we adjust all references that pointed to the old copies to now point to the new copies this is relatively easy why the program stopped as chris already explained um problem how to do this while the program is running um let's see um stop the word compaction so this is the the classic variant of this assume you have a couple of references to my object the object here is this one it has a header it has some fields and tgc copies the object while the word is stopped so far so good updates all the references and we then you can reclaim this old object and we're good now if you want to do this concurrently while the java application is running you have a situation like this um so you have your object you have a couple of references pointing into this object um you copy it and then you update all the references and then you have the situation some references point to the out copy some point to the new copy um and then you change something in those objects um and one one thread probably changes in this field here the other thread changes in object the other object here and which one is which now which one is good at this point you have an inconsistency in the heap and this is exactly what must not happened according to the java memory model solution here is we need to coordinate um all threads somehow to agree on which object to write to right um how does that work so let's see um first of all each object has a header this header has a very overloaded meaning in the jdk it contains um marking bits it contains pointer to log objects and the h of objects and even the hashcode is encoded there so we add one more overloading there um we put our forwarding pointer there um the meaning is if the object isn't if the header is an ordinary object header then it's not forwarded um if it's forwarded then we set a certain bit which indicates that it's pointing that the rest of the header is pointer to the new location so um what happens now when when we have several threads that want to do some work with the object while um the evacuation is running um we have let's say one thread on the left side one thread on the right side here um the way to go is each of those threads makes its own copy of the object so we have we actually have three or even more copies of the object now um and then each thread tries to update the forwarding pointer of the original object with an atomic compare and swap operation which means that only one of those threats can succeed and all the other threads that try to do the same will fail but will see the um the the pointer of the succeeding threat at which point turns out this one wins and this is the um object the object to write to now um how how to do this in code means um we need a barrier um chris already mentioned right barriers [Music] more generally barriers are snippets of code that the compiler inserts into the let's say the code of your application when you access any object in the heap for example let's consider this simple example here um you have an uh a get field of an of an object this is reading a field out of the object this and the other situation is we have a put field here it's writing a reference to the object here what the compiler would do with this is it would insert a barrier so this one here this uh this in gray is the barrier that shenandoah would insert after an object is loaded so this is not a right barrier it's a load barrier um and it modifies the sphere this load barrier ensures the what we just seen earlier the agreement on which object is which um it actually uh would insert another barrier here for this but this is the the right barrier for this right access because we also need to coordinate for marking but this is not the topic of this talk um i want to show you how this load reference barrier looks like this is inserted after every load so this is what it does it checks if the object that is just loaded if it's in the collection set in the working set of our current collection if it is then it copies the object it tries to atomically update the forwarding pointer of the original object and then if it succeeds we use this v1 otherwise we use whatever the other succeeding threads just gave us and that's it um this is a simplified version the truth was that it's a little bit more complicated for performance reasons but this is the uh conceptual correct version so um this is basically how we do the epic creation this is this is the the very core of the shenandoah algorithm if you want to um it solves the problem of the concurrent evacuation and also of update reference i cannot go into details of this but this is actually quite easy next so this was a big part of the problem the the problem of depending on heap size or the size of the live data set in terms of the pauses you can still have significant pause times that are caused by the roots scanning here usually this is taking just a few milliseconds but if a application uses like many threads it will go to the roof i have seen customer applications that are using like thousands of threads 20 000 threads customers sent me a stackdump that was a zip file that was 17 megabyte in size um so this can go quite often out of control so let's see how we handle this one thing is dj and i hand this here what does this mean um jni handles is everything that yeah jni can give me when you call new global rev new weak global ref um but it also means for for the purposes of this you see stuff like intern strings um synchronizer roots synchronizer roots happens every time you do a synchronized statement then the compiler id the runtime of the jvm will use synchronizer objects and this contributes to the root sides also stuff like jvmti and a few other things why do we need to handle this why the world has stopped a similar problem like when you scan the route um you have if you have concurrent modification during marking or concurrent modifications of those objects during uh evacuation or updating we need to coordinate uh for consistency and the solution is actually the same um [Music] you place barriers there um whenever stores happen on jni handles or load reference barriers when loading from jni handlers um the difference to the ordinary barriers is that this is happening in the run time and in the uh of heap references and not on references that are inside the heap this is the only difference there is a new problem here um this is the concurrent cleaning of weak jni handlers in jni you can have weak references to re-candles to objects which mean that if the referent of the object is unreachable it gets cleared and you can't access it anymore and when you do this concurrently you can have the situation that um it's not cleared yet and the gc is clearing all the references and a java thread could go there and load the object even though it should be unreachable um just pick it out and resurrect it and this must not happen um the solution to this is um what we call the weak lrb the weak load reference barrier which is inserted in for example and i get object field um it works pretty much like the regular load reference barrier but it pretends a null value when the referent is actually unreachable it looks like this basically checking if the object is marked here and if it's not marked then it simply returns now this is all we we are going to need this later again for the week references i will talk about this now so um we handle dj i handles um now weak references are another class of problem which is kind of similar to this but a bit more complicated um also um in traditional gcs this can contribute very significantly to the post times if you have an application with like thousands or millions of weak references which this can make your life not very comfortable with this um what is what does it mean weak reference processing um weak references you probably have used if your java programmer are a concept to um like holden reference to an object but not strongly like usually but instead so called weakly which means that if the referent is otherwise unreachable then you will not see it again you will probably see another value instead so weak reference processing from the point of view of the gc means determine the reachability of the reference of the reference objects clear the unreachable reference and then enqueue the unreachable reference objects into terror reference queue so that the the application can process them for like cleanup of native resources or something we have several types of reference objects in the jvm the ordinary one which happens when it is not explicit is implicit when you have a reference field or array elements is a strong reference um then we have with decreasing reachability soft references which are usually cleared only when they are unreachable and some like certain threshold is reached in terms of memory pressure so if memory is full and you have unreachable soft references they will probably get cleared which is useful for stuff like caches or something like this then we have weak references which are usually always cleared as soon as the object becomes the referent becomes unreachable phantom reference are a special type of reference which are used for cleaner purposes [Music] the referent here is always unacceptable by the java program but the phantom reference will be processed only as soon as the referent becomes properly unreachable there is one other type of reference which you haven't heard about probably it's called the final reference this is an internal um type in the jvm for ensues for implementing finalizers basically finalizers are is a method in java that allows you as a programmer to do certain actions when an object becomes unreachable kind of a destructive concept but not really quite the same so how does it work how would this be handled in a traditional gc i need to hurry up a little bit because i'm running out of time but um let's go this quickly so usually how to do this is um we mark the original sub crop sub graph of the heap by traversing these strong references first this can be done concurrently like like the g1 gc does or the concurrent marking sweep does um and then we but we need to stop as soon as we reach a soft week or phantom reference there and then while the world is stopped um we can determine the reachability of those other parts like look at the weak references and mark through this weekly reachable subgraph and so on so um this needs to happen in this order in several phases um because the reachability um is decreasing from there so everything that is reachable by a weak reference is probably also reachable by a phantom reference and so on i have a little um diagram here which which visualizes this so let's suppose we have gc roots here like um local variables they have strong pointers the strong ones are the black ones here um we determined that this here is strongly reachable by following these references here right it also reaches a weak reference at which point we will stop marking and it holds a reference to this object but this is strongly reachable which means that this will stay alive we have a weak reference we stop here um this holds a reference to a object that is otherwise not reasonable which means this can get become can become cleared and here we have the example how final reference works um those are a little bit special um final reference means this object here has a finalizer and we see it's not reachable by anything else here but itself is referencing it might be referencing a phantom reference the phantom reference must not get cleared before it's really becoming unreachable even by final references so this is why we have this green graph here this can only be determined why the word is stopped green means it's only reachable by a finalizer this hint this here is properly unreachable and can be cleared right away by the phantom reference so um let's see we have a couple um from there we can make a couple of simplifications um to the whole concept of reachability of soft weak and phantom references software references are kind of like they act as like a strong reference for example if the memory pressure threshold is not yet reached it will act as a software as a strong reference or if it's um if we actually are under memory pressure then it acts like a weak reference so this is basically the same as a weak reference except for a couple of additional uh constraints weak weak references get cleared when the referent is not strongly reachable so this doesn't depend on it only depends on the property of strongly a strong reachability here phantom references are basically the same they get cleared when they are not reachable the problem is we have final references which must keep phantom references alive because phantom references must not get cleared as long as they are reachable by a finalizer even though the finalizer may be unreachable by strong references which means overall we need two reachability levels strong for ordinary object graph traversal and finalizable and with this insight we can make the marking of this graph here completely concurrent if you have not one marking bit but two marking bits one marking bit for the strong strongly reachable and one marking bit for finalizable reachable then we can make this marking process completely concurrent by switching um the bit here so if we go come here by marking and strongly which will see a final reference we switch to the other bit and mark the rest here only by the finalizer a bit if we were to have another marking thread later figure out that we have a strong reference like coming from here to there this would be upgraded to strongly reachability okay so we solved this marking problem of weak references but how to clear them um the problem is similar to what we've seen before with jni weekends suppose you have a reference that is um which referent is unreachable um and the application cause reference get on it and it may it would normally return the referend that is otherwise not reachable um but would we resurrect this object which must not happen so the solution is to do the same sort of barrier that we've seen earlier in dj and i we can as pretend that is reference as nile so that we can clear those reference concurrently with the java program so i have the diagram again so this solves the problem of weak references we have two more classes of problems here which is one as one is concurrent class unloading i don't have the time to go into this detail here um just saying that it's already implemented in shenandoah since jdk 14 [Music] and we also have the problem of scanning those threads stacks and local variables concurrently this is also very complicated would take another talk of this size to explain this it's currently worked on in my team and is to be included in jdk 17.

[01:06:24]um with all this together this means that we still have pauses here but they are basically only for bookkeeping purposes inside hcc and the pause time here is constant time everything else happens concurrently with running java threads which should get your post times under one millisecond well under one millisecond even um yeah some concluding words um on availability of shenandoah gcc so um we have don't have any special needs from the operating system which means it's basically working as it is on uh linux macos solarus and windows as far as we know um others if we have other um requirements contact us we should see what can be done um hardware wise chain doors running on intel 64 and 32-bit systems it's running on the new arm 64 systems we have work in progress on arm 32 but it's not done yet um we actually have we know that some uh folks are working on power pc ports it's um work in progress everything else is not supported yet um jdk version wise it's a bit more complicated um the latest release jdk 15 it's in there um the other ones between jdk 15 and jdk 11 they are not supported anymore so if you are there try to upgrade to this they have shenandoah but it's um kind of outdated um we have the jdk 11 which is stable lts um it is in upstream open jdk since jdk 11.0.9 it's you also have a back port of shenandoah and jdk8 it is supported and ready for production but it's not in upstream jdk yet um jdk 16 is just around the corner and we have the a couple of new features in there too um but it's not there yet um yeah context so if you information about shenandoah you will find in this wiki page here that's mentioned or if you have any questions on this mailing list or contact us on twitter uh this is my handle this is alexa shipyard handle which is also contributing to shenandoah um yeah and with this i'm done thanks thank you thanks roman uh thank you to you both um the i'm just looking i don't see any any extra questions in the comments section at the moment um the the link to the slack is in there um so obviously if anyone wants to continue the conversation about what we've heard this evening feel free to do so if you think of anything at a later date that you want to ask obviously roman has just presented us with his contact some contact details there as well um but look i want to firstly thank um thank both speakers obviously um oh i think we might have a question uh yeah there we go um well um kind of we are not evacuating all regions we only evacuate regions that we find enough garbage in so this is it um new memory allocations happen only in empty memory regions and this is actually a typical concurrent you see problem we need to start collecting while we still have enough free memory to actually fulfill the allocations and the evacuations by hcc so this is a yeah a common concurrency problem figure out figuring out when to start to see so yeah cool thank you um unless any other questions come through i just wanted to i was saying uh thank you to you both um for your time and uh your presentations um and to some of the other people from deaf blue who i've been speaking with and putting this together thank you to all of those people as well and to beth who works for trg alongside myself uh who helps us run our events so thanks to everyone that's put this together thank you to everyone that attended um so yeah as as most of you know we we try and run these as often as we can which we're trying to do monthly meet up so keep an eye on the meetup page um on my jumper here it does actually say the roundabouts that's our meet up brand we have seven different meetups so if you go to the roundabouts dot co dot uk um you can see not just about the jvm um but if any of you are interested in javascript devops we do a testing meetup we've got more general agile one that's all in there as well before we go um there is another question roman just i'll put it i'll i'll read it out uh oh here we go yeah when are the empty regions released for all allocations um yeah at the end of the update references phases exactly there is a special case when we figure out that after marking that a region has absolutely no reachable objects in it we can reclaim them immediately which happens more frequently than you would think so yeah you can release you can reclaim a couple of regions right after marking and some more after updating all the references cool um so that's that's it really the the like i said these the slack channel is in the comments section um so you can find the link there um obviously um as i mentioned earlier if you if you do put anything online on your social media or just hashtag jbm roundabout like i said that does help us get the following um to be even bigger um so thank you everyone and uh we will hopefully see you in february the details should be announced very soon um thank you and thanks again chris and roman yeah thank you yeah goodbye bye now okay