CppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures"

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 the Clang and LLVM teams at Google

And I'm here to talk to you a little about performance.

and efficiency, and making code fast,

and all the different things that go into that.

But before I do too much

I want to give actually give you guys a little bit of

one might say are expectations.

Because I have been reading the twitter feed

from all these folks, that talk about

all these crazy good questions

I just want you guys to essentially know

this is my view

of what Performance 101 should be.

Okay? This is going to be kind of an intro talk.

You guys are hard core, really deep performance nuts.

You may be a little bit bored, and please be kind,

because I'm going to gloss over some things

you could heckle me thoroughly if you really want to

We're going to talk about efficiency, performance,

algorithms and data structures.

And the first thing we are going to do is we're not going to talk about them.

We're going to talk about why anyone cares about them.

How many folks here think it's really important

to have high performance in C++?

Raise your hand if think that it's super important.

Everyone thinks it's important!

And the folks here who have a really clear idea why performance is important.

Now, all the people who didn't raise their hands the second time,

Please reconsider raising your hand the first time.

We actually need to understand why performance is important in C++,

before we actually decide it's important, we're going to care a lot about it.

I'm going to tell you why I care about performance in C++.

Most of it comes down to a quote from Nicolas Werth.

Which I will try to pronounce correctly but fail miserably.

I actually really like a lot of our stuff,

I think he encapsulates a lot of my thoughts,

what's core to my philosophy here.

The software is getting slower more rapidly than

hardware becomes faster.

This is particularly in contrast to

the kind of normal Moore's Law approach:

Hardware's getting faster, all the time

it's okay, we don't need to make software faster,

because the hardware will catch up.

And it turns out that's not really true.

We're really good at writing slow software.

Even in C++, we're really good at writing slow software.

It's hard to write fast software,

and it takes a lot of effort.

And so it's important to think about

why that might matter no matter how fast

the processors get.

And to give you an idea of just how much

I think Nicholas Werth is on the same page

I just have to mention he actually wrote a book

entitled Algorithms + Data Structures = Programs.

I did not realize this as I was picking

the title of the topic.

Anyways, we're going to come back

to the title of this book.

Because he predicted some whole elements

of this talk in this book.

So how many folks here have read this book?

Anyone? All right! A long time ago.

It's a good book. It's a good book.

Okay, so I actually think the idea that

software is getting slower too quickly, right?

is really getting slower at an astonishing

rate is even more important than before.

And for pretty specific reasons.

There was a very seminal event that

happened in the technology world some time ago

that changed, in my opinion and a lot of

other peoples' opinion, how we look at

computing devices, the performance of

computing devices, the challenges we face

running software for computing devices.

And this event was the iPhone. Okay?

And when Steve Jobs introduced the iPhone,

he was not doing anything particular to C++

but he was changing how we

think about computing.

Mobile was now a first class compute citizen.

It took the world a little while to even

realize that 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 hard and challenging

to fit big bulky systems into.

And we essentially get into this annoying

situation of, we have small, we have fast

machines. We have to choose one.

We don't get to choose though.

We're going to choose small almost every time.

But it gets worse.

Because the other problem that the iPhone

introduced that people weren't

really focused on at the time

was the problem of a battery.

What do we do about the battery in your phone?

You phone's battery, I mean my phone's

battery is about dead. Right?

How many folks here have charged their

phone today? (Laughter from audience) Okay?

That's a problem. That's not a feature.

That's a bug. (Laughter from audience) Okay?

Yes, How many folks are charging their phone now?

(Laughter from audience) Okay so we kind of

entered this new problem domain, suddenly

power became relevant.

There's some kind of shady research I want

to push back against.

There's some research into power efficient

instructions. If you ever read about power

efficient instructions or optimizing

power usage, you should become very suspicious.

And you should probably run the other direction.

Because this is mostly total junk science. Okay?

Here's the number one leading theory

about how to save this, how to save

battery life. Finish running the program.

(Audience laughter) Seriously, race to sleep.

That's the actual technical term, race to sleep.

The faster your software runs, the less

power it consumes. Now people get really

upset about this. 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 really figured out

how to run processors and do work

on processors in a

power efficient way. Do you know what we

have figured out how to do with processors

that has made our battery lives improve

over time? We figured out how to turn them off.

This is literally how your phone, your

laptop, like if you have your computer

on your desk. Every single

microprocessor, general purpose

microprocessors you can get today.

The way it conserves power is by

turning itself off as rapidly and as

frequently as possible for as long a

period time as possible. The more

your processor turns on, the less this

little green goes yellow and then red.

Bad stuff right? So we actually want to

make code faster in order to save battery

life. Universally, this is true.

There are some extreme exceptions to it

There'e some really weird stuff around

out on the fringe. But 99.999999% of the time

You want to run code faster to save

battery. But batteries aren't the only

story when it comes to saving power.

This is one of Google's data centers.

You'll note that this is a very large building

and the only thing it is doing is taking

electricity and turning it into heat.

That is it's job. And it's really good

at it's job. And unfortunately,

electricity costs a lot of money.

And in fact, 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 it's on the

two extremes of computing platforms that

we find convergence. Right? When you drop

to a phone, or you go up to a data center

all of a sudden power dominates. Right?

We'll talk about compute per watt.

This is another picture of the data center

by the way. I just want to clarify what

this is. This is one of my favorite pictures

Those are enormous vents blowing out stem vapor.

I don't know much about 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,

its not too cool, its actually efficiently

cooling the ?. Anyway this is trivia.

So the compute per watt tends to

dominate in the data canter 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 when the chip is turned on.

Makes sense? Alright? Now I say raw speed

isn't everything because when we talk

about performance is really important

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?

Oh, you can be honest, I've heard it!

All right, I had James Gosling sit across

from the table and tell me

I was a complete moron because I didn't

believe Java that 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 areas and scenarios.

For example if you have a specific application

and your specific application is going to

run for a long period of time

and you're concerned about the ?

of the application and you have a

very well tuned virtual machine

for your Java, and you've tuned

the garbage collector to precisely match

the desired kind of garbage collection

interruption frequency for your application

If you get all of that, Java will

very often ? perform to C++. 9:26