Compacting GC in Ruby 2.7 - Aaron Patterson

guys you know what to do [Applause] they're tender laughs we've been waiting for this moment from the very beginning of our community four years ago Aaron Patterson Thunder laughs [Music] really really nervous actually before we start I want to take a selfie with everyone I heard that it's that we're supposed to hug each other here so I want to take a photo of everybody giving a hug so can we do that said okay okay [Music] oh god I'm so nervous [Laughter] all right so first I want to say I want to say thank you so much for having me really it really really means a lot to me and I was I was actually really moved by the pivot rules oh my thing ah there we go I I think that the the pivot rules are the best I think that they are amazing so and and I want to I want to encourage all of you to become a speaker I think like it's really hard for new people to give talks or to get into speaking and I think it's because a lot of people think oh well I don't have anything I don't have anything to teach anybody or I don't know what to say on stage but the thing is every single one of you knows something that somebody else doesn't and you might not know what that thing is but it doesn't really matter just get up on stage and talk about some idea or something that you're working on anything that you do because somebody out there won't know about it and someone will learn something there is somebody out there who is not as experienced as you and you can teach them something so please become a speaker the other thing I really liked about the rules are hugs this is good because I love hugs and I want you to give me a hug so so well not now we'll wait until after the wait we'll wait until the after party to that but yes please please come give me a hug say hello say hello to me so I guess you know this I don't need to say but my name is Aaron Patterson my name on the Internet is tender love and if you don't recognize me in person this is what I look like on the Internet this is my real face here and I have I have a couple cats this one his name is Gorbachev puff-puff thunderhorse the third we call him Gorby I'll tell you why you can ask about his name late if you want this is that her name is SeaTac Airport Facebook YouTube Instagram snapchat I think that's it we call it we call her just SeaTac for short actually I I felt so bad I I introduced my cats and my presentations and at one one one conference there was somebody translating me into sign language and I thought oh man why did I say this name this is so terrible for the sign language people anyway I have I have stickers of my cats so if you'd like a sticker of my cat and come just come ask me like if you don't know what to say if you want to come say something to me you don't know what to say ask me for a sticker I'll give you I'll give you a sticker of my cat so if you want one just come say hi I'll give you one I work for a company called it's a tiny startup called github [Applause] we recently acquired by a late stage a late stage lifestyle business anyway you could say you could say that this is my active job so I'm on the Ruby core team and we're responsible for doing development on the Ruby language itself I started looking through my commit history this year and I found out that this era is actually my tenth year in October it'll be ten years since I've been on the Ruby core team oh I I'm also on the rails core team responsible for developing rails and I decided to look through my history there as well and I found I've been on the core team since 2011 but my first commit was in 2009 so almost I guess it's ten years committing as a committer in eight years as a core team member and Jeremy is the first one that merged my my commit so I I want to talk now I'm telling you about my history a little bit and I'm not doing this to just say like oh I'm great or anything but I I really want to talk to you about why I've been in or how I got involved in the community and why I've been involved for so long and why I've stayed for so long and the first reason is that I really love Ruby I love the Ruby programming language I've actually been doing development work since 1999 was when I got my first programming job I got a job so I got into Ruby in around 2005 because some of my co-workers went to a conference called no fluff just stuff where Dave Thomas was gave a presentation about Ruby and my co-workers brought it back and showed it to me so at that time around 2005 I was a reluctant Java programmer and programming in Ruby felt like a breath of fresh air to me actually before I was a Ruby programmer I was a I was a Perl programmer so Ruby felt really really nice to me the the language was just so easy everything everything just worked the way that I thought it would work when I made a mistake it was easy to tell why I really like the language because the basic patterns of the language were so easy to pick up so you you don't have to learn many rules in order to program in the Ruby programming language it meant that my mental overhead was a lot lower and I'll show you exactly why later I also didn't have to write a lot of boilerplate code I really did not as a Java developer I did not like writing all those getters and setters so I'm gonna show you an example of what I like I googled Java 1 3 because that's what I had to program in at the time so I'm gonna show you an example of programming in Java at that time so this is here's two examples here they're doing the same thing one is Java one is Ruby they're essentially taking two lists of strings and then just calling like two in taun them basically converting them to integers so in Java 1:3 we didn't have generics so you had to pull everything out of a list cast it and then push it back do whatever and push it back onto the list now the funny thing is that this Java example I don't think it actually even works because when you do a parse int it returns an int value and that integer isn't actually an object which means you can't push it on to an ArrayList which only supports objects so this is what I'm talking about when I say mental overhead we're in Ruby everything is an object and you don't need to think about these particular differences you just learn that one rule everything is what an object so I can treat everything that way so here I want to talk a little bit about my first serious Ruby program that I wrote in in 2005 I wanted to see the Lord of the Rings movie the third Lord of the Rings movie was coming out and it came it was being released and they were gonna show all three Lord of the Rings movies in one day and that day it was on my birthday and I was it was also a day early so it was a day early release for the third movie I was really excited about this I wanted to do it or I wanted to go see these movies for my birthday so I went to work and they they were selling they were selling movie tickets online I went to work and I tried to buy the tickets but of the website was crashing and also at the time I was working on a Java app and this Java app took no kidding about 10 minutes to compile so every time I had to make a change or every time I made a change I'd to wait 10 minutes to test it so what I decided to do was during this 10-minute break I would write a ruby program that would try to buy those movie tickets for me and I wrote this program and I even put my actual credit card number into into the Ruby program written to disk in it in a plain text file and so so I wrote the program and what it did was it would it would make a request and I knew what a failure case was so I knew like okay when I get an error the page looks like this I knew if it failed I'll just retry and keep her trying I'll retry and if I get a response that's different I'll just log a message but I'll retry anyway because my thought was that it's probably gonna keep failing but maybe with a different page or something and if I see the log message I can just kind of go take a look and fix it so I ran the program and I was worth doing my normal job and I forgot that it was running and then I looked in the terminal and I saw like oh man there's a whole bunch of log messages oh no something changed so I went to the website and I tried going through the process and it turns out that it had been succeeding over and over and over again so I called the credit card company and I asked my credit card company I asked him like a really awkward question I said hi I wasn't sure how to ask this how how many times have I charged my credit card today and they said oh well you charged it once and I'm like oh wow that's great so then I called the ticketing company because I didn't think me like maybe they didn't actually get the tickets maybe I didn't you know it didn't actually work so I called them and I said hi you know I've been trying to buy tickets online and credit card company says I got charged but I want to make sure that I got I actually got the tickets and the I gave the person my information and the guy the guy on the phone says oh yeah yeah it's right here you you bought two tickets but it looks like we've actually tried to charge your credit card hundreds of times and I was like oh yeah the the website wasn't working so I was just hitting refresh I I don't know I don't know so the moral of this story is I never write in filled with always have some sort of exit anyway so around that like I also love I also love rails and around that time was the same time when DHH made his woops here's a blog video and I I decided to try it out and I fell in love with rails to me had exactly the same features as Ruby it was easy it just worked everything worked the way I thought it was it would work and there was no boilerplate code I really loved that about the framework in the language but there was something more to it than just these specific traits not not just these specific traits about Ruby the language and rails of framework that drew me to the community but actually the community values it was the values of the language and the framework that really resonated me there were my values these values were Ruby and rails were trying to shift all of the burden from the programmer onto the computer like I don't want to do that work I don't want to have to know about whether it's an int or an object the computer should figure that stuff out for me and this is the type of mentality that I wanted to work with I wanted the computers to do like I'm lazy what the computer to do my job come on anyway so this is what I what was important to me was if ting the burden from the developer to the to the computer this is what I wanted to do every day but unfortunately I was a Java programmer at the time but I thought to myself you know I I must write rails I kept thinking to myself I must write rails and this is this is a photo of me from 2006 I looked it up and unfortunately at that time nobody was hiring rails developers it was not a job that existed now two friends of mine two co-workers they quit they quit their jobs and they decided to start a start-up and they decided to do it in rails and I was so unhappy being a Java developer that I decide I was like all right I'm gonna quit my job and join all of you and unfortunately that cost me 25 percent of my salary because unfortunately nobody was writing using rails at the time anyway after I joined this company I knew I had to do I had to do something about this the reason my salary had dropped so much is because nobody there was no competition nobody was hiring rails developers and there weren't any really any rails jobs out there so I decided to get involved with Ruby the language and rails of framework so that I can improve them and try to get make them better and increase their popularity such that we could have more companies so I could go work at a different different job a different better job and get more people involved in the communities writing ruby apps and writing Ruby code so that not just so that I could get a job somewhere else but also so that everyone else could have this feeling that I felt - which was having development be fun so basically the long sword is a long story and very roundabout way of getting to say like I I really want to thank all of you I want to thank all of you for writing rails applications I want to thank you for writing Ruby code because you're the one you're the ones that are help spreading these values and making it so that we can all have jobs and writing code for fun so all right that yes thank you you should give yourself a round of applause good job right more right more Ruby code please so now let lets let's do the technical portion of my presentation which I apologize to you at almost 9:00 p.m. this is a very technical talk but I will do my best to make it easy well I'm trying my best to make it easy so I'm gonna talk to you about a compacting GC for MRI is a patch that I've been working on some code I've been working on and it took me three years to complete it to be honest this presentation is about the most this is this presentation is about the most difficult code I've ever written in my life so I hope that I have distilled it so everyone can understand and if you don't ask please please ask me questions I I don't think I'll get to come to Ukraine very often so take advantage of my time here and ask me stuff please so first off what what is compaction essentially what compaction is is basically taking allocated memory and free memory like say we have a picture of this is our computer memory here we have allocated and free chunks in our memory and we're basically just rearranging them so that they're all next to each other like this and then combining them together so we have just one allocated memory chunk in one free memory chunk and some of you may may remember this it's essentially doing like defragging your hard drive but instead of doing this on a hard drive we're actually doing it in memory so this is this is for those of you that don't know it's exactly what I described it's just only on a hard drive so that is what compaction is but why should we compact what is the benefit of compaction one benefit is that it gives us more efficient memory usage so for example let's say we have memory layout that looks like this but we'd like to allocate something new we want to allocate something down here but it's too wide so it won't fit inside of that free memory area and if we try to allocate over here it's too wide for this one too so we can't we can't fit there and in this case we're essentially out of memory because we can't allocate what we need now if we were to rearrange these such that the free memory was chunked together now we actually have an area wide enough that that chunk that we wanted to allocate we can allocate so we're able to use our we're able to use our memory more efficiently the other advantage is CPU caches now when a program reads memory it has to go through the CPU in order to get that memory has to ask the CPU the CPU will read memory in chunks from your RAM and that chunk will be stored inside of a CPU cache so it's basically a fixed-width amount of memory that's read out of your main system memory now when the program executes it'll try to read it it'll it'll ask the CPU give me the some memory the CPU will read it it goes into the CPU cache and as the program reads it says okay that's good we can read out of here it's fast but now we want to read a different area we have to move to a different section of RAM because we didn't finish our computation so we move over here read that amount of memory and then continue on with our program now unfortunately reading from a different location is much slower than reading from CPU cache if we could read always be reading from a CPU cache our program will be able to run faster and this is where compaction can help us out if we were to rearrange the memory that we needed so that we have allocated chunks all together when we do this read all the data that we need can fit inside of the CPU cache and we don't have to pay the price of moving to a different reading from a different location jumping that jumping around costs us time now this this phenomenon of reading from one section of CPU cache this is what's called good locality because it means that all the data that we need it's local to each other now another another advantage is copy-on-write friendliness at work at github we use a unicorn web server it saves memory by using a copy-on-write technique and compaction can increase the can increase copy-on-write efficiency and what copy and write is is when a let's say we have a parent process whenever the parent process forks a new process it'll create a child process but that child process that child process copies the parents memory but actually it doesn't copy the parents memory what it actually does is it points to the parents memory like this so when you fork a new child you don't double the amount of memory you use because it looks like it's doubled but it's not actually we're just pointing at the parents memory this is called virtual memory now if the child process wants to write to some memory let's say it wants to write to this free chunk down here the operating system will copy that memory from the parent process to the child process such that the child can read from it so essentially it severs that arrow there and copies that section down to the child process now unfortunately the operating system can't copy just the amount of memory you need it'll copy a fixed-width chunk and what that means is it'll it can copy more data than you actually want it to copy so instead of just copying this free memory here it actually might copy the free memory and the allocated memory even though we only wanted to write to the free memory so this means that our child process actually consumes more memory than we really wanted it to now all these problems that I've shown you essentially they're all solved by doing something which is called eliminating fragmentation compaction is the solution for eliminating the problems of fragmentation and again fragmented memory is essentially a memory that looks like this where we have free memory that's interspersed with allocated memory and compaction is just moving it around so that we have allocated memory all next to each other and free memory all next to each other so this is a non non fragmented heap now in Ruby there's actually before we before we actually talk about the compactor itself I want to say that our Ruby program actually has two heaps we can think of it as having two heaps let's say let's imagine the memory that's inside of our computer the total amount so we have system memory here's is our total amount of memory here now when we allocate memory we use the malloc system call that system call asks the operating system for memory when we do that creates something that I like to call the malloc eat this is all the memory we allocate using malloc inside of this is Ruby's object heap so this is where we allocate Ruby objects out of the Ruby object heat so we essentially have two different heaps here than now I'll keep in the Ruby object heap Ruby's object heap is contained inside of the malloc keep and every time we allocate a new Ruby object it comes out of Ruby's heap right here so it'll live in there ideally the Ruby heap would be exactly the same size as the malloc heap but our program will actually allocate data outside of the Ruby heap in the malloc keep itself and I'll give you an easy example of that one example is a string so in this example the Ruby object representing the string is allocated inside of Ruby's object heap but the actual string buffer itself is allocated inside of the malloc heap and this is one reason why the MAL keep and the Ruby heap will never be the same size now the important thing here to remember is that fragmentation that problem we discussed earlier can occur inside of both of these heaps not just Ruby's heap for the mail keep at work we use an allocator called je malloc I recommend using this in production it is safe to use we use it and it is great so go Google this later we're not going to talk about it now just remember je malloc Google for the Ruby heap we use something called GC compact which is the patch I wrote in the subject of the presentation today so let's take a look at how Ruby's heap is built and I don't mean the system memory or the Malachy I mean the Ruby object heap stored inside of those two Ruby's he play out looks something like this Ruby objects are represented by a fixed amount of memory each Ruby object is 40 bytes wide so it's 40 bytes wide and we call those 40 by chunks of slot and each slot can either be empty or filled and later I'm going to introduce a new color called moved we'll call it move but right now we'll just think empty and filled each of these slots are contorted on a contiguous chunk of memory and that contiguous chunk of memory is called a page so this is one page and each page is approximately 16 kilobytes now ruby's object heap is made up of multiple pages so it's consisted of many different pages so we have multiple 16 kilobyte pages and each of these 16 kilobyte pages is allocated using malloc like this now one final thing to know about this is that each slot has a unique address so each one of these slots has one unique address so now we have all the information we need to build our compactor trust me you'll see so let's let's look at the now that we know about this heap layout let's look at the actual algorithm we have the information to build the algorithm the algorithm that I use is called a two-finger compactor and it was originally implemented in 1964 which is a long time ago it originated from Lisp it is not the most efficient compaction scheme but it is very easy and we can talk about why I chose this later it consists of two different steps essentially moving objects and then updating the references we're gonna look at moving objects first and then updating references the algorithm itself works by pointing to different fingers which is why it's called a two-finger compactor on either side of the heap and one of them is called a free pointer and one is called a scan pointer the free pointer moves to the right until it finds a free slot and the scan pointer moves to the left until it finds a full slot so scan scan free scan yes okay once it finds those two once it finds a free slot and a full slot it swaps them like this and then it leaves a forwarding address says okay the object that wasn't 9 at slot 9 it is now at slot 4 so we'll leave a forwarding address there then we repeat the algorithm the free slot free pointer moves forward the scan pointer moves backwards it swaps them and leaves a forwarding address and we repeat this process until the two fingers meet and at this point we have compacted the heap that's it it's completely compacted we have one we have one more step and that step is updating references let's say we have a heap that looks like this this is before compaction after compaction it's going to look something like this in order to update the references what we do is we essentially walk through each object asking for its references and updating them so a points at six six did not move so we move on be points at nine nine move to four so we update its reference to point of four C points at five our points at eight but it now needs to point at five so we move it and then continue on with this process through each object in the heap llego arrow yes until we're done now all of our references are updated we've compacted the heap and updated references once everything is done we just changed these two moved slots back to free slots and that's it we've done it so I'm gonna show you this algorithm in Ruby in Ruby code I translated it to Ruby code because I wrote it all in C and this is a ruby meetup Ruby conference and I think we might like reading Roo Roo be better than C so this is what the algorithm looks like and I don't need you to read it too closely essentially it's just what I describe to you in English essentially what we do is we check to see have these two pointers nut and if they haven't we go through our loop here we copy and leave a forwarding address and then down here we check okay now we need to move the move the free free pointer and then here we retreat the scan pointer and then we check to see if they're met we just repeat this process so that's it now this is what the reference updating code looks like again in Ruby it would look something like this all we do is iterate over each slot in the heap looking at its references and then updating the references for that particular slot now looking at this code it seems like updating references is actually the easiest part of this process but in fact it's actually the most difficult and the issue is right here this method slot reference is hiding a whole lot of complexity and to give you an idea what that complexity is we have to know like how do hashes hold references how to arrays hold references how do objects-- hold references how to regular expressions hold references how to ranges hold references all the different types of objects that are in a ruby program we need to know how they hold references and how to update them so I'm going to show you the actual reference updating code this is the actual reference updating code hold on a sec this is this isn't all of it I will show you all of it that is all of it now I didn't count I didn't count exactly but I estimate that the reference updating code is approximately 80% of the code that I had to write so because it's so difficult and complex I want to talk a little bit about it that I want to talk about some of the challenges behind that essentially it's supporting C extensions is one of the hardest parts I came up with a way to support or a scheme for supporting C extensions this has been the blocker for ever why this has never been implemented is essentially how do we support C extensions I came up with a way to do it that I don't think anybody else had come up before with before and I'm gonna introduce to you now and we'll talk about how it works so as I said the most difficult thing about updating references is figuring out where those references are stored for example we can read the implementation of an array like let's say you and I tonight all of us together we are ruby core developers we're on we're all on the Ruby core team all of us and we're implementing this patch all of us we can go look at the implementation of array and we can read the code and understand how arrays store as references to other objects we know that it points at a buffer and that buffer points at a bunch of other objects so since we know that we can say when it in the compaction scheme we can say okay that we know it's an array we know how to update its references we'll go do that we can do the same thing for hashes we can go look at the implementation of a hash we know that a hash points at some values it also points at some keys and we can update all of those locations and we can repeat this process for all type strings classes modules everything we can go all of us on the Ruby core team all of us we can go read that code and fix it so the GC can update all these known types these are known types because they're all known to us but this asks begs a question like what is if we have known types these known types are implemented by Ruby what about unknown types what are those unknown types I consider those to be types implemented in C and I'm gonna give you a concrete example of an issue we ran into at work at work we use a yeah Joel as our JSON parser and from this code this is a C extension and this this is the main struct of the C extension it can actually store two Ruby objects in that struct right here this this way like the way that it's used at runtime is will actually malloc this malloc this struct then we have a ruby object allocated out of the Ruby heap so the malecon is stored in the malloc heap and the Ruby one is stored in the Ruby heap the Ruby object points at the Malick's one then that Mallett one points at two different other Ruby objects the Builder stack and the parse complete stack and we don't really care what those are we just know that it has those references now the GC doesn't know anything about this type so it doesn't know anything about this struct at all so it doesn't know how to update these references so if the compactor decides to move one of these objects and the struct would point at the wrong location in the whole program would crash I'm using all of the keynote all the keynote stuff so how do we fix this how do we prevent this type of crash the secret in dealing with this is to use the yeah jewel marking function the marking function all C extensions have to mark the references and the way that they mark the references they have to keep those references alive and the way they keep them alive is by using the RBG c mark function so when an object is passed to our b GC mark we essentially don't let it move anymore so we say anything marked with our b GC mark cannot move so I'll give you an example here we have a heap that looks like this with a yeah L object that points at two unknown objects so here's our Ruby code up here and then we have an array object that points at two strings for example during the mark phase we introduce what's called a pin bit table and during the mark phase when our BGC mark gets called it pins those things so yeah Joel uses our BGC mark and we pin those two we say okay they can't move anymore now the Ruby array won't use our BGC market uses a different function called GC mark no pin and these are private functions and since they use those uses those functions those do not get a pin bit set now during compaction we say we do exactly the same algorithm we did before except that we scan for a free where we look for a free and then when we get to the scan point the scan and pointer says well that's pinned we can't move it and then just moves on so it swaps those two and does exactly the same algorithm it just says oh if there's a pin bit we won't move it okay yes now during reference updating it looks at the the reference updater looks at yeah Allen it doesn't know how to update references but that's fine because we know that none of them moved so it's safe it does know how to update arrays so it fixes those and then moves on with the rest of the heap is normal sorry I'm so I'm so proud of my keynote [Laughter] okay so known types known types use GC mark know pin and this is an internal function to Ruby and it doesn't pin those objects where unknown types this is a public function will use our BGC mark and it will pin those things so another thing that i introduced is a way to allow movement inside of C extensions to do this I introduced three different concepts compaction callback an open marking and a new location function so the GC can't update a C extension but a C extension can update itself so the yeah L extension knows what its own internals the C extent GC doesn't know yeah JAL's internals but yeah jewel does I can do it the C extension can update itself so what we're gonna do now is a quick walkthrough of how to update the yeah L extension so that it supports compaction before compaction before we add compaction support we have to declare mark functions a mark function and a sweep function so these get called when the GC marks and freeze we register these two these two callbacks essentially what I introduced is a third a third callback where we say okay now we have a compaction callback as well and this compaction callback will get called every time the GC compacts next we need to update the marking function where we say rather than calling our b GC mark we call our b GC mark nope in so this says hey mark this reference but don't pin it finally the last step is we need to update the compaction callback so that it gets the new location of that object so this function RB GC location will give us the new location of the object if it moved now I want to show one known issue there's actually one known issue with this this whole scheme up until now everything that seemed great but there is actually one issue that's kind of annoying so let's let's look at some Ruby objects let's say we have three different Ruby objects one implemented in Ruby one implemented in C and the third one we don't care either one doesn't matter let's say you're a C extension author and you have a ruby object and it points at this third object you have a ruby object air points at this one and you have a c object and it points at this other one now you know that the Ruby object will mark this third one so you think ah I don't need to mark it from C so I will not mark it I will mark this one it's automatic this one's automatically marked and I know that it's automatically marked so I'm not gonna mark it here I just won't do it I am a lazy developer I'm a lazy and not good developer so what will happen during compaction in this case in this case since the object wasn't marked via our VGC mark the compactor will think it's okay to move so it'll move it like this during compaction and then during reference updating it'll update the Ruby AAB because it knows how to update those references but it won't update the see object because it doesn't know about those references so we change it to a free when the program executes it blows up because we have a bad pointer now maybe this isn't common this may not be a common case I did find it in three different places one is here in the Ruby VM instructions not going to go to in depth into how this particular thing works but essentially it's that same object set up just kind of twist it a little bit now I was able to fix this particular issue by introducing a patch called direct marking which is shipped in Ruby 2.6 and essentially what it does is it eliminates that third Ruby object so all Ruby objects are marked directly from instruction sequences so this means those objects won't move anymore the other side benefit of this is it means that your programs will actually consume less memory we found about a 3% memory reduction in production when we used Ruby 2 point 6 so that that fixes this this particular issue the other one I found in JSON the JSON gem does exactly this object setup so I fixed that one unfortunately a neat thing that you can do is since these references are held in Ruby you can write a ruby program to cut the reference so I can cut that reference using a pure Ruby program now that pure Ruby program might be a weird ruby program but you can do it and if you do that the garbage collector will run and it will get rid of that object and then the program blows up so I'll give you I'll give you an example yeah look at that terrible slide so here's our problem code what happened was we say okay the JSON JSON gem says give me the internal constant na n and it assigns it to a global and it never marks it so what I did was I said okay I will remove the na n constant run the GC and then the program will crash so this is this cuts the reference right there and crashes the program the fix is actually super easy we just say hey go mark these object it's fine found exactly the same issue in the message pack gem and I was able to write a peer Ruby program that would cut the reference and of course make the whole thing blow up but the idea is that pure Ruby programs should not crash so I was able to write a write an issue saying hey I wrote a pure ruby program using message pack I know it's a weird program but it's egg V is the process so you should consider this a bug and fortunately I was able to convince the authors and they agreed so we fixed it but now this is kind of a long story but what this really boils down to is one very simple rule for us is that for us C extension writers is if you hold a reference you must mark the reference that's it it's one simple rule if you hold a reference mark the reference now I'll give you an even easier rule very easy and that is to don't write C code if you don't write C code if you just write Ruby code you don't need to worry about any of this all right so I want to go through one more challenge and that's an object ID this is an annoying challenge so a theme throughout these slides is that the overall theme is that having direct access to a ruby object prevents the object from moving that is the overarching theme if you know where it is in memory we can't really move it so direct AXA direct memory access prevents moving generally speaking so one example this this you may not know this but one example of direct memory access is actually the actually from object ID it's based on the location so if you call object ID in the one slot it'll return one and on two it'll return two and on nine it'll return nine okay look if you call object ID in your actual Ruby program it's kind of obfuscated but that number you get back is actually based on the location in memory now the question is if I move this Ruby object what she shouldn't have and the answer is it depends so I'll give you an example let's say we have an object ID after we move so we run this code allocation for we compact the heap it moves to one now when you call object ID the number you get back as one and it makes sense because you didn't see it when it was in slot four you didn't know so let's do another example oh we create a new object it goes in for we access the object ID it returns for we compact the heap it moves to one what should this be well we need to we have to remember what that object ID was because all of us expect it to stay the same so in order to do that I introduced at a global hash of scene object IDs this is essentially the implementation but written in Ruby I wrote it in C this is the Ruby translation so we look at the memory location and we store off the one that you saw then we can return it so in this example again I'll show you we move we allocated in for here we store it into a table at four we saw the object ID was four so we compact moves to 1 and then we update the table so we know the object in one is has an object ID of four so we returned 4 here so everything works now let's do any more an even more annoying example create a new object we access the object ID as usual we compact the object ID remains the same everything is good but then we allocate a new object ID and that object ID is in 4 what's at that object ID B it's a very annoying problem so what this is is we had we essentially have a collision and in this case what I did is I said ok if you've seen if we've seen this we'll just increment by 1 and if you haven't just keep doing that until we find one that hasn't been seen before so in the in this case we'll say ok we do the same same thing here allocated for compact it moves one points at four we allocate a new object that goes in four and then this one will now be 5 so we incremented by one now of course we also have to clean this up in the GCC because when the object gets freed we have to clean up that table this is the code for cleaning up the table so in short don't use object ID actually go ahead and use it it's fine I'm not telling don't go out and like don't go out and rewrite everything to not use it I mean if you're using it in production code you probably shouldn't be do use something else you can but you know just in general try not to use it that much but it's okay like don't don't run out and change your code so let's take a look at the actual impact we studied what the memory layout looks like at the beginning of the presentation and I want to show you a visualization this is a basic rails application this is what the memory looks like the heap looks like for a basic rails application and each column in this image is a page that we talked about it's a page and each dot in that page is a slot so it represents a Ruby object each red dot is a ruby object that cannot move it's pinned each black dot is a ruby object that can move and each white dot is free space so we can see from this that our heap is very fragmented we have a lot of free space interspersed among our allocated objects now after we run the compactor it looks like this so it's kind of hard to tell but it actually got skinnier which means we were able to eliminate some pages and you can also see that we don't have we don't have all those free slots everywhere so I'm gonna show you one more example and this is on the github application the top column or the top one is before compaction and the bottom one is after compaction and it's very large but we can see an impact and I'll show you this is this isn't the full heap here is the full this is the full thing so you can see that it does actually compact things over to the side so I want to talk a little bit about future plans and then we'll end this first off I want to do some performance improvements to this patch right now it is very very inefficient it goes through four different steps those four steps are a full GC moves all the objects updates references then does a full GC again I think we can eliminate this last GC I don't think that's necessary and I also think it may be possible to eliminate the full GC at the beginning essentially what we would do is just say after a major GC has occurred then we'll do the compaction so we can reduce it to two steps another thing I'd like to do is implement a sliding compactor and essentially the difference between a sliding compactor and a and a two-finger compactor is that rather than doing swaps we essentially just slide everything down like this everything gets slid down like that now the reason I want to do this is because it has a couple advantages over a two-finger compactor first off it has better locality so for example like the the two-finger compactor it means that your objects will end up in random locations through your memory it'll be compacted but the location is random so for example let's say you allocated an array and that array has a bunch of objects in it those objects could end up scattered everywhere where a sliding compactor will slide all those together and hopefully get us better locality the other advantage is it supports variable widths so we said earlier each Ruby object is only 40 bytes wide and the two-finger compactor it depends on that fact it depends on the the fact that it's a fixed width a sliding compactor does not depend on that at all so we can get rid of that requirement and what that means is we can another thing I want to implement is variable width allocation if I'm able to implement variable width allocation what that means is we can eliminate their nests the requirement of things like je malloc so that is the end of my presentation you can go there and see the actual bug and it is finally merged thank you so much for having me it is an honor to be here and if you have questions wait clap and then questions all right clap [Applause] questions that's a good question now first thought to two issues the the patch that I showed the patch that I gave or a showed here only impacts the Ruby heap it doesn't impact the Mallik heap and the the performance of the Malik heap is different than the performance of the Ruby Heba so I guess the answer is kind of nuanced yes it will eliminate it will eliminate those Ruby pages but typically when that occurs that that type of thing occurs it's actually to do with the system's malloc we've seen that in production as well which is why we switched to je malloc and JE malloc will release back to the operating system more efficiently so the answer is yes but also also another thing is I guess I didn't Oh two gigs okay so another another thing I failed to mention here is that this is I should have put this in the things I want to do part but this is a manual compactor you have to specifically say GC doc compact the next step is to make it automatic but since it's so efficient in since it's so inefficient right now I don't want it to be automatic thank you right so so two things is first off I wanted to make sure that as many as many objects could move as possible second there are a lot of things actually there's three reasons second there are a lot of things that use object ID but you don't know it for example hash keys hash keys we'll use object ID so it means that a bunch of hash keys could get pinned I found one weird thing is calling like what was a to I on a string will actually look at the object ID and there's a reason for it but it's just annoying it's like you you wouldn't even know in your code that's happening so a lot more objects could get pinned than I wanted and the third reason is I forgot what the third reason well it's ah the third reason the third reason is that the the pin bits are ephemeral they only happen on mark so calling object ID wouldn't keep the pin bit around forever right so that's why basically implementation implementation details make it hard so doing this annoying stuff was a win for all cases even though I had to write some annoying code I should have had I should have had a actually actually we're talking about so another thing I'm gonna do is change it to a global ID that just increments forever and not based off memory at all yes thank you thank you sure so we use it in production the place that we use it it's manual you have to trigger it yourself so what we do at work is we do it right before Unicorn forks so basically back at the let's find my slides here let's see way back at the beginning of my presentation here so we use it for copy and write performance essentially what it means is we say like okay at this point before we fork before we actually fork to a child process we'll compact all of these together so that when the child process does get created all the free slots are together and we copy as little memory as possible down to the child process so we we try to share as much memory as possible you'll see with you'll see with web server forking web servers like unicorn that the amount of memory will actually grow and then plateau at a certain point and this reduces the height of the plateau how about it does that answer your question okay [Music] [Music] those are extremely good extremely painful question nobody reviewed okay like I'm just gonna be I'll be I'll be honest with you the patches I think the patches may be like 3,000 Lian 3,000 lines long and unfortunately like I really really really really really wanted somebody to review it because it was so complicated that I was sure I got something wrong right so I like we had been testing it for a while at work and the way that the way that we test it is we would just try it and see if it crashed and if it didn't crash then were we're doing pretty good so I submitted that was at that point I thought okay well I'll submit I'll submit the patch now but one one thing is that I gave I gave these caveats in my presentation the the let's find it here or was it known issue so there's known issue stuff I made the patch I made the patch I submitted it and I knew it was long and I was really really hoping someone would review it and I thought for sure so I gave this presentation in Japan though I gave it in Japanese because I thought for sure that this known this known issue would be a blocker like we wouldn't be able to merge the patch because of this because of this issue and I thought for sure I would have to convince the rest of the core team like hey this this is correct we need to do this people need to mark the references it's their bug not ours so I submitted I submitted the patch and within I don't know 48 hours Matz responded was like yeah good go for like it's fine and I thought I thought I had like a couple more months to work on it so I was like okay does anyone else like any everyone else ok with this and nobody responded and like koe Ichi he's the VM author he was like oh so can you commit this now please and I'm like fine so I commit it and it breaks all the tests nobody reviewed it nobody literally nobody reviewed it so like it was it was breaking test and I was just really really trying to fix them so it was insanely stressful it was very stressful and I think the problem the problem with this particular thing is that this particular this particular feature is the thing I talked about earlier trying to find references for everything it's so complicated and you have to do it you can't do it incrementally it has to be everything if you don't do everything it will break and because of that the patch got very long and of course nobody wants to nobody reads long patches it's just a fact right like you have to keep your patches short so that people will read it and actually review the code so the that is the long answer is that nobody nobody reviewed the patch as for testing I wrote some tests for it and the tests when we ran the tests I could run the test locally and it was fine but when they went up to the CI it would crash the CI so basically we would just I would cut the errors on the CI and just keep trying to fix them and ruby's CI is different than most CIS it runs all the tests on many different architectures but you'll know like a lot of when you submit a pull request typically the CI runs your test once right and then you gives you a green check or whatever the problem with the doing GC work is that garbage collectors are inherently random and that means that the bugs that come up are random so that means if you get a checkmark like you could get a checkmark green checkmark like 99% of the time but that 1% it's important you have to fix a hundred percent right so you can't just run the test once so Ruby's CI runs the test constantly over and over and over and over just constantly so I submitted the patch and it started breaking the builds but it would break like 1% of the builds but that's still like a bunch of messages in our slack channel like yelling at me so finally finally the other day literally the other day like finally we sat down and reviewed it reviewed it and Koichi finally understood the algorithm and we've got all most of the bugs fixed basically at this point so it was not an easy or fun process I will say that I don't think it's I wouldn't say that it's difficult to become a ruby core contributor but to do this might take a while so you can get involved fairly easy the C code actually isn't that bad and if you want to be a ruby contributor we actually there's a lot of Ruby or a core contributor there's a lot of code in Ruby that's just written in Ruby so you can check that but yeah to do this it might it might take a while I could not I could not have written this when I started for sure I hope that answers yes yes right so it still has it'll still have benefit for say like if you're using Puma threaded web server you'll still get benefit out of it hopefully from reduced memory overhead because we can eliminate some of those pages since we have compacting pages it means they are compacting compacting the pages means that you'll need fewer pages overall on average so it should save some memory there and when we get the when I change it to a sliding compactor hopefully it will reduce or it'll speed up your program due to increased locality but to be honest like so this is an interesting thing I think I think ruby has really really bad locality to begin with so I'm not sure that we'll actually see any improvements there until so I have like a very long game plan here the it I don't know how technical you want me to get I'm gonna dunk it to get technical just gonna do it so if you have a class a class contains a method table this is just an example of poor locality that method table is a hash you can imagine it as a ruby hash now that ruby hash is allocated the inside of the malloc keep okay it's not allocated as a ruby object there is a ruby object but it points at a at a location in the MAL keep and what that means is that that hash is not stored next to there not stored next to each other and memory they're not contiguous which means when you access that hash it has to jump to different locations so we already have poor locality in the first place so this is the reason why I want to be able to do variable width variable width allocations is so that we can say okay I'm gonna allocate a hash and I'm gonna allocate the actual backing structure of the data structure that will allocate the Ruby object and will allocate the actual structure next to it so we'll get good locality out of that and that should increase performance for things like hash lookups and for method tables and those types of things but for us to get to that point I got to go through all this like it's a major yak shave essentially so hopefully those things will help out threaded web servers but in the short term I would look for lower memory usage [Applause] [Music] you you

Channel: #pivorak Lviv Ruby MeetUp

Views: 4,980

Rating: 5 out of 5

Keywords:

Id: H8iWLoarTZc

Length: 65min 32sec (3932 seconds)

Published: Mon Jun 10 2019

Reddit Comments

[u/BorisBaekkenflaekker]

I'm so happy we have Aaron around!

[u/wild_sloth_formation]

Thanks for sharing!

[u/fxhpstr]

Anyone got a TL;DW?