So hi there, everyone.
My name is Chandler Carruth.
I work for Google.
I work on our C++ language platform.
I work on our C++ compilers.
Specifically on the, the Clang and LLVM teams at Google.
And I'm here to talk to you a little bit about performance and
efficiency and making code fast.
And all of the different things that go into that.
But before I do too much, I wanna actually give you guys a little bit of a, a,
want to manage some expectations, because I've been reading the Twitter feed from all
these folks and they're talking about all these like, crazy good questions.
I just want you guys to know this is essentially like my view of what performance
101 should be. Okay?
This is gonna be kind of an intro talk.
If you guys are like, hard core, like, really deep performance, and
that's, you maybe a little bit bored, and, and, and
please be kind, because I'm gonna gloss over some things.
You could, you could, you could heckle me thoroughly if you really want to.
So we're gonna talk about efficiency performance algorithms and data structures.
And the first thing we're gonna do is we're not gonna talk about them,
we're gonna talk about why anyone cares about them.
How may folks here think that C++, you know, it's, it's really important to have perf,
like high performance in C++?
How many folks here think that's super important?
Everyone think it's important.
How many folks here have a really clear idea of why performance is important?
Now, all the people who didn't raise your hands the second time,
please reconsider raising your hand the first time.
Okay?
We actually need to understand why it is we care about the performance in C++ before we
just decide its important, we're gonna care a lot about it.
I'm gonna tell you why I care about performance in C++.
Most of it comes down to a,
a quote from Niklaus Wirth which I will try to pronounce correctly but fail miserably.
I, I actually really like a lot of Wirth's stuff.
he, I think he encapsulated, encapsulates a lot of my,
like things that are core to my philosophy about software here.
Says software is getting slower more rapidly than hardware becomes faster.
All right. This is particularly in contrast to, to,
you know, the, the kind of normal Moore's law approach to hardware's getting faster, great.
And that, all the time, it's okay, we don't need to make software faster cuz it,
the hardware will catch up.
And, and it turns out that's not really true.
We're really good at writing slow software.
Even in C++, we're really, really good at writing slow software.
It's hard to write fast software and, and it takes a lot of effort.
And so, so it's important to think about why that might matter, no matter how fast the,
the processors get.
And to give you an idea of just how much I think that,
that Niklaus Werth is really on the same page just, I,
I have to mention, he actually wrote a book entitled Algorithms + Data Structures ,.
I did not actually realize this one is
picking the title of the topic, but, you know.
Anyways, we're gonna come back to this book because he predicted some whole elements of
this talk in this book.
So, look, how many folks here have read this book?
Anyone?
How, all right!
>> Long time ago.
It's a good book.
Okay.
So, so I actually think that the idea that you know, software is
getting slower too quickly, right, it's getting slower at a really astonishing rate,
is even more relevant today than it has been before, and, and for pretty specific reasons.
There was a very seminal event that happened in,
in the technology world sometime ago that changed in, in my opinion and
in a lot of people's opinion, how we look at computing devices, the performance of
computing devices, the challenges we face writing software for computing devices.
And this event was the iPhone.
Okay?
And, and when, when Steve Jobs introduced the iPhone, he was, he was not doing anything,
you know, particularly to C++, but he was changing how we think about computing.
Mobile was now a first-class compute citizen.
I mean it took, it took the world a little while to even realize that that was,
that was what had happened that day.
But that's what happened.
We now have to care about mobile.
We have to care about things that are small, right, things that are, are really hard and
challenging to fit you know, big bulky systems into.
And we essentially get into this, this annoying situation of, you know,
we have small and we have fast machines and we have to choose one.
We don't get to choose both.
We're going to choose small almost every time.
But it gets worse.
Cuz the other problem that the iPhone introduced,
that people really weren't as focused on at the time, was the problem of the battery.
What do we do about the battery in your, in your phone?
Your phone's battery, I mean my phone's battery is about dead, right?
How many folks here have charged their phone today?
[LAUGH]
Okay, that's a problem, that's not a feature, that's a bug.
[LAUGH] Okay, yes, like how many folks are charging their phone right now?
[LAUGH].
Okay, so, so, we hav, we, we, we kind of entered this new problem domain.
Suddenly power became relevant.
Now, a lot of people talk about there, there's some,
there's some kind of shady research out there that I wanna, I wanna push back against.
There's some research into power efficient instructions.
If you ever read about power efficient instructions or optimizing for
power usage, you should, you should become very suspicious and you should
probably run the other direction because this is mostly total junk science, okay.
Here's, here's the number one leading theory about how to save, this.
How to save battery life.
Finish running the program.
[LAUGH] Seriously, race to sleep, that's the,
that's the actual technical term, it's race to sleep.
The faster your software runs, the less power it consumes.
Now, people get really upset about this.
Like, no, no, no, if I run software really fast,
then it heats up my processor, all that excess heat, that's the wasted power.
But it's not, okay?
Here's the thing.
We've never figured out how to, to run processors, and
do work on processors in a power efficient way.
You know what we figured out how to do with processors that has made our
battery lives improve over time?
We've figured out how to turn them off.
This is literally how your phone, your laptop, you, like, if you have a computer on
your desk, every single proc, microprocessor, general purpose microprocessor you can get,
today, the way it conserves power is by turning itself off, as rapidly and
as frequently as possible, for as long of a period of time as possible.
The more your processor turns on, the less this, this little green goes yellow, and
then red.
And, bad stuff, right?
So we actually want to make code faster in order to save battery life.
Universally, this is true.
There, there are some extreme exceptions to it, there's some really weird stuff around
out on the fringe, but 99.9999% of the time you want to run code faster to save battery.
Okay.
The batteries aren't the only story when it comes to saving power.
This is one of Google's data centers, okay.
Now you'll note that this is a very large building.
And it is cons, it the only thing it is
doing is taking electricity and turning it into heat.
>> [LAUGH].
>> That is its job.
And it, it's really good at its job, okay?
And unfortunately, electricity costs a lot of money.
And in fact, it's not, it's, it's a finite resource.
There's a certain point at which the cost goes away.
You simply cannot have any more electricity at a particular point in time.
And so power becomes very, very important in a data center, as well.
And I find it interesting that,
that it's on the two extremes of computing platforms that we find convergence, right?
When you drop to a phone, or
when you go up to a data center, all of sudden power dominates, right.
And we get, talk about compute per watt.
This is another picture of a data center.
By the way, I just wanna clarify what this is because this is one of my favorite pictures.
Those are enormous steam vents blowing out water vapor.
And apparently, I don't know this, but apparently, when you can see the water vapor,
the data center is operating at peak efficiency.
Because it means, it's not too hot,
it's not too cool, it's actually like efficiently cooling the cen, datacenter.
Anyways, random trivia.
So we end up wanting compute per watt.
And that tends to dominate in the data center.
And this is actually kind of the same thing we're trying to pull off on a phone or
anything else.
We want to maximize how much compute we can get out of
the watts we're going to burn while the chip is turned on.
Make sense?
All right.
Now, I say that raw speed isn't everything because, because when, when we talk about,
you know, performance is really important we, you'll get some mixed messages from people.
How many folks have heard this adage.
After all, Java is faster than C++!
How many folks have heard it?
Come on, you can be honest.
I've heard it.
All right I, I, I had, I had James Gosling sit across from a table and
tell me I was an, a complete moron because I didn't believe that Java was faster than C++.
And at the time, he was right.
And I learned better.
So it turns out that Java is faster than C++ in certain very specific scenarios.
For example, if you have a specific appla, application.
And your specific application is going to run for a long period of time,
and you're concerned about the throughput of that application.
And you have a very well tuned virtual machine for your, your Java, and
you've tuned the garbage collector to precisely match the, the,
the desired kind of garbage collection interrupt frequency for your application.
If you get all of that, Java will very often beat the performance of C++.
Unfortunately, it's a bit hard, all right?
But Java, Java actually can beat performance of C++.
Now, I'm not being entirely serious here.
You know Java's faster right like, it's, it will work for all these things, so
why are we here, why aren't we still using C++?
Like why aren't we at JavaCon?
I told you I was gonna troll some.
Well, [SOUND] C++ doesn't give you performance, okay?
It's not gonna magic up some performance that that's gonna make your program faster.
Java isn't gonna give you performance either.
The thing that C++ gives you, that I think is particularly valuable,
is it gives you control over the performance of your application.
When you need to fix a performance problem in C++,
the means to fix it are fairly direct, available, right.
And they tend to not ruin your software, okay?
And in Java, this is actually a lot harder, I feel.
I think this is why we have this perception of a performance difference between
Java and C++.
Okay, it has much less to do with the intrinsic speed of the languages and
much more to do with how easy it is to take control over your performance.
Right, to actually change it to work the way you want.
Okay.
So with that bit of motivation,
I want to talk about the two ways that I view performance, okay?
My high level thesis is that there are two kind of,
you know, sides to the perfomance coin.
One is actually efficiency, not performance, okay?
And efficiency comes through algorithms, all right.
Primarily you're, you're going to get efficiency through algorithms.
You don't get efficiency through almost anything else.
But performance you get through data structures.
And I think this is gonna be kind of interesting.
I don't believe there's a whole lot of performance gained from changing algorithms,
whereas you can have tremendous performance gains from changing data structures. 'Kay?
So
lets, lets actually dig down and see why I'm making these claims.
First thing we need to understand is what I mean by efficiency, all right.
Precise definitions here.
well, somewhat precise.
How much work is required by a task, right?
You have some task, you wanna compute something.
How much work do you actually expend to compute that, okay?
Now, improving the efficiency of an algorithm, right, some,
some kind of algorithmic computation typically involves doing less work.
I like this understanding and this definition because it's very simple.
You can explain it to people.
It's like well, I could do a whole lot of work, or I could do less work.
It gets me the same result, right?
That's an algorithmic im, improvement.
That's an efficiency improvement.
These are, these are incredibly powerful, right?
You almost have to do these or, or your software runs terribly slowly, right?
And this is what we, we, we understand at a fairly intrinsic well, right?
Now a different thing I want to define is an efficient program, right.
Not just efficiency, but what does it mean when you are efficient?
Well, for the purposes of this talk, let, let's, let's talk about efficient as,
you know, when, when you've kind of reached the minimum amount of
work that the particular problem you're trying to solve necessitates.
Right, for some kind of theoretical algorithmic complexity argument we
believe that this is, this is the best algorithm on the table.
We can't do less work and actually get the results we need here, right.
That's an efficient program.
It does a minimal amount of work.
Folks happy with this definition?
All right.
So, performance, right.
So how do we actually define this.
How quickly a program does its work, 'kay.
So, so the idea here is that if you want to improve performance, you don't do less work.
That would be changing how efficient your application is, right?
What you do is you actually you have to do the same amount of work faster,
in time, okay?
And that's what gives you a performance improvement.
Does that make sense to you folks?
All right.
Now, the other thing I wanna point out is that there's no such thing as performant.
How many folks here think performant is a word?
>> [LAUGH]. >> It is in German.
>> [LAUGH].
>> Performant is not a word.
I don't care what Wiktionary or
some other user edited, you know, dictionary tells you, performant is not a word.
And there's actually a reason why performant is not a word, okay?
There, there is not a point at which a program is, is,
you know, doing the, the, the maximal speed of work, right?
What is the maximal speed of work?
Well we, there's actually, like, this Bremermann's, like,
thesis about, about, about the limit at which, you know, you can compute something.
But, this thing involves, like, the speed of light and other, like, crazy constants.
Just totally unrealistic.
There's nothing, there's nothing real about that limit.
And so calling something performant as if like, oh no,
we're done working on it now, right?
It's efficient and it's performant, right.
Can't be improved further.
This doesn't make sense.
Okay, and, and so just erase this term from your vocabulary, okay? Yes?
>> Does it mean,
performs to a minimally acceptable level?
Does it mean, so the question is, does this mean it performed, it performs.
>> It performs well enough.
>> It performs well enough, it performs to a minimal acceptable level.
I would suggest saying, it performs well enough.
>> [LAUGH].
>> As a slightly more precise statement.
I, what is performant?
Like, the thing is,
if you draw the analogy to efficient, right, then it's highly misleading.
Right?
An efficient algorithm we think isn't wasting anything.
But, like I, performing well enough could still be leaving a whole lot on the table.
I actually would argue that, that essentially every piece of software that I've ever seen,
and every piece of software that you have ever seen, is, is,
you know, horribly slower than it could be.
Right?
So, so, what is, what does it even, what is good enough?
I don't, I don't have a good answer here, right?
And so I would actually say what you mean there.
So what does it even mean to improve performance if we don't have like
an instinct in mind, right?
If there's not, just like limit, then,
then it becomes a little bit harder to understand how we're making progress?
So I'm gonna define kind of a more practical limit here than the, than the like
theoretical computational limit according to physics because that's not useful.
Okay.
So, so there are a couple of assumptions that we need to have in order to define,
what the kind of the limit of performance is, right?
The software's going to run on a specific, real machine, right?
Not some theoretical physical construct.
It's not going to store data in a black hole, right?
And if you read some of the theories about computational, like,
like, theoretical possibilities.
They actually, they actually talk about black holes as computational devices.
It's very strange.
I don't understand, I'm that terrible at physics, so I don't understand this.
But specific machine, right?
And there is a theoretical limit of the,
the rate at which that machine can process data, right?
There's a limit on exactly how quickly it can do in any particular task we give it.
There is an actual theoretical limit to that, and
that's the limit we should be striving for.
Another way to think about this, which isn't an entirely accurate but
I find it a very useful way to think about this,
is that we're trying to light up all the transistors, right?
We're trying to actually engage the entire chip,
the entire piece of hardware available to do a computation.
In order to do that computation as rapidly and as effectively as possible, right?
All these things, you want all of them, rather than you know, cause usually,
usually we, we get like a little tiny piece down here to work on our problem.
A little tiny piece up here, folks know what this is?
>> [INAUDIBLE]
>> Okay, this is, this is the Sandy Bridge Intel CPU.
Okay.
Sandy Bridge Intel CPU.
There are eight cores on this thing.
There's, there's a bunch of logic processing down here or
well, this will be the cache, the logic processing up there.
One of them, right?
You've got, you've got more cache in this middle section and
you've got a bunch of cores.
These little mirror exceptions on each side, those are, those are the cores of the CPU.
Okay?
And these, and you can kinda see the layout, it's very similar,
there's a lot of symmetry to it.
But, but the really fun thing, and I, I, I couldn't find an image of this,
is they've done some heat maps of the CPU, when you're doing computations, to see how
many of these, how much of the chip you're using to, to do work, and it's very little. Right?
It's actually very, very little.
So, that's, that's actually part of the problem.
Okay.
It, it, it really all comes back to watts.
If we have circuits, if we have,
you know, traces on this chip that we're not using, then we are wasting them.
I mean, we, the, the, the, the chips do amazing things to mitigate this.
They'll actually turn off whole sections of the chip to save power.
Like subsections of the core will be turned off to save power.
But ultimately, we're still wasting at least the space to actually put those pieces of
the chip in. Right?
We could have a faster chip,
if we just made it all the parts that we were going to use.
And if we could use all of them.
Now, don't take this to the, the absurd level, please.
I've had a bunch of people who have heard this argument about lighting up
all the transistors.
And they were like, well, I could light up all the transistors, buddy.
[LAUGH]. >> [LAUGH]
>> Like.
Just give me one minute here, I'll light up all those transistors.
And, I'm not talking about that, okay?
I, I'm really talking about, you know, using, productively, the entire chip, right?
Trying to effectively leverage the hardware that we have.
Make sense, folks?
This is how I think about performance. Okay.
So, let's think,
let's talk about how we actually get better efficiency through algorithms?
All right.
Algorithms, I think you guys probably have a pretty good understanding,
how many of you folks here have had an algorithms like, you know,
complexity theory class?
Everybody's hand goes up, I hope.
Okay, I'm not gonna spend lots of time on this, right?
The, algorithms are really nice to work with, right?
You can play with them at higher level languages.
You can experiment with the algorithms.
You can figure how they're doing the work, where they're wasting effort, right?
It's really, really easy, because it carries across all the languages,
it doesn't matter what your processor is, or your, your system looks like,
algorithm complexity is this like really nice common mathematical concept.
And, and so I'm hoping that you guys are good here.
You're really good, here.
But don't get the lazy.
You have to be, you have to pay attention to your algorithms.
It's incredibly important.
It's more important than everything else I'm gonna say.
The only reason I don't spend more time, is,
I think you guys have a very good understanding of this, already.
So the only thing I want to actually spend some time on, is a particular example of how,
how you need to adapt your thinking when you're actually writing software to
see that there is an algorithmic opportunity, right?
I know that you guys know how to analyze algorithms.
I know that you guys understand like, you know, what the complexity cost is?
But how do you break out of the, the model of, you know, writing software to
think about like, oh, hold on, there's a more efficient algorithm here, right?
And it all centers around doing less work.
You have to realize when you're doing work that you did not need to do.
And my, my example here,
my favorite example for algorithmic improvements is sub-string searching.
Cuz everyone knows about sub-string searching, it's old, right?
It's been well done.
Marshall over here has been through this about 80 million times.
Hopefully I haven't gotten any of this wrong, Marshall.
Just like, heckle as much as you need to, right?
So, of course you start off doing sub-string searching, and
you get an in-squared algorithm.
Probably, you folks probably understand why this would happen, right?
You're looping over, over the string, looking for, for your sub-string, right?
But you're also looping over your sub-string to see if you found a match.
And that means you can actually loop, you know, twice over everything.
It's no good.
Well, there's some kind of obvious waste here, right?
You're looping over the sub-string many, many, many, many times, right?
That's, that's work, right?
Is there a way to not do that work? Right?
And the first approach we have, right.
Is, is kind of the Knuth-Morris-Pratt approach.
Which essentially loops over your sub-string, computes some, some special table
information, so that you can actually skip ahead as you're scanning for a match, right?
So that you don't keep iterating over your, your, kind of,
your, your sub-string, when you're looking in the larger string, right?
That's how you save work.
It's an algorithmic improvement. Right?
And the second one is,
is Boyer Moore and, and this one's kinda really interesting because it realize,
well, you still spend all this time at the front of your stream, right?
We can do way better than that if we jumped to
the back of the stream,
>> [COUGH] >> Cuz we'll
skip over whole chunks of the text we're actually searching in.
Not just skipping over the, the sub-string, right?
So, you can skip sort of the back,
then however long our needle is that lets us jump ahead faster.
We do less work.
You want to look for
ways you can do less work any time you're dealing with an algorithm.
Makes some sense.
Excellent.
Okay.
There's yet
another perspective on doing less work though that has nothing to do with algorithms. Okay?
And I want to talk about this because I
see this come up time and time again.
Where people don't understand why their code gets kind of slower, and slower and
slower over time.
And they profile their code and nothing in their code is slow.
Just kind of everything is kind of not fast.
And they, they'll come to me and they'll be like what did I do wrong?
And usually I'll spend five minutes looking at their code and I'll find you
know a hundred things that they did wrong and none of them will make a difference, okay?
So this is very frustrating.
Now a lot of this, not all it sadly sometimes the problems are much more subtle.
But a lot fo this comes from kind of a systemic minor efficiency problems.
That don't have to do with algorithms.
They just have to do with mistakes.
And they're easy to make.
So I wanna call them out.
So you guys really, really watch for them.
These can cost you a tremendous amount of performance.
Okay.
So here is very basic code.
Does anyone here think that this code is slow?
Got some hands, okay.
So, so you'll probably know exactly what I'm looking, I'm going to suggest doing.
I'm gonna suggest that, you know, we don't actually need to,
to allocate memory every time we do push back.
We can reserve it ahead of time.
We know how many elements are coming in.
We can jump right to the end and just have the memory available.
Right?
Now, we've added a line of code.
How many folks think that this code is more complex?
How many folks think this code is more complex?
A little bit more complex.
All right, how many folks think that this code is more clear?
I actually think this code is a lot more clear.
Because now I know that you're you actually expect this pattern.
This wasn't a mistake, right?
You didn't do something by accident.
There was not like accidental goof here with your push back.
You actually ment to push exactly as many elements as, as were in this imput, right?
It makes the code very, very explicit.
I like that.
Okay.
The nice thing is that it also removes wasted effort.
We do not need an amortized growth construct to do this efficiently.
We don't need all of the complexity that vector brings along for
the ride, whom we don't reserve.
All right, so by taking a very simple step of explicitly documenting what we want to
happen, we actually make the code more efficient.
Okay, make sense?
All right.
What about this code?
How many folks think this code is, is reasonably efficient?
>> [COUGH].
>> No one.
Good.
Okay, how many folks think this code is big O one?
You think?
Anyone think this code in linear?
I'll give you a hint.
This code in linear.
[LAUGH] Okay.
So, so what's going on here?
We have, we have a string key, right?
We have a giant, you know, map of data structure, right?
We look up a key in the data structure.
This is a silly, silly example.
It's a very silly example.
But it comes up a lot in code.
Now why who here thinks this code is, is linear?
>> Is linear in the length of the key in the menus.
>> Linear in the length of the key.
The, the code is linear in the length of the key.
Okay, let's assume the key is small.
[LAUGH] How many of you think that this code is linear.
Stefan.
>> It's linear because if that key's a control finder captor, it can force a captor.
Yes, okay, so Stefan points out a very subtle thing that,
like, if you, if you have some, some malicious attacker, attacking your code,
that can actually force the key to always go into anyways.
I'm not worried about malicious.
Why is this just boringly bad?
>> [INAUDIBLE].
>> Okay. If it,
it keeps computing the hash of this key.
So every time, so the way unordered_map works.
All right, right.
We give it a, we give it a key.
It has to compute a hash, takes that hash, it has to fit that hash into a hash table.
It looks up in that hash table.
It then chases some pointers then finds some, some, some data and it gives you an answer.
Now, how many times do we do that here?
We did that like four times, okay?
And we got the exact same result every single time.
Okay?
We do not need to do this four times.
This is actually really expensive.
I have found a preposterous amount of code,
which is actually slow, purely because of this pattern.
Okay, and I'll get to why it's slow because of this pattern.
But the key to realize is that you're wasting effort, okay?
We can do this much more efficiently.
Not more, not increasing the performance, we can just do less work.
Right?
We add this one simple variable.
>> [COUGH]
>> And all of a sudden this code becomes fast.
Okay?
Very, very straight forward. Now
>> [COUGH]
>> Why do I bring up these simple examples?
I bring up the simple examples because it
is critical
>> [COUGH] >> That you always do this things.
Okay?
Not some of the time.
Not after profile discovers a problem.
You won't find a profile that points to these problems.
That's part of, that's part of what makes them really tricky.
Okay?
The key here is that you always want to do these things because they don't actually make
your code worse.
If your code isn't important to perfor, to performance. Fine.
Okay, it's still readable.
All right.
It's not getting a lot more complex.
You're not adding a burden for a future maintainer, right?
If anything you're making it more explicit and
clear what the intent of the software is, okay.
You should do these things by rote, by habit.
You should do them everywhere in your code, right.
This is one of the things that I learned working on the LBM and
Clang open source projects because they are absolute zealots about this stuff.
They are crazy about micro-optimizing these kinds of things.
And people get angry cuz they're like, but this is a micro-optimization.
And it's really not.
Like, sometimes, sometimes they go overboard and they ask you to
make your code more complex or less readable in order to achieve something like this.
But this is not more complex or less readable.
But anyone here think this is more complex?
Anyone?
'Cuz I, like, I actually think this is way less complex because I actually like,
pulled one thing.
There's nothing else going on here.
I, this isn't a micro optimization.
This is just writing elegant code that happens to also be very efficient.
Okay.
And this is why efficiency is so much more important than performance, right?
You can make small mistakes like this, they can add up in costs.
>> [COUGH] >> Yes?
>> [INAUDIBLE].
>> So, so, so the comments you know, in this case I'm also using
the default constructor on the option of the dictionary and, and yes I am.
However there is no way with unordered_maps current interface to,
to insert something without that constructor.
>> [INAUDIBLE].
>> So, so, so the question is is there a balance between the default constructor and,
and, and doing it this way.
Not really.
So I don't think this is, this is too bad because if you look at the old code, right?
I was gonna default construct this anyway.
All right, no matter what I do, I will default construct it first and
then insert into it.
>> [INAUDIBLE] >> There are other ways to check.
I actually don't think that those matter a lot and their much harder to reader.
And I would, my whole point is that you shouldn't, you shouldn't,
do something that makes you code hard to read for the sake of this.
But you should do it when it's actually not hurting your code at all.
and, and one, one of my questions about actually the, the, the Center Library is,
is I actually think it's a real problem that it makes your card more hard to read.
The other problem is, and this is I wish I had put is on a slide.
So if, if you do so, so, the idea here is that you can do a find, and
you can use the find to determine, oh,
this isn't in the unordered_map, without ever constructing the object, right?
And then you can only insert into it if it isn't.
However, that actually will compute the hash twice, that will actually do
the look up into the hash table twice and, and that's almost certainly more expensive.
If that isn't more expensive it's expensive enough to remove, make the default
constructor cheaper or don't store really huge objects in hash tables, right?
There are other things to store them in.
Makes sense?
And, and you'll note that I used an example here of a unique_pointer in a hash table.
I actually think this is a great design pattern or
at least, it could be a great design pattern, which keeps your look-up table very small,.
>> [COUGH]. >> Very efficient and
keeps large data kept to the side.
>> Question. >> Yes, question.
>> [COUGH].
>> I happen to agree with you that we should do this, but on the question of whether it's
more or less complex, I'll give sort of a, a devil's advocate argument which I think is.
The code itself, I mean, is not more complex but it does require more concepts to
understand for a new developer who may be less familiar with things like references or,
you know, memory allocations observed in your earlier example.
>> Okay, so the comment is that this may actually be more complex in some senses,
cuz while the code isn't getting more complex there, there are some more C++ concepts at
play in this code which a, which a, which a reader would have to be aware of.
I can't, I, I can't really disagree with that.
However I don't believe that it is possible for a programmer to effectively and
correctly use a C++ data structure without understanding references and, and
how they interact with that data structure, and
so I'm not particularly worried about adding that burden.
I mean, I'm a little worried, but not a lot worried.
Yes?
>> I would argue, the solution to that is code review.
>> And, and, and, and, there's a comment that the solution to that is code review.
Another question?
>> [INAUDIBLE].
>> So, so, the, the, the comment is wouldn't it be better to insert, which returns a pair
of boolean iterator rather than to just you know, directly get, grab a reference.
That's actually a great question.
If the default constructor were not, like, really convenient for determining whether or
not it's in the cache, I would agree with you.
But if you imagine writing out the code with the insert,
it will be horrible compared to this code.
Okay?
Now, now, there, what you may be pointing out is
just how bad the interface to this data structure really is.
[APPLAUSE].
I'm gonna come back to that.
Okay, so there's a whole other of talk about that.
Okay.
So always do less work.
Always do less work.
One more question.
>> Just a statement, don't call reserve in a loop.
>> A statement, don't call reserve in a loop.
I don't believe I did.
>> You did not.
>> Okay.
[LAUGH] Whew.
Yes, I agree, don't call reserve in a loop.
Call reserve when at one point you have a priori knowledge this is the likely or
desired size.
Yes?
>> In the previous example you, didn't you call, didn't you return it by value?
>> I did return by value, yes.
>> [INAUDIBLE].
>> So, so, so the comment is, didn't I return this by value?
I did, and I should not have, because this is subtle.
And I apologize for being subtle in a slide that's supposed to be intro thing.
This is more efficient than moving it.
But that's a bug in the language.
>> [INAUDIBLE] >> [LAUGH].
>> So, so most unfortunately, if I were to move this local variable into the result,
that move construction could not be alighted by the compiler.
However, because this happens to be the first variable that I declare, and
because I return it from the only return statement, I can actually have named return
value optimization fire here, completely allied the copy, and it's more efficient.
Again, I'm sorry, I should have not, I did not mean to dive into that level of detail.
We're not supposed to be focused on the return value here.
>> You can also pass, you know, the pointer to the array [INAUDIBLE].
>> The comment is that you could pass a pointer in to this I, I, please don't.
>> [LAUGH].
>> [APPLAUSE].
>> I, I, that's bad.
Okay, so, so why is that bad though?
You could pass a pointer in but when you do,
all of a sudden the, there, there's no way to tell where that pointer came from.
There's no way tell whether that pointer points to you know, the same thing that,
that, stuff going into access constructor points too.
There's, like we lose a ton of information about what the semantics of this program are.
And if you actually have a very nice optimizing compiler,
it loses that information, as well.
And you'll see it actually produce more poor code.
Output parameters are not faster.
It's, it's kind of a myth, okay?
Return value optimization, named return value optimization, and move semantics,
essentially removes the need for output parameters, from a performance stance.
There are there are extreme edge cases where they still matter, but
they're rather extreme.
And they usually aren't strict output parameters,
they're usually input output parameters, which are just a totally different beast.
Okay.
So trying to make a little bit more progress.
So, always do less work.
The other thing I wanna mention is I don't just want you to be
thinking about this with the STL data structures.
Those are important, right?
But you guys are gonna be designing your own APIs, and
when you do, you need to be thinking about allowing the users of
your API to do less work when they know they don't need to do the work.
Right?
This is actually a two-way street, both the design of the API and
the usage of the API have to work in concert to actually have efficient code here.
All right.
So, now let's talk about performance and data structures.
All right.
So, I'm gonna give the game away.
Discontiguous data structures are the root of all performance evil.
This is simply a fact.
If you don't believe me, I'll try to convince you.
specifically, please say no to linked lists.
Okay?
Please, please say no to linked lists.
There is almost nothing more harmful you can do to the performance of
an actual modern microprocessor than to use a linked list data structure.
So why do I say that?
First, we need to understand the context here.
Have a modern processor.
I, all of my numbers, by the way, are targeting an intel Sandy Bridge CPU x86.
I'm sorry I don't work on ARM.
If you work on mobile devices this will be a little bit less relevant, but not much.
So we have, you know,
roughly a billion cycles per second, which is kind of an annoyingly big number.
We have 12 cores in every, you know, socket on your motherboard. Right?
We have three execution ports per core.
This is essentially how many instructions that core can execute simultaneously because
your chips are actually executing multiple instructions in every cycle.
This means that we can execute something in the ballpark of
36 billion instructions every second, okay?
Now unfortunately, most of that time is spent waiting for data.
About 50% of that time in almost every application.
In some applications upwards of 75% of that time is actually spent waiting for
data rather than executing instructions.
If this horrifies you, good.
It should, right?
This is terrible, right?
If you ever wanted to know why software is getting slower so
quickly, it's because of this.
We need faster memory.
Unfortunately, we don't know how to build faster memory, right?
We'd like to build faster memory, but we have no idea how to.
So, what do we do?
At this point, you need to understand how the memory architecture and
hierarchy of a processor works.
And the best way to understand this is with, I think,
literally my favorite table of data about performance in the world, okay?
So, this is from Jeff Dean.
Works at Google.
You may have heard of' him.
He's kinda of smart.
He knows a lot about performance.
He he wrote this down, to, to, because he kept getting questions.
And he kept getting into discussions which pivoted, the,
the disagreements in the discussions, pivoted around a different understanding of, kind of,
the basic back of the envelope, timings, of different operations.
And so he just summarized how they break down.
Okay.
So the ones we'd really wanna pay attention to here are the,
are these, these ones with L in them.
L1, L2, and down here we have L3.
No the, he doesn't have L3 in there.
And main memory, right.
So main memory is way down here.
Way down here.
Okay.
So the way modern CPU's work is they have layers of
caches on top of main memory that are much, much faster.
But the trade off they make for being much faster is that they're very small.
All right, they can only hold a very small amount of data.
And the way they hold small amounts of data is that you have a, a line of data, right?
You, some number of bytes of data.
It's usually very small, around 64 bytes, 128 bytes, something in that range, right?
And this line of dat, of contiguous data is held in the cache.
And it can hold some number of these lines of data.
Maybe it's, you know, 100,000.
But it's not millions and millions and millions of them. Okay?
And so you run out, right?
The way the processor fetches your data is it asks the L1 cache,
cuz that's the fastest one, you know, do you have that data?
And it's really fast.
But the L1 cache is tiny, all right?
And if it doesn't have the data, then you fall back to L2.
And if that doesn't have the data, you fall back to main memory.
And we're at 20 times the speed of L2.
We're at 200 times the latency of L1, all right?
So it's roughly 100 times slower than a cycle.
Now, when you think about like, you have, you have one cycle.
We can execute, right, some 36 operations in a single cycle.
And it takes100 cycles to get a byte of memory into the processor.
We have a problem, okay, and the only way to solve this is actually to
get your data into one of these higher caches that's actually going to be faster.
There is no other solution, you have to get your data to fit.
'Kay?
And so everything is designed around having contiguous data and
a small amount of contiguous data so
that it can stay reasonably populated in these L1 and L2 caches.
Modern processors also have an L3 cache that's even larger,
it doesn't really matter for the explanation though, right?
It's, it's caches all the way down.
Caches all the way down. Okay.
So how do, how do,
you know, mainstream data structures, then interact poorly with this?
Let's look at standard list.
Anyone here use standard list, in, in code?
Come on, like, some of you have used standard list.
No, it's okay, don't be embarrassed.
Some of you have used standard list.
I've used standard list in code, okay?
Now, it's a doubly linked list, it's very nice,
it's very generic, it's very flexible, it's got a great API well, an okay API at least.
Each node is separately allocated.
That's actually it's killer.
Each node is separately allocated,
that means that those nodes could be placed anywhere in memory they like.
There's no predicting, okay.
And every traversal operation on a list has to chase pointer after pointer after pointer.
Pointer from node one to node two to node three to node four, right.
You guys know how a linked list works, right.
Right, and that's really slow.
Essentially every single time you traverse that pointer, you take a cache miss, right.
You drop down this hierarchy, right.
And so every time you move from one node to the other, assume that you have
essentially a 1% chance of being in L1, you know, maybe a 10% chance of being L2 and
a, you know, more like an 80% to 90% chance of being in main memory and
you'll understand why these things can be incredibly slow. Okay?
Now, if you're lucky, right?
If you're lucky, or if you work very hard, you may be able to pack these things
slightly more densely, but you're not going to get lucky for long.
You're going to actually have cache misses, okay?
So, so standard list has a real problem, there.
Now, it does have a good use case.
If you very rarely traverse your data structure.
I mean, very rarely, right?
Algorithmically rarely.
It can be very useful for improving the algorithmic properties of updating your
data structure, right, and that's where a linked list really shines.
If you traverse your data structure, you know, on the same order of magnitude,
number of times, as you update your data structure, you should never use linked lists.
Ever.
Right, it's just, it's just terrible.
Making sense to folks?
Any, like, anyone want to challenge this?
Are you're all just like, you're drinking the cool aid, you're happy.
>> [LAUGH].
>> I mean I'm, I'm good if you guys wanna drink the cool aid, right.
That's okay.
So just use STD Vector.
That's what it all comes down to, just use the vector.
It's better, okay?
A lot of people respond, like, but what about stacks or queues.
Well okay a vector is a stack.
Yes.
>> So what about, iterator invalidation?
>> W, the question is what about iterator invalidation?
the, the answer I have to that is, is yes, some problems are hard.
Still don't use the linked list.
[LAUGH].
In a more serious answer to that question,
there are good ways to avoid iterator invalidation.
And I'll actually mention one cuz I'm gonna,
I'm gonna hit an issue of iterator invalidation.
Okay.
So, so vectors are stacks, right?
So you're done.
But queues are actually interesting.
But there's this great trick you can use to make your vector into a queue,
most of the time.
If you have an unbounded queue that just grows, like, for
the entire life of your program and is totally huge, this doesn't work so well.
But if you have a reasonable bound on your queue,
either on the lifetime of the queue, or you know roughly like the maximum number of
elements you'll ever want to insert into the queue, you can use a much nicer approach.
Have a vector, insert the things into the back and
just don't remove them from the front.
Keep an index, write what you move forward through the vector, and
because you're not removing them from the front, you won't invalidate anything, right?
Not gonna invalidate the indexes into this vector, it's very, very convenient that way.
Don't keep actual iterators because pushing onto the back of a vector will
invalidate iterators.
All right? Indexes into vectors are actually really,
really powerful because they are invalidated less often, right.
And then just keep your index moving forward.
You can even move out of the front, objects, right?
You can just leave the little, like,
husks of partially formed objects, if you like Sean Parent's view of it.
Or, you know, default constructed objects, if you like Eric Niebler's view of things.
Right, whichever one you want.
Like, if you, you can actually get all of the efficiency you really need here,
as long as you, you're okay essentially having a vector the size of
the total number of elements you need to process.
Now you can't always do that, but
when you can it's a much more efficient data structure.
And there are kind of variations on it where you can essentially reuse a vector in,
in, in various ways to achieve much, much of the same results.
It's a little bit like a garbage collected queue. Yes.
>> Wouldn't a deck be easier?
>> The question is wouldn't a deck be easier?
If the standard had a good deck, it would.
>> [LAUGH]
>> unfortunately, the standard deck is one of the worst data structures I've seen.
The particular requirements on the API mean that implementing deck is just horrible.
And for some reason every single standard library implementation I've worked with for
the last you know, eight years has, has been even worse than the, the,
the in, interface mandated.
So I avoid it like the plague.
I'm much more likely just to re-roll what I need on top of a vector.
The other reason that I,
I, I tend to do this is because you rarely need all of the power of a deck, right?
The deck is kind of the Swiss Army knife of segmented almost amortized, but
somewhat linked data structure.
And usually you need like one or two of those features not all of them.
And when you only use one or two, the performance tends to be tremendously better.
Now I would encourage you to not do any of this until you've profiled because we're
not in the efficiency bucket anymore.
We're back into the performance bucket.
And this, I, I admit this is complex, but I think it pays off in the performance.
Now maps are kind of tricky.
Maps are kind of tricky because you can't just easily like, rig up, a, a,
an associate of data structure out of that factor.
It takes a little bit more work.
There ways you can do it but it takes a lot more work.
Unfortunately, using standard map is an exercise in slowing down code. Okay?
If you think that a,
that a link list is bad, maps are worse.
I, I'm gonna be really blunt here.
I, I have no code that I have ever worked with which should have used standard map.
I don't believe there are problems in real software that it solves effectively.
Okay?
So maybe a somewhat radical position, but
I would actually just strike this data structure from the library if I could.
Okay, why do I think that?
That seems radical and crazy.
So, here's the thing, standard map, it is a linked list.
But it's a linked list where all of the non-traversing operations
are essentially removed.
Okay?
Because if you want to insert into it, you have to traverse it.
If you want to remove from it, you have to traverse it.
Even if you play all of the tricks, you pull out, you know, the,
the insertion hint element into your maps so that you, you immediately jump to
the right node of your binary search tree to insert, a decent chunk of the time,
you're going to rebalance the tree, which is a terrible traversal. Okay?
And
one of the slowest things you can do on a cash oriented architecture. Okay.
Std::map is terrible.
If you absolutely must have a sorted associative container of things,
then what you really want is just a sorted sequence of things.
And, and, you know, binary search your way to associativity on top of it,
i.e just use a vector, don't use map.
But, but, but, wait, wait, unordered_map will say this, right?
>> [LAUGH]
>> Unfortunately, unordered_map will not say this.
Std::unordered_map is, is, is, to me, much more fuss.
So I, I, I despise standard map.
Because I don't feel is a good tool for any job. Right?
It's a bad tool for a rare job.
But std::unordered_map is more frustrating to me because this is
actually the job you usually have.
You usually just want to associate a key to a value.
And an unordered_map, despite the somewhat cumbersome name, seems to do exactly that.
But it does so in a terrible way, okay.
So it is essentially required, based on the standard,
to be implemented in terms of buckets of va, of key value pairs.
And, and I, I can't express to you how much of
this implementation detail bled into the interface.
You can actually get bucket iterators in to an unordered_map.
How many folks knew this?
You can get a bucket iterator in to an unordered_map, and
iterate the elements of a bucket and observe where they start and where they end, right?
You can also get an iterator over the buckets in the map, rather than over the elements.
It's incredibly hard to build a map which does not
actually use separate buckets from the hash table as a consequence, right.
And, and so what, what you end up with is, this, this great hash table which
has you know, a pair of, of a, a hashed value and, and a pointer in it.
Sorry, sorry, usually just a pointer in it. Right?
As a pointer points to, oh, yeah,
a linked list of the key-value pairs that are in the map.
So we're back to linked lists despite the fact that we were going for
the efficient data structure, these hash tables and all the other great things,
at the bottom it's actually a bunch of linked lists, all right?
They're back.
So, so, the performance of this is actually pretty terrible.
You will always have a cache miss when looking up into an unordered_map.
I mean, the first time, you might get away without hm,
you know, having cache miss the second time.
But the first time, you're essentially going to take a cache miss.
Because you're going to be chasing pointer, too many pointers.
It's extremely frustrating, okay?
And the other thing that's a little bit frustrating is that it's not that we
don't know how to do this better, okay?
A good hash table looks something like this.
You don't use buckets.
You use open addressing in to a table of key-value pairs.
Right, just a flat contiguous table of key-value pairs.
You use local probing to find where to place values when you have a collision.
The local probing here is key, okay?
You will have collision, collisions in any hash table implementation.
You're going to have them.
You have to plan for it, okay?
By, by finding and, by finding an adjacent or quadratically adjacent node to insert your
key-value pair into you actually maximize the cache locality of, of handling a collision.
The difference between doing something like what I described here,
an unordered_map, is massive.
We're talking orders of mag, like 10x performance reduction sometimes when this is
in your critical path, when you have a high load factor on your, on your hash table.
It's really, really bad how, how this actually performs in the real world.
So it would be very nice if we could do this.
The other thing I do wanna mention is, if you, if you design your hash tables this way,
you then have a constraint which is a little annoying.
You have to keep your key and values small.
So if you have enormous values, right?
Suddenly they're a little bit more awkward to deal with.
But, but there's an easy solution to that.
When you actually have an enormous value, like a really big chunk of
data that's when chasing a pointer starts to make sense, right.
And so you can put your value as a unique pointer, to the actual large data.
You keep a very data dense,
very efficient, table structure, despite having a large chunk of data.
Okay.
So.
I can get my next slide.
That's, that's my idea of efficiency through algorithms and
performance through data structure at a very high level.
Right?
Like 101, okay?
I would love to stay up here and
talk to you guys about the details here for another like two hours.
But I think we'll probably get hungry.
So the only thing else I wanna mention is that this is all a lie.
>> [LAUGH].
>> So, unfortunately it's not quite this simple.
I, I am sorry that it's not quite this simple but
there, things get a little bit more complex.
You can't just pick your algorithms in isolation to achieve the efficiency,
you know, constraints you have.
And then, when you profile, go over and pick your data structures based on those things.
It doesn't work that way, right.
Data structures and algorithms are actually intertwined. Right?
And this is
actually what Niklaus Wirth's book was all about.
That these two things, one informs the other.
And most importantly data structures have this tendency to inform your algorithms.
And so you actually have to think of both of these at the same time.
You can't, you can't manipulate them in isolation.
You have to understand why you're considering a data structure change. Right?
That's driving your performance
considerations, you have to understand why you're considering your algorithm change.
That's driving your efficiency considerations.
But you're going to potentially have to change both in concert in order to
actually have them work together.
Okay?
Now the other thing that, that, that's really frustrating is,
is, there's some places where what I described just isn't true.
Okay?
Not all performance is rooted at data structure failures.
Sometimes, you have an algorithm,
which actually just imposes a data access pattern on top of
a perfectly nice data structure, that ruins its performance on modern processors.
And so, so don't ignore the possibility of, of, kind of a reversal of the roles, here.
It's very rare.
I, I would encourage you to start off, thinking about things in
terms of algorithms for efficiency, and data structures for, for performance.
But, it's by no means a hard and fast rule.
The, the final thing I, I have to mention just for full disclosure,
we also are subject to some worse is better problems in, in the real world.
There are going to be cases where the exact opposite of everything you know or
want to believe will be true.
For example, bubble sort is the fastest sort algorithm for small data sets.
>> [LAUGH] >> Despite being quadratic and
like algorithmically and being a terrible idea most of the time, if you have under 64
like elements and they're all numbers, bubble sort will probably win over anything else.
It's really frustrating, right?
Worse is better.
And if, if the reverse kind of property is also true.
So, there was this great paper about cuckoo hashing or cuckoo hashing.
Anyone hear, hear of this, this crazy idea?
It's insane.
Okay, so I'm gonna, I'm gonna explain it in like five seconds.
And, and the idea is you, you, you know how a hash table works, right?
You have a hash function of your key, right?
You, you models it by the size of your table.
You look up that slot, that's where you put your entry.
Right?
But what, what happens when you have a collision? Right?
I'm suggesting you use
very localized probing right around the colliding spot.
Well there's another way you could do it.
Cuckoo hashing says no, no, no, no, no.
Just, just rehash things.
So there's a backup hash algorithm that you can use.
And so if you hit a collision, you swap out with the guy in the spot, and
you use the backup algorithm on, on that, that entries key.
>> Mm-hm.
>> And you find a different entry for it.
And you put it there.
And if you have collision there, you do the same thing again, right?
And you keep going. Right?
And, and
it turns out that there are all these beautiful properties with this.
It fixes all of the complexity bounds of hash tables.
Everything becomes constant ti, amortized constant time,
the hash table is beautiful and self-balancing in the collision space.
It's glorious.
Unfortunately, it means that you have a locality hostile probing pattern.
So every single probe is a cache miss.
Essentially guaranteed because you're actually, your guarantee is rare too.
And so it's never going to be warm in the cache, you're always gonna take a cache miss
and it's, it's actually significantly slower in practice than localized probing
despite having better, you know, algorithmic guarantees across the board.
It's really, really frustrating.
Okay, so.
With that, my takeaways are, you know, number one, efficiency and
performance do matter and they matter today more than ever.
Batteries, small devices, these things really, really influence it.
C++ doesn't give you performance.
It helps you control it.
It helps you make your performance better.
Okay.
Please do be mindful of your algorithms, right?
We wanna develop pervasive habits of using APIs in a way that,
that avoids wasted work and designing your APIs to facilitate that use, right?
You wanna use contiguous, dense, data structures that maximize cache locality and,
and I hope that you have some fun writing some really fast C++ code without making,
you know, your code reviewers cry at the end.
You know? And I hope that this is all true and
you guys have enjoyed this whether your performance concerns look something like this
or more like this.
Otherwise, questions?
>> [APPLAUSE] >> Questions?
By the way.
Before you ask me,
we do have mic, microphones up.
So if you wanna stand up and
go up to the microphone, then we will all, as, as Scott reminded us.
You know, hear your dulcet tones.
>> So can we have vector with in-place storage for small sizes in standard?
>> The question is, can we have vector with in-place storage for
small sizes in the standard.
What do you mean by can?
>> [LAUGH] >> So unfortunately, I, in C++98, so, so
fun factoid, in C++98.
It was actually a conforming implementation to embed a small buffer of
memory inside of your standard vector implementation.
And as long as the number of elements was below the size of that buffer,
you could store them in line.
And this is great.
You don't have to call in allocation function.
It's, it's, it's essentially perfectly cache local.
Really, really efficient.
Unfortunately, this fact, essentially wasn't awa, no one seemed to be really aware of it,
and it was broken in C++11 by a very subtle change.
In C++11, we added a move constructor to standard vector.
And the move constructor for standard vector, has this infuriating requirement.
It does not invalidate any iterators on move.
This is the only barrier to having a small sized optimized vector.
But as far as I can tell, it's a deal breaker, and, and, and
Stefan, I know you wanna say that it isn't, but it is.
>> Yeah [INAUDIBLE].
>> Anyways, this is silly and we should fix it, but
I don't think we can break the existing code.
I, I actually regret this, I think this is a terrible mistake.
I believe like, like that the small size optimization is so
valuable that we went out of our way to like, like to force it back into standard stream.
Right.
But we, we have no attempt to do this with vector.
It's, it's tragic.
All right.
>> So do you have a Google code version of a map that has all of these cool features.
>> [LAUGH].
>> Do I have a Google code version of a map that has all the cool features?
So, so, I, there is one, the open source project is really annoying to find and use.
It's, like, I don't remember what it's called Goog perftools or something?
It's in this really weird repository, it's called dense hash-map.
You can find it.
It's been copied into Chrome,
it's been copied into a bunch of other open source projects.
Protocol Buffers has it.
The problem is.
And I'll, I'll forewarn you, our implementation is suboptimal.
>> [LAUGH] >> no, suboptimal is the wrong word.
It's actually, it's actually really, really fast.
It's just really, really ugly, okay?
So, so the API design was not great here.
There are a lot of warts in the interface.
I don't really like, I don't really recommend it, wholeheartedly.
But if you need the performance, yes.
Go, go and go and find it.
If you actually search for dense hash-map with underscores, you'll probably find it.
Other questions?
>> Hello what about a custom allocated for us map?
>> So what about a custom allocator for a map?
So, so you can do that, and I'm sure that John Lakos has been thinking that
the entire time I've been standing up here talking.
unfortunately, I have two problems with that.
One is that I have maps which are on interface boundaries.
And those interface boundaries are API boundaries, and so they're not templates.
And that makes adding an allocator to a map really hard.
Okay?
So the fact that allocators are in the type system essentially means that for
a large number of applications, it's unavailable.
Now even if it is available,
the other problem is that while map gives you a little bit of locality it's pretty
common that your map types are actually about the same size as your pointer types.
And so you're getting essentially half the locality that you could have.
if you didn't have those, like, left and right-hand side pointers in there.
And so it still ends up losing compared to like a dense hash table.
Other questions?
Going once.
>> [INAUDIBLE] for our known face containers.
And that actually has a fairly substantial effect.
>> John says that, that it has a substantial effect.
I, I don't disagree.
It, it, it totally makes it better to use an allocator.
Right?
The problems I had is that it, it's of limited applicability.
Unfortunately, because of the type system stuff.
And, and I know, I know you guys are working on fixing that.
>> [INAUDIBLE].
>> Okay. So, so, so
you're saying there's a pool built of the data structure?
>> Yeah.
>> Okay.
If, if I had a standard map with that, maybe I would,
maybe I would like standard map a little bit more.
I, I, I suspect that the, the left and
right hand pointers would still make me grumpy though.
Okay.
Another question.
>> 'Kay. So now that we're all
gonna use standard vector.
>> Yes. >> Instead of anything else? Right?
[LAUGH].
>> Yes.
>> has, have you guys looked at the latest Facebook vector optimization?
Is it relevant?
>> yeah.
Oh, sorry.
I promise that was not the question.
[LAUGH] I'm not allergic to Facebook, I promise.
[LAUGH] So, so I've looked at it some.
I I have some problems with it so I, to be fair I haven't looked at
maybe the latest ones so, so back when they released their their original string and
vector optimizations I looked at it pretty carefully.
And, and unfortunately it,
it does a lot of semantic changes to achieve one particular benefit, right.
And the particular benefit is essentially the ability of the operating system to
do a reallocation, right.
To just reassessing your,
your pointers in the page tables, and give you more space without moving data around.
And that works really, really well if one thing is true and
that is that your, your, your address is not part of your identity.
There are very large number of objects in in real world C++ code who's address are part of
their identity and, and it's a really subtle to teach programmers about that, you know oh,
oh, oh, why did your performance slow down by like a huge amount well because you're,
you're, you're address entered into your identity and
so we turned off all of our data structure optimizations.
Right?
It, it's, it creates this bi-modal world where,
where this seemingly unrelated minor change to your implementation triggers
the cascading deterioration of performance of data structures.
And I really don't like that.
I would like to find better ways to do it.
and.
The other thing is that the performance benefits of that don't seem to
be all that significant.
I think a lotta the other performance benefits they got were just from
tuning the vector implementation.
Which it's in pretty sore need of.
I mean it's, it's kind of, a lot of the standard library vector
implementations are much neglected because, it's just a vector.
Why could it possibly matter?
For example, I think that the, the growth factor for a lot of standard library
vectors and limitations has been like, historically wrong and
it's only recently that they've gotten, been made more appropriate.
>> What growing factor would you like?
>> I, I, Well, the question is what growth factor I would like.
And, and I would not, like, say that off of the cuff.
I would have to go back and dig up the people who did the work to.
To demonstrate what the correct growth factor was.
It was a very small, it was very small difference that preserved the algorithmic
properties, but turned out to be much more efficient.
It was at like 12.
I don't, I don't have it offhand, sorry.
>> [LAUGH].
>> Did I see a hand, [INAUDIBLE] I saw a hand over here?
Oh, Scott, oh.
>> [LAUGH].
[LAUGH]
Presumably you're not thrilled with forward list.
But my question really is do you
have some suggestions on the kinds of data structures that
you'd like to see added to the [INAUDIBLE]
>> So, so the comment is, I, I'm probably also not thrilled with forward list, I'm not.
[LAUGH] Although, although I'll point out Forward list does have half the overhead.
Which is at least a nice benefit if, if that's the right data structure.
But the further question is what data structures I'd
like to see added to the standard library.
Number one, unequivocally, is an excellent open-addressed hash, hash table.
That is the single most important data structure for,
like, day in, day out programming, to improve performance.
I mean, by, by such a huge margin that it's kind of terrifying.
And what I'd really like to see is,
I'd like to see it's name be easier to type than all of the bad ones.
Because, like I don't know, like, I can get up here and I can give these talks, and you
guys are a great audience, and I hope you go and tell everyone else you know about this.
But this is a really poor way to ensure that programmers actually use
the right data structure.
I actually have much higher faith in their unwillingness to
type more characters [LAUGH] leading them to the right data structure.
which, I mean, I don't mean that to reflect poorly on you all.
I am a very lazy typist, okay.
So, so, so that's actually, I don't know,
I don't know how much further I would go from that.
The other things that I kind of want to see there's some fabulous work around building a,
a map, a sorted map interface on top of a vector that gives you very good efficiency
guarantees and actually represent kind of the modal operation of stop acting like a map and
let me add data to it.
Now make it act like a map again.
Right?
Sort it once, bashing up the sort.
Those types of, of data structures could actually be really, really, useful for, for
mapping and for other things, I think.
I'd also like to see, a very easy way to have something like forward list.
For example, a great forward list limitation I solved.
It uses tagged pointers to represent whether the pointer needs to be de-allocated.
Now this seems like a trivial thing but the way that they would use this is that they
would batch large allocations, and then chain together contiguous nodes in it.
Using a tag to indicate that that node didn't need to have it's memory released.
And they always allocate it from the tail up, and this allows you to do really kind of
nice pooled allocations, even outside of the data structure and I would love to see that.
I would love to see pooled allocations inside of the existing data structures.
I think that would be great.
I really want to find a solution to the kind of allocator problem that does not exist in
the type system.
And does not involve dynamic dispatch.
Cuz right now, we have either the current allocators which invade your type system and,
and cause all kinds of API guck, which I don't like, okay.
But on the other hand, we have a really,
really great attempt by, by Pablo and, and Alister, and
other people to solve that with polymorphic allocators that aren't in the type system.
But they introduce dynamic dispatch and, and
indirection around the memory allocation and that.
That's kind of, that's kind of yuck too.
And I don't have a solution to this.
I don't know what the solution looks like.
But I really want one.
Like I really, really, really, really want one.
I'd, I'd, I don't know that there are that many more data structures to add if we
have good control of allocation.
Other questions?
I mean, I'll keep talking and you, you guys, unless you guys want me to get off the stage.
>> [LAUGH]. >> You should stop asking questions.
All right, well thank you very much.
no, one more, no one more.
A noble attempt. [LAUGH]. >> This whole time I've been feeling bad for
the guy at the start that said that pass me this, pointer and you said no.
And its like maybe not passing a pointer but
passing a reference to effect everything.
Where do you use the memory for that?
>> So, so I'm gonna let you in on a secret.
When you pass references, you're passing a pointer.
I, I know that it, I know, I know that it would be nice if it weren't, but it is.
>> No, but I mean using memory in the vector.
It's like while get line.
[INAUDIBLE].
>> No, no, no, no, no, just, just, please, just return it by value.
Like, I'll let you know another crazy thing, if you return it by value and, and, and
the compiler can ever inline that function the,
the compiler will actually like deduplicate your allocations for you, it's fine.
The compiler can see allocations.
This is why I don't want a dynamic dispatch.
Around them.
As long as the compiler can see the allocations,
it can actually fix a lot of these things.
And you can keep the clean code. Yeah.
>> [INAUDIBLE].
>> no, actually I think GCC does a pretty good job of this, too.
>> [INAUDIBLE].
>> Yeah.
[INAUDIBLE] Oh, don't even.
[LAUGH] Yeah, I mean.
It's, it's just map, okay?
I, I pick on map not because map is worse or
better, but because it's used orders of magnitudes more often. Yes.
>> What about persistent data structures?
Does that, does that add [INAUDIBLE] for us [INAUDIBLE].
What about persistent data structures?
Does that not call for link lists?
Well, define persistent data structures?
>> They are immutable to everybody and you just make copies of, of the structure itself.
>> Okay, so the idea is immutable data structures which are,
which are not being updated.
Yes.
Immutable data structures are perfect for link lists, and they tend to
have higher cash locality properties because you tend to not mutate them.
You tend to have decently hot reads on them.
They're not being.
Updated very often.
they're, they're still slower than, than cache.
Like densely cache populated data structures.
But sometimes algorithmically, they're the only option available. Right?
And this is
where the algorithm data structure tie kicks in most often.
Are things like communicable data structures.
Where you have algorithmically constraints like I have to have sorted data.
It doesn't matter whether I ne, I want sorted data or it's slow to produce it.
I have to have it.
Cause if I don't have sorted data, data, the, the the rest of my algorithms fall over and,
and there's no hope right.
>> [INAUDIBLE].
>> Sometimes you can do that, but, sometimes you can't.
If you have to have if you have to have sorted data
continuously during updates right, there are very few options left to you and
it's an algorithmic constraint that produces itself.
The weird thing is that, that's insanely rare.
Right, I, so rare that I had yet
to see a single piece of code that actually needed that.
Every piece of code that did that, you can go in and
say like, well you don't really need to keep it sorted all the time.
There's this nice batch point where we can sort.
Right, but, I'm, I'm holding out the theoretical possibility that it exists.
Maybe. Yes? >> Like the a lot of the current compromise for persistent data structures.
But the, they're actually doing it pretty bad.
Nodes like the hash are a bad choice, for instance.
[INAUDIBLE]. >> So the comment is.
>> [INAUDIBLE]. >> The comment is that for
a lot of the persistent data structures,
they're trying to use larger nodes in order to, to compensate for this.
I mean, it's the fundamental argument behind B-trees,
is that rather than doing a binary tree.
We'll step a whole bunch of things in a single node so
that we get some cache locality and most b trees tend to pick cache sized nodes
roughly where they can, or nice multiples of cache sizes to, to maximize this property.
And yes, that's great and it, and it's a fabulous way to engineer cache locality
into an algorithmically constrained problem space.
But it's also incredibly rare.
Like if you're working on a file system absolutely.
But you're also probably not using standard map, if you're working on this.
>> [INAUDIBLE].
>> Yeah.
>> [INAUDIBLE].
>> All right, any other questions, otherwise I think we should get some food.
Oh, one more question [LAUGH].
>> So what.
What do you think about page erase because I mean, they.
>> Say, say that again.
>> What do you think about page erase?
Erase to where you have not to keep as well as memory, but pages?
And a hint of overhead.
>> So, so the question is what do we think about page erase?
Page erase would just be trees, just any other chunked, chunked linked data structure. Right?
It's where you're essentially trying to
amortize the cost of the links by putting more things into each linked node.
Right?
And it is an engineering trade off but it's complex it, it tends to have more bugs.
It tends to be slightly slower.
It may be the only option, but I would avoid it if I could.
>> [INAUDIBLE].
When do you want to use a, binary search or [INAUDIBLE].
>> The question is, where is the point that you want to do a binary search versus
actually doing a linear search because it's short.
My suggestion is that you call the binary search function.
And you file a bug against your standard library implementation,
until it makes that determination for you correctly every single time.
>> [LAUGH].
Yes stated library implementor.
[LAUGH]. >> In the case of lower bound and
friends we are unfortunately required to perform login i dont believe
we can go an-
>> So, so Stephan points out that, that the standard requires that you evoke login.
And, and, so, so, so, that's not, that's not an option.
And I challenge that.
>> If it's order log in though, we could be seeing that.
>> Because if the order log in, then the constant factor is fine, and
I'm, I'm pretty sure, I'm pretty sure we could, we could make this work.
Any other questions, and maybe we could actually get to dinner?
[SOUND].
[LAUGH].
>> What does the leverage stand to
why one [INAUDIBLE] like [INAUDIBLE].
>> So, so the question is why does Sarah Levy only provide a single layer of
data structure rather than providing a large number where people can pick and choose.
I have a lot of answers to this I will give the short ones, ,.
The first one is, do you trust developers to pick and choose?
I don't.
And I don't mean that as as insulting thing.
I just don't think that they have the time, energy.
Or should spend the time or
energy, trying to choose between 50 different, like, crazy tree implementations.
I would much rather that there are reasonable defaults.
The, the second reason is that, as, as,
as you tend to have more variations, I think you tend to be domain specialized.
And when you're domain specialized,
you probably just don't want anything from the standard library, or at most you
want some utilities from the standard library to build your own data structure.
And, and so I think you see very rapid dominitioning returns there.
Where it would actually be better to just make it easy for
them to define a domain specific data structure that does exactly what they want.
That that actually tends to have really good results in practice.
And with that I think we should get some dinner.
It's been a pleasure.
Thank you very much.
[APPLAUSE].