Original subtitles

focus on how to measure and compare performance of different data structures and algorithms.

This specific module is a bit special, in that it presents a toolbox that we will use intensively throughout

the rest of the course. Some of the concepts presented may seem odd or abstract at first, and they might

take some time to get used to, but hold on, once you are through this module and we have established a common

language for performance complexity comparison, the remaining modules will be much more concrete.

We just need this toolbox first. So, without further ado, let's consider

a few different ways of measure performance. So, one strategy is to use a stopwatch to simply measure the

time it takes for a given action to complete. That was actually what we did in the introduction,

comparing two implementations on an iPhone and a laptop respectively.

However, that approach comes with some drawbacks, because a lot of things are in play when measuring one

thing as the hardware the executes the implementation, where more capable hardware may result in a faster

execution time, even though the algorithm implemented in itself is just the same or maybe even slightly worse

than an algorithm running on some less capable hardware. Other things can influence the measure time, too,

such as the compiler optimizations, and possible simultaneously running programs that may eat resources from our machine.

Measuring execution time with a stopwatch has another drawback, namely the fact that it is only a single measuring point.

Specifically, that single measurement does not say anything about how the execution time may behave for

smaller or larger inputs; for example, how the execution time may grow for our log reader when more log

lines are supposed to be analyzed. We can achieve a better understanding on the nature of the performance

behavior for varying input sizes by considering the number of instructions executed by the machine when

running a given program. If we're shown that each instruction takes a certain fraction of a second to

execute, then the total time usage is just a matter of multiplying this per instruction time with the total

number of instructions. For example, consider the function from the intro that just reads the provided log

file and counts the number of log lines. We could assume that the two first lines in the function uses one

instruction each, summarizing to two instructions. And for the sake of simplicity, that the contents of the

for loop uses four instructions. If the log file contains 100,000 lines, we thus end up with an expression

for the total number of instructions executed that looks like this.

The last + 1 comes from the return statement. If we, instead of assuming 100,000 log lines are using the

letter N to symbolize any number of log lines, then we get a more general expression that looks like this.

Now we can get an idea of the complexity of an algorithm for a given input size simply by inserting an

appropriate number of N in the formal layer. An interesting question we could now ask is how this expression

grows when N increases, and this leads us to the third approach of measuring performance, namely, to look at

the nature of the curve that the instruction count formally from before represents.

And remember that the number of instructions directly relates to the execution time.

Consider the following examples of such curves. The formula from before represented a straight line like this.

A straight line means that the execution time is somewhat reliable, so that an increment in the input size,

or N as we named it, of 500, say, from 1000 to 1500, results in the same execution time growth than an

increment of the input size from, say, 10,000 to 10,500. Here is another example of a line where the

execution time increases slightly faster. Often when the curve looks like this we are happy,

because then our algorithm does not get relatively more cumbersome for a larger input.

We also say that the execution time grows linearly with the input size, and linearity is good.

An example of an even better looking curve is this one. And as you can see, increasing the input size with

a certain amount has a higher relative impact on the execution time for smaller inputs than for larger inputs.

That is, increasing the input size with, say, 500 again, will result in almost no additional execution time

when the input is sufficiently large. Of course, this is a quite ideal performance behavior for an

algorithm, and as we shall see later on, there are ways of searching for data that has exactly this property.

And this basically means that the extra time we need to find the needle in the haystack only increases a tiny

bit, even if the haystack grows significantly in size. On the other end of the scale is a curve like this.

As you can see, this curve has opposite properties than a formal one.

Even though the execution time only grows slowly for small input sizes, the execution time will explode in

size whenever the input gets large enough, and notice that this explosion can happen even if the execution

time is very small for small inputs. Naturally this is the worst imaginable behavior for an algorithm,

because this effectively sets a probably rather low upper limit for how large inputs we can handle.

So, considering the curves that represent the instruction count can give us a pretty good understanding of

how the execution time grows when the input size grows. With that mindset in hand, we can start considering

other performance characteristics. For example, we could consider a best-case scenario for an algorithm,

that is, a curve that represents the most optimistic simulation for an execution, a guarantee that states

what the shortest possible execution time can ever be. We can also consider the worst-case scenario,

that is, an upper limit for how bad an algorithm can perform for a given input size.

When talking about algorithms, this curve is very interesting, simply because there is often a desire to

solve problems as fast as possible, not only when the input is nice, but also in the worst possible situations.

And then, it is useful to know how bad the algorithm will possibly behave.

As a last example, consider a performance behavior that is nice, except for certain spikes, as shown in this curve.

If we are running the corresponding algorithm numerous times, multiple times, it can be interesting to

consider the amortized performance, that is, what is the real cost when summarizing the execution times

across multiple executions. Do the spikes contribute significantly to the execution time in the total

picture, or can they, so to speak, be balanced out? So, that was four ways to consider performance measuring.

In the next clip, we will zoom in on how to come from program source code to its related execution time curve.