Alan Talbot “How to Choose the Right Standard Library Container, and Why You Should Want Some More”

so I'm Alan Talbot and I was here last year and I gave a talk that spent some time on the subject of standard library containers so I found that the containers are not as well understood as they should be and I continue to see incorrect usage even on the part of people who should know better for instance earlier versions of me so programming this thing about programming right it's it's kind of like being in a Robert Heinlein novel you keep running into earlier more foolish versions of yourself right so today I'm going to dive in a little deeper to that subject and hopes that you will teach me something so we're gonna look at three case studies which I think are kind of interesting and actually fairly common scenarios one of which is out of my work from just a few weeks ago so this is for real but first I'm gonna start with little history this is a tale of letters so a really long time ago I was working really long time ago I was working for a company called New England digital writing music notation software and we made a gadget called the sing clavier which was the first professional digital synthesizer I mean this was back aways and the computer was a mini computer the PC wasn't really a thing back then I mean you know the Apple 2 was just out the IBM PC was just out dos 1.0 had just been released the computer was completely homemade as was the OS and the XP L compiler I assume you all know it X BL is if you don't it's a variant of PL one so this computer had 64 K of RAM that's K why do you don't know what K is I imagined but it 8k was reserved for the OS so I had 56k to work with needless to say I had to be a little bit careful of my data structures so then in the 90s I was writing music notation software for myself my own company and I was writing it for the Mac and I had a Mac se which by the way I still have anyone's interested in a see me after but it had four megabytes of RAM that's em but not only did I have to be careful of size I also couldn't really depend on the OS to do a good job for me of memory allocation it was really slow so I would get these big chunks and do it myself inside the big chunks and in the 2000s helped me out here is that what you call MERS is it the zeros what is it oh the naughties I love this okay excellent the proof should spin right the Nadi's I like that and I had a 32-bit PC with 4 gigabytes of RAM that's G as in B but this was big data back then because I was working for one of the major digital map companies making digital maps of the United States and in order to get Texas into memory I actually had to do this little trick some of you may remember there was some little like registry thing or something you could do to get the OS to give you 3 gigabytes instead of 2 because otherwise it says you you know every process gets up most - even though there was 4 there so I did that and I got it to fit turns out things really are bigger in Texas even the digital map did so once again I was memory constrained and speed was also very important when I started working there their product creation process took 3 weeks to run that's W I rewrote it and after I rewrote it it took 8 hours to run that would be H so performance matters so so as you see I've had some experience managing memory and processor resources but now I work for this railroad engineering firm and I write train railroad simulation software and I just got a new computer a couple months ago and it's got 32 gigs of memory and lots of processors right and they run it over three gigahertz so there's no problems anymore right of course not and yet a few weeks ago customer was complaining that his simulation took way too long so I ran it on my aforementioned super super super computer whatever we call it now and it took seven and a quarter hours that's H again to run now mind you my contributions to C++ have been all mostly pretty much about container optimizations of efficiency and I've had the experience I just mentioned and I gave a talk about this last year so obviously I wasn't doing anything wrong with containers right of course not so if I even talk about containers I mean I rather run dank mundane right it's kind of like I don't know talking about sorting I mean is this worth a CPP con hour let's review containers real quickly so you know all this stuff right I mean we all know all this I talked about it everybody's talked about it you know vector is like this deck is like this list is like this this isn't news I'm not even to talk about the associative containers because we're sticking to sequences today but the story is the same right and so these properties lead to these designs right these are the design choices that are baked into the standard library right for instance vector has pushed back and popped back because the Rotter 1 I was late and it doesn't have push front and pop front because there are in you know insert order an etc etc right debt has those things because their order 1 and list is great everything's actually order 1 right so this is all well known so choosing a container is easy right it shouldn't be an issue everyone knows this what's to talk about well not quite so these truths that we hold to be self-evident are entirely dependent on the particular situation used to be floating-point operations where the things you had to watch out for this is a long time ago right limit your floating point multiplies today it's floating points faster than integers right I discovered this to my shock not all that long ago but today it's cache misses and heap allocation of the things we do lots of those are the things that are really expensive that we need to watch out for so it's not the case that Big O complexity actually is the entire story we have to look at the situation and these are some examples of that and like I say I've covered this before but what I want to do today is look at some very specific cases that are a little bit more interesting than just this so I was driving back from an afternoon of rock climbing and a ridiculously good Mexican meal in Santa Fe with Howard Henan and Jonathan Wakeley and they were busy shooting down a proposal I had to add push and pop front to vector and I won't go into that but they convinced me it wasn't as good an idea as I thought it was but in the process they introduced me to a new container type and I want to look at this a little bit so let's start with this example this is actually a pretty useful use case and it it comes up more than once in the software that I'm working on and I suspect that other people have probably run into this as well so we've got a lot of objects and they all have a small Q that does something so how do we implement this well if that small Q doesn't have a maximum size that we can count on we need something that will handle that right so the most obvious well before we talk about how to do it let's say let's look at my little test case by the way the standard library solution is the Q container adapter that requires push back and pop front which means it works only on lists and debt right so I wrote this little tiny test case and I sort of oversimplified the code this isn't like the whole code but I just wanted you to get the idea basically we're gonna have a lot of widgets and we're gonna thrash this in this outer loop reps times and each thrash we're gonna go through and we're gonna add some things to every queue to it to every widget and we're gonna then take away some things and those adds and subtracts are randomized and the randomized between one and some size that's an input to this algorithm so this just sort of simulates some real-world ish and of thing but because because we're randomizing between one and size the size it's gonna kind of float around roughly the the size of the queue is gonna float around sighs at least it's ordered magnitude wise I guess I don't know someone who's a theorist could disagree so I left out some of the code I left out the randoms random number stuff but all right so let's do this with lists it's the most obvious way it's what the standard library sort of pushes you towards this you know okay problem with list is as we all right we're gonna allocate allocate allocate allocate and they're all over the place right and in the heap so you're locality of reference in general is non-existent so here's our widget it's utterly simple to implement with lists I didn't use the queue adapter just because I wanted to keep it consistent across these examples and it just does basically nothing much at all how does it work so I did I made a container of size 10,000 and I thrashed it 10,000 times that I set my rough queue size to 10 and I got these numbers on my computer it doesn't matter as long as you use the same computer it doesn't matter what the numbers are okay now let's look at a vector because someone here is thinking we'll wait a minute I saw you talk last year and you said don't use lists for this use vector it's gonna go faster for something small like this because sure you're gonna be sliding or you know sliding stuff around in the vector but it's small and it's gonna be in cash and it's gonna go fast I don't get to use standard queue but so what the locality of reference will be excellent I'll only get one allocation most of the time sometimes it'll reallocate if it grows but then it won't move again if it doesn't have to grow beyond that right all that good stuff so how does that do well here's the code it's still really simple except that I don't have a pop front so I have to do it you know that way and also I did it reserved because we all know that vector works better if you pre reserved something so I preserve decides don't worry about how it got there I cheated I use the global nicely done right times down by three and a half memories down by a factor of five right I guess I'll get a bonus this year but wait a minute right you say there's something there's some other container I can never remember what it's called right that we could be using here oh right a deck the deck has the best properties of the vector and a list right you can pop push and pop front you can it's fast to iterate right so let's try it with a bet with a deck and to see what happens so right we don't know what's going on out there the decks complicated I mean at the very least it's got a block I mean the deck has blocks right link chain chain of blocks it's going to have at least one block which we can't control the size of and and then it's gonna have another allocation for its indexing thing whatever however that works right so some stuffs gonna happen but you know people who write standard libraries are very bright and they know what they're doing and they think about this stuff and they're gonna make it work well no question so let's just try it what's that for this particular test I was using visual studio with 2017 yes there are others but this is the one I had handed it's a drop-in replacement for lists we get back to this utterly simple code could have used Q standard q how'd it do wow that's pretty cool I cut the time almost in half but woops memory just went up almost three times in fact it's it's more than half the original size using lists now sometimes this trade-off might be fine right and sometimes it might not and something that you got to remember is the fact that your stuffs running fast and you're using all this memory the fact that you're using all that memory may be causing somebody else's code to run slower so the whole program they run slower there's a lot of interactions going on out there we're gonna talk about that more later but this is a possibility so are we done are there any other options well it turns out there is so this container that those guys were talking to me about it's got various names but I like I forget one of them came up with this name for it but I like this name I like it's called the shifty vector so how does its work it's just it's a vector it's just like a vector but the elements are in the middle of the space of the of the capacity and can grow in either direction it's got a push front pop front and when it hits the end shifts back into the middle if it needs to well if we will need to because it hit the end it will reallocate just like a vector if it needs to because it's got push front and pop front it can be used with standard kill if there were one and we can see it work here all right pop push back pop front push back I'll do that again right so how does this do well I don't have one so I wrote this little sort of very kludgy simulacrum of one I used vector and I made the assumption that I'm only going to ever push back pop front and you know because I didn't want to write this hole I still reserved and what I'm doing here is I'm keeping a front pointer otherwise it's just the same vector but I'm keeping a front pointer when I do a pop I'm just gonna return the front pointer in advance so now my empty test is is the front equal to the end or not okay where it gets interesting is here so push so I'm when I first wrote this it was a little easier to read and it was longer and I refactored it down into a nice tight code so it fit on the slide it's very slightly harder to parse but and I can go into this in detail later if someone wants to ask about it but basically it's pretty simple it always does it push back and it always resets the front pointer it turns out you have to do that even if nothing happens because turns out you can not do a push back yeah let me rephrase it if you do it push back on an empty container you will invalidate a pointer that you had previously set to begin that is a little bit subtle and it has to do with the way the standards written and it's not it's probably not actually necessary that it worked that way from a you know technical point of view but it is how it works so I need to preserve the front pointer which I do with this X which is just the offset from the beginning and then if if the size of this thing is at the capacity I now have a choice either it's full and I need to just let it do its thing it's a vector it'll reallocate and move or I need to get rid of the ones I'm not using anymore that I popped from the front which is which I do with an erase any questions about this by the way if you're paying close attention you may notice that I do it when I do a pop I don't actually destruct the object it's all right they're just ants this is just a test yes yes it is this is very different from deck and I'll if I have time or after woodall go into that some more the question was is it different from deck so that's how it works how'd it do so it's two and a half times faster than deck four and a half times faster than vector and we're back of course to using the same memory as vector because it is a vector nothing changes right it's just how I you know messed around inside the vector that changed so for this reason I think we should have some more containers and I think this would be a great one to add because I think this is a common enough pattern that it would be nice to have this in the standard library so about now I would have expected someone to put up his hand and say yeah but wait a minute this is completely contrived if I change any of these numbers I'm gonna get different results right exactly that's exactly the point okay every situation is different that's if you that's the one takeaway of this talk is every situation is different so you've got to measure you can't depend on rules of thumb they're not always right all right you can't depend on the stl design it won't always lead you in the right direction and you have to try different stuff and you have to be very careful because your assumption that worked in the last hundred times you did it may completely not work for this situation and sometimes it's rather tricky and you got to really think about it so just a little aside there's a couple of other vector variants that I think are really interesting one is fixed capacity so that's different from an array an array a standard array is fixed sized so you always have all of those elements they're constructed this is fixed capacity so it's just like a vector only it doesn't go out on the heap you've got you tell it how much storage you've got and that's your capacity inside of that you can do any you want when you hit the end it does something about it throws an exception or something and then the other very useful variant would be local cash or short string optimization or there's several other terms for it where it it does the fixed capacity thing until it runs out of room and then it goes out on the heap just like any other vector both of these have been proposed for the standard library and I was like I would like to see them I actually personally think that vector ought to give you these options out of the box but sadly it doesn't so the next example is a pattern which is typical of certain kinds of games now I'm not a game person so this isn't personal experience but I also think that this pattern is probably much more widely applicable than just for games so the idea here is that we've got a large bear not even large we've got some number of objects and we have frequent turnover right some things are getting blown away some things are getting created right you think about spaceships are coming in you're shooting them but you're getting more ammunition I don't know I'm not a gamer but the thing is that you've got pointers in iterators to this stuff all over the place there's all these interconnections so they can't be moving around on you right so deleting something or inserting something can't mess can't mess up your pointers but order is typically not important on the other hand reliable iteration fast iteration is important now the only container that does this even remotely in the standard library is lists but all every we already know the lists limitations we've talked about it and the lack of locality of reference gonna cause not only poor iteration but jerky iteration which I have to assume is gonna be bad for your video game so I did a very simplistic example of this I didn't show the code because it just does this there's nothing nothing tricky going on I just wrote code that did it this algorithm each out each the elements are trivial but I wanted them to not to not have zero size so they've got some size to them I'm gonna have count elements and I'm gonna thrash reps times just like the other example you can think of the this loop the reps loop as the game cycles and each cycle I'm gonna go through the entire list reads times and you know accessing each of the elements in turn and then I'm going to delete every nth element which there's got to be some sort of worst case right and then I'm gonna put back as many elements as I took out and doesn't matter where they go cuz order is not important so they'll probably go on the end whatever alright so I ran it with these numbers again I had a container of size 10,000 I thrashed it a thousand times I did a hundred reads and then I took out every fifth element and put him back and that took 14 and a half seconds and used that much memory using a list and we know list isn't a great solution for this but it's the one that's there so well how could we do better well it turns out there's a container called a colony and this container is also being proposed for Standardization and the colony is designed to solve this exact problem okay these are some characteristics of the colony what's most important here is that pointers and iterators are not invalidate 'add and memory for those memory from elements that have been deleted is kept around and reused but it also is smart because it uses blocks just like a deck if a block gets totally empty it returns it to the operating system it has a separate data structure which they call a skip field which marks the deleted elements in such a way that to optimize iteration so iteration is quite fast even though it has to pay attention to the elements that aren't there and then of course there's other there's another structure that is there to identify the deleted elements so they can be reused so this as being this proposal and the implementation as written by Matthew Bentley I'm not going to go into this in too much detail because first of all I don't know enough about it to do so and second of all he did a fantastic job of talking about this three years ago right here at this conference I highly recommend you watch his excellent presentation about this and this is a link to the code and and the paper describing how to use it so this is another one of these things right who knows what it's doing it's doing all this complicated stuff but it's a container it looks just like a you know any other standard library container it's a drop-in replacement it was very easy to use and I have made I changed two lines of code in my little sample to change it from list to colony what happened well five times speed up and marginally less memory footprint and it's going to have significantly better iteration characteristics so I find this quite compelling and this is another thing I'd like to see get into the standard myself because I think this has broad application and there's lots of games out there so where were we oh right okay I was just saying that knowing all this stuff I couldn't be doing anything wrong in my program with containers uh certainly not so I started banging away at my bug my problem and I noticed something I noticed that when I ran the simulation at a one-second time stuff it ran fun when it changed it to a tenth second time step it ran 100 times slower well that's not right because I'm doing 10 times as much work storing 10 times as much data it should have run 10 times slower and it always had run 10 times slower and suddenly it was a hundred times slower so this seemed like it could be a clue but I'm not sure what it was a clue of so I profiled it well how about that it was spending all kinds of time in vector allocation but I'm doing all the right things I'm reserving I'm you know move semantics right and you know return value optimization right so why did you know and it always worked why is it suddenly not working well I noticed that it ran fine at one second with the electrical system on yeah and if I turned the electrical system off and ran it at a tenth of a second it ran fine so what's the difference well with the electrical system on the program is generating a lot more data and memory in more so it uses it uses Dex actually to store all this logging information that it generates as the simulation runs and I'm doing a lot more of that with the electrical system on because there's a lot more data to store so I started to wonder if maybe because all this stuff is going on at once what's happening is I'm using a bunch of vectors every time step I'm creating a bunch of vectors and then they're going away and then I'm creating a bunch of vectors and then they're going away and I start to wonder if maybe the memory system or you know the cat between the cache and the memory system I'm just it's getting it's thrashing and some and I'm reaching some saturation point so I started to wonder if I was actually a victim of one of the things I spent a bunch of time talking about in my previous talk which was loss of capacity history of these vectors so let's revisit this and look at exactly what's happening in a vector so when you haven't when the vector is empty there's nothing on the heap you've got the vector body in your local scope when I say local I mean either in your object or on the stack so there's nothing on the heap when you add the first element it allocates room on the heap for one element we know this right you know but you can't and you can't you can't always reserve the right amount sometimes you if you reserve too much you're gonna waste memory sometimes you you know reserving is not always an option and so if you allocate an I mean you insert another element you're gonna get a second allocation another element and a third allocation now you finally got room it finally grew enough that you can put another one in without having an allocation right this isn't news I'm assuming ok with the reserve right much better just sits there until you have to add another one and then it reallocates and that grows bigger than your reserve right but what happens when you're done with this vector and you need another one right well what do we do we destroy it right we destruct it we throw it in the trash I think who cares if it ends up on the beach down the coast throw it away poof it's gone and now we're gonna allocate a new one with the original reserve notice it's not the same size right we had all this space extra space and now we don't anymore because we threw away that allocation right so I started thinking what could I do about recycling this thing is there some way that I could recycle this and not lose that so not only not lose the capacity which which would prevent further thrashing as the vector grows but also not lose the allocation at all so I don't have to reallocate at all well what if I move the vector into the recycling and clear so I've cleared it there's no elements and I've moved it over there neither of those things changes the allocation or changes the capacity right now and I need another one I move it back and there it is it's empty I stick my element in it no allocation no change in capacity this is a very important point the actual size my actual capacity has been preserved so if I'm using a lot of these over and over again for the same kind of thing the size of the vector will will grow and it'll thrash around in memory until it reaches a big enough and then it'll just sit there and if I have a bunch of them well they'll all tend to sort of float up to that size and then just sit there because they're big enough and if every once in a while somebody overruns it well okay they do so how you actually would do this depends on your situation but here's a kind of a simple little approach that I actually wrote and tried and just let you look at in a minute so the interesting things to look at here are that you know if there's if there's nothing in the recycling bin then I'm just gonna reserve just you know whatever size I would have reserved anyway if there is something in the recycling bin I'm just gonna move it out of the recycling bin and then pop the back of the recycling bin when I distraught I'm going to clear it and push it into the recycling bin where it gets interesting is this guy over here the the copy constructor so the copy constructor is assigning from another from another vector but that assignment is not going to carry the capacity history right if I construct a new vector with another vector the new vector is going to be of the exact right size to hold the size of the vector I'm constructing from and I don't want that so I'm going to call the default constructor so that I get one off the recycling bin if one's available and then just do an assignment what's interesting here is you don't need to do this for the copy assignment operator why any thoughts right it's already in play that vector has already been used so there's no reason to it's already yeah it's already in size so I implemented this exact code in the program I work on the train to a railroad simulator and did it speed up of course it did over 12 times so now it's a 35 minutes that's M if you're keeping track instead of four hundred and thirty five minutes and this was not a simple example I whipped up for a lecture this was the real world real customer and it made a big difference I yeah so right the the amount of memory that I was theoretically using right if you just measured the allocations if you went and measured each allocation and added up that number would be more with this scheme because instead of using the you know a vector that grew you know by whatever the growth factor is and you know I don't know I think maybe visual Studios use one this is one point five or something you've got something which is perhaps too big for your particular immediate use but oh thank you yes I forgot to repeat the question the question was wouldn't we be using more memory this way and the answer is we were using more memory in terms of actual allocated pieces but what was happening was I was creating all these holes in memory you know because I create something and there's something else was something else from elsewhere in the program would go here right and then I take it away and the hole would be there and then I create again over here and then something would go there you know on and on and on so I was creating this big mess in the heap that was never getting compacted down and I'm pretty sure that's why it inflated the way it did does that answer your question so the takeaway from this for me was as I said don't make assumptions you've got a measure you've got to try several different approaches and those approaches may be tricky right you may have to really think about it to think of what's going on because it did not occur to me for a while what could possibly be going on and then I thought of this and I tried it and sure enough Wow at work that was the problem no your containers right basic complexities not the whole story and you need to know how all the standard containers work and you also need to know what other containers might be out there in boost or you know proposed for the standard library or something that you can whip up on your own if you need to and then and I think this is I mean if I were teaching a beginning computing class this would be something I would stress you know is one of the fundamentals of computer science know what's going on in the computer know what's going on in memory understand that heap allocations are expensive and that locality of reference is critical because of the way computers work today and you know it's going to be if you know that stuff you're gonna be able to understand what's happening and really it seemed to me this was the theme of Andres talk as well you really have to think about how computers work these days so that is how to choose the right container and why you should want some more yes um I right the question was how do I member how did I measure memory I just used a standard well standard I used windows call operating system call and asked for the peak commit you know that I can't remember the name of the call yeah the peak commit of the program so it's like the maximum amounted it yeah the size of the footprint yeah and I was you know I was running enough stuff that the size of the footprint was was significant I mean it wasn't at RIT you know it wasn't a trivial amount so it seemed like it gave me some reasonable order of magnitude I did not I know yeah thank you I'm terrible with that deep Mars question was did I you try to use allocators and I did not the thing is all of these the whole world changes if you're using allocators right it makes it a different a different different world with the same principles apply but different answers and different solutions and I was interested in situations where people didn't want to get into that and want to just use what's available easily but I think that the the same principle applies that you know if it's not working you need to look at all the tools and get the custom allocators is a tool that is specifically designed to address this type this sort of issue yes so the question was are there good quality implementations of these stent of these containers that aren't standard in the standard the colony implementation I would guess is probably very good quality I don't know enough about it myself to know that for sure but it it's been looked at by the committee quite a bit already and I know that he's been working on it for quite a while be a good question you know you could ask you know look up the the the links but I would guess so the shifty vector I don't know if any of those are out there I'm thinking of that I'd like to actually create one because I'd like to try and get it standardized if so it'll go through a process that will ensure that it's high-quality including going through boost and suchlike I see I think you were next so basic string isn't a container and it's probably a good idea not to use it as one I didn't explore it the associative containers are two kind of a different world because they serve a different purpose I mean you wouldn't want to use one for any of these particular problems but when you're talking about something that is solved by a map using an unordered map or other variants of hash map of which there are some very good implementations out there are certain you know is certainly an interesting way to go there was a very good talk about hash maps C++ now last year that I went to you might want to look that up so the question was are there tools that would allow you to investigate containers for your particular use so I don't know the answer to that I'm seeing a nod somewhere in here I would think that in general your particular use is different from every other particular use and you're gonna need to put instrumentation in in some way so that you can tell what's happening in your particular case because that this the situation that I was in the scenario I explained here was very particular not just to my particular program but to this particular use of it in this particular case and it worked great 90% of the time or 99% of the time it's just not this one time so I don't I don't know if there'd be tools out there that could help you with that because they they wouldn't be testing the same thing that the earth right I know it sounds like a great tool you should write one yes yes so the way it would work and I mean something I forgot to mention about that is in my little implementation was very very elementary and not didn't even doesn't even do everything it needs to do the real implementation would be much more efficient than what I was doing but I believe that the way it would work most efficiently is that it wouldn't ever move until you hit the end and once you hit the end then the question is where does it slide to and I think the principle is you're going to slide it to the middle because you're going to assume that it's equally likely that someone wants to put something on one end or the other it it's possible that you could write one that where that was a user input to say oh I'm more likely to push things on the back or I'm more likely to push things on the front and then you could get some further advantage by knowing that and did I repeat the question I don't remember but the question was the question was does it shift to the middle and if so is that the best solution yes the question was what did I mean by timesteps point one so so the program that this example came from is a railroad simulation and it simulates turns running on tracks and the electrical condition of those trains etc etc and any sort of a simulator I mean this is all happening in the real world continuously so we have to somehow simulate that in the computer but it can't be continuous so there's a time step you say we recalculate everything every one second of simulated time right so we say okay we're if the train is here and it's going you know a foot a second when one second later it's gonna be here in between there is no in-between because there you aren't your only simulating the Train here and here right so if I'm if I'm simulating it one time one second at a time and I get a hundred you know takes 100 seconds to do something if I simulate it every tenth of a second so it's moving a tenth of a foot at a time well it should take a thousand seconds right because I'm doing exactly ten times as much work I mean close enough and in fact it was taking a hundred times longer because of the problem but it's but in norm under normal circumstances it would be ten times the amount of work for ten times the number of time steps other questions yes yes so the question is I found that if I took out the electrical aspect of the simulation the problem went away I didn't go look at that code because the I knew I knew what was taking the time because I profiled it and I knew that the time was being spent allocating and deallocating vectors the electrical data in fact all the data and the program is being dumped into memory as the simulation operates and that's all being stored index so I knew it wasn't that directly and it may be that if this wasn't the problem I would have gotten to that eventually but this turned out to be the problem because once I did this the the non-linearity disappeared so a little aside here why by using decks not vectors or something else to store all that data I was dumping into memory anyway any thoughts right you can't you can't use big vectors when I say big I mean big relative to your memory space you just can't use them because of the way they grow what's that yeah well you have it's except that it's not because if your vector is half of memory and it tries to grow it can't curve you can't grow right and and if you have more than one of them it just becomes it just becomes impossible Dex on the other hand use blocks which relative to that sort of size are very small so it grows really nice and smoothly right up to the top of memory without any problem and you can have a bunch of them and they're all just allocating these blocks and it all fills in the problem is I was creating a bunch of holes in that and it was just creating thrashing that's my guess that's correct the shifty vector is a vector it's a kind it's a variant of vector absolutely yep it's not a different kind of container but for the shifty vector examples so the question was the question was does the shifty vector have the same problem of growth yes that was a different kind of problem and that's a problem that I actually think there's a whole lot of I mean it comes up all the time where you just you want a small list of things but you want a lot of them and you want it to be high performance but you can't count on saying you know I mean an example would be I've got an employee record and I've got and you know we support up to ten phone numbers but I only want two but almost everyone has two phone numbers or less right so I want to make room for two phone numbers but you know but it has to be able to grow out there into ten so that's where you want the local optin you know the short string optimization vector for example in this case you know it's it's a queue so you want the shifty vector optimization so the question was how big were these vectors that were causing this problem that the recycling solved I didn't actually I can't remember if I actually measured that I might have I can't remember but in general they were on the order of hundreds of elements they weren't they were they could be as small as tens of elements but they were unlikely to be thousands of elements so to give you oh I guess the element so the question was byte total byte size I guess the elements were probably a couple of hundred bytes maybe they're less than 500 bytes somewhere in there yeah yeah no there these things weren't small I was generating quite a few of them but but but they were ending up all over the place and chewing up memory that's my assumption anyway other questions any I keep you keep looking at me like you're gonna tell me go ahead I'm here to learn okay yeah so so deep deep Mars comment was that the the visual studio library implementation of Dec at least at some point was using a very small block size so is 256 so you would either have you know that would be depending on your size of ear or you know a single element of course if the sig level is bigger than that I personally wish that you could adjust the block size I think you should be able to adjust the block size because I think that would allow you to tune it and I think you would see tremendous differences depending on how you tuned deep March points out that the C++ 98 didn't have variable template arguments properly handled and there that was the main reason why the deck block size wasn't adjustable as a template argument as I think it should be so they couldn't fix that be nice to do another one that allows it STD - yeah so so the question was isn't the aren't these rather special case containers and if you need them you should go get them from somewhere and meanwhile the standard library has sufficient containers for most purposes and you're right vector I mean said this last year back vectors the one container to rule them all always start with vector not quite I don't I don't quite agree I'm it is true that these cover many many cases but I think these are compelling enough examples that it makes sense to have a few more it is not easy to get this stuff right to get these containers right so it if we can standardize it we have a much better chance of having one that's right generally speaking now that's not I mean this is the this is a conversation we could have all night and do have all night on the committee all the time like what should and shouldn't be in the standard and it's always a value judgment but adding more containers that especially if they're variants of existing containers like if there's a way I personally think it would be great if you could if we had one vector that did all this stuff because really all you're saying is I want a vector but I want to control a couple of things like does it do this does it do that which would help to address that colony is a completely different container and whether that has enough general purpose use or whether there's just enough games out there that to make it worth putting the standard that I can't answer myself but it certainly has raised about an interest in it's still on the table now we're over a bit I get us little signs actually given our slightly late start it was probably pretty close thank you for all your questions thank you for coming [Applause]

Channel: CppCon

Views: 17,468

Keywords: Alan Talbot, CppCon 2019, Computer Science (Field), + C (Programming Language), Bash Films, conference video recording services, conference recording services, nationwide conference recording services, conference videography services, conference video recording, conference filming services, conference services, conference recording, event videographers, capture presentation slides, record presentation slides, event video recording, video services

Id: yjPKVOYcw28

Length: 62min 12sec (3732 seconds)

Published: Wed Oct 16 2019