ACCU Keynote by Andrei Alexandrescu

47
© 2015- Andrei Alexandrescu. Do not redistribute. 1 / 39 There’s Treasure Everywhere Prepared for ACCU 2016 Andrei Alexandrescu, Ph.D. 2016-04-21

Transcript of ACCU Keynote by Andrei Alexandrescu

Page 1: ACCU Keynote by Andrei Alexandrescu

© 2015- Andrei Alexandrescu. Do not redistribute. 1 / 39

There’s Treasure EverywherePrepared for ACCU 2016

Andrei Alexandrescu, Ph.D.

2016-04-21

Page 2: ACCU Keynote by Andrei Alexandrescu

Working Title

© 2015- Andrei Alexandrescu. Do not redistribute. 2 / 39

How to Write and

Deliver a Keynote

Page 3: ACCU Keynote by Andrei Alexandrescu

What’s (in) a Keynote?

© 2015- Andrei Alexandrescu. Do not redistribute. 3 / 39

• Friend 1: “Just talk about things you like.”

• Friend 2: “Should have no code and no math.”

Page 4: ACCU Keynote by Andrei Alexandrescu

Things I Like

© 2015- Andrei Alexandrescu. Do not redistribute. 4 / 39

Page 5: ACCU Keynote by Andrei Alexandrescu

Things I Like

© 2015- Andrei Alexandrescu. Do not redistribute. 4 / 39

• Confusing aphorisms

Page 6: ACCU Keynote by Andrei Alexandrescu

Confusing Aphorisms

© 2015- Andrei Alexandrescu. Do not redistribute. 5 / 39

When you hear hoofbeats, think

horses, not zebras.

Page 7: ACCU Keynote by Andrei Alexandrescu

Confusing Aphorisms

© 2015- Andrei Alexandrescu. Do not redistribute. 6 / 39

When you hear hoofbeats, think

horses, not zebras.

—Not an African Proverb

Page 8: ACCU Keynote by Andrei Alexandrescu

Things I Like

© 2015- Andrei Alexandrescu. Do not redistribute. 7 / 39

• Confusing aphorisms

Page 9: ACCU Keynote by Andrei Alexandrescu

Things I Like

© 2015- Andrei Alexandrescu. Do not redistribute. 7 / 39

• Confusing aphorisms

• Fast code

Page 10: ACCU Keynote by Andrei Alexandrescu

Things I Like

© 2015- Andrei Alexandrescu. Do not redistribute. 7 / 39

• Confusing aphorisms

• Fast code

• C++ Concepts

Page 11: ACCU Keynote by Andrei Alexandrescu

Toto Washlet

© 2015- Andrei Alexandrescu. Do not redistribute. 8 / 39

Page 12: ACCU Keynote by Andrei Alexandrescu

The Toto Company

© 2015- Andrei Alexandrescu. Do not redistribute. 9 / 39

• Offers 8 washlet models

Page 13: ACCU Keynote by Andrei Alexandrescu

The Toto Company

© 2015- Andrei Alexandrescu. Do not redistribute. 9 / 39

• Offers 8 washlet models

• Of these, 7 have a remote control

Page 14: ACCU Keynote by Andrei Alexandrescu

The Toto Company

© 2015- Andrei Alexandrescu. Do not redistribute. 9 / 39

• Offers 8 washlet models

• Of these, 7 have a remote control

• A remote control

Page 15: ACCU Keynote by Andrei Alexandrescu

Washlets with Remotes

© 2015- Andrei Alexandrescu. Do not redistribute. 10 / 39

• Combine two nice things

• Complex and interesting

• Modern and cool

• Unlikely to be super useful in practice

Page 16: ACCU Keynote by Andrei Alexandrescu

“Why Concepts didn’t make C++17”

© 2015- Andrei Alexandrescu. Do not redistribute. 11 / 39

• Not enough time

Page 17: ACCU Keynote by Andrei Alexandrescu

“Why Concepts didn’t make C++17”

© 2015- Andrei Alexandrescu. Do not redistribute. 11 / 39

• Not enough time

• “The Concepts TS does not specify any

concept definitions”

Page 18: ACCU Keynote by Andrei Alexandrescu

“Why Concepts didn’t make C++17”

© 2015- Andrei Alexandrescu. Do not redistribute. 11 / 39

• Not enough time

• “The Concepts TS does not specify any

concept definitions”

• “Use of concepts sometimes results in worse

error messages”

Page 19: ACCU Keynote by Andrei Alexandrescu

Upcoming

© 2015- Andrei Alexandrescu. Do not redistribute. 12 / 39

“Why Concepts did

make C++20”

Page 20: ACCU Keynote by Andrei Alexandrescu

Sentinels

© 2015- Andrei Alexandrescu. Do not redistribute. 13 / 39

Page 21: ACCU Keynote by Andrei Alexandrescu

Let’s talk about linear find

