14
Aug

Optimization – Programming Languages


So now that we have a better understanding of how to check that our program is correct and test it to gain confidence, let’s talk about optimization–making our program faster. Over on the right, I’ve doodled the tortoise and the hare. You can tell this is a hare and not, let’s say, a mutated donkey because of the label; those labels are always correct. This bears reference to one of Aesop’s fables–a Greek writer from times long ago– in which the hare, although in some sense faster was relatively lazy and was eventually beaten out by the tortoise. In the real world, performance matters. We’ve heard, for example, that if you don’t render a web page in 6 seconds or less shoppers will go to another website. For the vast majority of applications, things in this class: airline autopilots, banking transactions, things related to energy or power or transportation, performance matters less than correctness. Job one–test it, debug it, get the right answer. Job two–make it fast. In this sense, optimization refers to improving the performance of our code. Can we make our web browser take less time to render the same web pages? A lot of modern interpreters, from JavaScript interpreters to Python, use a technique known as Just-in-Time Improvement, which is sometimes abbreviated as JIT, to fix up or improve code right before they run it so that it’s faster but gets the same output. So our basic optimization idea is going to be to replace the input webpage–the HTML or JavaScript fragment– with one that takes less time to process but has–and this is super critical– I cannot emphasize this enough–exactly the same meaning. We must produce the same output with optimizations on and with optimizations off, aside from the time it takes. We absolutely can’t change the meaning. We have to be correct. In that sense, optimization for programming languages is somewhat similar to editing for conciseness in natural languages. If you say something redundant and it’s possible to remove that redundancy without changing the meaning, you can strike it from written text. We’re going to do the same thing with optimization. Here I’ve written JavaScript code to compute the factorial function, and this code is correct. Now, of course, as soon as I say that there’s going to be one minor typo, but let’s just assert that this code is correct. It actually computes factorial. But it’s a little slower than it needs to be. You may have noticed that I wrote 1 times N times factorial of N minus 1 instead of just N times factorial of N minus 1. This is correct–multiplying something by 1 doesn’t change its meaning– but it’s slower than necessary. If we’re talking about arithmetic, whenever you see 1 times N, you could just replace it by N, and now you’re saving time because we’re removing notes from our abstract syntax tree. This means it takes less time to do our recursive walk and interpret it, and we have fewer multiplications. And multiplication is an arithmetic operation that this CPU has to perform; it takes some amount of time. In fact, especially in something like factorial, if I’m asking for the factorial of 10, we’re going to call this function a large number of times. So even though it may not seem like I’m saving much, I save it every time we’re in this loop. And this is why I suggested earlier that performing such a simplification or optimization is like editing someone’s writing so that it’s more concise. If I just edit that part away, this factorial is still correct; it just takes a little less time.

Tags: , , , , , , , ,

There are no comments yet

Why not be the first

Leave a Reply

Your email address will not be published. Required fields are marked *