Name: 2.仕事を最適化するためのベントレーのルール (2. Bentley Rules for Optimizing Work)
Uploaded: 2021-01-14T10:26:47.000Z
Duration: 1 h 20 min 10 s
Description: VoiceTubeの動画で発音を聞きながら英語表現を覚えよう！学べる英語：

基礎受動態

The following content is provided under a Creative

Your support will help MIT OpenCourseWare

continue to offer high quality, educational resources for free.

To make a donation or to view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

JULIAN SHUN: So welcome to the second lecture of 6.172,

performance engineering of software systems.

Today, we're going to be talking about Bentley rules

All right, so work, does anyone know what work means?

there's actually a formal definition of work.

The work of a program on a particular input

is defined to be the sum total of all the operations executed

of how much stuff the program needs to do.

to reduce the amount of stuff that the program needs

to do in order to improve the running time of your program,

So algorithm design can produce dramatic reductions

For example, if you want to sort an array of elements,

Or you can use an n squared time sort, like insertion sort.

So today, I'm not going to be talking about algorithm design.

You'll see more of this in other courses here at MIT.

And we'll also talk a little bit about algorithm design

We will be talking about many other cool tricks for reducing

But I do want to point out, that reducing

the work of our program doesn't automatically translate

And this is because of the complex nature

So there's a lot of things going on that aren't captured

There's instruction level parallelism, caching,

vectorization, speculation and branch prediction, and so on.

And we'll learn about some of these things

does serve as a good heuristic for reducing

the overall running time of a program, at least

So today, we'll be learning about many ways

them Bentley optimization rules, in honor of John Lewis Bentley.

So John Lewis Bentley wrote a nice little book back

in 1982 called Writing Efficient Programs.

And inside this book there are various techniques

for reducing the work of a computer program.

So if you haven't seen this book before, it's very good.

Many of the original rules in Bentley's book

had to deal with the vagaries of computer architecture

of Bentley rules just dealing with the work of a program.

We'll be talking about architecture-specific

But today, we won't be talking about this.

One cool fact is that John Lewis Bentley is actually

So John Bentley was one of Charles Leiseron's

Charles Leiserson was Guy Blelloch's academic advisor.

And Guy Blelloch, who's a professor at Carnegie Mellon,

was my advisor when I was a graduate student at CMU.

And I had the honor of meeting John Bentley a couple of years

And he told me that he was my academic great grandfather.

Yeah, and Charles is my academic grandfather.

And all of Charles's students are my academic aunts

OK, so here's a list of all the work optimizations

So they're grouped into four categories, data structures,

So there's a list of 22 rules on this slide today.

In fact, we'll actually be able to look at all of them today.

So today's lecture is going to be structured

And I'm going to be spending one to three slides on each one

字幕リスト動画再生

2.仕事を最適化するためのベントレーのルール (2. Bentley Rules for Optimizing Work)

constant

expression

structure

character