© 2015- Andrei Alexandrescu. Do not redistribute. 14 / 39

• Nothing out of the ordinary:

Range find(Range, E)(Range r, E e) {

for (; !r.empty; r.popFront) {

if (r.front == e) break;

}

return r;

}

• Implemented many times in many languages

Page 22: ACCU Keynote by Andrei Alexandrescu

To index or not to index

© 2015- Andrei Alexandrescu. Do not redistribute. 15 / 39

• Indexed access and pointer arithmetic

changed relative speed over years

• Today: indexed access has a slight edge

◦ Less aliasing

◦ CPU has sophisticated indexed addressing

Page 23: ACCU Keynote by Andrei Alexandrescu

Linear find using random access

© 2015- Andrei Alexandrescu. Do not redistribute. 16 / 39

Range find(Range, E)(Range r, E e) {

size_t i = 0;

for (; i != r.length; ++i) {

if (r[i] == e) break;

}

return r[i .. $];

}

• Task: make it faster

Page 24: ACCU Keynote by Andrei Alexandrescu

Linear find with sentinel

© 2015- Andrei Alexandrescu. Do not redistribute. 17 / 39

Range find(Range, E)(Range r, E e) {

auto c = r[$ - 1];

r[$ - 1] = e;

size_t i = 0;

{

scope(exit) r[$ - 1] = c;

for (;; ++i)

if (r[i] == e) break;

}

if (i + 1 == r.length && c != e)

++i;

return r[i .. $];

}

Page 25: ACCU Keynote by Andrei Alexandrescu

But. . . but. . .

© 2015- Andrei Alexandrescu. Do not redistribute. 18 / 39

• That doesn’t work for all types!

• r[$ - 1] = c may throw

• Also, find itself doesn’t work for all types

◦ Need to define only when we should

• Need to choose “right” implementation

automatically

◦ With sentinel for certain types

◦ Conservative for the others

Page 26: ACCU Keynote by Andrei Alexandrescu

Linear find with sentinel, take 2

© 2015- Andrei Alexandrescu. Do not redistribute. 19 / 39

Range find(Range, E)(Range r, E e)

if (isInputRange!Range &&

is(typeof(r.front == e) == bool)

) {

...

}

• is(typeof(e) == T) Does expression e

“work” and has type T?

• e must look like an expression syntactically

• Boolean returned, compilation not stopped

◦ SFINAE on steroids

• Still, how to choose with/without sentinel?

Page 27: ACCU Keynote by Andrei Alexandrescu

static if to the rescue

© 2015- Andrei Alexandrescu. Do not redistribute. 20 / 39

Range find(R, E)(R r, E e)

if (isInputRange!R && is(typeof(r.front == e) : bool)) {

static if (isRandomAccessRange!R && hasSlicing!R) {

static if (is(typeof(

() nothrow { r[0] = r[0]; }

))) {

... sentinel implementation ...

} else {

... indexed implementation ...

}

} else {

... conservative implementation ...

}

}

Page 28: ACCU Keynote by Andrei Alexandrescu

Please note

© 2015- Andrei Alexandrescu. Do not redistribute. 21 / 39

• Sentinel technique old as dust

• Yet not applicable directly to generic code

• Must use proper introspection techniques

• is and static if widely applicable

◦ Mold structure depending on capabilities

◦ stdlib: static if every 88 lines as wc

counts

• Does the optimization help?

Page 29: ACCU Keynote by Andrei Alexandrescu

Find with Sentinel

© 2015- Andrei Alexandrescu. Do not redistribute. 22 / 39

5 6 7 8 9 10

0

2

4

6

Input size [millions of elements]

Tim

e[m

s]

Page 30: ACCU Keynote by Andrei Alexandrescu

Relative Speedup

© 2015- Andrei Alexandrescu. Do not redistribute. 23 / 39

5 6 7 8 9 10

20

25

30

35

40

Input size [millions of elements]

Speedup[%

]

Page 31: ACCU Keynote by Andrei Alexandrescu

Sentinels

© 2015- Andrei Alexandrescu. Do not redistribute. 24 / 39

• Widely applicable technique

• Let’s use them for something more complex

• How about Tony Hoare’s partition?

◦ Workhorse of sorting and the selection

problem

Page 32: ACCU Keynote by Andrei Alexandrescu

Baseline (1/2)

© 2015- Andrei Alexandrescu. Do not redistribute. 25 / 39

size_t pivotPartition(Range)(Range r, size_t pivot) {

r.swapAt(pivot, 0);

size_t lo = 1, hi = r.length - 1;

loop: for (;; lo++, hi--) {

for (;; ++lo) {

if (lo > hi) break loop;

if (r[lo] >= r[0]) break;

}

// found the left bound: r[lo] >= r[0]

Page 33: ACCU Keynote by Andrei Alexandrescu

Baseline (2/2)

© 2015- Andrei Alexandrescu. Do not redistribute. 26 / 39

// found the left bound: r[lo] >= r[0]

for (;; --hi) {

if (lo >= hi) break loop;

if (r[0] >= r[hi]) break;

}

// found the right bound: r[hi] <= r[0]

// swap them & make progress

r.swapAt(lo, hi);

}

--lo;

r.swapAt(lo, 0);

return lo;

}

