2. Bentley Rules for Optimizing Work - VoiceTube: Learn English through videos!

Subtitles section Play video

The following content is provided under a Creative
Commons license.
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
at ocw.mit.edu.
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
for optimizing work.
All right, so work, does anyone know what work means?
You're all at MIT, so you should know.
So in terms of computer programming,
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
by the program.
So it's basically a gross measure
of how much stuff the program needs to do.
And the idea of optimizing work is
to reduce the amount of stuff that the program needs
to do in order to improve the running time of your program,
improve its performance.
So algorithm design can produce dramatic reductions
in the work of a program.
For example, if you want to sort an array of elements,
you can use a nlogn time QuickSort.
Or you can use an n squared time sort, like insertion sort.
So you've probably seen this before
in your algorithm courses.
And for large enough values of n,
a nlogn time sort is going to be much
faster than a n squared 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
later on in this semester.
We will be talking about many other cool tricks for reducing
the work of a program.
But I do want to point out, that reducing
the work of our program doesn't automatically translate
to a reduction in running time.
And this is because of the complex nature
of computer hardware.
So there's a lot of things going on that aren't captured
by this definition of work.
There's instruction level parallelism, caching,
vectorization, speculation and branch prediction, and so on.
And we'll learn about some of these things
throughout this semester.
But reducing the work of our program
does serve as a good heuristic for reducing
the overall running time of a program, at least
to a first order.
So today, we'll be learning about many ways
to reduce the work of your program.
So rules we'll be looking at, we call
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.
So I highly encourage you to read it.
Many of the original rules in Bentley's book
had to deal with the vagaries of computer architecture
three and a half decades ago.
So today, we've created a new set
of Bentley rules just dealing with the work of a program.
We'll be talking about architecture-specific
optimizations later on in the semester.
But today, we won't be talking about this.
One cool fact is that John Lewis Bentley is actually
my academic great grandfather.
So John Bentley was one of Charles Leiseron's
academic advisors.
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.
So it's a nice little fact.
And I had the honor of meeting John Bentley a couple of years
ago at a conference.
And he told me that he was my academic great grandfather.
[LAUGHING]
Yeah, and Charles is my academic grandfather.
And all of Charles's students are my academic aunts
and uncles--
[LAUGHING]
--including your T.A. Helen.
OK, so here's a list of all the work optimizations
that we'll be looking at today.
So they're grouped into four categories, data structures,
loops, and functions.
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
as a series of many lectures.
And I'm going to be spending one to three slides on each one
of these optimizations.
All right, so let's start with optimizations
for data structures.
So first optimization is packing and encoding
your data structure.
And the idea of packing is to store more than one data value
in a machine word.
And the related idea of encoding is
to convert data values into a representation that
requires fewer bits.
So does anyone know why this could possibly reduce
the running time of a program?
Yes?
AUDIENCE: Need less memory fetches.
JULIAN SHUN: Right, so good answer.
The answer was, it might need less memory fetches.
And it turns out that that's correct,
because computer program spends a lot of time moving
stuff around in memory.
And if you reduce the number of things
that you have to move around in memory,
then that's a good heuristic for reducing the running
time of your program.
So let's look at an example.
Let's say we wanted to encode dates.
So let's say we wanted to code this string, September 11,
2018.
You can store this using 18 bytes.
So you can use one byte per character here.
And this would require more than two double words,
because each double word is eight bytes or 64 bits.
And you have 18 bytes.
You need more than two double words.
And you have to move around these words
every time you want to manipulate the date.
But turns out that you can actually
do better than using 18 bytes.
So let's assume that we only want to store years
between 4096 BCE and 4096 CE.
So there are about 365.25 times 8,192 dates
in this range, which is three million approximately.
And you can use log base two of three million bits
to represent all the dates within this range.
So the notation lg here means log base of two.
That's going to be the notation I'll be using in this class.
And L-O-G will mean log base 10.
So we take the ceiling of log base two or three million,
and that gives us 22 bits.
So a good way to remember how to compute the log
base two of something, you can remember that the log base
two of one million is 20, log base two of 1,000 is 10.
And then you can factor this out and then add in log base
two of three, rounded up, which is two.
So that gives you 22 bits.
And that easily fits within one 32-bit words.
Now, you only need one word instead of three words,
as you did in the original representation.
But with this modified representation,
now determining the month of a particular date
will take more work, because now you're not explicitly
storing the month in your representation.
Whereas, with the string representation,
you are explicitly storing it at the beginning of the string.
So this does take more work, but it requires less space.
So any questions so far?
OK, so it turns out that there's another way
to store this, which also makes it easy
for you to fetch the month, the year, or the day
for a particular date.
So here, we're going to use the bit fields facilities in C.
So we're going to create a struct called date underscore t
with three fields, the year, the month, and the date.
And the integer after the semicolon
specifies how many bits I want to assign
to this particular field in the struct.
So this says, I need 13 bits for the year,
four bits for the month, and five bits for the day.
So the 13 bits for the year is, because I
have 8,192 possible years.
So I need 13 bits to store that.
For the month, I have 12 possible months.
So I need log base two of 12 rounded up, which is four.
And then finally, for the day, I need
log base two of 31 rounded up, which is five.
So in total, this still takes 22 bits.
But now the individual fields can now
be accessed much more quickly, than if we had just
encoded the three million dates using sequential integers,
because now you can just extract a month just by saying whatever
you named your struct.
You can just say that struct dot month.
And that give you the month.
Yes?
AUDIENCE: Does C actually store it like that,
because I know C++ it makes it finalize.
So then you end up taking more space.
JULIAN SHUN: Yeah, so this will actually
pad the struct a little bit at the end, yeah.
So you actually do require a little bit more than 22 bits.
That's a good question.
But this representation is much more easy to access,
than if you just had encoded the integers
as sequential integers.
Another point is that sometimes unpacking and decoding
are the optimization, because sometimes it
takes a lot of work to encode the values and to extract them.
So sometimes you want to actually unpack the values
so that they take more space, but they're faster to access.
So it depends on your particular application.
You might want to do one thing or the other.
And the way to figure this out is just to experiment with it.
OK, so any other questions?
All right, so the second optimization
is data structure augmentation.
And the idea here is to add information to a data structure
to make common operations do less work,
so that they're faster.
And let's look at an example.
Let's say we had two singly linked list
and we wanted to append them together.
And let's say we only stored the head pointer to the list,
and then each element in the list
has a pointer to the next element in the list.
Now, if you want to spend one list to another list,
well, that's going to require you walking down the first list
to find the last element, so that you
can change the pointer of the last element
to point to the beginning of the next list.
And this might be very slow if the first list is very long.
So does anyone see a way to augment this data structure so
that appending two lists can be done much more efficiently?
Yes?
AUDIENCE: Store a pointer to the last value.
JULIAN SHUN: Yeah, so the answer is
to store a pointer to the last value.
And we call that the tail pointer.
So now we have two pointers, both the head and the tail.
The head points to the beginning of the list.
The tail points to the end of the list.
And now you can just append two lists in constant time,
because you can access the last element in the list
by following the tail pointer.
And then now you just change the successor pointer
of the last element to point to the head of the second list.
And then now you also have to update the tail
to point to the end of the second list.
OK, so that's the idea of data structure augmentation.
We added a little bit of extra information
to the data structure, such that now appending
two lists is much more efficient than in the original method,
where we only had a head pointer.
Questions?
OK, so the next optimization is precomputation.
The idea of precomputation is to perform some calculations
in advance so as to avoid doing these computations
at mission-critical times, to avoid doing them at runtime.
So let's say we had a program that needed
to use binomial coefficients.
And here's a definition of a binomial coefficient.
So it's basically the choose function.
So you want to count the number of ways
that you can choose k things from a set of n things.
And the formula for computing this
is, n factorial divided by the product of k factorial and n
minus k factorial.
Computing this choose function can actually
be quite expensive, because you have
to do a lot of multiplications to compute the factorial,
even if the final result is not that big,
because you have to compute one term in the numerator and then
two factorial terms in the denominator.
And then you also might run into integer overflow issues,
because n factorial grows very fast.
It grows super exponentially.
It grows like n to the n, which is even faster than two
to the n, which is exponential.
So doing this computation, you have
to be very careful with integer overflow issues.
So one idea to speed up a program that
uses these binomials coefficients
is to precompute a table of coefficients
when you initialize the program, and then
just perform table lookup on this precomputed table
at runtime when you need the binomial coefficient.
So does anyone know what the table that
stores binomial coefficients is called?
Yes?
AUDIENCE: [INAUDIBLE]
JULIAN SHUN: Yea, Pascal's triangles, good.
So here is what Pascal's triangle looks like.
So on the vertical axis, we have different values of n.
And then on the horizontal axis, we have different values of k.
And then to get and choose k, you
just go to the nth row in the case column
and look up that entry.
Pascal's triangle has a nice property,
that for every element, it can be computed
as a sum of the element directly above it and above it
and to the left of it.
So here, 56 is the sum of 35 and 21.
And this gives us a nice formula to compute
the binomial coefficients.
So we first check if n is less than k in this choose function.
If n is less than k, then we just
return zero, because we're trying
to choose more things than there are in a set.
If n is equal to zero, then we just
return one, because here k must also be equal to zero,
since we had the condition n less than k above.
And there's one way to choose zero things
from a set of zero things.
And then if k is equal to zero, we also
return one, because there's only one way
to choose zero things from a set of any number of things.
You just don't pick anything.
And then finally, we recursively call this choose function.
So we call choose of n minus one k minus one.
This is essentially the entry above and diagonal to this.
And then we add in choose of n minus one k, which
is the entry directly above it.
So this is a recursive function for generating this Pascal's
triangle.
But notice that we're actually still not doing precomputation,
because every time we call this choose function,
we're making two recursive calls.
And this can still be pretty expensive.
So how can we actually precompute this table?
So here's some C code for precomputing Pascal's triangle.
And let's say we only wanted coefficients up
to choose sides of 100.
So we initialize matrix of 100 by 100.
And then we call this an init choose function.
So first it goes from n equal zero, all the way up
to choose size minus one.
And then it says, choose n of zero to be one.
It also sets choose of n, n to be one.
So the first line is, because there's
only one way to choose zero things
from any number of things.
And the second line is, because there's only one way
to choose n things from n things, which
is just to pick all of them.
And then now we have a second loop,
which goes from n equals one, all the way up to choose
size minus one.
Then first we set choose of zero n
to be zero, because here n is--
or k is greater than n.
So there's no way to pick more elements
from a set of things that is less than the number of things
you want to pick.
And then now you loop from k equals one, all the way up to n
minus one.
And then your apply this recursive formula.
So choose of n, k is equal to choose of n minus
one, k minus one plus choose of n minus one k.
And then you also set choose of k, n to be zero.
So this is basically all of the entries above the diagonal
here, where k is greater than n.
And then now inside the program whenever
we need a binomial coefficient that's less than 100,
we can just do table lookup into this table.
And we just index and then just choose array.
So does this make sense?
Any questions?
It's pretty easy so far, right?
So one thing to note is, that we're still
computing this table at runtime, because we
have to initialize this table at runtime.
And if we want to run our program many times,
then we have to initialize this table many times.
So is there a way to only initialize this table once,
even though we might want to run the program many times?
Yes?
AUDIENCE: Put in the source code.
JULIAN SHUN: Yeah, so good, so put it in the source code.
And so we're going to do compile-time initialization.
And if you put the table in the source code,
then the compiler will compile this code
and generate the table for you that compile time.
So now whenever you run it, you don't
have to spend time initializing the table.
So idea of compile-time initialization
is to store the values of constants
during compilation and, therefore,
saving work at runtime.
So let's say we wanted choose values up to 10.
This is the table, the 10 by 10 table storing
all of the binomial coefficients up to 10.
So if you put this in your source code,
now when you run the program, you
can just index into this table to get the appropriate constant
here.
But this table was just a 10 by 10 table.
What if you wanted a table of 1,000 by 1,000?
Does anyone actually want to type this in, a table of 1,000
by 1,000?
So probably not.
So is there any way to get around this?
Yes?
AUDIENCE: You could make a program that uses it.
And the function will be defined [INAUDIBLE] prints
out the zero [INAUDIBLE].
JULIAN SHUN: Yeah, so the answer is
to write a program that writes your program for you.
And that's called metaprogramming.
So here's a snippet of code that will
generate this table for you.
So it's going to call this init choose function
that we defined before.
And then now it's just going to print out C code.
So it's going to print out the declaration of this array
choose, followed by a left bracket.
And then for each row of the table,
we're going to print another left bracket
and then print the value of each entry in that row, followed
by a right bracket.
And we do that for every row.
So this will give you the C code.
And then now you can just copy and paste this and place it
into your source code.
This is a pretty cool technique to get your computer
to do work for you.
And you're welcome to use this technique in your homeworks
and projects if you'd need to generate large tables
of constant values.
So this is a very good technique to know.
So any questions?
Yes?
AUDIENCE: Is there a way to write the output other programs
to a file, as oppose to having to copy and paste
into the source code?
JULIAN SHUN: Yeah, so you can pipe the output of this program
to a file.
Yes?
AUDIENCE: So are there compiler tools that can--
so we have three processor tools.
Is there [INAUDIBLE] processor can do that?
We compile the code, run it, and then [INAUDIBLE]..
JULIAN SHUN: Yeah, so I think you
can write macros to actually generate this table.
And then the compiler will run those macros
to generate this table for you.
Yeah, so you don't actually need to copy and paste it yourself.
Yeah?
CHARLES: And you know, you don't have
to write it in C. If it's quicker to write with Python,
you'd be writing in Python, just put it in the make file
for the system you're building.
So if it's in the make file, says,
well, we're making this thing, first
generate the file in the table and now you
include that in whatever you're compiling
or/and it's just one more step in the process.
And for sure, it's generally easier
to write these tables with the scripting language like Python
than writing them in C. On the other hand,
if you need experience writing in C, practice writing in C.
JULIAN SHUN: Right, so as Charles says,
you can write your metaprogram using any language.
You don't have to write it in C. You can write it in Python
if you're more familiar with that.
And it's often easier to write it using a scripting
language like Python.
OK, so let's look at the next optimization.
So we're already gone through a couple
of mini lectures already.
So congratulations to all of you who are still here.
So the next optimization is caching.
The idea of caching is to store results
that have been accessed recently,
so that you don't need to compute them again
in the program.
So let's look at an example.
Let's say we wanted to compute the hypotenuse
of a right triangle with side lengths A and B.
So the formula for computing this is, you
take the square root of A times A plus B times B. OK, so
turns out that the square root operator is actually
a relatively expensive, more expensive than additions
and multiplications on modern machines.
So you don't want to have to call the square root
function if you don't have to.
And one way to avoid doing that is to create a cache.
So here I have a cache just storing the previous hypotenuse
that I calculated.
And I also store the values of A and B
that were passed to the function.
And then now when I call the hypotenuse function,
I can first check if A is equal to the cached value of A
and if B is equal to the cached value of B.
And if both of those are true, then
I already computed the hypotenuse before.
And then I can just return cached of h.
But if it's not in my cache, now I need to actually compute it.
So I need to call the square root function.
And then I store the result into cached h.
And I also store A and B into cached A
and cached B respectively.
And then finally, I returned cached h.
So this example isn't actually very realistic,
because my cache is only a size one.
And it's very unlikely, in a program,
you're going to repeatedly call some function
with the same input arguments.
But you can actually make a larger cache.
You can make a cache of size 1,000,
storing the 1,000 most recently computer hypotenuse values.
And then now when you call the hypotenuse function,
you can just check if it's in your cache.
Checking the larger cache is going
to be more expensive, because there are more values
to look at.
But they can still save you time overall.
And hardware also does caching for you,
as we'll talk about later on in the semester.
But the point of this optimization
is that you can also do caching yourself.
You can do it in software.
You don't have to let hardware do it for you.
And turns out for this particular program here,
actually, it is about 30% faster if you do hit the cache
about 2/3 of the time.
So it does actually save you time
if you do repeatedly compute the same values over and over
again.
So that's caching.
Any questions?
OK, so the next optimization we'll look at is sparsity.
The idea of exploiting sparsity, in an input,
is to avoid storage and computing
on zero elements of that input.
And the fastest way to compute on zero
is to just not compute on them at all,
because we know that any value plus zero
is just that original value.
And any value times zero is just zero.
So why waste a computation doing that when
you already know the result?
So let's look at an example.
This is matrix-vector multiplication.
So we want to multiply a n by n matrix by a n by one vector.
We can do dense matrix-vector multiplication
by just doing a dot product of each row in the matrix
with the column vector.
And then that will give us the output vector.
But if you do dense matrix-vector multiplication,
that's going to perform n squared or 36,
in this example, scalar multiplies.
But it turns out, only 14 of these entries in this matrix
are zero or are non-zero.
So you just wasted work doing the multiplication on the zero
elements, because you know that zero times any other element
is just zero.
So a better way to do this, is instead of
doing the multiplication for every element,
you first check if one of the arguments is zero.
And if it is zero, then you don't
have to actually do the multiplication.
But this is still kind of slow, because you still
have to do a check for every entry in your matrix,
even though many of the entries are zero.
So it's actually a pretty cool data structure
that won't actually store these zero entries.
And this will speed up your matrix-vector multiplication
if your matrix is sparse enough.
So let me describe how this data structure works.
It's called compressed sparse row or CSR.
There is an analogous representation
called compressed sparse column or CSC.
But today, I'm just going to talk about CSR.
So we have three arrays.
First, we have the rows array.
The length of the rows array is just equal to the number
of rows in a matrix plus one.
And then each entry in the rows array
just stores an offset into the columns array
or the cols array.
And inside the cols array, I'm storing
the indices of the non-zero entries in each of the rows.
So if we take row one, for example,
we have rows of one is equal to two.
That means I start looking at the second entry
in the cols array.
And then now I have the indices of the non-zero columns
in the first row.
So it's just one, two, four, and five.
These are the indices for the non-zero entries.
And then I have another array called vals.
The length of this array is the same as the cols array.
And then this array just stores the actual value
in these indices here.
So the vals array for row one is going
to store four, one, five, and nine, because these
are the non-zero entries in the first row.
Right, so the rows array just serves as an index
into this cols array.
So you can basically get the starting index
in this cols array for any row just
by looking at the entry stored at the corresponding location
in the rows array.
So for example, row two starts at location six.
So it starts here.
And you have indices three and five,
which are the non-zero indices.
So does anyone know how to compute
the length, the number of non-zeros in a row
by looking at the rows array?
Yes, yes?
AUDIENCE: You go to the rows array
and just drag the [INAUDIBLE]
JULIAN SHUN: Right.
AUDIENCE: [INAUDIBLE] the number of elements that are
[INAUDIBLE].
JULIAN SHUN: Yeah, so to get the length of a row,
you just take the difference between that row's offset
and the next row's offset.
So we can see that the length of the first row is four,
because it's offset is two.
And the offset for row two is six.
So you just take the difference between those two entries.
We have an additional entry here.
So we have the sixth row here, because we
want to be able to compute the length of the last row
without overflowing in our array.
So we just created an additional entry in the rows array
for that.
So turns out that this representation will save you
space if your matrix is sparse.
So the storage required by the CSR format
is order n plus nnz, where nnz is the number of non-zeros
in your matrix.
And the reason why you have n plus nnz,
well, you have two arrays here, cols and vals,
whose length is equal to the number of non-zeros
in the matrix.
And then you also have this rows array,
whose length is n plus one.
So that's why we have n plus nnz.
And if the number of non-zeros is much less than n squared,
then this is going to be significantly more compact
than the dense matrix representation.
However, this isn't always going to be the most
compact representation.
Does anyone see why?
Why might the dense representation
sometimes take less space?
Yeah?
Sorry.
AUDIENCE: Less space or more space?
JULIAN SHUN: Why might the dense representation sometimes take
less space?
AUDIENCE: I mean, if you have not many zeros,
then you can figure it out n squared plus something else
with the sparse created.
JULIAN SHUN: Right.
So if you have a relatively dense matrix,
then it might take more space than storing it.
It might take more space in the CSR representation,
because you have these two arrays.
So if you take the extreme case where all of the entries
are non-zeros, then both of these arrays
are going to be of length and squares.
So you already have 2n squared there.
And then you also need this rows array, which
is of length and plus one.
OK, so now I gave you this more compact representation
for storing the matrix.
So how do we actually do stuff with this representation?
So turns out that you can still do
matrix-vector multiplication using
this compressed sparse row format.
And here's the code for doing it.
So we have this struct here, which
is the CSR representation.
We have the rows array, the cols array, and then the vals array.
And then we also have the number of rows, n, and the number
of non-zeros, nnz.
And then now what we do, we call this SPMV or sparse
matrix-vector multiply.
We pass in our CSR representation,
which is A, and then the input array, which is x.
And then we store the result in an output array y.
So first, we loop through all the rows.
And then we set y of i to be zero.
This is just initialization.
And then for each of my rows, I'm
going to look at the column indices
for the non-zero elements.
And I can do that by starting at k equals to rows of i
and going up to rows of i plus one.
And then for each one of these entries,
I just look up the index, the column index
for the non-zero element.
And I can do that with cols of k, so let that be j.
And then now I know which elements to multiply.
I multiply vals of k by x of j.
And then now I just add that to y of i.
And then after I finish with all of these multiplications
and additions, this will give me the same result
as if I did the dense matrix-vector multiplication.
So this is actually a pretty cool program.
So I encourage you to look at this program offline,
to convince yourself that it's actually
computing the same thing as the dense matrix-vector
multiplication version.
So I'm not going to approve this during lecture today.
But you can feel free to ask me or any of your TAs
after class, if you have questions about this.
And the number of scalar multiplication
that you have to do using this code
is just going to be nnz, because you're just operating
on the non-zero elements.
You don't have to touch all of the zero elements.
And in contrast, the dense matrix-vector multiply
algorithm would take n squared multiplication.
So this can be significantly faster for a sparse matrices.
So turns out that you can also use a similar structure
to store a sparse static graph.
So I assume many of you have seen graphs
in your previous courses.
See, here's what the sparse graph representation
looks like.
So again, we have these arrays.
We have these two arrays.
We have offsets and edges.
The offsets array is analogous to the rows array.
And the edges array is analogous to the columns array
for the CSR representation.
And then in this offsets array, we store for each vertex
where its neighbor's start in this edges array.
And then in the edges array, we just
write the indices of its neighbor's there.
So let's take vertex one, for example.
The offset of vertex one is two.
So we know that its outgoing neighbor
start at position two in this edges array.
And then we see that vertex one has outgoing edges to vertices
two, three, and four.
And we see in the edges array two, three, four listed there.
And you can also get the degree of each vertex, which
is analogous to the length of each row,
by taking the difference between consecutive offsets.
So here we see that the degree of vertex one
is three, because its offset is two.
And the offset of vertex two is five.
And it turns out that using this representation,
you can run many classic graph algorithms
such as breadth-first search and PageRank
quite efficiently, especially when the graph is sparse.
So this would be much more efficient
than using a dense matrix to represent the graph
and running these algorithms.
You can also store weights on the edges.
And one way to do that is to just create an additional array
called weights, whose length is equal to the number of edges
in the graph.
And then you just store the weights in that array.
And this is analogous to the values array in the CSR
representation.
But there's actually a more efficient way to store this,
if you always need to access the weight whenever
you access an edge.
And the way to do this is to interleave the weights
with the edges, so to store the weight for a particular edge
right next to that edge, and create an array of twice
number of edges in the graph.
And the reason why this is more efficient
is, because it gives you improved cache locality.
And we'll talk much more about cache locality
later on in this course.
But the high-level idea is, that whenever you access an edge,
the weight for that edge will also
likely to be on the same cache line.
So you don't need to go to main memory
to access the weight of that edge again.
And later on in the semester we'll
actually have a whole lecture on doing optimizations
for graph algorithms.
And today, I'm just going to talk about one representation
of graphs.
But we'll talk much more about this later on.
Any questions?
OK, so that's it for the data structure optimizations.
We still have three more categories
of optimizations to go over.
So it's a pretty fun lecture.
We get to learn about many cool tricks for reducing
the work of your program.
So in the next class of optimizations
we'll look at is logic, so first thing is constant folding
and propagation.
The idea of constant folding and propagation
is to evaluate constant expressions
and substitute the result into further expressions, all
at compilation times.
You don't have to do it at runtime.
So again, let's look at an example.
So here we have this function called orrery.
Does anyone know what orrery means?
You can look it up on Google.
[LAUGHING]
OK, so an orrery is a model of a solar system.
So here we're constructing a digital orrery.
And in an orrery we have these whole bunch
of different constants.
We have the radius, the diameter, the circumference,
cross area, surface area, and also the volume.
But if you look at this code, you
can notice that actually all of these constants
can be defined in compile time once we fix the radius.
So here we set the radius to be this constant here,
six million, 371,000.
I don't know where that constant comes from, by the way.
But Charles made these slides, so he probably does.
CHARLES: [INAUDIBLE]
JULIAN SHUN: Sorry?
CHARLES: Radius of the Earth.
JULIAN SHUN: OK, radius of the Earth.
Now, the diameter is just twice this radius.
The circumference is just pi times the diameter.
Cross area is pi times the radius squared.
Surface area is circumference times the diameter.
And finally, volume is four times pi times the radius cube
divided by three.
So you can actually evaluate all of these two constants
at compile time.
So with a sufficiently high level of optimization,
the compiler will actually evaluate all of these things
at compile time.
And that's the idea of constant folding and propagation.
It's a good idea to know about this, even though the compiler
is pretty good at doing this, because sometimes
the compiler won't do it.
And in those cases, you can do it yourself.
And you can also figure out whether the compiler
is actually doing it when you look at the assembly code.
OK, so the next optimization is common subexpression
elimination.
And the idea here is to avoid computing the same expression
multiple times by evaluating the expression once and storing
the result for later use.
So let's look at this simple four-line program.
We have a equal to b plus c.
The we set b equal to a minus d.
Then we set c equal to b plus c.
And finally, we set d equal to a minus d.
So notice her that the second and the fourth lines
are computing the same expression.
They're both computing a minus d.
And they evaluate to the same thing.
So the idea of common subexpression elimination
would be to just substitute the result of the first evaluation
into the place where you need it in future line.
So here, we still evaluate the first line for a minus d.
But now in the second time we need a minus d.
We just set the value to b.
So now d is equal to b instead of a minus d.
So in this example, the first and the third line,
the right hand side of those lines actually look the same.
They're both b plus c.
Does anyone see why you can't do common subexpression
elimination here?
AUDIENCE: b minus changes the second line.
JULIAN SHUN: Yeah, so you can't do common subexpression
for the first and the third lines, because the value of b
changes in between.
So the value of b changes on the second line.
So on the third line when you do b plus c,
it's not actually computing the same thing
as the first evaluation of b plus c.
So again, the compiler is usually
smart enough to figure this optimization out.
So it will do this optimization for you in your code.
But again, it doesn't always do it for you.
So it's a good idea to know about this optimization
so that you can do this optimization by hand when
the compiler doesn't do it for you.
Questions so far?
OK, so next, let's look at algebraic identities.
The idea of exploiting algebraic identities
is to replace more expensive algebraic expressions
with equivalent expressions that are cheaper to evaluate.
So let's look at an example.
Let's say we have a whole bunch of balls.
And we want to detect whether two balls collide
with each other.
Say, ball has a x-coordinate, a y-coordinate, a z-coordinate,
as well as a radius.
And the collision test works as follows.
We set d equal to the square root
of the sum of the squares of the differences between each
of the three coordinates of the two balls.
So here, we're taking the square of b1's x-coordinate
minus b2's x-coordinate, and then
adding the square of b1's y-coordinate
minus b2's y-coordinate, and finally,
adding the square of b1 z-coordinate
minus b2's z-coordinate.
And then we take the square root of all of that.
And then if the result is less than
or equal to the sum of the two radii of the ball,
then that means there is a collision,
and otherwise, that means there's not a collision.
But it turns out that the square root operator,
as I mentioned before, is relatively expensive compared
to doing multiplications and additions and subtractions
on modern machines.
So how can we do this without using the square root operator?
Yes.
AUDIENCE: You add the two radii, and the distance is more than
the distance between the centers,
then you know that they must be overlying.
JULIAN SHUN: Right, so that's actually a good fast path
check.
I don't think it necessarily always gives you
the right answer.
Is there another?
Yes?
AUDIENCE: You can square the ignition of the radii
and compare that instead of taking
the square root of [INAUDIBLE].
JULIAN SHUN: Right, right, so the answer
is, that you can actually take the square of both sides.
So now you don't have to take the square root anymore.
So we're going to use the identity that
says, that if the square root of u
is less than or equal to v exactly when u is less than
or equal to v squared.
So we're just going to take the square of both sides.
And here's the modified code.
So now I don't have this square root anymore on the right hand
side when I compute d squared.
But instead, I square the sum of the two radii.
So this will give you the same answer.
However, you do have to be careful with floating point
operations, because they don't work exactly
in the same way as real numbers.
So some numbers might run into overflow issues or rounding
issues.
So you do have to be careful if you're
using algebraic identities and floating point computations.
But the high-level idea is that you
can use equivalent algebraic expressions to reduce
the work of your program.
And we'll come back to this example
late on in this lecture when we talk
about some other optimizations, such as the fast path
optimization, as one of the students pointed out.
Yes?
AUDIENCE: Why do you square the sum
of these squares [INAUDIBLE]?
JULIAN SHUN: Which?
Are you talking about--
AUDIENCE: Yeah.
JULIAN SHUN: --this line?
So before we were comparing d.
AUDIENCE: [INAUDIBLE].
JULIAN SHUN: Yeah, yeah, OK, is that clear?
OK.
OK, so the next optimization is short-circuiting.
The idea here is, that when we're
performing a series of tests, we can actually
stop evaluating this series of tests
as soon as we know what the answer is So here's an example.
Let's say we have an array, a, containing
all non-negative integers.
And we want to check if the sum of the values
in a exceed some limit.
So the simple way to do this is, you just
sum up all of the values of the array using a for loop.
And then at the end, you check if the total sum
is greater than the limit.
So using this approach, you always
have to look at all the elements in the array.
But there's actually a better way to do this.
And the idea here is, that once you
know the partial sum exceeds the limit that you're
testing against, then you can just return true,
because at that point you know that the sum of the elements
in the array will exceed the limit,
because all of the elements in the array are non-negative.
And then if you get all the way to the end of this for loop,
that means you didn't exceed this limit.
And you can just return false.
So this second program here will usually
be faster, if most of the time you
exceed the limit pretty early on when
you loop through the array.
But if you actually end up looking at most of the elements
anyways, or even looking at all the elements,
this second program will actually
be a little bit slower, because you have this additional check
inside this for loop that has to be done for every iteration.
So when you apply this optimization,
you should be aware of whether this will actually
be faster or slower, based on the frequency of when
you can short-circuit the test.
Questions?
OK, and I want to point out that there are short-circuiting
logical operators.
So if you do double ampersand, that's
short-circuiting logical and operator.
So if it evaluates the left side to be false,
it means that the whole thing has to be false.
So it's not even going to evaluate the right side.
And then the double vertical bar is going
to be a short-circuiting or.
So if it knows that the left side is true,
it knows the whole thing has to be true, because or just
requires one of the two sides to be true.
And it's going to short circuit.
In contrast, if you just have a single ampersand
or a single vertical bar, these are not
short-circuiting operators.
They're going to evaluate both sides of the argument.
The single ampersand and single vertical bar
turn out to be pretty useful when
you're doing bit manipulation.
And we'll be talking about these operators
more on Thursday's lecture.
Yes?
AUDIENCE: So if your program going to send false,
if it were to call the function and that function
was on the right hand side of an ampersand,
would it mean that would never get called,
even though-- and you possibly now
find out that, the right hand side would crash simply
because the left hand side was false?
JULIAN SHUN: Yeah, if you use a double ampersand,
then that would be true.
Yes?
AUDIENCE: [INAUDIBLE] check [INAUDIBLE]
that would cause the cycle of left hand,
so that the right hand doesn't get [INAUDIBLE]..
JULIAN SHUN: Yeah.
I guess one example is, if you might possibly index
an array out of balance, you can first
check whether you would exceed the limit or be out of bounds.
And if so, then you don't actually do the index.
OK, a related idea is to order tests, suss
out the tests that are more often successful or earlier.
And the ones that are less frequently successful
are later in the order, because you
want to take advantage of short-circuiting.
And similarly, inexpensive tests should precede expensive tests,
because if you do the inexpensive tests and your test
short-circuit, then you don't have
to do the more expensive tests.
So here's an example.
Here, we're checking whether a character is whitespace.
So character's whitespace, if it's
equal to the carriage return character,
if it's equal to the tab character,
if it's equal to space, or if it's
equal to the newline character.
So which one of these tests do you
think should go at the beginning?
Yes?
AUDIENCE: Probably the space.
JULIAN SHUN: Why is that?
AUDIENCE: Oh, I mean [INAUDIBLE]..
Well, maybe the newline [INAUDIBLE]..
Either of those could be [INAUDIBLE]..
JULIAN SHUN: Yeah, yeah, so it turns out
that the space and the newline characters
appear more frequently than the carriage return.
And the tab and the space is the most frequent,
because you have a lot of spaces in text.
So here I've reordered the test, so that the check for space
is first.
And then now if you have a character, that's a space.
You can just short circuit this test and return true.
Next, the newline character, I have it as a second test,
because these are also pretty frequent.
You have a newline for every new line in your text.
And then less frequent is the tab character,
and finally, the carriage return for character
isn't that frequently used nowadays.
So now with this ordering, the most frequently successful
tests are going to appear first.
Notice that this only actually saves you
work if the character is a whitespace character.
It it's not a whitespace character,
than you're going to end up evaluating all of these tests
anyways.
OK, so now let's go back to this example of detecting collision
of balls.
So we're going to look at the idea of creating a fast path.
And the idea of creating a fast path
is, that there might possibly be a check that
will enable you to exit the program early,
because you already know what the result is.
And one fast path check for this particular program
here is, you can check whether the bounding boxes of the two
balls intersect.
If you know the bounding boxes of the two balls
don't intersect, then you know that the balls cannot collide.
If the bounding boxes of the two balls do intersect,
well, then you have to do the more expensive test,
because that doesn't necessarily mean
that the balls will collide.
So here's what the fast path test looks like.
We're first going to check whether the bounding boxes
intersect.
And we can do this by looking at the absolute value
of the difference on each of the coordinates
and checking if that's greater than the sum of the two radii.
And if so, that means that for that particular coordinate
the bounding boxes cannot intersect.
And therefore, the balls cannot collide.
And then we can return false of any one
of these tests returned true.
And otherwise, we'll do the more expensive test
of comparing d square to the square of the sum of the two
radii.
And the reason why this is a fast path
is, because this test here is actually cheaper
to evaluate than this test below.
Here, we're just doing subtractions, additions,
and comparisons.
And below we're using the square operator, which
requires a multiplication.
And multiplications are usually more expensive than additions
on modern machines.
So ideally, if we don't need to do the multiplication,
we can avoid it by going through our fast path.
So for this example, it probably isn't
worth it to do the fast path check since it's
such a small program.
But in practice there are many applications and graphics
that benefit greatly from doing fast path checks.
And the fast path check will greatly
improve the performance of these graphics programs.
There's actually another optimization
that we can do here.
I talked about this optimization couple of slides ago.
Does anyone see it?
Yes?
AUDIENCE: You can factor out the sum of the radii
for [INAUDIBLE].
JULIAN SHUN: Right.
So we can apply common subexpression elimination here,
because we're computing the sum of the two radii four times.
We can actually just compute it once, store it in a variable,
and then use it for the subsequent three calls.
And then similarly, when we're taking
the difference between each of the coordinates,
we're also doing it twice.
So again, we can store that in a variable
and then just use the result in the second time.
Any questions?
OK, so the next idea is to combine tests together.
So here, we're going to replace a sequence of tests
with just one test or switch statement.
So here's an implementation of a full adder.
So a full adder is a hardware device
that takes us input three bits.
And then it returns the carry bit and the sum bit as output.
So here's a table that specifies for every possible input
to the full adder of what the output should be.
And there are eight possible inputs to the full adder,
because it takes three bits.
And there are eight possibilities there.
And this program here is going to check all the possibilities.
It's first going to check if a is equal to zero.
If so, it checks if b is equal to zero.
If so, it checks if c is equal to zero.
And if that's true, it returns zero and zero for the two bits.
And otherwise, it returns one and zero and so on.
So this is basically a whole bunch
of if else statements nested together.
Does anyone think this is a good way to write the program?
Who thinks this is a bad way to write the program?
OK, so most of you think it's a bad way to write the program.
And hopefully, I can convince the rest of you
who didn't raise your hand.
So here's a better way to write this program.
So we're going to replace these multiple if else clauses
with a single switch statement.
And what we're going to do is, we're going
to create this test variable.
That is a three-bit variable.
So we're going to place the c bit
in the least significant digit.
The b bit, we're going to shift it over by one,
so in the second least significant digit,
and then the a bit in the third least significant digit.
And now the value of this test variable
is going to range from zero to seven.
And then for each possibility, we
can just specify what the sum and the carry bits should be.
And this requires just a single switch statement, instead of
a whole bunch of if else clauses.
There's actually an even better way to do this,
for this example, which is to use table lookups.
You just precompute all these answers, store it in a table,
and then just look it up at runtime.
But the idea here is that you can combine multiple tests
in a single test.
And this not only makes your code cleaner,
but it can also improve the performance of your program,
because you're not doing so many checks.
And you won't have as many branch misses.
Yes?
AUDIENCE: Would coming up with logic gates for this
be better or no?
JULIAN SHUN: Maybe.
Yeah, I mean, I encourage you to see if you can write a faster
program for this.
All right, so we're done with two categories
of optimizations.
We still have two more to go.
The third category is going to be about loops.
So if we didn't have any loops in our programs,
well, there wouldn't be many interesting programs
to optimize, because most of our programs
wouldn't be very long running.
But with loops we can actually optimize these loops
and then realize the benefits of performance engineering.
The first loop optimization I want to talk about is hoisting.
The goal of hoisting, which is also called loop-invariant code
motion, is to avoid recomputing a loop-invariant code
each time through the body of a loop.
So if you have a for loop where in each iteration
are computing the same thing, well, you
can actually save work by just computing it once.
So in this example here, I'm looping
over an array of length N. And them I'm setting Y of i
equal to X of i times the exponential of the square root
of pi over two.
But this exponential square root of pi over two
is actually the same in every iteration.
So I don't actually have to compute that every time.
So here's a version of the code that does hoisting.
I just move this expression outside of the for loop
and stored it in a variable factor.
And then now inside the for loop,
I just have to multiply by factor.
I already computed what this expression is.
And this can save running time, because computing
the exponential, the square root of pi over two,
is actually relatively expensive.
So turns out that for this example, you know,
the compiler can probably figure it out
and do this hoisting for you.
But in some cases, the compiler might not
be able to figure it out, especially
if these functions here might change throughout the program.
So it's a good idea to know what this optimization is,
so you can apply it in your code when the compiler doesn't do it
for you.
OK, sentinels, so sentinels are special dummy values
placed in a data structure to simplify the logic of handling
boundary conditions, and in particular the handling of loop
exit tests.
So here, I, again, have this program that checks whether--
so I have this program that checks
whether the sum of the elements in sum array A
will overflow if I added all of the elements together.
And here, I've specified that all of the elements of A
are non-negative.
So how I do this is, in every iteration
I'm going to increment some by A of i.
And then I'll check if the resulting sum is less than A
of i.
Does anyone see why this will detect if I had an overflow?
Yes?
AUDIENCE: We're a closed algorithm.
It's not taking any values.
JULIAN SHUN: Yeah, so if the thing I added in
causes an overflow, then the result is going to wrap around.
And it's going to be less than the thing I added in.
So this is why the check here, that
checks whether the sum is less than negative i,
will detect an overflow.
OK, so I'm going to do this check in every iteration.
If it's true, I'll just return true.
And otherwise, I get to the end of this for loop
where I just return false.
But here on every iteration, I'm doing two checks.
I'm first checking whether I should
exit the body of this loop.
And then secondly, I'm checking whether the sum is less than A
of i.
It turns out that I can actually modify this program,
so that I only need to do one check
in every iteration of the loop.
So here's a modified version of this program.
So here, I'm going to assume that I
have two additional entries in my array A.
So these are A of n and A of n minus one.
So I assume I can use these locations.
And I'm going to set A of n to be the largest possible
64-bit integer, or INT64 MAX.
And I'm going to set A of n plus one to be one.
And then now I'm going to initialize my loop variable
i to be zero.
And then I'm going to set the sum equal to the first element
in A or A of zero.
And then now I have this loop that
checks whether the sum is greater than or equal to A
of i.
And if so, I'm going to add A of i plus one to the sum.
And then I also increment i.
OK, and this code here does the same thing
as a thing on the left, because the only way
I'm going to exit this while loop is, if I overflow.
And I'll overflow if A of i becomes greater than sum,
or if the sum becomes less than A
of i, which is what I had in my original program.
And then otherwise, I'm going to just increment sum by A of i.
And then this code here is going to eventually overflow,
because if the elements in my array A
don't cause the program to overflow,
I'm going to get to A of n.
And A of n is a very large integer.
And if I add that to what I have,
it's going to cause the program to overflow.
And at that point, I'm going to exit this
for loop or this while loop.
And then after I exit this loop, I can check why I overflowed.
If I overflowed because of sum element of A,
then the loop index i is going to be less than n,
and I return true.
But if I overflowed because I added in this huge integer,
well, than i is going to be equal to n.
And then I know that the elements of A
didn't caused me to overflow, the A of n value here did.
So then I just return false.
So does this makes sense?
So here in each iteration, I only
have to do one check instead of two checks,
as in my original code.
I only have to check whether the sum is greater than
or equal to A of i.
Does anyone know why I set A of n plus one equal to one?
Yes?
AUDIENCE: If everything else in the array was zero, then
you still wouldn't have overflowed.
If you had been at 64 max, it would overflow.
JULIAN SHUN: Yeah, so good.
So the answer is, because if all of my elements
were zero in my original array, that even
though I add in this huge integer,
it's still not going to overflow.
But now when I get to A of n plus one,
I'm going to add one to it.
And then that will cause the sum to overflow.
And then I can exit there.
So this is a deal with the boundary condition
when all the entries in my array are zero.
OK, so next, loop unrolling, so loop unrolling
attempts to save work by combining
several consecutive iterations of a loop
into a single iteration.
Thereby, reducing the total number
of iterations of the loop and consequently
the number of times that the instructions that control
the loop have to be executed.
So there are two types of loop unrolling.
There's full loop unrolling, where
I unroll all of the iterations of the for loop,
and I just get rid of the control-flow logic entirely.
Then there's partial loop unrolling, where I only
unroll some of the iterations but not all of the iterations.
So I still have some control-flow code in my loop.
So let's first look at full loop unrolling.
So here, I have a simple program that
just loops for 10 iterations.
The fully unrolled loop just looks like the code
on the right hand side.
I just wrote out all of the lines of code
that I have to do in straight-line code,
instead of using a for loop.
And now I don't need to check on every iteration,
whether I need to exit the for loop.
So this is for loop unrolling.
This is actually not very common,
because most of your loops are going
to be much larger than 10.
And oftentimes, many of your loop bounds
are not going to be determined at compile time.
They're determined at runtime.
So the compiler can't fully unroll that loop for you.
For small loops like this, the compiler
will probably unroll the loop for you.
But for larger loops, it actually
doesn't benefit to unroll the loop fully,
because you're going to have a lot of instructions.
And that's going to pollute your instruction cache.
So the more common form of loop unrolling
is partial loop unrolling.
And here, in this example here, I've
unrolled the loop by a factor of four.
So I reduce the number of iterations of my for loop
by a factor of four.
And then inside the body of each iteration
I have four instructions.
And then notice, I also changed the logic
in the control-flow of my for loops.
So now I'm incrementing the variable j
by four instead of just by one.
And then since n might not necessarily
be divisible by four, I have to deal with the remaining
elements.
And this is what the second for loop is doing here.
It's just dealing with the remaining elements.
And this is the more common form of loop unrolling.
So the first benefit of doing this
is, that you have fewer checks to the exit condition
for the loop, because you only have
to do this check every four iterations instead
of every iteration.
But the second and much bigger benefit
is, that it allows more compiler optimizations,
because it increases the size of the loop body.
And it gives the compiler more freedom
to play around with code and to find ways to optimize
the performance of that code.
So that's usually the bigger benefit.
If you unroll the loop by too much,
that actually isn't very good, because now you're
going to be pleading your instruction cache.
And every time you fetch an instruction,
it's likely going to be a miss in your instruction cache.
And that's going to decrease the performance of your program.
And furthermore, if your loop body is already very big,
you don't really get additional improvements
from having the compiler do more optimizations,
because it already has enough code to work with.
So giving it more code doesn't actually give you much there.
OK, so I just said this.
The benefits of loop unrolling a lower number of instructions
and loop control code.
And then it also enables more compiler optimizations.
And the second benefit here is usually the much more important
benefit.
And we'll talk more about compiler optimizations
in a couple of lectures.
OK, any questions?
OK, so the next optimization is loop fusion.
This is also called jamming.
And the idea here is to combine multiple loops
over the same index range into a single loop,
thereby saving the overhead of loop control.
So here, I have two loops.
They're both looping from i equal zero, all the way up
to n minus one.
The first loop, I'm computing the minimum of A of i
and B of i and storing the result in C of i.
The second loop, I'm computing the maximum of A of i
and B of i and storing the result in D of i.
So since these are going over the same index rang,
I can fused together the two loops,
giving me a single loop that does both of these lines here.
And this reduces the overhead of loop control code,
because now instead of doing this exit condition check two n
times, I only have to do it n times.
This also gives you better cache locality.
Again, we'll talk more about cache locality
in a future lecture.
But at a high level here, what it
gives you is, that once you load A of i and B of i into cache,
when you compute C of i, it's also
going to be in cache when you compute D of i.
Whereas, in the original code, when you compute D of i,
it's very likely that A of i and B of i
are going to be kicked out of cache already,
even though you brought it in when you computed C of i.
For this example here, again, there's
another optimization you can do, common subexpression
elimination, since you're computing this expression
A of i is less than or equal to B of i twice.
OK, next, let's look at eliminating wasted iterations.
The idea of eliminating wasted iterations
is to modify the loop bounds to avoid
executing loop iterations over essentially empty loop bodies.
So here, I have some code to transpose, a matrix.
So I go from i equal zero to n minus one,
from j equals zero to n minus one.
And then I check if i is greater than j.
And if so, I'll swap the entries in A of i, j and A of j, i.
The reason why I have this check here
is, because I don't want to do the swap twice.
Otherwise, I'll just end up with the same matrix I had before.
So I only have to do the swap when i is greater than j.
One disadvantage of this code here is, I still
have to loop for n squared iterations,
even though only about half of the iterations
are actually doing useful work, because about half
of the iterations are going to fail this check here,
that checks whether i is greater than j.
So here's a modified version of the program, where I basically
eliminate these wasted iterations.
So now I'm going to loop from i equals one to n minus one,
and then from j equals zero all the way up to i minus one.
So now instead of going up to n minus one,
I'm going just up to i minus one.
And that basically puts this check,
whether i is greater than j, into the loop control code.
And that saves me the extra wasted iterations.
OK, so that's the last optimization on loops.
Are there any questions?
Yes?
AUDIENCE: Isn't the checks still have [INAUDIBLE]??
JULIAN SHUN: So the check is--
so you still have to do the check in the loop control code.
But here, you also had to do it.
And now you just don't have to do it again
inside the body of the loop.
Yes?
AUDIENCE: In some cases, where it
might be more complex to do it, is it
also [INAUDIBLE] before you optimize it,
but it's still going to be fast enough [INAUDIBLE]..
Like in the first example, even though the loop is empty,
most of the time you'll be able to process [INAUDIBLE]
run the instructions.
JULIAN SHUN: Yes, so most of these
are going to be branch hits.
So it's still going to be pretty fast.
But it's going to be even faster if you just
don't do that check at all.
So I mean, basically you should just text it out
in your code to see whether it will give you
a runtime improvement.
OK, so last category of optimizations is functions.
So first, the idea of inlining is
to avoid the overhead of a function call
by replacing a call to the function with the body
of the function itself.
So here, I have a piece of code that's
computing the sum of squares of elements in an array A.
And so I have this for loop that in each iteration
is calling this square function.
And the square function is defined above here.
It just does x times x for input argument x.
But it turns out that there is actually some overhead
to doing a function call.
And the idea here is to just put the body
of the function inside the function that's calling it.
So instead of calling the square function,
I'm just going to create a variable temp.
And then I set sum equal to sum plus temp times temp.
So now I don't have to do the additional function call.
You don't actually have to do this manually.
So if you declare your function to be static inline,
then the compiler is going to try
to inline this function for you by placing
the body of the function inside the code that's calling it.
And nowadays, the compiler is pretty good at doing this.
So even if you don't declare static inline,
the compiler will probably still inline this code for you.
But just to make sure, if you want to inline a function,
you should declare it as static inline.
And you might ask, why can't you just use a macro to do this?
But it turns out, that inline functions nowadays are just
as efficient as macros.
But they're better structured, because they evaluate
all of their arguments.
Whereas, macros just do a textual substitution.
So if you have an argument that's
very expensive to evaluate, the macro
might actually paste that expression multiple times
in your code.
And if the compiler isn't good enough
to do common subexpression elimination,
then you've just wasted a lot of work.
OK, so there's one more optimization--
or there's two more optimizations
that I'm not going to have time to talk about.
But I'm going to post these slides on Learning Modules,
so please take a look at them, tail-recursion elimination
and coarsening recursion.
So here are a list of most of the roles
that we looked at today.
There are two of the function optimizations
I didn't get to talk about, please take
a look at that offline, and ask your TAs if you
have any questions.
And some closing advice is, you should
avoid premature optimizations.
So all of the things I've talked about today
improve the performance of your program.
But you first need to make sure that your program is correct.
If you have a program that doesn't do the right thing,
then it doesn't really benefit you to make it faster.
And to preserve correctness, you should do regression testing,
so develop a suite of tests to check
the correctness of your program every time
you change the program.
And as I said before, reducing the work of a program
doesn't necessarily decrease its running time.
But it's a good heuristic.
And finally, the compiler automates
many low-level optimizations.
And you can look at the assembly code
to see whether the compiler did something.