00:00:04.800
hold on I got to get a couple photos
00:00:10.469
this isn't part of my this isn't part of my presentation time I just need some photos everybody
00:00:23.160
not yet no Friday home right now this is just this is Aaron time right now this
00:00:29.200
is Aaron time you're gonna have to wait for Friday hug though there's a special
00:00:35.949
portion in my presentation for Friday hug so let's wait a second
00:00:41.410
I mean I'm choosing to stay behind the podium because I'm not wearing any pants
00:00:47.519
just I am wearing pants and sturdy you can see okay so the title of my talk
00:00:53.980
more compact to you CNM all right my name is Aaron hello um I am a
00:01:00.420
twenty-something hipster nerd now a 30-something hits you nervous
00:01:08.830
my name is tender love if you don't recognize me in person this is what I look like on the Internet
00:01:14.220
yesterday I was I was very jet-lagged I'm still a little bit jet-lagged but yesterday just this is how I felt
00:01:20.289
yesterday was it's Friday toon year yay Thursday um but today today today today
00:01:27.100
is Friday so let's weekend now now is the time for Friday hugs I
00:01:33.670
want everybody to stand up and I want you to give the Internet a hug with me
00:01:39.570
this is a tradition that I do and I will explain why in a minute okay
00:01:48.240
all right everybody one two three happy bride okay thank you
00:01:59.250
so I do this I do this every Friday a hug the internet the reason I do it is because I work from home and I get kind
00:02:05.800
of lonely so the internet the internet is my water cooler so that's how I say hello everyone I was actually in I was
00:02:13.420
in Japan a couple weeks ago and I decided to go to some retirement homes
00:02:21.160
and do Friday hug there and this is a photo of one of them who hear you're
00:02:28.989
doing Friday hugs there oh I'm just kidding that's not true there's a real
00:02:35.290
photo but I was out there I'm on the Ruby core team in the rails core team and I have a quiz for you today is this
00:02:44.530
Ruby or rail I work for a company called
00:02:55.290
github I don't know if you've heard of it this is a small company I work for it
00:03:02.170
is I have to I have to make this a joke at every conference it is the only legit
00:03:07.900
company I've ever worked for so this is this is not if you thank you
00:03:14.110
thank you this is not to be confused with NASA's presentation where he was showing off widget but I thought it was
00:03:23.110
kind of cool because he posted the link to and it was on github so it was legit on git
00:03:29.769
but I actually was going around and I well I forked to the project so there is
00:03:35.920
actually two of them so now it's it's two legit and those are two legit on on
00:03:41.410
git yes those of you grew up in the 80s know
00:03:51.920
what I'm talking about all right so anyway I love you can get but I will not force push it on you so I
00:04:00.350
work for I work for github as a Ruby and rails developer and what I mean by that
00:04:06.710
is I actually work on Ruby and rails for github so fortunately github allows me
00:04:11.960
to do open source development as my as my full-time job though I have recently become mister manager but I still do
00:04:19.760
open source development and mr. managing as well so anyway I get to work on open
00:04:25.550
source code all day and I just want to say like you know github loves open source and I am extremely grateful that
00:04:31.850
they let me do this I have two cats this one is the attacker
00:04:37.460
for Facebook YouTube Instagram I didn't include the Instagram part and chooses
00:04:43.490
to - for short this is the more famous one his name is Gorbachev puff-puff thunderhorse and they or Gorby puffs for
00:04:51.830
short they love each other very much actually that's not true he he hates her and she loves him and they just hate so
00:04:59.450
she always snuggle with him and he gets annoyed and leave but they they're
00:05:04.570
totally experts in getting in my way for example they like to sleep on my keyboard like this and this is like this
00:05:11.180
is a I'm constantly cleaning hair out of my keyboard because of these these cats
00:05:16.780
I'm a mechanical keyboard enthusiast I love mechanical keyboards and I'm
00:05:21.800
going to show you this is my this is my list of my mechanical keyboards I own five or godox keyboards three of them
00:05:28.970
are infinity ergo docks is one of them's in Irbid ah cz and the other ones the original I own two planks and one a tray
00:05:35.030
us and this is very sad this is
00:05:40.630
thousands of dollars of keyboards I
00:05:45.730
shouldn't spend so much money on these things what I do this is my this is my daily driver one this
00:05:51.470
the infinity or godox pencil when I use daily all the other ago does look very
00:05:56.570
similar to this one but this is my daily use one this is my travel keyboard whose
00:06:02.420
what a point cooks like I have this one here with me today so if you want to take a look at that afterwards please come say hello to me and I will show it
00:06:08.750
to you and you can type on it and it's very loud and I want you to enjoy how
00:06:13.880
loud it is ok this is this is the atreya keyboard this is an interesting interesting keyboard as well I like this
00:06:20.960
keyboard a lot but I don't travel with it because this one fits more keys into
00:06:26.690
a smaller space and it's easier to pack although I do love this keyboard I also have a I figured you know I was putting
00:06:33.170
in these slides about my keyboards I figured I may as well show off all the other crap that's on my desk so I also
00:06:40.250
use an L track Mouse as a roller Mouse and that is my cat lying there in the
00:06:46.970
background and the reason I got those Mouse is because well I was having RFI
00:06:52.669
problems but also the cat kept sweeping on my mouse pad so this is the this is a situation I was living with like I could
00:07:00.200
barely use the mouse pad and it would get really bad like this like that and I
00:07:06.800
don't want to move them out of the way because I feel bad but actually reviewed this mouse pad if you go on Amazon I
00:07:13.610
review this Mac and there's like thousands and thousands of comments on
00:07:18.710
my review for this mouse pad because I think the title the mousepad was like it
00:07:23.810
was I really enjoy the 50 25 to 50% of
00:07:28.940
this mouse pad I can use it any time so it is it is a popular popular review on
00:07:35.390
Amazon so that's actually how people know me is this review i use a norman
00:07:41.600
layout this is different than Dvorak Ricordi it's actually based off of qwerty where they moved as few keys as
00:07:50.120
possible but to improve your like improve typing it took me about three
00:07:55.820
weeks to learn that so I I have a completely custom setup and what that means is that I'm totally used on a laptop basically now the reason I
00:08:03.949
did all the stuff is because at one point I had really bad RSI issues like I couldn't type at all I my hands are just
00:08:10.580
hurting all the time and I realized the reason the reason I was getting these pains in my hand is
00:08:17.150
because I wasn't thinking about my work environmental at all like I just would type on whatever and I don't care how I
00:08:23.840
sat or it didn't matter even though I was spending you know however many hours a day at a desk so I never really
00:08:31.069
thought about that much at all and I once I started thinking about it and actually getting into the stuff that's
00:08:37.820
the reason I spent so much money on these keyboards and things was to make sure I didn't get that pain again so
00:08:43.190
what I want to pass on to you today is to think about your work environment and to invest in yourself Don said this
00:08:49.760
earlier yes call back to you so make sure we thinking about your work
00:08:55.250
environment so you don't get injured like I did I you don't want to get injured and then do the stuff you should
00:09:01.760
do it in advance please or so please invest in yourself or treat yourself as I like to say I also love puns but
00:09:14.089
sequel puns make me very upset no sequel
00:09:20.750
puns please take a photo so I want to
00:09:27.380
talk a little bit a little bit about error messages there was an awesome talk yesterday about error messages and I
00:09:33.230
enjoyed I enjoyed that presentation and I want to tell you about my relationship
00:09:38.480
with error messages and that's that I have an incredibly short attention span I like to cure meat and this is this is
00:09:47.449
some of the sausage that I make like I made some sausage at home and I promise it relates to error messages uh so I
00:09:54.740
like to make sausages this is this is a some pancetta that I made I made this I
00:10:00.230
also enjoy making bacon though I couldn't find any photos of it for some reason and I love to make
00:10:11.990
so I love I love to cure meats and stuff and I want to make bacon and when you go
00:10:18.660
buy it at the store it was about $4.99 a pound and okay that's for expensive they
00:10:24.810
can I apologize for the imperial units but it doesn't really matter because I've used the same units throughout so
00:10:29.970
you can figure out the price it's $4.99 per some unit now when I went to make my
00:10:36.690
own bacon I would I had to buy raw pork belly could cure it myself and unfortunately when I went to buy that
00:10:43.500
that ended up being $5.25 per pound and that really bothered me because the raw
00:10:50.610
pork belly was more expensive than the cured pork belly and presumably they had done more more processing on that so it
00:10:57.270
bugs me that I wanted to make my own at home and I wasn't saving any money doing it
00:11:02.550
so I went around to several stores and kept buying these raw pork bellies and
00:11:07.800
they I noticed that they kept coming in the same box and no matter what butcher
00:11:13.680
I went to they would they would put it in the same box and I'm like hmm the interesting so I figured out where the
00:11:19.170
box came from and I found out that it was actually a wholesaler and I found out if I went and bought these pork
00:11:25.290
bellies from the wholesaler they were about two dollars and 25 cents a pound so that was a great discount
00:11:31.220
unfortunately if you want to buy pork bellies from a wholesaler you actually had to have a business license so I
00:11:37.410
needed to incorporate a business and that's where I that's why I started my consulting company adequate industries
00:11:46.990
everything adequately so I started this
00:11:52.940
consulting business so that I could go buy go buy these pork bellies now when I
00:11:58.579
filled out the online forms a cost about I don't know forty dollars to start a business and I was filling out the
00:12:04.370
online forms and like they kept asking you youth questions this is where the short attention span comes in they kept
00:12:10.519
asking me these questions and I didn't know how to answer them so I was just like like I'd saw the forum and give me
00:12:17.300
some errors and my eyes would glaze over because I didn't understand the errors so I'd just fill out keep filling out
00:12:23.300
stuff like putting in stuff and checking stuff until it finally let me through and I'm not quite sure what I put into
00:12:31.610
the form but it let me through and they took the government took my money so I figured I must have done everything
00:12:38.000
right right they they wouldn't take my money unless I did it right right
00:12:45.910
so anyways fast forward like I had the business for maybe three years or so and
00:12:52.130
I get a I get a call one day from from an auditor from the cities and she says
00:12:59.149
to me your business isn't set up correctly and I said oh really
00:13:06.100
and so she explains to me she explained to me what was wrong with the business and I had no idea what she was talking
00:13:12.199
about and I'm like I don't know what I have no idea what you're talking about and she said well yes your business is
00:13:18.320
set up completely wrong and I said well yes but you took my money so why did you take my money if it's all set up wrong
00:13:24.230
and she's like well I don't know but you're going to have to pay some fines and I'm like oh gee and so she says well
00:13:32.870
how much you know how much money have you made with the business and I'm like I don't make any money with the business I omitted the part about pork bellies uh
00:13:41.540
I don't make any money with the business so uh she said okay well I you don't
00:13:49.100
have then you don't have to pay any fines but we we want to close down your business want to close it and I said
00:13:54.920
okay that's fine I don't want to pay any I don't pay anything you can go ahead and close it down so she says okay Gregg closes it down
00:14:00.529
and then about two weeks later I get a letter from the city asking me whether or not I wanted to renew my business so
00:14:09.410
I replied yes in second segment and so I
00:14:15.199
may or may not still have a business not totally sure anyway so that is my my fog
00:14:23.389
of error messages so anyway let's move on a bit I want to say I want to say
00:14:29.389
thank you thank you to the organizers for having me thank you all of you for coming here today I love coming to
00:14:35.990
Singapore was my fourth or fifth time I think it's at this conference I love being here the talks are always amazing
00:14:42.500
I saw some of the best talks this year I've seen so far I learned so much when I'm here and I enjoy talking to the
00:14:49.399
people because there's so many talented engineers here I always leave feeling inspired so thank you all very much
00:15:01.030
oh oh oh are we okay
00:15:16.020
alright so we're going to talk about mark compact GP for MRI this is this is the ongoing development that we're doing
00:15:21.430
it gets github last year I spoke about garbage collection as well and at the
00:15:28.150
end of my talk I proposed a propose a thing called an idea called heat
00:15:34.450
splitting and we were working on that at github and we ended up abandoning the project so this is a unfortunately I am
00:15:42.610
a failure of a software engineer so I'm now a senior software engineer telling
00:15:47.800
you that I am NOT great at programming but anyway we abandon that project for a different project called compaction and
00:15:54.580
that's what I want to talk to you about today I actually introduced compaction a tiny bit last year and said that it was
00:16:00.340
something that was impossible to do with
00:16:05.620
MRI but it turns out I was wrong so I am frequently wrong apparently I as I was
00:16:14.200
about heat splitting so we're going to talk about a compaction this this year now Ruby already has a marking
00:16:23.170
compacting GC and so we're not really going to focus too much on the mark side of this we're going to talk about the
00:16:28.780
compaction side but in order to talk about a compacting garbage collector we actually have to have two things already
00:16:35.080
we need to have objects and we need to have free space we have to have something to compact and we have have to
00:16:41.230
have some place to contact them into so the roadmap is going to be we're going to look at how allocations work then
00:16:48.490
collections and we'll focus on compaction and move into the actual implementation details of compaction and
00:16:55.120
I took a page from Lonnie two o'clock yesterday and reserved the slide for
00:17:00.130
local jokes so if you have any local jokes please tell them to me later so
00:17:07.320
first let's talk about allocation now this is an example of some code that allocates a whole bunch of objects of
00:17:13.690
you but when we execute this code where do those objects go like where do they
00:17:19.459
actually get put and what actually allocates them what I think is interesting is that allocation is
00:17:25.039
actually the garbage collectors responsibility and when you I thought that was always weird when you hear the name garbage collector you think oh it's
00:17:31.490
actually getting rid of any garbage but actually creating garbage is also the garbage collectors job as well so it's
00:17:38.059
not just the garbage collector it is also a garbage producer which is interesting to me and if you look
00:17:45.049
through Ruby's code the source code the the source of all objects comes from a function called RB new obso if you want
00:17:52.399
to dive into the code go look for this go look for this function you can read through it and learn how objects are
00:17:57.889
allocated this function actually searches the memory stays for a new place that put the object and returns
00:18:03.830
that object back to you so the way that Ruby actually divides the computer's
00:18:09.019
memory is we have a heap which is some amount of memory Ruby actually divides that heap into pages so we have many
00:18:15.980
pages then it divides those pages further into objects so each of the pages have objects and whenever we
00:18:21.980
allocate an object we look for a space in one of those pages and if there is space and we put an object there and if
00:18:28.370
there is no space and we'll allocate a new page and then we'll put objects in that in that new page when we have to
00:18:34.549
allocate a new page that's called a slow path allocation so we say give me an object I'm going to if there's no room
00:18:41.360
then the process will actions will allocate a page and then put that object go so it's called a slow path allocation
00:18:46.460
because we have to go through all the work of creating a new page if there is free space that's called a Fastpass
00:18:52.429
allocation it's it's because all we have to do is just return that object back we have we have space for it so when you're
00:18:58.159
running your application in production you want to reduce the number of slow path allocations that you're doing in
00:19:03.230
production and increase the number of fast path allocations so in order to do that you can tweak some of the garbage
00:19:08.929
collector garbage collection knobs and one to tweak is this one called RV GC
00:19:15.559
heap free sloths and this basically says the number of clots that we're going to have available so we tune ours up fairly
00:19:22.639
high at github such that when a request comes through we don't have to do any slow path
00:19:27.910
allocations all of them are fast paths so we keep a large heap these pages are also called arenas if you hear that term
00:19:35.530
it's essentially the same thing just an amount of memory that we reallocate in some place so if we look further into a
00:19:42.100
page layout I said pages are where we store new objects but what actually happens is when we allocate a page that page gets
00:19:48.580
prefilled with a bunch of free slots so we have a bunch of these free free areas
00:19:54.520
in a page and when you allocate objects out the objects get put into those free slots as we're running our program so
00:20:01.750
it'll go through there and allocate put them into those free slots now when it
00:20:08.230
when objects get freed they actually go away from those freeze those slots and they just get turned into free slots
00:20:14.140
again I'll just go away when they're GC they get turned into free slot and then we can reuse those
00:20:19.960
slots later now slots are fixed with which so each object is only 40 bytes wide but that's
00:20:27.940
kind of interesting when you think about it like if a ruby object is only 40 bytes how do we store things like hashes
00:20:34.179
or arrays we know how she's grow larger than 40 bytes though so how does that actually work the way this works is if
00:20:40.960
we have memory like this our computer's memory and we have some page in the memory when we allocate objects in there
00:20:47.710
let's say we have some kind of hash object in there what will do is will allocate what's called an SD hash
00:20:53.530
structure out on on the heap it's not actually allocated inside of that page it's allocated somewhere else in the
00:21:00.280
computer's memory and the way that we actually allocate those SD hashes is with the mallet call now when a GC
00:21:09.400
occurs and you want to free that hash it's the hashes responsibility to say okay before I get freed I'm going to
00:21:16.360
call the free function on the SD hash now that SD hash will get freed up and then the garbage collector will free the
00:21:23.320
Ruby hash object itself so that's how we're able to store objects larger than 40 bytes in the computer's memory and
00:21:31.000
this will be important a little bit later so this memory up at the top here that's managed by the system allocator
00:21:36.820
where that slice at the bottom is managed by garbage collector now interesting facts
00:21:42.360
about these two areas are that we can control the layout and the format of objects that are allocated inside of the
00:21:48.659
GC so we can move those things around and manipulate them but the ones that are outside those system allocations we
00:21:54.419
can't necessarily control where those are with the system allocator we can do some little tricks but we don't have
00:22:01.409
nearly as much control over them as we do with the objects allocated in the GC so anything allocating the GC is much
00:22:08.720
much better for us than if it's a system allocated so in summary we're going to
00:22:14.220
summarize with some Ruby code a heap has many pages a page has many slots a slot can either be empty or have an object
00:22:21.470
those are the conditions of our of our memory so when we look at collection
00:22:26.730
we're going to talk about collection oh we talked about this a little bit in the last year but we're going to do a little
00:22:33.299
refresher because it's important to understand how collection works in order to see the tricks we can do with
00:22:39.120
compaction so Ruby uses a mark and sweep garbage collector and the algorithm
00:22:44.250
roughly goes something like this if we have Ruby objects those Ruby objects
00:22:49.590
form a tree in memory this is kind of what the tree looks like now if we cut one of those cut one of those slice
00:22:56.639
those arrows from the tree we actually have to free up all those things and that's where the garbage collector comes
00:23:02.429
in we cut that relationship it fries those fries those objects so the actual
00:23:07.710
the actual algorithm has two different parts the mark mark part and the sweet
00:23:14.159
part which is why it's called a mark-and-sweep garbage collector so the
00:23:19.919
way this works is if we have some sort of have some sort of tree we go through what is called a mark phase and we walk
00:23:26.070
through the tree we're starting from the root so in this particular example we'll go from the root to eight F and then
00:23:33.120
from s to D B and C and then from the D we go back to a and anything at the end
00:23:39.899
of this mark phase that hasn't been marked we free it so that's what happens those all get those all get freed and
00:23:45.720
that's the overview of a mark and sweep mark and sweep implementation now the
00:23:51.659
thing that actually those edges is a function called GC mark and that's going to be important later
00:23:58.230
where is that GC mark right there so that that function is what marks those
00:24:03.510
arrows so it's important this function name is important and we'll look at it later so if we're to look at this in
00:24:09.360
Ruby code we would say like hey object give me references I'm going to walk through each of the references and call GC more from this now the downside of
00:24:16.860
mark-and-sweep is that it's kind of a slow swell algorithm but there are different tricks that we can do to
00:24:22.380
increase the speed of the algorithm such as incremental incremental marking and lazy sweeping and we actually discussed
00:24:28.920
those in depth last year so if you want to know more about that watch the watch
00:24:34.020
the top now onto compacting we've looked at how
00:24:39.180
objects are created and destroyed but how does this actually relate to compacting now let's say we have a bunch
00:24:45.780
of objects like this and we free up some of those objects like that the amount of
00:24:52.980
memory that's actually consumed is still the size of all of those pages even though we freed up all those objects we
00:24:58.230
didn't actually decrease the size of the memory right now let's say we're freeing more objects and all of a sudden that
00:25:05.310
top page becomes free in this particular case what will happen is when the page becomes completely free Ruby will
00:25:11.880
actually free that page up so it goes away and now we're able to reduce the amount of memory that the process uses
00:25:18.360
so now what if we have a situation like this where we freed up many objects and the sum of those objects equals the size
00:25:25.860
of one page now if we could move those objects around it would be nice to move
00:25:32.220
them around like this and then we could actually free up that page like that so
00:25:37.410
unfortunately today object can't move so if we can't do this in rubies that you
00:25:43.470
have installed on your production machines today and this is where compaction comes in and this is the work
00:25:49.410
that we've been doing at github is working on a compacting garbage collector and you can actually find all
00:25:54.780
of these all these changes here so this is this is the Ligeti
00:26:01.370
let G C on legit so if you want to find
00:26:08.160
all that work is up here on github so I'm going to talk about the actual contacting side of this now the
00:26:15.360
compaction algorithm algorithm that we're going to we're going to talk about is called two-finger compaction there's actually many many different compaction
00:26:22.410
algorithms but this is the one that we implemented it's called two-finger compaction yes I was playing with
00:26:28.920
keynote and it was fun so the downsides
00:26:36.840
of this particular this particular algorithm the first disadvantage this algorithm has is that it's not very
00:26:42.900
efficient and you'll see you'll see the algorithm in action a little bit later and the second problem with this algorithm is that it actually places
00:26:49.650
objects in a random random locations in memory you'll see why in a minute here
00:26:54.660
but the the major advantage behind this algorithm is that it's actually very simple to understand and simple to
00:27:00.870
implement with and I am very lazy so those things appeal to me greatly so the
00:27:08.220
the algorithm has two steps which is moving objects and updating references so it first it moves the objects I'm
00:27:15.360
going to actually update all the references for the objects we're going to look at the algorithm here so the algorithm starts with this is a page
00:27:22.320
that we have with some free slots in it and some objects on the slots and up at the top there those are the actual
00:27:28.020
addresses of the objects so it starts out by putting two pointers on either
00:27:33.060
end of either end of the page and the less pointer is called the free point or
00:27:39.930
the right pointer is called the scan pointer and what happens is the left pointer moves to the right until it
00:27:45.270
finds a free slot and the right pointer moves to the left until finds an object and when those two things happen it
00:27:51.990
swaps those two so in this case we stop right here and we just swap those two and then it actually writes out a
00:27:58.770
forwarding address so the object that used to be in B now is in one so it
00:28:04.560
leaves the one address there and we repeat this so this the left scans until
00:28:10.440
it finds free the right scans until it finds an object it swaps and leave the forwarding address so it keeps
00:28:16.820
repeating this process until those two pointers meet so it will repeat and then
00:28:21.890
finally when they meet we've moved all the objects next to each other so the actual the actual code for implementing
00:28:28.610
this is it looks like this and it's really it's really very simple you can see up there we take a scan pointer and
00:28:34.640
a free pointer those are the things that are moving through through the heap and then we basically just swap the two we
00:28:40.490
do a mend copy of one to the other and then we're done so unfortunately if we
00:28:46.550
have let's say some Ruby code that looks like this the the objects are related to
00:28:51.890
each other they have a relationship with each other so indicated by those arrows there we have maybe some hash at points
00:28:57.470
that a points at a symbol in a string now unfortunately after we compact the heap it'll end up looking like this and
00:29:04.130
now that hash points at two locations that no longer contain the objects that we're looking for so because of that we
00:29:11.540
have to make another pass through the heap and actually update those references so it points with the right thing and this is a very easy algorithm
00:29:18.860
all we do is start at one end and we just move along looking at each object to see that see what references that
00:29:25.520
object has if it has references we look at the follow those references look for the forwarding addresses then we simply
00:29:32.420
change the references to point at the forwarding addresses so in this particular case object number four used
00:29:38.270
to point at six and seven now it needs to point at five and three so all we do is update those arrows the point at five
00:29:44.150
and three and then continue on through the through the keep updating references like that so once we reach the end of
00:29:51.710
the end of the heap we're done and we've updated all the references everything is working yay then the final step is to go
00:29:58.520
through and change all these forwarding addresses back to free free slots and now our heap is back to a normal Ruby
00:30:05.870
heap and all the objects are moved next to each other so I want to show a little bit of the updating update reference
00:30:12.290
code and I'm just going to show it for just four arrays but basically all we do
00:30:17.900
is we have this C code that basically iterates through every single one of these slots in the
00:30:23.309
slots in your heap and then calls an update references function down there at the bottom and updates the references
00:30:28.950
for those objects now if we go look at that that update object references was actually in a very large function and
00:30:35.429
what it is it's looking at the type of the object and depending on the type it updates the references so for example
00:30:41.249
one of the one of the things is an array is the case statement inside of that function where we handle arrays and we
00:30:47.399
say okay well this is a shared array we update that pointer if it's not a shared array then we go through and update all
00:30:52.950
the references inside of the array so that's all we have to do we're done it is that easy a so there's there's
00:31:00.690
actually a the the cost of this algorithm is that we have to visit each slot three times we have to visit every
00:31:08.220
object once in order to move all the objects we have to visit every object again in order to update the references
00:31:15.600
and we have to visit every object again in order to remove those free free slots in the future we can probably remove
00:31:22.769
that last step and just treat these forwarding pointers as free slots but you can see we have to walk through
00:31:29.039
every single object twice at least so compaction challenges I want to talk
00:31:34.440
about some of the challenges we've had implementing this implementing this compactor at work one all these all
00:31:41.279
these problems boiled down to essentially object addresses so every object in your system every Ruby object
00:31:48.269
has an address an address and memory now unfortunately a lot of the code out there specifically the C code out there
00:31:55.169
today believes that these addresses are constant that the the address for that particular object will never change now
00:32:03.240
unfortunately if we will have some C code that says points that this object
00:32:09.090
and it says oh this address number four that'll never change right fine now unfortunately with a compactor that
00:32:17.820
is no longer true so uh the primary offender of this this rule is
00:32:25.259
specifically C code and we're going to look at those look at how to address these C code issues because we have to
00:32:31.019
address this in order for it to actually be a production-ready thing the three problem cases we'll look at
00:32:36.090
our C extensions and how we dealt with that hash tables and also global variables in C so for C extensions the
00:32:43.710
way we dealt with that is a little trick I use now so far the object
00:32:50.490
relationships we've looked at have been hashes that point at strings and symbols and these are just normal
00:32:55.919
normal Ruby objects right now these are regular references and we can handle these regular references pretty easily
00:33:02.279
because they're implemented inside of MRI we know how to update those references we can fix them but what if
00:33:08.490
we have some C code over here some C data structure the points that our a Ruby object how do we how do we actually
00:33:15.269
handle that so if we don't if we don't handle that then the garbage collector
00:33:22.200
could actually free the hash and then our our our C code would explode right
00:33:27.990
if you have if you have C code it has to do something to make sure that that Ruby
00:33:33.600
hash stays around and if that Ruby hash doesn't stay around then that C code must explode so how do we how does the C
00:33:40.830
code actually handle this so the C code has to say well I want that hash to stay
00:33:46.529
around because I'm referencing it and in order to do that in order to do that the C extension author actually has to call
00:33:52.710
a function called RB GC mark so they call our b GC mark on that ruby object
00:33:57.809
in order to say hey i'm still holding a reference to this don't free this don't
00:34:03.120
free this object now what's interesting is if you remember back to our market our mark sweet algorithm you'll note
00:34:11.069
that the way we actually mark references was we have a function called GC mark not our v GC mom so actually internal
00:34:18.510
data structure is normal regular Ruby objects use this function called RB GC mark so our called GC mark so in this
00:34:25.349
way we can differentiate between objects that are held by C extensions versus objects that are held by just normal
00:34:32.550
regular Ruby objects so in this particular case we can say okay well you
00:34:37.589
know don't move that hash it's being held on to by a C extension but the
00:34:43.500
string and the symbol those are okay to move okay we can move both because they're just being held by Ruby
00:34:50.070
a ruby object and we know how to fix those now I want to prime you for
00:34:55.710
questions to ask me later what happens if you have a C extension that references a symbol like this that doesn't market what is that case what do
00:35:02.100
we do then so please ask me that later so let's look at hash tables this is
00:35:08.760
probably the least interesting problem but also most frustrating or maybe both
00:35:13.950
of those I'm not sure it's it's an interesting / fun and not fun problem
00:35:19.140
and you'll see why here so a normal hash table a hash table all it does is that have some sort of a bucketing system
00:35:26.070
where we take some we take some value and we compute a hash code for that
00:35:31.560
value and based on that hash code we stick to the stick that data structure into some bucket right so we have some
00:35:38.460
key value pair for example we have some hashing function that computes the hash
00:35:44.310
for the key and say in this case it computed 6 and it stores the key in value there that way later on what we
00:35:50.490
can do is take that same key compute the hash key for it again and get access to
00:35:56.490
that value we're all we're all familiar with this we know roughly how hashes work we use these day-to-day I think
00:36:03.390
especially if you're a rack user so the default hashing function unfortunately
00:36:09.900
is this and you don't need to understand the sneak code I'm going to point out exactly to you what the problem is the
00:36:15.930
default hashing function actually uses the memory address that uses the object
00:36:21.390
address so if you take the hash value of some Ruby object it's going to be the
00:36:26.580
object address now the problem is that if that object moves well that address
00:36:31.650
changes and if that address changes well then the hash code changes for that object and if that hash code changes
00:36:39.480
then we can no longer look up the object in the hash right so this is an issue for hashes I yes I said this if the
00:36:47.190
address changes then so does the hash so how do we how do we fix this clearly if
00:36:52.920
you use some key in the hash we want to be able to look up that value again so what do we do well the solution that we
00:36:59.490
have taken on for who don't allow house keys to move so it's just these these certain groups of
00:37:05.950
objects they cannot move okay now I put a little star by that because I want to
00:37:11.680
give you feed you another question which is what about strings so ask me this later in the Q&A section or if we have
00:37:18.520
if we don't have time ask me over a beer so the final thing I want to talk about is a global variable and I'm going to
00:37:26.290
show you an example of global variables that we had to deal with in MRI and I sent a patch to fix this so in this case
00:37:34.150
we have a global variable here called separator and this separator actually points in a string called slash it's
00:37:39.280
just slash you'll note you'll know the slash from when you do file dot joint okay now that that global variable is used
00:37:46.690
again down here when you say file dot doing so it's okay take those two things join them together with that string and
00:37:52.210
we're great now what happens if we assign the separator to nil and then GC
00:38:00.030
so let's take a look at this code we say assign file call and separator to nil
00:38:05.260
and the other one to nil then we do a GC and then we start you'll actually get a seg date and that is because I'll show
00:38:11.290
you in a minute it this segment is not occur with JRuby so I shouldn't plug
00:38:17.320
JRuby some time on me MRI scene bud there you go so the reason this sexy
00:38:24.580
happens is because we have the string in memory we actually have three references to it we have the global variable in C
00:38:30.580
pointing at that object and then we have these two Ruby constants pointing at the object now this code here that our
00:38:36.970
that's in the lower right I'm assigning those global objects to those constants to nil and then we do a GC start so we
00:38:47.350
assign those to nil we do a GC start the GC says well there is no references to
00:38:53.830
that flash object anymore so I'm going to free it so it frees it because the global variable does not know how to
00:39:00.220
market so it frees it and then when the final file dot join runs everything
00:39:06.160
blows up because we have no reference to that object anymore so in this particular case uh
00:39:13.240
what we did or what I did was submit a patch to stop using this global variable so look up the value rather than rather
00:39:19.990
than use some global variable as a cache so this issue is similar to compaction
00:39:26.440
because we're not able to update update the references of those global variables which is what that what's that what the
00:39:33.670
compactor needs to do so global variables the the hash issue and the global variable issue are very similar
00:39:40.000
because when those objects move we can't update we can't update those references so the general problem is essentially
00:39:46.570
that we can only update Ruby objects appointed other Ruby objects and we can
00:39:53.740
update those we can only update core classes to MRI so I want to I showed a
00:40:00.910
few examples of the issues there are many issues but we've fixed them one by one piecemeal and it seems to be working
00:40:08.440
most of the time so I want to show you a result of the compaction we're actually using we use the compactor in production
00:40:15.010
and I want to share some of the results with you that we found this is an example of a rails heap I'm just going
00:40:20.500
to show a bare bare rails project so the
00:40:26.109
compaction code looks like this essentially we open an open a file we write out the heap to the file we have
00:40:32.050
to specifically compact the heap by calling GC compact then we write it out again so to run this with the rails
00:40:38.380
script Runner now if we graph all the graph with the slots look like if we
00:40:43.450
graph the heap before the before we were on compaction the heap looks like this now each of these columns are a page and
00:40:51.820
we talked about pages earlier each of the red dots are objects that we cannot
00:40:57.700
move each of the green dots are objects that we can move in each of the white
00:41:03.520
the white location that is free space and these pages are sorted by the number of objects that cannot be moved now
00:41:11.440
after we compact it for you if we look at this graph again it looks something like this or you can see now we've got
00:41:18.490
all the green objects move to one side of the heap and we have all the white space on the other side of the heap and
00:41:24.640
we can allocate into there so before compaction we had 552 pages
00:41:32.029
and of those pages 528 of those pages have space on them for allocation now
00:41:37.789
the problem with this is is that every time we write to a page that page may be copied to a child process where we're
00:41:44.720
using unicorn in production which is a forking web server so copy-on-write optimizations are important to us now
00:41:50.690
after compaction we are only 160 thousand of our 552 pages have space for
00:41:58.039
allocation so maybe only 167 of those pages can possibly be copied where previously 528 could now this lower
00:42:06.829
number is better for copy-on-write optimizations because we would like to have fewer pages we copy to child
00:42:13.309
processes now we can actually improve this we you saw all those red dots at
00:42:19.249
the bottom if we can fix those red objects such that there are fewer of them we can improve this number ideally
00:42:25.309
we would have no red objects but you saw earlier we have those issues where there are some that we cannot move there are
00:42:31.940
some that we found that I didn't show in this presentation that we fail we can't move them but with a bit of development
00:42:38.299
work we can so I want to show you some of the heap graphs well a heap graph from our production
00:42:43.910
application and the reason I didn't include many of these graphs is because
00:42:49.220
they're very big we have a very large heap and production this is what it looks like after compaction you can see
00:42:55.489
it is quite wide now the good news is I mean the bad news is if there's a lot of
00:43:01.400
red objects on here the good news is is that it follows the trend of a basic rails application so we can say basic
00:43:07.099
rails app is generally representative of the heap so why compact I've talked
00:43:14.599
about how to build compactor and I gave one reason the one reason is to free up space like this we want to free up if we
00:43:21.079
can we want to free up those pages the other is for coffee on write optimizations which I mentioned a little
00:43:26.450
bit earlier we use a forking web server unicorn in a forking setup all the child processes share a memory with the parent
00:43:33.289
process but as soon as either of them write to those processes we get that memory copied and that inquiry
00:43:38.730
the overall memory used on the servers so we want to reduce that so for example
00:43:43.920
in this case before compaction basically all of these pages could be written - all of them have free space on it so
00:43:50.160
potentially all of them could be copied to a child process whereas after compaction you can see here only those
00:43:56.070
pages can be copied to the child process and these pages remain shared among the
00:44:01.349
among the parent and child processes now I want to talk about reality here for a
00:44:07.109
minute unfortunately let's get back to reality sorry uh we're going to talk a little
00:44:15.960
bit about I want to talk a little bit about agile agile development so agile agile development tells us the fail fad
00:44:22.220
now I've created a new development style a new better development style that I
00:44:28.619
call fail continuously so I've actually
00:44:36.599
created a new continuous integration server where where we actually
00:44:41.690
continuously fail and today I'm really proud to present a new product from
00:44:48.810
adequate industries it's called Aaron CI where your test will fail constantly so
00:44:56.250
I guess I'm coming around here making a tongue-in-cheek a tongue-in-cheek assertion that I I am somewhat of a
00:45:03.000
failure and it is true because if we look at the real-world results of this compactor we saw in production maybe
00:45:09.359
only a 2% improvement or a 2% for dust2 percent reduction in memory usage on our
00:45:16.800
production machines this is nowhere near the amount that we expected because if
00:45:22.440
you look at these if you look at these graphs here we would expect ok well you know maybe in this case we have most of
00:45:28.770
the shared and presumably only 30% of it can be copied so you'd expect us to have
00:45:34.530
maybe I don't know 60% reduction in memory but that's not true or a 30%
00:45:41.369
improvement it's not true and and we're trying to figure out why like I said this is ongoing development and I want
00:45:47.790
to share with you two possibilities or two reasons why we're not the improvements that we expected there
00:45:53.180
are two possibilities one is essentially poor compaction and the other one is
00:45:58.250
maybe a small percentage of the heap is actually compact and I'll explain that in a second I glossed over some stuff in
00:46:05.509
this presentation some stuff lots of stuff now if we look at this boom for compaction graph I've divided up these
00:46:12.859
pages into four four parts and the reason I've divided these pages into four parts is because if you write to
00:46:19.369
one page the entire page does not get copied only 25% of the page gets copied
00:46:25.190
okay so the problem is that this free space there 25% of every single page
00:46:31.910
that's open that particular free space that can possibly be copied may be equal to this free space here so if that's the
00:46:39.440
case and we'll see no improvements in in copy-on-write so if the number of
00:46:44.779
quarter pages is equal to the number of full pages after compaction then we won't see any improvements now the other
00:46:51.950
possibility is that maybe the Ruby heap is actually much smaller than the amount of memory that we've allocated we talked
00:46:58.819
a little bit earlier about hashes being allocated in one area and Ruby's GC allocated in a different area
00:47:04.549
maybe Ruby's GC is it's just a small percentage of the memory that's being used so a compaction will have very
00:47:10.400
little effect on it maybe it's large maybe it's small so we have to measure that and I want to talk a little bit
00:47:16.609
about measuring and then I'm going to hurry because I'm totally over time we're measuring this now with a thing
00:47:22.640
called malloc stop logging and what this is is we say every time you make a call
00:47:28.099
to malloc we log the stack so we see who made that call and figure out what the problem is I'm going to show you how to
00:47:34.130
do this on OS 10 but you can also do this with Val grind and the what's called the massive allocator so lookup
00:47:41.509
that later the way to do this with OS 10 is you simply set a variable called now
00:47:46.640
it's back logging no compact and what this does that logs every single mouth call and now you put the process to
00:47:53.809
sleep because you can only analyze live processes because of a thing called address randomization which don't just
00:48:03.040
don't worry about it so you put the process to sleep and say okay in another
00:48:08.560
terminal ask for the mouse history give me all all by size for that particular pit I just put in some kid that's
00:48:15.600
obviously not the paid you're going to have so what that does is it actually prints out all of the live allocated
00:48:22.480
things so this mallet stack logging logs of reallocation logs every three and the
00:48:27.490
mallet history actually takes that history and calculate what is allocated now and what are the stats for those
00:48:33.400
particular things so a sample of the stock log is like this I know you can't read it one record looks something like
00:48:39.040
this where we say okay we had one call for some amount of bytes and that's what the stack looks like so you can see who
00:48:45.280
made that call now I wrote some code to process it and it's kind of small but I
00:48:50.590
want to point out I want to point out a few things about this processing code one is I use the flip flop operator the
00:48:57.370
other is I use a protected method and the other is I have a method here with no parentheses are so I'm using all the
00:49:06.880
worst practices from from this conference so if we use it if we use
00:49:12.730
this code the process process the output of this malice stack logging we can see an empty program will have something
00:49:18.790
like this where 17% only 17% of the heap is managed by the garbage collector
00:49:24.100
where 83% of it is managed by the system and that's for an empty program this very basic empty program here now we can
00:49:33.460
actually we can actually adjust with okay yes thank you earned good job we
00:49:38.800
can we can adjust this let's say we change the number of slots that we
00:49:44.110
initialize with let's say we start out with a hundred thousand Ruby objects and get the stack for that this is what it
00:49:50.920
will look like so we started with 17 with an empty program and we can actually increase the amount that's used
00:49:56.080
by the garbage collector so we're testing in this in production right now unfortunately logging this data is slow
00:50:02.620
so we're trying to come up with a better way to do it the test results will guide us how to actually fix this and improve
00:50:08.980
the performance of the compare so depending on what the test results are it will tell us where we need to
00:50:15.940
focus so if the test results show that most of the heat is taken up by the garbage collector then we need to fix
00:50:22.450
all those red dots and allow those to move if it turns out that the Ruby GC is
00:50:28.299
a small percentage of the heap then we need to allow variable with objects and start allocating hashes into rubies
00:50:33.880
rubies garbage collector now the truth is that both of these things need to happen but the test results will tell us
00:50:40.359
which one to focus on so that we can get the best best results for this so I'm going to finish up here because I am way
00:50:46.510
over time I will summarize why should we compact compaction allows us to save us save memory in two ways which is freeing
00:50:54.880
up freeing up pages and also improving copy-on-write performance we've developed this this patch is open source
00:51:02.559
software which you can go check out here the plan is to upstream this sometime
00:51:08.500
this year I'm hoping to get it done by September for Ruby kaikki and that is
00:51:16.329
all thank you very much I'm so happy I could be here
00:51:24.550
all right questions there you go yeah you can go to the mic hi I'm going
00:51:34.460
to get a new laptop so I was wondering when will we get a new edition of stickers with Gorbachev in future well
00:51:42.110
there's no there's no new edition no new edition right now I brought stickers with me I if I am invited back next year
00:51:49.160
I will definitely bring new stickers we I brought I brought stickers there
00:51:55.040
justly we've had the same stickers for a year we recently moved so my my brand
00:52:00.740
manager my wife hasn't had time to design new ones so will I'll have some
00:52:08.030
next year awesome and now for a more serious one yeah what will happen with object IDs since they depend on the
00:52:14.180
memory where objects was allocated I'm sure that's that's a great question so the question is well what will happen with object ID the object IDs are based
00:52:21.080
on based on the location of the object in memory so when you call object ID
00:52:27.560
that number is directly related to where that object is in memory and the way that we're handling that is we actually
00:52:33.190
lazily figure out what the object ID is and cash it on the object and then we have another a separate lookup table for
00:52:40.040
collisions so basically what will happen is your object has no object ID until you call object ID then it will
00:52:47.210
calculate the object ID based on you the address or if that value has already
00:52:52.370
been taken from some other value so the moral of the story is please do not call
00:52:57.800
object ID you can do it but it could be slow in the future yes
00:53:10.100
like oh the excitation will be here what
00:53:15.360
would be what welcome to be coffee there is this expectation that the stuff in
00:53:21.690
the the green the red and green that that that would just be shared but can't those same cans of things in those pages
00:53:29.670
also change over time and the copy-on-write could kick in for those pages sure sure yes that's a great question so
00:53:35.190
the question is I can't move the the red and the green objects that I showed earlier move around and or or get freed
00:53:43.320
or have something new be written there over time and then have that ruin the copy-on-write optimization and the
00:53:50.130
answer is yes it's possible but what we did is all that all those objects that I
00:53:57.060
showed you are immediately after rails boot so it's all just code that we've loaded in and initialization objects so
00:54:05.160
those will likely not change so it should be long-lived long-lived objects but yes it's possible
00:54:11.570
okay yeah I guess I just don't intuitively know like active record is in there just like messing everything up
00:54:18.060
after you've loaded it and like you know messing around with with Singleton's and whatnot I didn't know how much it causes
00:54:23.580
that something sure I know the code most we got most of the stuff that I showed there is just compiled Ruby code it'll
00:54:31.350
never that stuff will never change if we were doing compaction later on like
00:54:37.620
after each request or something like that yeah it would it would completely ruin it
00:54:42.780
yeah okay I figured the answer was something like that thank you yeah all
00:54:48.870
right okay hello hi thanks for that it
00:54:56.700
was really good to see the internals of Ruby oh thank you a two-part question
00:55:01.740
actually in the loop does it go through the entire or just a page so can you say
00:55:08.760
that again you mentioned about the loop for compaction I go through the whole
00:55:14.460
page or the whole heap it goes through the entire heap okay so is it possible
00:55:19.650
that a pointer are moving the object you leave a pointer there
00:55:25.070
that pointer itself could move later does that happen a pointer what do you mean so the way
00:55:31.820
you are moving the object yeah can a pointer also move I is it even possible
00:55:38.800
no I mean you can move so the object the object will get moved but after we've
00:55:45.080
updated all the references then none of the none of the Ruby objects should
00:55:50.120
reference pointers that aren't actual Ruby objects okay thanks mm-hmm yeah
00:55:57.020
okay hello Aaron hello and how does an anomaly anonymous class act in this
00:56:06.460
compacting is it going to stick around forever or is it going to be moved like
00:56:11.750
a normal object all objects remove equally it doesn't delete I assign it to
00:56:17.660
a glow to a constant like you can say I don't know a equals yep and it doesn't
00:56:23.450
care okay great
00:56:29.400
people hi Aaron you have thanks for sharing I just know you mentioned you go about
00:56:36.240
2% for Team ideation right about the memory location Yeah right
00:56:43.020
I have no idea how the computers are squeezed written but one thing that I am
00:56:51.210
quite confused is a but you are trying to read the whole page right if there is
00:56:59.520
no it you got the one I'm quite curious
00:57:04.860
up the cosa allocation of the new object
00:57:11.280
I might be faster than your composition script so I miss the John unable to free
00:57:20.250
the whole pitch sure yeah yeah okay so the question is uh how does the how can
00:57:28.200
the compactor keep up with allocation yes yes both new object yeah yeah that's
00:57:33.900
a good question this right now it's it basically stops the world stop the world compactor and
00:57:39.780
you have to actually call an object or you have to call a method called GT compact so we had to we modified our
00:57:46.410
modified our boot process to say okay before before we actually listen for
00:57:53.730
requests we compact everything and that pauses the process for maybe our
00:57:58.800
particular heat it would pause the process for about 100 milliseconds and
00:58:03.840
then continue on so it doesn't actually allow any allocations during the compaction favor all right cool okay
00:58:13.800
there's one in the back isn't there's a mic there you can go to the mic yeah
00:58:25.380
sorry well you may have a ye I will be managed memory as well system managed memory or
00:58:32.190
me no I think so vehicle chamber why do we need to separate these two type of
00:58:37.380
memory management White House will be managed to all memory in and also mention about the 40 kV sighs
00:58:44.220
sure what can it be dynamic sure that's a good question so the question is why can't why can't Ruby manage all of the
00:58:50.580
all the memory why do we have this 40 byte 40 byte limit right so well the
00:59:03.420
answer is that garbage GC alga GC algorithms are a lot easier when you
00:59:08.880
have a fixed width fixed width slot so with a fixed width six with slot it's
00:59:14.940
much easier to write a GC I think that's basically the origin of it we can have I
00:59:21.140
don't think there's any particular limitation or reason why we couldn't
00:59:28.230
store everything in Ruby's garbage collector essentially it's just that someone needs to do the work to
00:59:34.260
implement that so if I had to guess the reason we have fixed with slots as
00:59:40.110
historic reasons max maybe I yes he's
00:59:45.900
not paying attention to places they go I will make that be the the answer thank
00:59:57.780
you for the talk umm you say something about the red positive say the hash you can remove the
01:00:06.630
location because the treat I see using such vectors we affect the way we write
01:00:13.860
Cole let's say like having a lot of the object at hands and there's unmovable
01:00:21.810
with actually affect the performance and therefore we may end the writing few has
01:00:28.530
or the kind of stuff like you think we affect our way of writing code right
01:00:34.320
right so the question is will the TV I guess is the behavior of the garbage
01:00:39.360
collector or the implementation details of the garbage collector will that impact the way that we write code
01:00:45.230
it shouldn't I don't think that it
01:00:50.310
should impact it I think I think most of those red objects we can actually eliminate so I think that with a bit
01:00:57.209
more development work we can reduce it such that the percentage of objects that can't be moved is very low and you would
01:01:06.029
I mean it would be so low that there is no reason for you to know that it is
01:01:11.609
even a thing so no I don't think it would have impact it okay thank you very
