CppCon 2015: Andrei Alexandrescu “std::allocator...”

let's start so we're start early because we're going to finish late so that's the right thing to do well I send this working title to a number of folks and that's not what what do I mean by this title and it was kind of difficult to so I had to explain my title so my title means okay here's my working title I had this working title which was too dark AC okay and then I thought it's not a very good title because you could make an allegation about an alligator Frankie this alligator caught my foot it ate my Crocs okay so there is a possibility of a connection there what I'm saying there is not a lot of connection between steadily cater and memory allocation this is my point and to wit my another working title of mine was design alligators that don't not work so you know being a program so this is not English it's not correct but it's sort of logic logically correct because you can imagine the programming put a parentheses around not work and that's like a verb not work like not work is a verb in you put the parentheses and it makes sense so it's made its I love grammatical malice that way in any language as it were anywho I hope it's okay so does it doesn't make clear that I'm not hearing peace okay is this clear to everybody I'm not here I'm here to destroy okay I'm on a warpath right now okay so just to make sure that my yes which oh okay um I was like oh my what question could be at this point so there's been something very interesting about memory allocation so this talk is not about making fun of the delicated because just too easy it's more about how to write good memory allocators doll do you have an interest in that kind of stuff you know I mean in the immortal words of Diana this is C++ and this is like the ultimate argument of kings we care so this is kind of stuff that we care about so let's see I have a pointer here it doesn't work but it's the if I if I look like works I can see but now I'm gonna use my left eye for the rest of my life okay so it's very interesting that memory allocation has been a cyclic of business it's very just like if you if you're a vendor of malloc if you made your living if you paid bills by implanting malloc that's that was kind of a wild ride because in 83 so when malloc when when sort of the Kernighan and Ritchie book came out it had a mini memory allocator which is what by today's standards rather naive and simple but other point was kind of a huge thing there's a huge deal first of all it was that you could write it without assembler oh my god they could do this she's awesome look at that void star in the cast and all of you know it doesn't it was like wonderful that you could do like layout control and that kind of stuff in with memory the way you wanted really put your God for the first time could put bits where you want it and this was amazing because like by those times like Pascal was there it was kind of weird to do that kind of stuff in Pascal it's not impossible right those like lists which is way high level and there's Fortran which is like again like it couldn't do that kind of stuff right so when malloc came about and would you know when seeing that kind of low-level coding it was some sort of an eye opener and everybody went on a bandwagon and said oh all of my everything I'll do from now on is going to use dynamic memory allocation I'm not sure if you remember but before that it was that memory allocation was kind of was the word it was an exotic thing to do Oh in my Pascal program I used like you know that carrot and knew and I forgot the operators they had right so it was kind of an interesting thing to that system level to use dynamic allocation so 1983 and you know fast forward 10 years - like malloc was done enough to be so bad that you know any code you wrote was better than it so another ten years later again malloc caught up sewed you know new horde alligators and G malloc and you know a lot of good new alligators came about DC malloc and whatnot and today you know it's kind of in the middle so today's like meal of the road you know so you should know about malloc and you should know how it's done and you should know that sometimes you can do better and here's where we are today okay look two years later but that's okay so I'm going to start with a bit of history this silence doesn't bode well I was expecting some murmurs like know what's going on here yeah yeah that kind of stuff yes thank you thank you for the sound effects here so by means of a bit of history so it started we see when we had where we had malloc and free and there's an asymmetry here because when I malloc member I passed the allocated size but when I free memory I don't pass the size back right is this good or bad bad why is it bad performance so essentially by committing to this API you already stated that I'm going to have to mine that size somewhere or another and eternity the first malloc that was sort of par for the course because they stored the size anyway because they need it for the size of the block that held a memory allocated and so on and so forth turns out this has been sort of a bad decision and it was kind of a we've been living with it ever since I was just talking with to Howard Hin Howard they are here there he is okay so I was talking to this fine gentleman Howard Hinnant and he said sound like been there done that and I would hate trying to do it again the doing anything any change exacting any change about memory allocation in in the respective standards so this is kind of an unpleasant thing so the color nose the size the current node knows the size but it doesn't pass it along and the allocator must manage the size that was out this is kind of a big deal size management is a kind of a complete pain in the proverbial we hate it it's a bad thing to wait give me a second here where are we I'm going to accelerate a few slides ahead they're not going to turn back just to make a point here Google for that number and you're going to find the you know the probably a part name at Sears it's a nail that you can put in the ground or whatever but it's also a proposal for the civil standard and omission of size information global operator delete aka free has unfortunate performance consequences and there's a lot of discussion about how to improve that what's the state of that Howard is it yeah all right why don't you google for it thank you very much hi delegation it's you know getting the management now so I gotta okay let me turn back here so this kind of a bummer okay and to if we could turn the time back and do it all over again we would do something like this we would say well let's define a structure that's block and it has the pointer and the length thank you very much and whenever I'm going to malloc I'm going to get back the block and I'm going to pass the block again when I release the memory the block has a size boom big deal right who cares essentially we do care right so there is importance attached to this so let's kind of say we if we want to design a new a locator let's start with this block simple structure all right it could hold two pointers etc it's a try and you know this it's pretty much equivalent and as the history goes the next generation was operator knew what's wrong about operator knew okay what's good about operator knew it Terry's the type information into the type right and it does all it can to throw it away as soon as possible because it forwards to malloc so the good and bad about new is it works with malloc it must work with Matt because historically it you know there's so much so many things you could at the same time so new was not like the highest priority there so so the new must work with malloc and then there's this whole side discussion about realloc because there's no renew right there's realloc which is awesome and is you never easy correctly right only Marshall and I were the two guys who know how to use it okay we're talking about this it's kind of funny but essentially operator knew was designed to work with malloc but you know I didn't I have you know like in that movie alert like I protest this is not a good thing operator knew what happened and I'll tell you what I think but it's okay that it's ads type information is great I love it there are few syntactic oddities the most interesting of which is I was just talking about this like int is a type right int is a type do we agree so far I have have your approval okay thanks beam on then in open square bracket 100 close square bracket is a type is it Z not it's a it's a fixed size array of 100 integers alright were you with me nothing up my sleeves okay new int I get a pointer to an int I get I allocate a new integer one integer and I get it a point back new int open square bracket 100 close square bracket what'd I get there's something wrong here ladies and gentlemen there's a syntactic weirdness because even though int of 100 is a type in and of itself when you put it at the tail of new it's good you know that the syntax of the operator new is going to interpret a completely different way it's going to say oh this guy wanted not a fixed size array of 100 integers give me a pointer to that guy but you want to dynamically size the array of integers and I'm gonna give him a pointer to it because what I care about that guy right so that's the syntactic oddities that is kind of weird there's no communication between you and the constructor which everybody who's done try to do anything with regard to like class level operator new and constructors and stuff know Spain fully well like people do all these kind of crazy tricks I think the best trick you can do is class level operator new is to forget all about it and never use it and like really pretend it doesn't exist in a language and then you'll be happy you lead a better life right there's you know there's ona you know when I operate a new anonymous you should join the meetings okay so the greater a distraction okay so we have the greater a distraction TGA I love vehicle names right so the greater rate distraction goes like this well operator new is kind of weird and but you know it had to be there well how about the race we'll gotta have an operator new with brackets at the end and that's gonna allocate erase and erase only and by the way you should be sure you should make sure that whenever you call new the normal new called delete the normal delete but over a call new the array new you should remember to call the delete already leave you know the rule this is old you know why you need to know the rule okay I wanted like a coherent so you guys talk you guys talk and guys talk three votes here what yes yeah so there's there's a thing with the race and you know you deal with the nunnery syntaxes just going to call the first destructor it finds on the way and that kind of stuff but in fairness there's no there's no reason for it to be honest there's absolutely no reason and it should have been not existent at all you should not have existed it's just to make life difficult for everybody I are recommend operator new for any serious use of memory allocation you can quote me on that the guy with the camera you should have me there right okay so follow me at I'd like if this were jail and I want to escape this would be awful because he's following me I couldn't okay so and then you know the history goes along came a CD a locator and you know the funniest thing about a CD a locator is it's not for memory allocation and I'm not kidding what is a CD allocator for construction no pointer types Pablo okay yes he's the guy so it was for oh where are we near and far pointers who's old enough to remember near and far pointers okay great so you turn to your left and explain to the younger generation what we've been going through you're better off not knowing yes that's right every knowledge about near and far ends up on your face okay so not good I recommend it so well one question is like is a sea alligator bad or not and this is a legitimate question to ask because I've talked to people who claim it's a non-problem if the alligator works to wait we've been carrying it in standards like through C+ 17 still there it didn't I it's like that you know the square wheel on the car so this it's a truck has many wheels and everything one of them is square and that's the delegator we've been carrying it and one great thing that I should bring to your attention is the alleys they're made this talk of last year here at this conference and it's entitled making alligators work and there's two issues with that talk number one the title what I mean you know let's do a bit of thought you know linguistic analysis on the title did you ever see like it's 2014 so it was like last year and steady alligator has been finished before 1994 so done like 20 years later like in the book right 20 years later and 20 years later we have and it was a double whammy it was like 180 minutes talked it was like two talks back-to-back 90 minutes plus 90 minutes and I set for most of it and it was 20 years after the fact and it was making alligators work there's no talk like making sort work I didn't go to a towline making making a CD vector work let's let's get that sucker working okay so the title already kind of is the smoking gun here ladies and gentlemen we have a problem here that right and the second matter I have with that talk so you know I sat through it and it's like okay so let me see where's the allocation happening there's not one slide on it that's dedicated to memory allocation which is very funny because allocators is in the title and linguistic analysis making alligators work I would expect there be very good at allocations because there are alligators right that kind of stuff so I'm an immigrant but you can't fool me with that stuff okay it's still I can figure out the basics all right so then I emailed Alice then I said you know could you please email me the slides because I want to call them and kind of use them as a reference and guess what he said nothing he didn't reply because he knew I'm gonna make fun of him so all right what's good and what could be done be better instead alligator I told you I did not come in peace friends did not come in peace so okay the short story here is that stood a locator is not a great alligator because it was not designed for that purpose it was designed for near and far pointers nyan 5 for pointers had to do with 16-bit systems and he had like pointers that were 20 bits with segment and offset again you don't want to know that stuff because it ends up on your face right so it was kind of a weird kind of thing that was essentially historically it was a bleep wonder in the history of computer science that has since long subsided it nobody cares about that stuff anymore and to wit does the committee the super committee actually removed everything related to near and far pointers from stood a locator essentially moving willfully its initial purpose which is very interesting and very telling so okay so there are few obvious mistakes that I noticed one is that you know that the first thing is like the type is a parameter in the allocator and that's a weird thing because type you know allocation should not have to do much with type at all it cares about two things one is the size and the other is the alignment do you care if you allocate for example they'll indulge me for a moment do you care to allocate an INT and an unsigned int in different ways probably not it's like what do I care they're both same size same layout even what do I care right taking this one step further reallocate about do you care about allocating an object of 128 bytes of type 1 t1 and another object of 128 bytes of type t2 do you care to allocate them in very different ways possibly well okay so alignment is kind of a different topic but you know I do care about the alignment but the type them set the styles and cells is like I have much less concern for and more often if I use a specialized very good a locator for t1 it's going to actually be a good a locator for 128 bytes it's going to be a very good allocate for that specific size and alignment not for that specific type alone so you care about size but not about the type so this whole thing putting the type in the allocator is weird it's not weird it is great with near and far pointers but it's not good for allocation so you know it's an allocate or not a data factory because the algorithm knows how to deallocate things and you know it's kind of odd it's not a it doesn't produce it construct objects it shouldn't be constructing objects it's just allocate memory even though it's a factor because it has construct and destroy it does have constructing destroy steal Howard doesn't it they didn't remove them those bastards man so it's in even though it claims to have factory powers it's still try fixing void star you know so that mean mine bubbles here so what I'm saying here is allocated should trade in memory blocks void star in size T that's it and just to mention like awful crotch remind you other all that good stuff that I'm sure is intimate knowledge to also if you don't need though that you don't get it Donna okay great another batch of obvious mistakes there's an assumption that alligators are stateless which is I'm picture them the oxymoron here a memory allocator that's giving me memory has no state right this is very interesting it's like the the empty bottle that you keep on drinking water from it's just you know it's like Sinbad you know the story it's like a magic you know this is empty but I'm pouring from it you know it's mysticism something is really interesting here except it's of course not it's like completely crappy right so allocate all alligators have steak some may have shared state it may be a global there because malloc that's how it works it has like global state dealing with some you know some is mana state you know I love like these complicated words you know the mana state pattern is like a global except it has a great name right mana state so well they have statement got a deal with it and by the way see process 14 does allow alligators to help state and you got it you got two gentlemen the front to here to thank for or pick their faces as you you know depending on your preference John linka San Pablo Halpern raise a hand please thanks very much there they are so you can talk with them yeah don't throw the tomatoes right now great so we have some state so definitely we want to support alligators with state and but there's something that public John did not do they did not do the composition thing which I think is the first thing you need to do with memory allocation if you want to write an alligator you gotta make it composable if you look at any allocated documentation you're going to see that it is a composition of several completely different allocation strategies look goo --gel Ford ugly alligator I'm going to say Doug the first sentence of like one of the first is like if the memory is low less than once at one kilobyte or whatever if the memory is less than one kilobyte then I'm going to do this stuff if it's between one kilobyte and 64 kilobytes I'm going to do some completely different strategy and if it's beyond that I'm just going to use their map or whatever help right so it's a composition of strategies depending on the size for example in this case if you turn to the windows a locator you're going to see the same thing oh for small objects is going to do this stuff and for medium objects this is completely different stuff and for a large judge is going to say out of memory and you know that kind of stuff my point is it's different right so and you're gonna see that even like four four one okay that small size allocated like up to 64 kilobytes for example that guy is inside its belly its you're gonna find an array of littler alligators each of whom is specialized for a specific size range in these buckets and all these good things so if you want to design an alligator you got to make composition the first thing in your design the first concern gating composition right is getting the alligators right so the rest of this talk is going to do composable alligators great close your eyes for a second because I want to go one slide ahead and back then I want to ask you a question okay close your eyes okay you design this so question for you what is the simplest composable alligator that you can imagine the null alligator excellent is the simplest allocation it's actually a useful alligator than all alligator what does it do nothing it is a show about nothing okay it does nothing but it does it in style it's always returning all whenever it try to allocate from it it's gonna you know when you try to free things what is going to do it's going to assert that the input is not what you pass to the null a locator for freeing it's gotta be now because you're not supposed to pass anything else because now you pass to the alligator what it passed you before right so the argument to free must be a previous return of knew of allocate right so interesting does it how much memory does he have was it infinite you know the word zero I mean it chews but my point you know this freedom here but what I'm saying here is Molly's are great what you'd call you know waveguides like in electrical engineering it's a great stopper for the wave the wave Gide I think all that stopper is it has a word for it terminator it's a great terminator so you can put that null a locator at the end of a chain of attempts of allocating memory at the end you say the hell with it I don't want to do I'm gonna use them a locator here and it's a great composition device but you know what that wasn't my next slide so can somebody tell me why next slide was the C the next simplest composable allocate that you can imagine huh slam that's very advanced so simpler I have a pass through what does he do it passes okay so let's let's kind of get a bit just a bit more sophisticated so this is a let's say it's a bit too simple now so a stack yeah but here's what I think we can do for back for back is this guy has to allocators anything any allocate is including an ally locator and that the knowledge is going to give you the pass through John so the for back alec is going to try the alligator number one and if that doesn't work it's going to try a locator number two the simplest composable alligator it knows how to try one and then try the next great let's design this guy and see what happens it and you'll see that once we start with composability the rest of the primitives are going to write themselves they're going to define them said that we will have no choice we will not have to be intelligent and that's a good sign right now I'm not kidding actually to not have to be smart is a great thing in software engineering right because it means you're you have the right frame of thinking at the right frame of reference and there's only one way to follow the tunnel right when I have too many choices like oh I could use this I could do that I could do that let me be smart about it right so let's pull this start putting on that string and see what our revels okay so I have an alligator as primary and fallback and they know how to allocate and deallocate memory and I'm going to use private it is because kind of it's got a fin on the slides I'm just going to kind of use private inheritance here although I could use membership and stuff but actually inheritance is nice because it gives me that empty based optimization thing so I shall use it and I have two primitives allocating the allocate this is all I know how to do who can implement allocate for me it's easy right so let me try float back allocator allocate you give me the size I'll give you a block back I'm trying the first allocator primary and if I didn't get a pointer I'm going to try the fallback okay I'm going to return the block so three liner do we know how to delegate this is like you know do these pants with my butt big right it's a trick questions friend it's a trick question friends it's it's tricky how can i implement the allocation with this setup huh dress trick you can't you can't you can't you gotta pass what you got from allocate you can't pass something wrong into the allocator right awesome I'll repeat yeah I see what you're saying so essentially you can queried with the primary allocator has a range of addresses that it can possibly return that kind of stuff yes extra crap so I got a essentially like my conclusion is where we found to deallocate this is API with allocate and deallocate is not enough do you agree with me again this is consequence the decision have been made when we wanted to have a composable fallback a locator and now we're dealing with what came out of you know we threw the Dominus on the floor let's you what so we gotta have a new primitive here which is called owns and also could the range check to do whatever ownership test but at the end of the day the primary locator must be able to tell whether a block came from it or not and only with that knowledge I'm able to implement the allocating it goes like this if P owns the block then PD allocate the block otherwise the backup the fallback allocate is going to deallocate again a four-line are very simple function but we added a new API primitive right so you know the primary key does must know how if whether it owns memory now question does the four back have to implement owns or not not necessarily but this you know it's kind of interesting like okay and another question is can this fallback allocate to this composite allocate of - can it implement on itself or not only if both so okay so you're doing my slides guys because this is part of good citizenry the fallback allocator is going to implement owns if both implement owns and it's going to do this Junction bit energy the primer owns it or the secondary owns it and there's no other way okay and you know that I love acronyms it is no there's never too many right you know what MD fina is it's a Latin word for let me let me see if I remember it even method ah method definition failure is not an error I'm not kidding so method if it means this in C++ if you write a method and if you never call it in a template class the tree is not going to be audible right it's not nothing's gonna happen you write the wrong method you don't call it and it's all good between friends right you get is the friend keyword somewhere so yes so the question was instead instead of implementing all sorts or as an implementation of owns right could a fallback allocator allocate a bit more memory and put right let me see that could even work what if the primary also always say both in the primary and the secondary allocate the boolean yeah we could do that but that's essentially that's time and space it's time and wasting on this implementation in space time wasting in the in the thing whereas in some alligator owns is a trivial one liner and I'm going to get there so the answer is time and space I it would be wasteful to do so for many alligators and also let me kind of specify here that very often was the fallback alligator it's going to be malloc like the last response of Kings is going to be like ah the hell with it let's use malloc and call it a day right and trying these strategies and stuff and any of the day English malloc ordinal allocate or whatever have have you but essentially is going to be unallocated as very dumb and doesn't know much about ownership so it's nice that the primary knows needs to know but the the Citiz the fallback doesn't need no buttons so alright um so suddenly I have a working system because I you know it's funny I wrote only two liners three liners for liners and something we have something that's working because it's trivial to write a stack a locator with what we have has a constant you know has a pool of data it just sits on the stack and it moves the pointer along when every allocated bounds the pointer whenever the allocated does nothing or bound the pointer back will get that and something we have something upwards because we have a fallback a locator that takes a stack allocate of 16 kilobytes and if that fills up when I use them a locator question can I do the allocation in the stack a locator who's with yes was qualified yes because we qualify yes everybody should be qualified yes because because depends on value the qualifier could be negative always right John your with yes or with no yes so it all depends on the qualifier excellent cancer volatile with qualifier so here's what I'm getting with this yeah here's what I'm going with this the allocate I'm gonna come back no worries so the allocate goes like this if the the pointer pointing to the beginning of the block plus the size of the block rounded up to the line month I'm gonna explain that in a second if that guy is exactly what my stack allocation my stack of locators pull ends then I can do the allocation in other words in plain language that means if this the allocation is that the allocation of the last allocation that happened then I came the allocate because I roll back the pointer but if it's somewhere in the middle I can't okay so with a stack a locator so whenever I allocate you move the pointer forward so behind this allocated space in front of is the available free space right so if there's it just so happens that some guy like way behind you once to deallocate memory it can't be done but if this is the last allocation that happened I can make a step back right so that pointer can move back no problem without without harm okay so we have a conditional the allocation which is interesting as as we talk like owns is trivial because it's like a very simple range test it's very cheap so we also have a new primitive which again comes from just looking at the definition there and we have a deallocate all that's very cheap and very risky as it were because it just goes resets everything and makes the memory usable again yes qualified question right yeah yeah so you don't need to you don't need to qualify but essentially here here's the deal at this level I'm only worrying about void star and size that's it no rats bodies involved that's true so at this level and it's kind of interesting so there's some there's something deep to this because many people approach allocation has a kind of object and everything matter but actually can isolate the two quite cleanly it turns out and then you can build a typed a locators on top of the on type allocators so let me give a few more explanations about the stack a locator because I think it's interesting um well that's okay gotta be really good with this you gotta have a degree so um it's very easy to use it because you just allocate stuff and you use copics it from my previous talk that um and you deallocate stuff and you kind of use it and all is good and it's this is actually a very powerful pattern this whole stack a locator bag by malloc because it turns out you can accelerate your application like 95% of all cases by doing stack allocation which is like super hot super great super awesome and it you know most of the time like you know web server whatnot your requests are going to be small enough to fit on the stack and you're still going to be have correct code because whatever larger allocation requests come about you're going to delegate to malloc and it's like a very powerful patent if you can actually make that generic this is awesome right let's look at the allocate function because I promised you a few details about this whole round to aligned who can tell me what run to a line does and what's the purpose of it stack a locator is going to move the pointer back a force in the in the buffer and it can't move like it let's say one to allocate one byte and I start with a stack like 16 kilobytes and let's say it's a line nicely to like word sighs now get one byte so I'm going to move the point the point I'm going to move from an aligned address to a line Andres plus one byte do you see the tsunami that's being initiated here what is it please the next allocation is going to be unaligned right how do you fix that yes you can run you know so there's a number of solutions and the simplest one is to whenever you get a request you run the top first thing and then you kind of allocate and if you start with rounded you add the round numbered math says it's going to work out right yes right so the question was why not being lazy about it and instead of aligning compulsively at the beginning of the allocation you kind of say well I'm going to align kind of fun of need basis right that's a valid solution I gotta say this that I don't see a big downside to it right so it's a good solution yeah I gotta have the type information I would say can't make it work so good point great so in this solution particularly I round up compulsively and I have a test for did I reach the end do I have room for this guy and etc so that kind of stuff great notice that my code is like not PTR compliant I will use null PTR and actually I'm using also like the brace initializers and everything but I do see a bug in this slide which is not Peter is not blue which bothers me to no end ok that's a bit of a bummer ok the second sort of I would say it's yeah maybe this maybe it's not the second way it's a very important pattern in memory allocation is a free list before we can the implementation who who could explain what the free list is and does yeah except from Fedor whom I know he's gonna yes it's not a fixed sized alligator oh it is but I mean I misunderstood sigh go ahead so you make a list of fixed size chunks and you whenever people ask for it if it just so happens is the right size you just give it from the list that's a list but not a free list the free aspect is interesting because the phrase has almost no overhead in in memory because it uses freed memory to hold its information freely who can intrusive it's a sort of an intrusive list how does it work yes yes the the free list enters in action when you deallocate that's why it's free list it's right so the funny thing about the free list is it starts empty it starts with nothing I know nothing but it has a backup a locator and the first allocations are going to go use the backup a locator but whenever deallocate the freelee's wakes up and comes and says ah is this the allocation of a very specific size that I care about and if so I'm going to thread it through a linked list to which I only have one pointer which is the head of the list and whatever an allocation comes about later the freeness goes huh is this allocation for this exact size and is my point or not now has have people freed object of the size before and if so is going to give you that object in all of one it's a very powerful pattern what are the downsides of a free list it never ends never all advantages you know you never give memory back to the backing story the free list could go forever so if you happen to allocate at some point a million objects of size 64 whatever you have for the free list and then you freedom the fries are going to keep them and it's going fragment your memory up to was ooh right another disadvantage Fedor so to summarize free list have better put it nicely have poor thread affinity awesome have poor thread affinity meaning thread allocates puts it on the global free list and other thread allocates and that the memory that was owned by a thread just a second ago you know nano second ago is going to go to a different thread and that's kind of weird that's going to have a cold cash and everything John what difference does it make if it's a different thread well what a chance of that that's why do you have to okay so you're kind of you guys are getting to something I was getting to anyway although there's no slice for it so I have no proof here but let me tell you this anybody who defines are free least a locator the first thing they do they make a thread local free list and that's the first line of defense there so you have like our thread you know and threads and each is going to have a mini free list and if those kind of don't work you may have a global free list or not as it's your choice so I'm giving you the engine to do that I'm not telling you how to do it right but this is an important point freely start contention intensive when you want to share them what's another disadvantage was really subtle free list another disadvantage yes memory fragmentation we talked about that yes oh yeah so it's intrusive and therefore if you mess with the already freed memory you're gonna miss your free list yes agreed okay right so it right so okay let me summarize you you guys got a slight with you know give like shorter so that in short it's complicated right I'm not kidding I'm not kidding so essentially free least have like really weird behavior depending on what's going on your system and sort of work what I wanted to to to say here the very solid disadvantage of free list which is non-intuitive is they are very cash adverse and people at when you first look at them they look great because like three days it's hot memory because I'm kind of getting from the free lease I'm releasing memory and getting back and it's kind of a great thing and actually that's not the case often very often free least are actually adverse to cash there I'm friendly to the cash and one one subtle aspect that happens is because of all those pointers that you have to write is your writing cold memory very often when you're free memory so it's it's not it's not the best thing because many applications free memory that's already cold and a good allocator tries to not write to called memory it turns out memory that's being freed is very often cold right okay nevertheless freelee's do have kind of they're great for small objects they do have great advantages so I kind of feel bummed a bit that we kind of dwelled on the disadvantage so much they're actually very fast if you stand right so let's do it so I'm going to template on our what's class a the first template parameter it's my parent allocator dialog the allocated time I'm sitting on top of with my free list right and this is generic so it could be any other allocator including malloc including a stack allocate or whatever right and we have a specific size that the list is interested in and the allocate function actually you can see that cursor if you squint really hard it's next to public right now you see who's got good eyes right so it's next to public right now so I'm going to move it slowly and I'm going to show you this is allocate um so if it just so happens that the size is the size I'm interested in and if the root is not null then I'm going to be able to return the next item in the list and this is a really quick operation it's all one and slice otherwise I'm going to allocate from the parent so this is my a location function the allocation function is um if well if if the length of the block is not my interesting size then I'm going to delegate from the parent because there's nothing to do but otherwise I'm going to essentially like do that trigger with writing at the in the first word of the memory that's being the allocate I'm going to write my next node and I'm going to maintain the single list are singly linked list that way which is great again it's a quick operation alright so there are few obvious improvements to the free list a locator such as I want a tolerance between Mir maximum for example if my free list is very good at allocating one kilobyte one kilobyte chunks right and you're asking for 900 bytes should I give you a little leeway there maybe I should write so I should have a tolerance I'd you know anything between 512 and one kilobyte is going to go in the free list of one kilobyte and people do that actually right so this is great it's very easy to add to allocating batches what's that idea allocating batches yes right so instead of allocating one object at a time I allocate a bunch of them and I'm threading the frillies through them even though it's contiguous and then I'm going to have a bunch of objects and it's going to cost me a lot less what's the problem there it's hard to detect when you can be allocated that big block right so that's it's kind of more difficult and a very interesting optimization is at an upper bound no more than top elements to the free list because you don't want need to grow infinitely so this is kind of a very good line of defense against that kind of free leads that go awry so you can say you know what I'm going to fix my free list to one thousand elements no more 1,024 whatever and then if you go beyond that you saturate the free list and you're kind of done accumulating in it and that works great and it's simple to implement okay so with all you know with everything that that's being said here's what the realistic free list looks looks like it has a parent a locator it has a minimum size in this case 17 it has a maximum size 32 so that's my tolerance between 70 and 32 are going to keep the objects in the free list and I'm going to allocate eight objects at a time because I saw I so can and I'm not going to remember more than 1024 one kilobyte element a 1 kilo element as it were and that's my locator ah how do you free the individual element in the list when you allocate yes oh you put it back in the list you're never free it means for any requests between 17 and 32 I'm going to allocate 32 bytes and okay the other upper bound you may be referring to is the 1,024 which is the top the maximal length of the free list right okay so this sort of more realistic free list and it's not difficult to import it's it's a good chunk of work especially this whole allocate at a time it's kind of a it's difficult it's not easy it's not trivial but it's feasible and the nice thing is now you have a free list in your hands that you can use with any other allocator question can i layer a free list on top of a stack allocator yes and it's going to kind of be in an interesting device because it's going to give me the ability to free things in the middle of the allocator if they are the right size so there's the there's compound interesting here right I'm gaining composition strength here right great how about an affix allocator this is an absolute classic memory allocation whenever you whenever people do a kind of advanced allocators they they kind of parasite another allocated I kind of add a bit of a few bits of data before and after the block what's a good use of that electric fence like you put like you put a signature here put a signature here and when I D allocated the signatures are not correct you kind of say oh there's a corruption there right so you can check you can instead of like safeguards you can put one kilobyte before and one kilobyte after large chunks and verify that when did the allocate they didn't write to those chunks right so people do that so you have an alligator that knows how to parasite a so they're going to sit on top of a and they're going to allocate before every allocation they're going to put a prefix object and at the end of the every allocation they're going to put a suffix object which by default is void meaning nothing and that's a great allocator to have as a composition device so you can use it for debug stats info actually what I've seen people use this for very nice is when every allocate memory you store in the prefix of the block the file and the line that requested memory the awesome did you see like Chandler's talk this morning right the plenary talk that's awesome because it showed all these great things with perfect and ooh even though people who use OSX they don't have it they kind of kind of write on Windows I'm sure they have like good tools for that yes we work for Microsoft oh yes that was an affirmative so Michaels are great tools and probably they're more visual as well UNIX has this perf tool OSX has nothing which is a bummer but anyhow do you know all of these great things you can see with perf you can't see who's asking for memory in Perth you can't it's dark matter you can't see with this kind of stuff you can so you can actually insert you can plop the file and line the requested memory and then when you free tick oh so this guy would this line in the this line in my 1 million lines program is the top contender for memory allocation this is awesome it's great information a fix a locator and to wit a very simple use of I fix a locator is an alligator that collects statistics like pass it flat was that this is I'm interested in and it's going to collect statistics for me so it's going to be how many calls that I have to allocate how many calls to deallocate and all of these nice pieces of information I can have per allocation data as we just talked I could have global information and I can slice and dice it after the program has ended any way I want it okay how long do we have well what happened to the five never telling me where were the 15 minutes five minutes deal okay the most interesting part of this talk you're not gonna hear it okay thanks five minutes so after this a break can I eat five minutes into your break okay I'm seeing like a couple of folks are literally sleeping so I don't you know I don't have an opinion you know I'm gonna sleep anyway so okay so very nice trick and I can't I can't not even though I'm not gonna go through the slides don't mess up my review because this is nice thing even though it's not in the slides here's how you can greatly collect information about memory allocation you write a macro you know that's gonna you know allocate with all capitals or whatever and inside the macro you put static-charge a con star star this file static unsigned int sorry int long line okay I'm trying to be politically correct here and then you put a pointer next static data okay and then whenever you are allocate and stuff you're going to update some statistics all of which you keep in a static structure this is my point is so static but and you have a pointer to sort of the next static piece of information and here's the thing you build up you compile the program and at the end of the program essentially have file and line information and a singly linked list that spans all of these places where information has been stored which is static data in your program and you can iterate it and get information with no dynamic allocation at all so again just to clarify so actually don't say static you define a little struct and you make a static instantiation of that whenever allocate memory and you collect in in there and these guys are going to assemble in a singly linked list and the whole thing pointers and everything they all point in static storage and without allocating one byte of memory of memory dynamically you collect at the end of the run we have a pointer to the being of the list and you thread you have all of your data right me male if you want details about this because it's awesome okay so now how many minutes 10 okay all right bitmap block this is a very good allocator because it stores one byte per block the one bit per block of information so have a hunk of memory and you say I'm going to organizing this guy in blocks of 64 bytes for every 64 bytes you're going to have at the beginning of the block one bit which tells you whether the block is occupied or not they have metadata one bit per block and then you have the blocks contiguous right what's the great advantage of the scheme yes get rid of all the disadvantage of free lists you can you know it can allocate any size because the arcade several blocks you store the metadata in a separate place which is always going to be hot this is a recipe for great things in memory allocation store metadata elsewhere than the data so you have the bits and there's bit operate like CPU constructors have been working hard on bit operations that are fast and you can do like sim D and all these good things on the bits there so it's pretty awesome so this I highly recommend this what are the disadvantages because there's never like only advantages these advantages huh yeah so you the block size is going to be like a sort of a he's gonna have internal fragmentation right it's going to allocate more than needed right because of that so um there's never a thing with only advantages right and also like multi-threading is weird you can't really add those bits are kind of messed up if you try to share like there's all the staring and stuff going on so anyhow I highly recommend this and there are a few more exotic alligators which I think I think you know like so cascading allocator consider I have a bitmap block but the big mailboxes sits on top of like one megabyte block so I allocate one megabyte and I'm sitting I'm I'm plopping a bit one of these guys on it and it knows how to organize that that megabyte but then I'm running out of them I'm done I'm allocating more than one megabyte what should I do next allocate another megabyte and organize that guy as a bitmap block and continue this is the cascading allocator it's going to allocate lazily as many as you need right and it's going to cleverly deallocate when you no longer use them and there's a fair amount of logical in there but it's very it's very coherent not difficult to do another very useful allocator is the segregate err what does he do quick without with zero minutes what Purdue said that thanks Marshall Marshall so we should you guys can't have Marshall answer every question here so everything less than or equal to the threshold goes to a small alligator everything greater than the threshold goes to large alligator period done any Jolla Gators will work awesome this is composition for you and these are each they take like 50 lines each maximum except for a heap data that bit block thing is like much bigger but these are simple and then you compose them in ways that you couldn't imagine so with this guy this is like an absolute classic memory allocation I have a small I'll just go for this this alligator blood jobs go to this guy and this is how the history writes itself right so these are very good do I need bones for implementing this guy no because the size tell me everything size tells me what I need to do it goes right so no problem there segregated is self composable you can compose with itself with another segregate ur and here's how it goes I have a segregate everything smaller than four kilobytes goes to another segregate err which in turn uses a free list for everything's more than 128 bytes and some medium allocator that I so define or everything bigger than four kilobytes goes to the Mallo cater in fact if you compose actually a good allocate is maybe 16 of these aggregators and you know how you organize them you're gonna is like in a binary tree binary search kind of thing you don't surface linearly for size you're clever about it you put that you know you layout the code by the binary search so you look at the code then you see oh this is this is optimized for these sizes right and actually that so there's more philosophy to this sometimes you do want the linear search because the smaller sizes are both more frequent and they're also like it's you know if you allocate a big chunk of memory you're going to do a lot of work with it so you can afford to be slower so there's a lot of philosophy that goes in there but it's up to you that's what I'm giving you the tools you use them bucket Iser and probably this is the last one that we're going to talk about what's the bucket Iser do just by looking at the definition bucket Iser I'm organizing yeah I use the buckets yes thank you very much all right so between sizes minimum maximum known at camp during compilation I with a specific step I'm going to for each category of size I'm going to have a separate elevator right so I'm bucket izing the space the size spectrum they're very useful this is actually a very simple optimization a very simple version of the bucket eyes is one that does logarithmic growth this linear logarithmic everything like the first power of two second power of two and so on right all right with this we're done friends because most everything you see about memory allocation is covered by these simple patterns almost everything I'm not kidding so this kind of we're done with the subject which is very cheesy because we didn't do a lot of work and you know we like being lazy like you know filler said why don't you do it lazily yes let's be lazy all the way right so we're kind of done here with the domain of memory allocation with remarkably little code and remarkably little smarts we just wanted to do composition and we followed the thread so let me tell you a bit more about the entire this is a realistic example by the way so as I said you know this realistic alga is going to have a bunch of these strategies composed together but let me give you the complete API just a minute so this type here that I found works for everything we talked about and more actually so we have a steady cost expert this is a my alignment via alignment of the allocator we have a primitive called good size which I give you a number and you give me the size that you are going to allocate anyway usually the number rounded up to the next allocation size very useful because I can actually when you do vector stuff you can say oh let me allocate the good size for this guy anyway so I can maximize my use of memory right so I have good size very useful primitive we have the allocate and we have the allocate primitive we have an new primitive called allocate all which is great for stack allocated yeah you don't use that with malloc actually the malachite that doesn't soup doesn't implement it doesn't define it right it's not there but with a stack earlier you can say allocate all and then organize the free list or whatever on top of it expand I want to expand the block in place reallocate I want to do what we Alec does on so we talked about it the allocate obvious the allocate all which is like allocate everything in all one we that's the line one thing you got to do it people do that it you need it for games who doesn't play games right yes so you gotta have aligned allocate so therefore it's in the API it's a necessary evil people need that you have Alan you have primitives on posts and windows you just wrap them and you're done finally getting their reward okay doesn't want to go forward all right so what we talked about here so first of all we destroy it's the delegator because it doesn't composition whatever you do it has it knows nothing about composition right and as I argued composition is everything you should care about in memory allocation writing good allocators is all about good composition okay so fresh approach from first principle would be to design an API for composable allocators that are simple and work together well in any way you want with what you saw you can implement pretty much any we can you can do anything with regard to memory allocation you can fly right so don't try at home right you know there's a professional driver close core said in commercials right you can't do anything really so understanding history is great because I couldn't figure out why a locator was a fail until I understood its history because you look at it has a low key has the allocate has constructed destroy it has everything and it was difficult for me to get away from the frame of mind in which it exists therefore it must be good to the point where you know this may be a mistake and let me see if I kind of clean my mind off of everything let me see if I can do better right and better me is composable okay with this I'm seeing people are like okay the hell with it I'm going so thanks very much I'll be here for a few more minutes

