So far in this course we've avoided 
talking about performance or program 
efficiency. 
And we've done that quite deliberatly. 
The reason is that it's very easy for 
programmers to worry too much about 
efficiency, to soon about efficiency or 
to be honest, to worry just plain 
incorrectly about efficiency. 
As a general rule, it's a better idea to 
design a simple program that's easy to 
understand, and easy to change and then 
worry about the efficiency later, once 
the program's running. 
What you can do then is you can run the 
program against a sample data set, and 
measure its performance, and see where 
the real performance problems are. 
What you'll find is you often get 
surprised. 
Some of the things you thought would be a 
performance problem get taken care of 
automatically by the programming language 
implementation. 
Other things you might have thought would 
be a performance problem turn out not to 
be. 
And then unfortunately there's some other 
things that you didn't think would be 
performance problems that turn out to be 
performance problems. 
That said, there's one category of 
performance problem you really need to 
fix as part of the design. 
That has to do with problems of 
exponential growth in the time it takes 
your program to run as the data gets 
larger. 
Alright, exponential growth in 
performance is not going to be a good 
property for your program to have. 
So what we're going to do in this video 
is look at how you can use Local to deal 
with an important category of these 
problems. 
I'm back in a version of the file system 
program, FSV6. 
And in this version, the definitions are 
the same. 
I've got this function made, skinny. 
And what made skinny does is make trees 
that are very skinny, they're not bushy 
at all. 
Each element just has one child until it 
gets down to the leaf. 
And if I say it makes skinny of two, for 
example, I get a tree that looks like 
this. 
There's an element that's called X at the 
top. 
It has one child called X and it has one 
child called Y, which is the leaf. 
So it's X, X, X, X and then Y at the 
bottom. 
So makes skinny of ten is ten X's and a 
Y. 
Make skinny of 100 is 100 x's and a y. 
That's all make skinny does. 
And then find is the function we designed 
before that just tries to find an element 
with a given name. 
So what I'm going to do now Is I'm going 
to call find of y on some trees of 
different depths. 
And I'm using a new BSL primitive here. 
It's a very special thing. 
It's more like an if than a function, 
because it evaluates its operands in a 
special way. 
But what time does is it evaluates its 
operands, it sees how long it takes and 
gives us back the time. 
So, what you can see here I'm timing how 
long it takes to find y in a tree 10 
deep. 
A tree 11 deep, 12, 13, 14 and so on. 
Okay? 
So, here we go. 
If I run that then the times I get Let me 
scroll this top so you can see. 
The time it takes in a tree that's 10 so 
y is the 11th. 
E is 2 milliseconds. 
This is in milliseconds. 
in the next one, it's 3 milliseconds, and 
the next one it's 7, then it's 20, 35, 
57. 
So now what I'm going to do is plot that. 
So let's look at this plot. 
A bad thing is happening here, isn't it? 
Each time, we make skinny one deeper. 
What's happening to the time it takes for 
this to run? 
It's increasing by what? 
It's increasing by pretty close to a 
factor of 2. 
Let me just add a couple more to see. 
We'll make that 16 and 17. 
If we extend the plot to, the numbers 
changed a little bit. 
'Kay? 
The numbers changed a little bit that's 
because it doesn't always compute the 
exact same time. 
It turns out that measuring how long a 
program takes to run is a very 
complicated thing. 
But these numbers are, are a good 
indication of how long it takes to run. 
So with this now extended plot- scroll it 
a bit so we can see all the data- it's 
really clear that it seems to be taking 
twice about as long to run, when we make 
the tree one deeper. 
Now that's a serious performance problem. 
The tree gets deeper by one. 
Find takes twice as long. 
That's an exponential performance 
problem. 
Okay? 
because, as the tree gets deeper and 
deeper, its basically 2 to the depth of 
the tree. 
That's bad. 
So why is that happening? 
Well here's why its happening right here 
in find. 
Look at what Find does here. 
It says, Well, go look for n in the first 
child. 
And if that doesn't produce False, then 
that's the value you want. 
So, produce that value. 
And from the perspective of producing the 
right value, this program is perfectly 
correct and good and wonderful. 
But the problem it has is that in a 
branch where it finds the value it's 
looking for, it searches in that branch 
twice. 
So in this particular degenerate case of 
the tree, where the tree is one long 
first branch, at the very top we search 
the next level down twice. 
And then for each of those, we search the 
next level down twice, because each time 
we first do this to see if it's there, 
and when we find out it is there, we 
search it again to produce the result. 
So We search this level twice. 
We search this level four times. 
Two times, two, each time it's two times 
more. 
And there's the exponential growth. 
So right there, there it is. 
There's the exponential growth. 
We can see why, it's a factor of two each 
time. 
So how do we fix that? 
Well it's really easy to fix that with 
local. 
Local's exactly what we want to use here. 
Basically, we're calling a function here, 
and then we're calling it here again, to 
recompute the same value. 
And what we can do is we can use Local to 
avoid re-computing the same value. 
Now watch here is the systematic way I do 
it. 
I find the enclosing expression that 
contains both computations. 
So here's one and here's another one, and 
I find the nearest enclosing expression 
that does it. 
In that case it's this if I wrap that in 
local, and I's give, I say define and you 
know I've think of some, some name here, 
right. 
I can call it try and I take this value 
here. 
This expression and I name its result, 
Try. 
So now I'm saying, hey, go do this fine 
and let's name it Try. 
And then each place I used to have the 
expression, I put, Try. 
And I need to close that Local, so that's 
going to be right. 
There the if, I add one more [UNKNOWN]. 
I do a command i to fix the indentation 
and now what this says is it says hey go 
look in the first child and lets call the 
result we get from that try and now I can 
look at the value try as many times as I 
want. 
In this case potentially twice. 
Without recomputing the value. 
I computed it only once here. 
I call it try. 
And then, each time I use try, I don't 
recompute it. 
So if we try this version of the program. 
Ha, sorry, pardon the pun. 
If we run this version of the program, 
and look at the performance numbers we 
get, look. 
No exponential growth. 
So this is a case where we use local to 
avoid recomputation. 
Now, I want to be really clear here. 
The reason this recomputation matters is 
because it's recursive. 
This recomputation leads to exponential 
growth because of the recursion. 
Here's a thing I would encourage you not 
to do. 
If you, for example, are going to take a, 
an argument that you consume and add one 
to it and use that twice, you know, using 
Local to avoid the computation of adding 
one twice isn't worth doing. 
That's going to make your program harder 
to read. 
For little and perhaps to be honest with 
you no performance game at all. 
Kay, because program in language 
implementations are good at spoting 
things like that and doing them for you. 
But here because we have a recursive 
function if the we do the re-computation 
at each level we get the expedential 
growth, exponential Performance problems 
are definitely bad. 
No one's ever going to say that's not a 
problem. 
So here it's worth using local to avoid 
the re-computation. 
So there you go, that's our second 
important use of local. 
We use it to avoid recomputing values. 
Especially in recursive functions because 
in those recursive functions that 
recomputation could lead to exponential 
performance problems and the general 
refactoring is you find the nearest 
expression that encloses all of the 
recomputed values. 
You wrap a local right around that 
expression, you give the value some name, 
like try or something else. 
And then you use that name in place of 
each of the original expressions that 
recomputed the value.