Page 34: ACCU Keynote by Andrei Alexandrescu

© 2015- Andrei Alexandrescu. Do not redistribute. 27 / 39

Make It Faster

Page 35: ACCU Keynote by Andrei Alexandrescu

Accelerating pivotPartition

© 2015- Andrei Alexandrescu. Do not redistribute. 28 / 39

• Currently: find from left, find from right,

swap, make progress

• Done when indexes meet

• Many index checks interspersed with actual

work

• Can’t plant a sentinel in the “middle”—final

pivot position unknown

Page 36: ACCU Keynote by Andrei Alexandrescu

Key Idea

© 2015- Andrei Alexandrescu. Do not redistribute. 29 / 39

• Plant sentinels at both ends

• Create a “vacancy” in the range

• Break swapAt into two assignments

• An assignment fills a vacancy and leaves

another one

Half swap!

• Work becomes matter of moving the vacancy

around

• At the end fill back the vacancy

Page 37: ACCU Keynote by Andrei Alexandrescu

Implementation (1/3): Setup

© 2015- Andrei Alexandrescu. Do not redistribute. 30 / 39

size_t pivotPartition(Range)(Range r, size_t pivot) {

if (r.length <= 1) return 0;

// Put pivot at the front

r.swapAt(pivot, 0);

auto p = r[0];

// Plant the pivot in the end as well as a sentinel

auto save = r[$ - 1];

r[$ - 1] = p; // r[$ - 1] is now vacant

Page 38: ACCU Keynote by Andrei Alexandrescu

Implementation (2/3): Core

© 2015- Andrei Alexandrescu. Do not redistribute. 31 / 39

size_t lo = 0, hi = r.length - 1;

for (;;) {

do ++lo; while (r[lo] < p);

r[hi] = r[lo];

do --hi; while (p < r[hi]);

if (lo >= hi) break;

r[lo] = r[hi];

}

Page 39: ACCU Keynote by Andrei Alexandrescu

Implementation (3/3): Fixup

© 2015- Andrei Alexandrescu. Do not redistribute. 32 / 39

assert(lo - hi <= 2);

assert(p >= r[hi]);

if (lo == hi + 2) {

assert(r[hi + 1] >= p);

r[lo] = r[hi + 1];

--lo;

}

r[lo] = save;

if (p < save) --lo;

assert(p >= r[lo]);

r.swapAt(0, lo);

return lo;

}

Page 40: ACCU Keynote by Andrei Alexandrescu

Partition

© 2015- Andrei Alexandrescu. Do not redistribute. 33 / 39

5 6 7 8 9 10

0

10

20

30

Input size [millions of elements]

Tim

e[m

s]

Page 41: ACCU Keynote by Andrei Alexandrescu

Partition Speedup

© 2015- Andrei Alexandrescu. Do not redistribute. 34 / 39

5 6 7 8 9 1017

18

19

20

21

22

Input size [millions of elements]

Speedup[%

]

Page 42: ACCU Keynote by Andrei Alexandrescu

Credit

© 2015- Andrei Alexandrescu. Do not redistribute. 35 / 39

• Thought I invented this!

• Nope: “Engineering of a Quicksort

Partitioning Algorithm”, Abhyankar & Ingle,

Journal of Global Research in Computer

Science, Feb 2011

◦ “Vacancy” idea, cannot choose any pivot

Page 43: ACCU Keynote by Andrei Alexandrescu

More Sentinels

© 2015- Andrei Alexandrescu. Do not redistribute. 36 / 39

• These sentinel-based optimizations are not

cherry picked!

• Dot product

• Set intersection

• Merge sorted lists

• Lexing and parsing

Page 44: ACCU Keynote by Andrei Alexandrescu

There’s Treasure Everywhere

© 2015- Andrei Alexandrescu. Do not redistribute. 37 / 39

• You just have to find it

Page 45: ACCU Keynote by Andrei Alexandrescu

There’s Treasure Everywhere

© 2015- Andrei Alexandrescu. Do not redistribute. 37 / 39

• You just have to find it

• (by using introspection)

Page 46: ACCU Keynote by Andrei Alexandrescu

Fastware

© 2015- Andrei Alexandrescu. Do not redistribute. 38 / 39

• A cornucopia of optimization techniques

• Benchmarking Techniques

• Strength Reduction

• Cache Friendliness

• Indirect Write Elision

• Memoization and Obliviation

• Hoisting and Lowering

• . . . and many more!

Page 47: ACCU Keynote by Andrei Alexandrescu

© 2015- Andrei Alexandrescu. Do not redistribute. 39 / 39

Destroy!