Channel: CppCon

Views: 140,376

Rating: 4.9407268 out of 5

Keywords: Andrei Alexandrescu, Programming Language (Software Genre), Allocator, CppCon 2015, Computer Science (Field), Bash Films, Conference Video Recording, Event Video Recording, Video Conferencing, Video Services

Id: LIb3L4vKZ7U

Length: 72min 27sec (4347 seconds)

Published: Tue Oct 13 2015

Reddit Comments

[u/acehreli]

This talk is related to his DConf 2015 talk.

[u/nealio1000]

This guy is one of the lead developers for Dlang if anyone is interested go to http://dlang.org/

[u/srnull]

Yes, somewhere in this 72 minute presentation that happens...

For those of us who don't have the time to watch random hour-plus videos posted to /r/programming the /r/cpp thread has some details about the presentation. That'll help inform if it's interesting to you or not.

[u/jtredact]

Ohh here we go again.. more allocator insanity. One day this guy's gonna break computing with some logical paradox

[u/way2lazy2care]

I'm pretty sure I could watch Andrei Alexandrescu talk about anything. He's got to be near the pinnacle of technical presenters. If I watched anybody else give this talk I would be asleep in 5 minutes.

[u/sellibitze]

Here are the slides.

[u/apatil4]

Very good talk. Thank you for sharing

[u/malaggan]

This is basically applying some functional programming concepts to the design of allocators. Monads and combinators.