Memory Allocation Explained: Best Practices for C++ Programmers

[00:00:09]hello today we are going to talk about memory allocation and what we think every programmer should know in particular we'll be talking about our experiences and lessons learned using general-purpose allocators such as malloc over the last 15 years designing custom ones and talking about the memory management bugs we helped fix so I'm Sammy al bara co-founder of a company called factories or rebuild debugging technology but beyond that most my career has been performance and reliability at various places and in academia as part of the George Washington University high-performance computing laboratory with me are Hannes and Paul hello I'm Hannes I am working with Semyon the debugging to China back trace I have a lot of background in networking where I previously like worked on the Linux corner stack and basically otherwise like switched around between languages quite a lot in the past time Ryan and Paul Kwang I used to work at Google and Nexus now I work somewhere else and in I spare time I also had concealed by common list I'm actually a whisper and unconference you get it that's how I met Sammy all right so thinking one thing that's very important as we entered this talk is that quite does this matter one might think we've been allocating memory then we dynamically for I don't know 60 years now this should be a salt problem turns out it's not and just switching your memory allocator for say this example my sequel 5 shows that you can have very different scaling and performance characteristics for different memory allocator for the exact same code and this is a hard problem because memory allocation is a very multi-dimensional problem as we will see so there's always trade-off and there's no like one best solution here all right and so the general interface for our memory allocator will be like malloc or free on POSIX or Windows it's heap out and he free I think what's important to see here is that the only thing we can do is pass a size get a pointer do whatever you want with it there's no more information and then at some point you're done working with that data and you pass it back to the allocator and given this I would say anemic interface the memory allocator is in charge of tracking what memory is currently available what is in use and so that when you make an allocation request he can go back and satisfy it without asking Bureau as for more memory has to make sure that it plays out your objects efficiently in memory so that you don't run into performance defects either in your hardware or in your operating system and it is not allowed to move objects around once you get an address from malloc for he bag it's there until you free it you kind of stuck with that decision and that's what makes it at its core the hard problem also very important if you mess it up there's no guarantees here all right so Sammy let's go so this is a it's it's actually a really hard problem the interface is simple but there are a lot of challenges in building or general-purpose money alligator so let's go into a little bit more detail as to some of those challenges one of the biggest problems is memory utilization your memory allocator needs to ensure that you are not wasting memory and one of the biggest issues in memory allocators is fragmentation over time blocks of memory are either too small or too large for the allocation requests made by the program and generally speaking there are two types of fragmentation that we care about one is external fragmentation to have blocks of memory available but they're too small for the size is requested so in the diagram here every block for example could represent a page of memory that's a smallest granularity in which your memory allocator can request memory from the kernel and the blocks in red are unavailable so in the third row sit down scientists look so in the third row here for example these blocks are available and an incoming request comes for three contiguous blocks that cannot be fulfilled because there there aren't three contiguous blocks available so then it would have to go back to the operating system to request more memory the other kind is internal fragmentation so the allocated blocks are too large for the reallocation robots so imagine you have all these available blocks you know per questing' you know three eight by allocations and you end up taking a page for each allocations and this example you have a lot of internal fragmentation a lot of wasted memory the other challengers allocator itself needs efficient data structures to be able to quickly determine which blocks of memory are available or in use and if those data structures are overly heavyweight they can contribute to in trouble fragmentation signify so very naive very allocator may for example just have a you know a simple fat linked list intrusive linked list of all available chunks in memory imagine the linkage of this intrusive linked list is something like you know eight bytes or sixteen bytes in this situation or talking about for every eight byte or sixteen byte allocation you have sixteen bytes of wastage on linkage and that could be fairly significant so the memory allocator does have to take this into account with respect to the data structure is used internally the other key design decision that a memory pallet memory allocator has to make is decisions around placement policy so how should it which blocks of memory should actually be utilized for any incoming request so similarly here we have these available blocks they have some incoming requests for you know a bytes of memory B bytes of memory and C bytes of memory your allocator can choose you know many different options with respect to which blocks of memory end up being utilized for these requests this can have pretty serious implications on performance for your program and it can Wadley vary between memory allocator is we have a very simple program here pretty bare-bones or we allocate space for three strings and then print them using printf and you can see within popular allocators today there's a good amount of variants so you have a which is you know Paul B Hana C me and you can see that the different allocators will play C's on different cache lines different pages and cetera et cetera and as you'll see later in the presentation this actually has can have significant implications for real-world workloads the sad reality is there is no perfect placement policy you're always gonna have an adversarial workload which will play break the place the in policy and this is something that alligators have to live with so there isn't one alligator that's the best for every single workload out there now a lot of these issues around fragmentation are made easier if you could actually move objects around the biggest challenge in cc+ course is these addresses have to be stable people will play things like pointer encoding tricks and succor etc up until recently people thought this was impractical if you'll get the literature everybody's like oh compaction would be great but it's not an option well it is an option and it is practical if you're interested Emory Berger who's prolific in the area of memory allocator research is giving a talk at CB v con this Thursday and you can learn more the graph here displays impact of fragmentation with Firefox over here you're running mesh which is a compacting memory allocator and the red is default je malloc memory allocator so firefox switch from system alligator to j Moloch there's a 20% reduction in memory and then we see another 16% or so reductions which linked you to mesh the other big challenge is multi-core so as multi-core became ubiquitous both the placement policies and all the support mechanisms backing them required major design with the revisions thank you so the first issue was to you know standard scaling issues as we went from a single threaded memory allocator to a memory allocator that had to be Fred sake so if you go back to the very beginning overly Dipsy all they did was slide the big walk in front of it then so i recreated that set up on a recent computer and what we see is that for each like malloc free pair if you have few threads constantly allocating and freeing memory 1 allocation one free takes roughly 50 mil nanoseconds if we reenable the Fred caching mode that is now standard in the C malloc that goes down by a third by 2/3 to 17 nanoseconds for allocation free pair so given this data you might say well you know just move everything to be or a thread it's gonna be much faster and yes it's true right if you essentially eliminate contention by giving each thread its own private key it's gonna be fast but it's gonna be very wasteful in memory because you can't recycle memory from one thread to the other so we kind of have to look for a happy medium and there are two options here but like BT malloc or older Lipsy malloc we just had this small fixed bounded size cache in front of what is sell at global he and then more recent alligators tend to go for multiple sub heaps but a fixed number of them and then you multiplex threads vehicle here is just to not eliminate but greatly reduce contention more interestingly to me I think is that the memory placement also becomes a harder problem because there's a bunch of sharing issues at all sorts of level of memory hierarchy we get fall sharing in a cache line but we also even have a similar effect if it's just read-only data that it has to figure out that you know there's the l3 cache is still valid then it has something else with when you share data on multiple threads on the same page and finally with Nemo placement and we'll touch on that later right and here's a new impact which I don't think I've seen described a lot or ever in the literature when you map memory or you grab more physical memory from the kernel that tends to be fairly fast right that's constant doesn't really matter how many threads are running however when you unmet it but we should observe is that as you run the same process with more threads either on more cores or even fewer course but more sockets this unpacking operation becomes much slower that's not just for unmad thing it's also just what should be faster release like m advise free or don't need syscalls so what does it mean for as well as we increase the number of cores on our servers like say we have a hundred and twenty eight Hardware threads on one socket with AMD epic to now well you see the expect allocation rate just a to scale roughly with a core account that's what we want more threads but then I decide to say that means the allocation rate will also scale with a core account and we just saw that margin of the allocations individually scale linearly the core cow so to me this feels like as we increase the number of hardware threads in our machines we can expect to hit new quadratic scaling bottlenecks that wear until now never an issue all right so at this point we probably should point out that validation is hot so whatever you basically do and how you try to validate your assumptions about like malach performance in a particular setting for example a production workload it is like probably never really going to work out that you can simulate or reproduce it like for example on other hardware in other settings with about configurations so you basically always have to end up trying to test in production or like at least as close in production as possible so I can name some examples where this happens particularly badly is for example most of the common production alligators tune themselves by the giving of CPU numbers so as soon as you increase like the number of CPUs you get different results also nowadays it very much depends on how you for example with the number of CPUs because sometimes in containers containers can actually limit the number of CPUs you actually use so during sudden in a container and your container uses a different or wrong way to reach the number of CPUs you probably like overestimate a lot of like settings and you are in your location other settings also play a big role like for example optimizations that the compiler does the version of the operating system etcetera etc another thing I guess I need to point out here because I was probably selected as more like security person here is that in general like we have memory management parks in our code and we somehow need to cope with them and Sona so nowadays it becomes more important that we actually are able to at least like limit the effects that memory management errors have for on us and don't give up don't give attack us like more tools don't give attack us more tools to actually be able to exploit them my view per example one example they are like a few years ago it was possible by a one-bite overflow to actually like have a local root exploit there you know some application that was set UID huge was able to execute code I love that take us control and the basic problem what you'd see for example here which is metadata layout of gilepsy one of the most like used one memory allocators is that you basically intermix the metadata of the allocations along with the allocation itself and so if you have an overflow behind like allocation one for example or allocation to you basically hit or can overwrite data which is part of the metadata header of the next one location and given that memory a locators are quite complex nowadays and you actually have for example in the case of the free chunk a lot of fields that you can write to you could actually create a lot of havoc and depending on like how you layout your fields it was possible to actually like run code because of this particular problem the problem here is that basically to to validate your heap you need to like have a consistent view but this is like not going where as the performance people who try to try to separate the heaps to make it faster for example in terms of to to not destroy caching behavior you basically can see a diagram which doesn't really point out what I try to say the more security guarantees you try to give the more in this case memory footprint for example you actually have to do this is for example like other Canaries or god pagers need to be inserted slim guard probably is not like a really used one a locator so it's hard to say if it actually like achieve is the goal of like low memory footprint low no performance high performance and high security guarantees but there's a trend that basically the more security options you add to a navigator the slower it performs or the more memory it uses [Music] so cool so we we just discussed some of the key challenges that comment building and allocator so this includes performance issues around CPU time around memory utilization multi-core challenges security challenges etcetera let's dive a little bit deeper into the sort of common design patterns of allocators today and once we have sort of a deeper understanding of those design patterns let's look at anti patterns that are quite common in the real world so one key design principle of most general-purpose so many allocators is they will have different code paths for different sizes of allocation so this is rooted in these three common assumptions one larger allocations who are less frequent and have a longer lifespan small objects are more frequent and have a shorter lifespan and objects are the same size they're usually allocated and destroyed together the third point it actually is an assumption that a subset of the popular alligators today make the first two are pretty much Universal and let's see what what this means and in the real world we have a stupid little program here where we time how long it takes to malloc and free different size allocations in this case I'm using J malloc master as last Friday but this is this same principle will apply it to TC malloc Lib C the C will just be like two steps and you can see basically here in J malloc and if I scale this further you'll actually see like four step functions so there's a specialized code path for smaller allocation the different code path for normal large allocations a different one for huge allocations and that's something that you should consider when you are allocating and deallocating memory a common mistake people make is they will have frequent large allocations with short lifespans so these are expensive to allocate because they do require an expensive syscall to request memory from your operating system so most allocators will have some threshold which one succeeded in in terms of the size of the allocation will go straight to your system Colonel to request more memory they also involved slower data structures that are typically global which has implications on multi-threading as well which we'll get into later and ultimately it is just more memory someone has to zero and there's a cost to that and it does end up thrashing your cache as well it's expensive to free for many of the same reasons so an interesting thing here is on multi-core doing that unmapped becomes excessive excessively more expensive and there is also a fast path to go straight to the operating system to deallocate that memory in addition to that for some allocators particularly in unix land alligators are relying for s work even for primarily for smaller allocations generally there's a threshold there it can be a major contributor to fragmentation here is an example of of what that fragmentation could look like so this is allocator this is a state of the heap you have 8 by 3 8 byte blocks here which are currently unavailable a Meg block and then another 8 byte block someone calls free let's say we decide to you know in some sequence of fries the alligator decides to coalesce these free blocks the coalescing is coalescing splitting are the main ways an alligator will help manage fragmentation they will coalesce and split free blocks so it decides to cool let's use 3/8 byte blocks into 24 blocks and then we malloc 32 in this situation it would be force to split this is splitting typically is more expensive than just a single step there is a cost of coalescing and splitting so in this situation alligator either has to pay the cost of coalescing and splitting or it will have to allocate more memory this can end up creating large holes the other challenge with alligators that are using s break is basically the heap only grows and can only trim and a lot of operating system we reclaim memory in the top region of the heap so what can you do about it 1 don't do it the other option is use a custom alligator and we'll talk about situations and situations where custom alligator does make sense there's a lot of situations where it doesn't make sense some memory allocators will have two nobles in there so you could alleviate some of the side effects so in the case of glitzy Malick's or the default malecon most linux's you have the MMF threshold Milaap which specifies one it should use em map of rest rate the benefit of using em map is a good on map just at specific mapping and you're less likely to have fragmentation you also have a trim limit for the top of the of the heap which you could tune and then last but not least some allocators if you can afford the memory you can also increase the threshold for when allocations are are cached another common auntie pattern that we see and some of you may be familiar with this while going to the details why is I see this quite a bit where people will malloc memory and then mem set in there like oh you know the cost is it's cheap it's just a cost of freeing that memory of writing that memory we're gonna write it anyway etc you can see the time to execute here with this malloc mem said and kalak is pretty massive and the reason for that in particular for large allocations is most things are demanded so you always want to use catalog so for example your operating system will have something called zero page there's just a physical page of memory filled with zeros right it'll allocate a set of virtual via VMAs for you virtual address pages and only when you write to that page will it actually allocate a physical page of memory for you so that means you could you know malloc you know ten million and it won't actually allocate the physical memory for you until you write to that memory and this is actually why you have this big disparity between the two this also applies to 0 to small allocations as well not all alligators will take advantage of this but for example Mac OS will not necessarily zero a freshly allocated memory and there is a performance differential associated with that cool so the other thing I wanted to introduce sort of a key design concept in a lot of alligators it is a notion of a segregated felis so a common assumption all of them will make it small objects are more frequent and have a shorter life span so generally speaking there's going to be a code path that is optimized for these objects so typically you'll have a Kashi that the thread level or something at the you know Arena level or heat level depending on your alligator which stands and which is used to fill full fulfill all incoming allocation requests and so you will have some kind of cache of the recently freed blocks in memory allocations who will be fulfilled from there when possible the the challenge there though is determining which free block to use and there are many strategies to this generally speaking one of the best strategy is to have something that's best fit and address ordered what that means is for example let's say I wanted to allocate I had an incoming allocation for 16 bytes of memory we walked through this list right and we'd be walking through in linear time we could use this 32 byte block but then you have a lot of internal fragmentation all right you're wasting 16 bytes of memory so a naive implementation we do have to walk through this full list to find the best fit or would have to use expensive index data structures that high constant times to be able to to actually fulfill the lookup so what a lot of allocators do is you will use what's called the segregated free list so pretty much every modern alligator today that is thread friendly will have some notion of a segregated free list at least at the thread cash level and basically what this means this is a great approximation for sorted best fit and what this means is you know allocation will tell you get rounded to the smallest size class that fits the request the size and then that relevant list is scanned so the other interesting here thing here is which is quite obvious is some alligators will actually utilize this on the allocation path as well which I'll again just shortly but typically you're at you know if you're allocating 7 bytes of memory you're allocated will typically round that up to a size class or some alignment so in the case of glitzy for example it'll make sure that everything is aligned at at a boundary and you can see for smaller allocations pretty much the smallest allocation size okay it's 24 bytes and that's a side effect of internal linkages which Honda's referred to earlier for how chunks blocks of memory are managed within Jamela within PT mark with something like J malloc or TC malloc they will actually apply the segregation for allocations and storage selection as well and so having knowledge of these size classes is even more important so in the case of PT malloc it just means that you won't be able to properly utilize the segregated free lifts in the case of J email not to soul manifests as a lot of internal fragmentation this is a pretty pretty business pessimistic example because I'm making allocation requests that are multiples of the size of three right so let me jump into the notion of slab allocations so I mentioned that some allocators today will make the assumption the objects of the same size they're usually allocated access and destroy together in other words you might have a linked list of type and you're going to be iterating over that linked list of type n there's a lot of localities so make sense to allocate them together generally there are two basic schemes that you'll find in allocators today this is a gross simplification one is a slap like scheme so TC malloc J malloc work this way the map that's allocated will have an optimization for tiny allocation sizes which is similar and essentially it'll pre initialize pages for the same allocation size so let's say I have a new 16 byte allocation coming in it would initialize a new four kilobyte page of memory for 256 16 byte blocks schemes glitzy will use something that's closer to a bum pointer scheme so it'll allocate new blocks from the current page on a first-come first-serve basis this can have drastic implications on the performance of your application especially if it iterates on dynamically allocated data structures so there are a few simple patterns you can follow to avoid this let's look at a simple example I have a high-performance key value store called Dongo DB and the backing data structure of dango DB is a giant linked list so this is a linked list of sixteen million nodes which contains two fixed length allocations the key is 34 bytes and the value is 64 bytes and we just want to iterate on the key in this situation and you can see there's a huge disparity between clip c and j my lock in TC malloc j malagant assume a lot generally we'll have very similar performance profiles J mallet is better about purging memory so the reason for this is the fact that the bottom pointer scheme will place allocations kindig you lessly while the slap scheme will place allocations continuously by size class and in this situation we have at 32 by allocation 64 by allocation and then another 32 by allocation for the actual linkage to node and so you'll end up with a memory layout that looks like this so on most modern hardware that we care about today you're looking at 64 byte cache lines and basically what this means is for the glib C implementation you're looking at a node every 2 cache lines with the values I care about while in something like J email akamalik etc you have two nodes per cache line and sort of a word and a half you can preload some some memory of the next word so you have a lot more data density and it's a lot more memory friendly of course there is a pathological case for slabs you're using a lot of you know variable length allocations in your data structures you can end up really thrashing your TLB right because everything is fragmented across so many size classes so key takeaway here is factor access patterns in your allocation sequences especially for read mostly data generally tried a couple allocations close to where they'll be accessed variable length allocations can be pessimistic a common mistake people make is they just assume Oh fewer Malick's is better for performance that's not the case with allocators like J malloc TC malloc if you end up have everything spread across a lot of size classes that will be bad for your TLB the fundamental reality though is you know if you really really want to optimize this down to you know you want to squeeze every cycle out the Mal'akh interface itself is inherently limited in its ability to express relationships between allocations so there are alternative interfaces that attempt to addresses but basically they all have significant limitations some cool work that Alexander further over did or Fraser University is providing an alligator interface allows programmers to specify the relationships between different allocations and one thing they were looking at is utilizing PMC's to automatically extract spatial locality I think one thing that would be very cool you know is for federal and Emory burger to talk would be awesome to see the techniques in mesh applied to some of the work that she's doing for performance all right the other thing I want to talk about briefly was growing a region of so most of us get it wrong but some people do get it right FB vector is a perfect example of a data structure that does get growing memory correct so a you know one mistake obviously is this growing by two has implications but one of the keys sort of secrets to FB vector is it is aware of the underlying alligator so we'll make sure that the capacity is always rounded to alligator size classes so blocks are fully utilized you don't have this internal fragmentation and it uses alligator extensions to grow in place and you can use these extensions yourself as well so TC Mal'akh has a few of these J Malik has a few of these unfortunately glitzy does not have anything here so in J Milwaukee F now lock X which given the size of an allocation that'll be turned back to you how much memory you would actually allocate for that size right the other thing it gives you is an alternative to be a lock which allows you to basically be a lock in place so let's say Assad crossed over there is 48 and you do the from 40 to 48 it can probably grow in place I'll just return there are other optimizations you can also apply so just use now lock X to round up your allocation size class and then Excel X next to attempt in place resize and this is great for performance there's gonna be a whole bunch of other useful extensions you haven't heard of as well so check out your allocator documentation one of the down down sides of the Mal'akh interface is it's not good for performance every time you do a free your allocator has to look up all these data structures to determine the size of the allocation that is free and at least some of the allocators this can be fairly expensive so j-mac has an interface where you could pass in the size of the allocation to avoid that logo and c++ generally speaking you're gonna know the size of underlying types and this is again very cheap optimization you can apply to improve performance so check out your Doc's alright so a lot of what I talked about touched on fragmentation I wanted to just briefly talk about how you can detect fragmentation generally what this will look like is your allocator will request more and more and more memory from your operating system not all of it may be resident generally it won't be here's an example of fragmentation the real world from some application so it'll look something like this Jamie Locke helped improve the situation drastically for this workload how can you measure fragmentation so a lot of a lot of alligators today will have allocated statistics interfaces the ones I touch on include CPT malloc J malloc TC malloc cetera will expose this mac OS alligator if she has malloc info J Malik has malloc stats prints and in the case of malloc stats print they'll give you a whole bunch of stuff and they'll also give you how many pages were actually allocated and how many of those pages on use so you just take the ratio of these two approximate external fragmentation and it's pretty decent measure of that so this is what fragmentation look like for the back trace debugger running on Firefox internal fragmentation is more difficult to measure but it can be quite substantial so the only options I know if today are wrapping on allocations which is pretty coarse-grained or dot from palaburn so over you run dot on back trace the back creates debugger again and dot tells us this particular allocation and in this function each byte is written to 1.2 times each PI in the blocks are into 1.2 times an average and read from one point four one times on average this is saying that we are allocating a lot of memory and not using most of it not reading lots of in there's probably more digging to do common sources of internal fragmentation that we've seen in the workload so we've dealt with our dynamically growing buffers that are not resize to fit so a lot of container structures will have shrink to fit call that if you do have a static structure other thing is just internal padding and alignment so if you're on a platform that emits dwarf check out the PA hole tool it'll tell you about any blocks of memory that are being wasted for alignment or padding so in this particular structure for example there's a 2-byte hole that's not being utilized for anything any useful data d2 alignment so rejiggering the data structures helps with that a general rule of thumb here is try to order larger fields first in your structures and also consider the access patterns of those fields as well alright so on the topic of fragmentation I'll hand it off to Paul to talk about how we can make fragmentation worse thank you all right I've already mentioned the TLB a couple times the TLB is this cache that let's try to translate virtual addresses to physical addresses more quickly and the thing you notice when you look at current chips is that the size of your level one TLB the fastest level of that cache can cover in the best case roughly about the same amount of memory as your level two data cache so if you have like say a large hash table that is bigger than 256 J like much bigger than your level 2 cache when you try to read into it find your data sure you'll find to have it's fairly no l2 cache misses probably go to memory but you will also have to pay for memory translation that can often be almost as slow as servicing the cache miss itself so what do you do about it well we could use larger pages that way you have the same number of entries in your cache but each entry covers more data and we're happier the problem with that is that huge pages are extremely is easy to misuse one very well known cases at Redis that uses 2j now the alligator and if you're not careful with it and you enable transparent huge pages quality bits allocation will be backed by huge pages then it Forks tries to serialize its heap and everything goes to hell so and this suppose it shows how to disable transparent speech pages you can also use the same interface to enable transparent each pages on Linux but I don't think this is the right way to do it but you don't probably don't want to enable a transmission pages for everything on your system because again when they fail and they feel really hard so instead what we should be doing is use dedicated hooks and our memory alligators so if you use a lips email you can use a lip shoot GL BFS to enable large page backing data you have similar hooks for a TC mallet and for J email so you have to be careful that this is really far from free probably want to talk to the system and these training people because the best way to use huge pages is to pre allocate them at boot time to make sure that you don't have later fragmentation that prevents our application from getting to free pages it expects and you're also going to pay good external fragmentation which makes sense right if you have say one four kilobyte page it has to be kept in memory because of one ten bytes allocation or you're wasting four K if it's the same thing for two meg page well now can we say two megabytes of data and that hurts a lot more okay you've already mentioned that the multi-core pollution created new scaling problems for memory alligators here's a new one that is very common I don't know if it has a good name so I just stole this term that the HIV people use it's called alligator bleed and it says essentially what happens when you have a producer-consumer pattern for the producer uses heap allocation to create the work units passes then say with like a ring buffer to worker a consumer and the consumer does its work and then freeze that work unit so what's gonna happen with obscene malik right you have the allocator calls Bala gets working it dispatches it to in my case a 32 entry single producer signal consumer ring buffer it goes you to worker the workers there's nothing because it's a micro benchmark and immediately calls free how fast can we do this data loop turns out it takes one point four microseconds per item to go through this process and if we look at the other at the stats we can't even fully utilize our two threads like what's going on here so here's one way to fix this we could simply send the working it back to the producer on a separate bring buffer and then the producer can create itself and now we get three exit poopin and actually do no disc alias we expect from the number of threads the reason this happens is that when we free in the wrong thread we end up using the operating system as a cue to transfer these resources back to the out producer thread and that's gonna be slow much slower than a lot free ring buffer and it can also happen let's say with J Enoch which uses the same workflow but instead of going through the operating system uses its own internal locks data structures so what can we do about it the first one is that it's always obvious when it happens I don't have a very good way to pinpoint these issues but one thing we can do is just look at the thread - statistics for all these worker threads and if we notice that there's like a lot of allocation that are in the thread cache for a size that the worker doesn't really use this is might be the reason for for filling the thread cache with useless information once we do not answer problem what can we do to fix it like I said we could use an explicit release Q and send the allocation back to the producer - that the producer can free it and recycle the application itself how that's a bit error-prone and that's a lot more overhead to decoder so I like to simply a lot of times the worker will already have a notification back to the producer to see a done with this work so we can take it back on that and send the allocation back to the producer finally the best thing to do is do something you know do it right just don't transfer ownership like if you use ger PC the request is pass it as it cost reference so you know that the caller just always maintains ownership of the original request all right something else that happens with thread we already mentioned that in order to alleviate contention with multiple threading we use arenas so that's a lot of kind of private sub heaps and we have find a ton of threads to them the problem here is that each of these arenas will have their own allocation cache they'll have their own resources and since it's very slow to transfer resources from one arena to the other detents you just hang on to their allocation so if you have a ton of threads that go in one arena do allocations and then go to sleep for instance because there's no more work to do for a while or because they're all waiting for disk i/o these allocations that were freed will just remain in the thread caches or discipline in the arena's will not be available for reuse anywhere else and that needlessly increases the size of your process so we want to avoid that we would like to avoid the out of memory killer so what can you do about it well maybe try to use fewer threads that way you'll have pure arenas and less wasted resources but that's not always an option so some allocators a game out in DC now that are geared toward server workloads will have explicit ways to turn off the heat for these threads and see Artemis idol please reclaim these resources and they will also have ways to enable background peanut breads that can go around and figure out that pita isn't being used so it's okay to free it and release it to other threads and yeah if you're in Linux there's some work to try to address that with restartable sequences that's a nice way to get per CPU data structures in user space but I don't know of any open Malak implementation that currently implement that in recent times we see lots of trends of computers getting more complex and so it appears that also how are like single memory to CPU mapping is not up-to-date anymore we can see this in the high end server space where we have multiple sockets and multiple sockets connecting to each other over like certain types of links which from some kind of topological structure over which they can intercom communicate memory but also like for example trends in mobile phones where people try to conserve power and one one way for example could be like actually to turn down certain memory chips and power them up only when needed and flush get the money back from more stable storage so what does what this means is like even like if you have like a pointer and the addresses memory we don't know if this memory is like actually fast or slower to speak to and one reason why we mentioned this and this memory allocation talk is especially because not a lot of memory allocations actually have a notion of non-uniformity in memory or like in excess latency and bandwidth to memory some are oblivious to this because like their internal i grew some kind of like lens automatically to try to keep data local but this doesn't need to be the case for lots of locators so if you are in the bad situations that for example your memory allocator or that you are for example allocating your first piece of data on one particular human owed this malloc will probably also gain a rate like the additional metadata along with it and will automatically bind it to this no one out but maybe this was just like the dispatch core which actually will just send all other work to other course and will first distribute like the memory allocation vote on them on when he looks at default is if you basically just a memory allocation with mmm we're just being this primal log you basically bind your your memory to or it tries to allocate from the local node and doesn't try to reach out to other nodes and this is not being easy over you you can't really overwrite it very easily there's some progress in like trying to measure like when memory can actually follow threads around but it's not the normal case so this is kind of like needs a lot of involvement in terms of how you program because you might need to actually use like lower late lower level libraries to actually extract your your cert affinities for example and find your threads and memory to certain course so basically it's the same picture what you see here you need to like be aware of how you're mapping between like your memory and your your threads huh and we will see later on when power discusses at how to for example use arenas manually to actually build up a mapping to to allow for more fine granular memory management here another thing we see this operating system is that memory a locators don't actually care about like the boundary the operating system is working on if it's like pages or even huge pages it just like takes whatever is available and if you actually rely for example a particular artifacts of like heuristics of your operating system trying to estimate like certain patterns your application is doing to the to the memory correctly you might actually want to end up to allocate your pages on page boundaries which is like the smallest granularity the operating system can handle and and we will prefer to use like POSIX normal I know sort of a light dialogue which basically like goes into the memory allocation and and tries to do some better job instead of manually trying to align them the memory along with it so one example is in gdb seem a low pitch in Malaga is that it actually splits up the allocation so whatever you have a cut off for example at the header to allocate realign your allocation to a page size this will become a non allocated after each chunk which can be allocated later on by a small allocation if it's getting being satisfied so we recommend this pattern again like for example in some memory our locators like for example so GFC you have the problem that Peter data needs to be like aligned before the page so in this case even like if you have a pension moment you actually have it a lot before the page so there would be an additional page right before your location additionally another thing where memory allocator some operating systems kind of conflict is like over commit I try to speed up here little bit to actually get the other sites the questions like when does an operating system actually allow you to allocate memory because sometimes the operating system knows ok no further memories are available or it can actually like say ok I dubbed that actually the application will handle or will actually use all memory which is which this application asks for we say an operating system over commits if it allows you to allocate way more memory then the operating system is actually able to store a memory or a physical memory or in swap Middle's has a tradition of basically doing that for a long time FreeBSD as well I think I heard Solaris isn't doing this as well as Windows so basically this dictates how you need to be careful with your memory allocations if overcommit isn't enabled on your operating system you can basically most depending on like how strict it is most of your allocation requests will be fulfilled and you will actually get a allocation back on windows also nervous for example you don't have memory or commit you actually need to check your man operation values for now and act according act accordingly there also so there are lots of people who actually say like ok so he looks basically this very there's a lot of over commit pass which uses a lot of over-committing you don't actually need to check for null pointers but they are also like different memory allocators in play between you actually receive them the memory from a locator and this is for example one one example they are linux would probably that just allowed you to give you the memory but in the end you're mano complementation at a limit which didn't allow you to to go any further and so you got no thank you if you get now not back you there's sometimes nothing you can do and you should probably trash accordingly and proper like lock message in other cases that I try to clear clear caches that you have for example in your application try to roofie whatever you can there for example ways to ask je malach to purge particular air arenas so it treats actually memory up and gives it back to the operating system and otherwise you can use in certain for certain alligators to try to push data back to or like the free memory back to the operating system okay in case of security as I initially said like it's difficult for alligators to be like really secure and to also be fast so there's like a problem on how or how far they can protect you they're actually know only a few things you should probably take along with you so first of all is like if you have actually crashes and if you have problems with your busy application using your memory allocator it probably doesn't crash at the site where the actual backers delivers because of like delayed meter data validation for example if you think about like if you work a linked list and you check actually actually every element it depends on when the element is actually being inserted and when a particular data structure of your meter data is being overwritten when the actually detection from the maloca implementation will for example abort your program in this case it's also like necessary to say that another of those memory debugging libraries which lots of people think they should run in production because they abort the program way earlier before if I don't run them they actually all also add gadgets to your program which can be exploited by by attackers so they have been in the past attacks using address and it has a for example on production systems and it's the I would still not recommend running them in production same is for example that Sony that for example malach is is also warning against like for example running my log check in production systems especially like if you are like in a security restricted area okay yeah so debugging has like this problem of trying to belong stitch being liked or making like your life easier between validating whatever you do in your and your heap and the state you are in at the moment so for proper debugger for example if you look at address space I just sanitizer you you add a lot of additional metadata and a lot of like synchronization overhead to actually make sure that nothing ever like is being missed from your allocation pattern when there should actually be an arrow I just quickly go over the debugging features so whatever you can do with this this debugging in memory alligators is basically lots of debuggers nowadays allow you to dump your debug your heap stage when you have a mini dump or core dump then you basically always can look in the menu it's of your memory are locators that you will find some other features that enable stricter checks whatever at the time when you do Malick's or freeze and will validate the methods are more strictly you can use like for example operating system provided tracers that allow you to follow malloc or freeze along with the application and very good time stamps to hopefully all of them in correct time and then see for example how our pointers are being created and being returned to your application and then being freed again you have certain malach options which you can able hopefully doing runtime some malloc libraries require you to actually compile your application you can use for example like more heavyweight machinery like a vagrant which is kind of like a virtual machine monitor that sits between your app and your pro your app and and the operating system and just like tries to look everything what goes in and out of a pointer and read with the right access from your pointers and looks at how which locator problems you might have of which pointer accesses you got wrong and then you have a 2 to 10 integration which basically are the sanitizers the work between that compiler and libraries and allow you to to figure out with higher performance what your problems are but they actually require you to recompile your application and maybe even like your dependencies so integration of them is a little bit more troublesome than some other filters I will also quickly mentioned you can't run a GWP a Sun which does not send for a Google wiper finally a Sun it was upstream and clang and it runs pretty well in fraud look it up okay so then all this discussions about how it's hard to do a general-purpose memory allocator and how you have to work around your weaknesses so I think a natural question is why don't we just write our own customary allocation we know what I app looks like we should be able to fit to it turns out that's very hard so this paper came out in 2002 because it rained custom memory allocation didn't compared a bunch of industry programs with customary allocators and he said that's just removed at choose tender DL malloc and see if it's a win turns out it's almost never went to write your own memory allocator so don't do it and if you do it make sure to measure your baseline because it might be a lot better than you expect however that's close with if you think this is actually a good idea you really know what you're doing so here's one thing gets useful it's sometimes you want to control the placement of your memory let's say you want to use persistent pram or you want to make sure that large hash tables are backed by gigantic one gig pages what do you do with that well different memory alligators offer you hooks to only replace the way that they interact with the memory with the operating system to get more bites nothing else oh you don't have to worry about all the algorithmic of memory allocation however this is most useful when targeted for specific allocation and apart from gene Malik I don't know which ones let you specify overwrite for one type of allocation which I email you can overwrite for a given arena and then target your in explicitly for these special applications then there's a the object pool which is mostly useful if you can avoid the construction of destruction overhead right however sometimes it still makes sense for instance if you need a stable allocation it's because you want types of levitation because you're doing locked reprogramming and someone might temporarily read and still pointer I'll need to figure out later that that data isn't useful if you do that with a standard memory allocator at some point the byte might become something else and you're just gonna start doing weird stuff in your code it also makes sense for some interesting edge cases I do want to point it out earlier we have frequent shortly applications and maybe you want to use an object pool for that and a nice bit here is that you won't have to write your own you can use boost you can use the one day and use a standard lip C++ but also like it's not that hard to write your own might make sense to specialize on your specific requirements if you're gonna do that because you really want to make sure that you have as little overhead compared to the regular knowledge interface and finally the one exception from that paper by Emily Berger and others in 2002 was region alligators they found that region alligators were the only one form of custom applicators that were useful they did offer increase performance at the expense of a much higher memory footprint alright so how does it region allocation work ah you grabbed a large chunk of memory contiguous and then for every allocation just incremented one pointer and free is an OA until I'd the very on you say well everything that was allocated in this region is good to go and that's when you freeze your chunks so to implement that well you could use the CDC ocular adapter or polymorphic allocators but I find that the state footprint simply - no if you enable or disabled or mean allocation for this specific object and the virtual calls add up so what I've been doing is a user region per thread and you have a thread local flag instead of a pool in each occasion and that flag says allocation time you want to use a regular alligator or do you want to use a region alligator and then when it comes to the allocation you don't know right you can't just read so but you do what I did as a have a metadata bitmap say I know my chunks are 2 Meg's and relying on two Meg boundaries then I can just have a bitmap that tells me for each 2 Meg range of memory if that memory is managed by malloc or by some other assistant alligator or if it's managed by my region system and that the allocation so you could do nothing at all all right and this is more tentative if you have the mix of short tip and long evalutation try to treat them differently so a DB does that but it's log structured a locator and defund it was very good for performance and fragmentation you could also try to do the same thing by specifying the arena you want to use in j-val all right so I close thank you you just aren't quite a few other talks that are interesting on the subject so Paul and I will be talking about cool lock free data structures that always perform better than their locked equivalent or in even some cases serial equivalent there is a talk Wednesday on TC my lock internals which will be going to a lot more detailing see the design implementation of TC malloc and then of course there is a mesh talk these are our emails and Twitter's and we'll just open it up for our questions huh you didn't get an icebreaker from your staff yeah actually have a question yeah you talk has a lot of malloc and trees now yep try to use make unique and vector dot resize how does that translate for example for like avoid avoid malar can you see our that kind of like oh is this ivory able to see through my location see ok it's this amount to basically zero a lot thing through your constructor so we're just gonna do the right thing how does you observe anything like that okay so there are two questions here one is given the standard C++ allocation interface how does that relate to malloc and free so it turns out that usually your battle you're allocating deallocate calls in the standard allocator will eventually go to regular malloc and free so all these things we said about making sure that your lifetimes are correct this cell applies in c++ right the other one was do we know of any C++ alligator or container that we know to use callek to make zero failing faster I don't think it would be a very good idea but also it seems very hard to guarantee with like by compile time reflection that this is what you want on the default constructor thank you cool all right if anyone wants to chat with us we'll be at the back-trace booth outside