<jupyter_start><jupyter_text>Software OptimizationWe are now getting to the end of IN1910. In fact, there are only four lectures left. We are now starting on our last new topic in IN1910: Optimization.The four remaining lectures will be organized as follows:| Lecture | Topics | | ------- | ------ || L21     | Benchmarking and Profiling || L22     | Mixed programming | | L23     | Parallel programming | | L24     | Summary of IN1910 |  What is Software Optimization?The word optimization gets thrown around, bet let us try to narrow down what we actually mean by it. The word *"optimize"* itself literally means to* *optimize* — Make the best or most effective use of (a situation or resource).To optimize software therefore means to make the software more effective. The word itself comes from the word "optimal", however, it is important to stress that making an "optimal" program is as good as impossible, as there is no single "optimal" program. The goal is therefore to make a program *better*, not to make it *the best*.It is also important to clearly distinguish software optimization with [*mathematical optimization*](https://en.wikipedia.org/wiki/Mathematical_optimization). Mathematical optimization is, put simply, what input arguments or parameters minimize or maximize some mathematical function. This kind of optimization is also a very important topic, and is often related to numerical methods such as *Newton's method*. When simply using the term *optimization*, even when talking about programming, it is not always clear whether one refers to optimizing the code itself, or if one is solving an optimization problem. Here it is important to be clear.In IN1910, we are looking at *software optimization*, not mathematical optimization. Our goal is to create more efficient programs.   Efficient ProgramsWhat do we mean by making more efficient programs? The main goal is often to make programs *faster*. Optimization is talking about *speed*. Optimizing a program is often about simply making it run faster. However, sometimes, optimizing might mean becoming efficient with other resources. One can for example optimize with respect to memory usage of the program, or with respect to broadband usage. For mobile programming, battery usage can be an important thing to optimize with respect to, or simply the the size of the program itself.Optimizing with respect to different resources can often be a trade-of. For a given problem we might be able to make it run faster, but to do so, we need to also use more memory. Then we need to weigh the pros and cons and choose which to focus on. For scientific programming, *speed* is usually what we care most about, and it is what we will mostly think about in IN1910.  When to optimize?The first question we want to look at, is *when* to optimize code. Ideally we would of course simply write efficient and optimal code from the get go, however, that is not realistic. When facing a new problem and coding, we already have our plate full simply trying to find a solution to the problem, if we at the same time was trying to optimize our code at every step, the whole process would take much longer and we would get stuck more easily.Because of this concept, most proficient programmers recommend to postpone optimizing to *after* having developed code that works. This statement was formulated by <NAME> as:1. Make it Work2. Make it Right3. Make it FastI prefer to paraphrase Beck as1. First make it work2. Then make it elegant3. Lastly, make it fastLet us look at each step seperately  1. First make it workWhen you start solving a brand new problem or implement a new feature, you cannot possibly focus on everything at once. A major goal in programming is as always to work *incrementally*. Therefore, when you sit down with a new problem, you should *ignore optimization*, and instead focus on the basics. Simply: *How do I solve this problem?*As you are breaking down the problem and implementing, and getting close to a working solution, you also need to *verify* that it works through verification and validation. This is done through rigorous testing, as we have covered earlier in the course. Writing an extensive test-suite of test cases, unit tests and integration tests can make us confident that we have a working solution.  2. Then make it elegantAfter you have managed to break down your problem and created a solution that seems to work, the next step is to make it "elegant". Others refer to it as making the code "pretty", or as Beck calls it, making it "right".The step of making the code elegant does not refer to the actual functionality of the code, but everything else. The major part of this step is referred to as [*refactoring*](https://en.wikipedia.org/wiki/Code_refactoring) code. Refactoring code means rewriting it, not to change its function, but to improve it in other ways. Refactoring can include changing the overall structure of the code, for example splitting things into functions, classes or modules in different ways. But it can also mean rewrite single lines, or changing variable names. The goals are simple: making the code more structured and readable. The benefits is that the code is easier to read, easier to understand and easier to maintain and develop further.> By continuously improving the design of code, we make it easier and easier to work with. This is in sharp contrast to what typically happens: little refactoring and a great deal of attention paid to expediently adding new features. If you get into the hygienic habit of refactoring continuously, you'll find that it is easier to extend and maintain code.— <NAME>, Refactoring to PatternsWhen refactoring code, you should also look closely at your code style. When working fast at prototypin and solving new problems, you are most likely not strictly adhering to a given style guide, but before you put your code into production (handing it in, publishing it online, sharing it with colleagues, etc), you should go back through and make sure your style is consistent and solid.Another important part of making code elegant, is to build in good documentation. In Python, this is about writing good docstrings. This step can wait untill you have both developed working code, and then have refactored it. This is because if you write your docstrings *before* the code or refactorization, then you might change things around so your documentation is no longer describing the actual code. And recall, wrong documentation is worse than no documentation.After making the code more elegant through refactorization and rewriting, you should rerun all the tests you made in step (1). This is because in the process of changing things around and rewriting it, you might have accidentally broken your code. By rerunning the tests, you can verify that the behavior of the program itself is unchanged. This also emphasizes how important it is to implement good and extensive tests.  3.  Lastly, Make it FastAnd now we are finally at the optimization step. The important point is that it is placed *after* developing a working code, and making that code elegant. Only after you have done these steps can you start looking at how to make this code faster.*How* to make the code faster is the topic we will turn to shortly. However, it is also important to emphasize that if we make changes to our code to make it more effective and faster, we should rerun tests and verify that our changed solution still solves the problem and that we have not broken it in our strive for speed.  Should you Optimize?The third step above was formulated as "Make it Fast", however, before you start doing this, you should also ask yourself *Should you even optimize?*  Optimizing code is a tricky task, and in the process of making your code faster, you are paradoxically spending time. If the goal of optimizing the code is to *save time*, you need to save more time with the optimized code than it takes to actually perform the changes.The XKCD comic below illustrates this point by showing how much time you can invest into optimizing your code and still save time. As the comic illustrates, how much time you save by optimizing depends on *how many times you run your code*.Source: XKCD 1205It is important to stress that if the goal is to produce code that is to be shared with others or sold, making the code more efficient makes a *better* product, and so the goal is itself not to save your own time, but save others time. The table above is more from the point of view of writing and using your own code. In addition, sometimes optimization is done as a learning exercise, in which case the time used in the optimization isn't "wasted time". In other cases it is about showing of, earning epic bragging rights or winning programming competitions.  Source: XKCD 974 Source: XKCD 1319  Benefits of optimizationMaking programs run faster is not only about *saving time*. In scientific programming, if we are able to make a program or experiment run faster, it not only saves us time, but it also enables us to carry out experiments at a larger scale, better precision or simply to run more experiments. Optimizing for speed is therefore important in that it not only enables us to do things faster, but it enables us to do *more things*.  Drawbacks of optimizationWhile *optimizing* and making more efficient code sounds great, it is important to remember that there are *drawbacks* to optimizing code as well.The first drawback is, as already mentioned, that it simply takes a lot of development time. This development time could have instead been invested into making code that was more general, contained more features, was better tested and so on. For scientific programming, time spent optimizing code could instead have been invested into exploring the problems in other ways, or analyzing results, writing papers and so on.Another aspect of optimization is that optimized code is also often less readable than less optimized, but more intuitive code. In the process of making the code faster, we are actually making it harder to read and understand. In effect, this also means that our code is also harder to maintain and further develop.In addition to these drawbacks, it is also easy to introduce errors to our code when optimizing, and if we are not careful we get erroneous results.There are therefore both benefits and drawbacks to optimizing code. You should therefore give some though to wether or not you even *want* to invest the time needed to properly optimize code, or wether you have code that is good enough for your current use cases.  How to OptimizeIf you have decided that you *want* to optimize your code, it's important to do so in a structured and organized manner, to ensure that we optimize things in an efficient manner. To do this, we will introduce some important techniques:* Algorithm analysis to figure what the theoretical difference between different approaches is* Timing and benchmarking to figure out *how fast is the code actually*?* Profiling to understand *what parts of the code needs to be optimized*We have already talked about algorithm analysis in this course, and here a big part of optimizing a program lies. By choosing a different algorithm or data structure to solve a specific problem, we can make our program a *lot* faster and scalable.    Timing and BenchmarkingTiming code is a good way to explore wether the steps we take to optimize our code is *actually* making things faster. There are many tools available for timing code, in Python, the built-in `timeit` package is a good choice. In Jupyter and iPython there are additional tools for using `timeit` to explore code fast. Let us look at an example. In [this StackOverflow post](https://stackoverflow.com/questions/327002/which-is-faster-in-python-x-5-or-math-sqrtx) a user is wondering which is faster, using `math.sqrt(x)`, or simply writing `x**0.5` to compute the square root, or perhaps alternatively `pow(x, 0.5)`.Now, this user was wondering which was fastest, and so simply asked. In fact, in addition to asking on StackOverflow, he also emailed the question to <NAME>, the original creator of Python.The email To Guide:>There are at least 3 ways to do a square root in Python: math.sqrt, the '**' operator and pow(x,.5). I'm just curious as to the differences in the implementation of each of these. When it comes to efficiency which is better?Guido actually responded to this mail with the following answer> pow and ** are equivalent; math.sqrt doesn't work for complex numbers, and links to the C sqrt() function. As to which one is faster, I have no idea...The interesting point here is that even Guido, Python's creator, doesn't imediately know which is faster. So if we don't know which option is fastest, and asking one of the top experts doesn't help. How can we check? Timeit can be used to simply *check* through experimentation.<jupyter_code>import numpy as np
import math

x = 23145
%timeit math.sqrt(x)
%timeit x**0.5
%timeit math.pow(x, 0.5)
%timeit np.sqrt(x)<jupyter_output>877 ns ± 20 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)<jupyter_text>When we use `timeit`, the computer performs a numerical experiment. Simply repeating the call many times, and taking the average. The reason it repeats the code many times it that a single timing will be affected by *noise*. Timeit will itself decide how many calls to perform, depending on how long a single call takes. We can also force it to take a specific amount of loops, but this is often not necessary unless we want more fine control. In our example, we only tried taking the square root of a single number, but let us instead try a large number of different numbers:<jupyter_code>def sqrt_numbers_math():
    for x in range(20000):
        math.sqrt(x)
        
def sqrt_numbers_exp():
    for x in range(20000):
        x**0.5
        
def sqrt_numbers_pow():
    for x in range(20000):
        math.pow(x, 0.5)
        
def sqrt_numbers_np():
    for x in range(20000):
        np.sqrt(x)<jupyter_output><empty_output><jupyter_text>We can also store the time from a call to `%timeit` in jupyter, if we append the `-o` flag:<jupyter_code>time_math = %timeit -o sqrt_numbers_math()
time_exp = %timeit -o sqrt_numbers_exp()
time_pow = %timeit -o sqrt_numbers_pow()
time_np = %timeit -o sqrt_numbers_np()<jupyter_output>18.8 ms ± 1.06 ms per loop (mean ± std. dev. of 7 runs, 100 loops each)<jupyter_text>By carrying out timeing experiments, we get an explicit control of how long different approaches to the same problem takes. Here for example, we learn that `np.sqrt()` is significantly slower than the other options. This is because `np.sqrt()` is made for also taking the square root of large arrays, and so it is not the best option for taking the roots of single numbers.Now, while `np.sqrt()` is signifigantly slower, it is still *fast*, so for a program that computes a square root less than a thousand times for example, using `np.sqrt()` instead of `math.sqrt` won't make a noticable difference. But if we are computing millions upon millions of roots, then the speedup might be noticable. Performing your own timing experiments rather than googling "which is faster, x or y" is a good habit. For one thing is that the info you find might be outdated, or belong to a different setup. Perhaps you find results for Python 2, but you are using Python 3? Or something changed in the newer numpy version, which you are using? If you use timing experiments on your own machine, you get empirical evidence of your own situation,.  Timing lines, functions and modulesThe `timeit` package can be used to test single statements, functions, or entire programs/modules. Which it makes sense to focus on depends on the specific problem, and where in the optimization process you are.   BenchmarkingA [*benchmark*](https://en.wikipedia.org/wiki/Benchmark_%28computing%29) is a specific test case one can use to test different solutions to a problem, or different codes. You can create your own benchmark test before you start optimizing, so you have something specific to work up against. The important thing is to test the different versions of the code against the *same benchmark*. If you keep changing your benchmark along with your code, then you cannot have a proper handle on how the different versions of your code performs.Benchmarks are also often formulated and then shared openly, as sort of a challenge to different people in the community. To have a publicly formulated benchmark makes it easier for different people to compare their solutions to a given problem against each other. This is especially true in computer hardware, where different CPU's and GPU's for example, are tested against different benchmarks to *rate* them against specific socres.  ProfilingThere is a rule of thumb in programming, called the 90-10 rule, which states that a program usually spends more than 90% of its time in less than 10% of the code. This has important consequences for how we should optimize a program. If you want to make a program more efficient, you should just open up the code, and go through it line by line looking for places to improve the speed. Because most of the code is not where the program spends a majority of its time, we are simply inefficient in where we use our time to optimize.Instead, we should identify the portions of the program that hogs the majority of the execution time of our program. These are normally called the *bottlenecks* of a program. Before you even start to think about optimizing code, you should identify the bottlenecks. Now, you can make guesses of where these are, they will for example often be inside loops, because the contents of loops gets repeated many times.However, research shows that most programmers, even very experienced programmers, are quite terrible at guessing at what parts of a program are the most inefficient. Except for the simplest cases, we cannot simply look at a code and say where the bottlenecks are. Therefore we turn to an important tool: Profiling. A Profile is much like a timing experiment carried out on a function or a module. However, in addition to timing the total run-time, it keeps track of *where* in the code the different time is spent. This gives us information about the bottle necks.  Example: The Drunkard's WalkThe following code models a random walker that takes random steps untill it reaches some predefined position called "home". This problem is often known as the *Drunkards walk*, as it models a drunk person rambling untill they get home and pass out.We implement it in an object oriented manner.<jupyter_code>import numpy as np
import matplotlib.pyplot as plt

class DrunkardsWalk:
    def __init__(self, home):
        self.x = 0
        self.home = home
        self.history = [0]
    
    @property
    def position(self):
        return self.x
    
    @property
    def steps(self):
        return len(self.history)
    
    def is_at_home(self):
        return self.position == self.home
    
    def step(self):
        self.x += 2*np.random.randint(2) - 1
        self.history.append(self.x)
    
    def walk_home(self):
        while not self.is_at_home():
            self.step()
        return self.steps
    
    def plot(self):
        plt.plot(range(self.steps), self.history, alpha=0.7)
drunkard = DrunkardsWalk(100)
steps = drunkard.walk_home()
drunkard.plot()
plt.show()
print(drunkard.steps)
for walker in range(5):
    drunkard = DrunkardsWalk(100)
    drunkard.walk_home()
    drunkard.plot()

plt.show()<jupyter_output><empty_output><jupyter_text>Let us profile this code. In Python, a standard package for profiling is `cProfile`, which should come pre-packaged with your python installation.<jupyter_code>import cProfile
np.random.seed(100122)
cProfile.run('DrunkardsWalk(100).walk_home()')<jupyter_output>10345833 function calls in 6.571 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   862153    0.087    0.000    0.087    0.000 <ipython-input-22-b157087bcb36>:10(position)
        1    0.000    0.000    0.000    0.000 <ipython-input-22-b157087bcb36>:14(steps)
   862153    0.245    0.000    0.331    0.000 <ipython-input-22-b157087bcb36>:18(is_at_home)
   862152    0.558    0.000    5.944    0.000 <ipython-input-22-b157087bcb36>:21(step)
        1    0.289    0.289    6.564    6.564 <ipython-input-22-b157087bcb36>:25(walk_home)
        1    0.000    0.000    0.000    0.000 <ipython-input-22-b157087bcb36>:5(__init__)
        1    0.006    0.006    6.571    6.571 <string>:1(<module>)
   862152    0.714    0.000    2.128    0.000 _dtype.py:319(_name_get)
  1724304    0.522    0.000    0.805    0.000 numerictypes.py:293(issubclass_)
   862152    0.543    0.000    1.414    0.000 numerictypes.py:365(issubdtype)
        1    0.000  [...]<jupyter_text>The output from cProfile shows the time used by the different functions of the program. For each function, a row is printed. The name of the function is shown on the right-most side. The other columns show different information* **ncalls**: The number of times the function is called* **tottime**: Time spent inside the function without sub-functions it calls* **cumtime**: Time spent inside the funtion *and* inside functions it calls* **per call**: The time divided by number of calls To understand which parts of the code are the slowest, we need to look down the `tottime` column and find the biggest number. Here the three biggest are:* `randint()` with 1.091 seconds* `step()` with 0.446 seconds* `walk_home()` with 0.282 secondsAt the top it says the total time of execution as 2.139 seconds, and so `randint()` uses about half of our programs execution time. Note also that there are some rows to functions that are tehcnical, such as `method 'disable' of '_lsprof.Profiler' objects`, which you can simply ignore.  More on cProfileThe `cProfile` package is a good tool for performing *function profiling* in Python. This means it explores how much time different functions spend. To get more control on how to analyze the outputs of `cProfile`, instead of just writing out a big table, we can use the `pstats` package ("profiling stats"). You can read more about `cProfile` and `pstats` on the official [Python documentation here](https://docs.python.org/3/library/profile.html).  Line ProfilingAn alternative to *function profiling* with cProfile, is to *line profile*. This means it divides the time use of your program into each seperate line. The benefit of line profiling is that it doesn't just tell you which function is slow, but exactly where inside a function which is slow.To do line profiling in Python, you can use the `line_profiler` pacakge. This needs to be installed. If you are using an anaconda installation, install it by writing:- Anaconda Python: `conda install line_profiler`Otherwise, install it using pip:- Other Pythons: `pip3 install line_profiler` To use `line_profiler` inside a notebook, we need to load it as an external tool<jupyter_code>%load_ext line_profiler
lpres = %lprun -r -f DrunkardsWalk.step -f DrunkardsWalk.walk_home DrunkardsWalk(100).walk_home()<jupyter_output>Timer unit: 1e-06 s

Total time: 0.029533 s
File: <ipython-input-11-b157087bcb36>
Function: step at line 21

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    21                                               def step(self):
    22      2354      28035.0     11.9     94.9          self.x += 2*np.random.randint(2) - 1
    23      2354       1498.0      0.6      5.1          self.history.append(self.x)

Total time: 0.035255 s
File: <ipython-input-11-b157087bcb36>
Function: walk_home at line 25

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    25                                               def walk_home(self):
    26      2355       2343.0      1.0      6.6          while not self.is_at_home():
    27      2354      32910.0     14.0     93.3              self.step()
    28         1          2.0      2.0      0.0          return [...]
{'fraction_non_alphanumeric': 0.057027316992654946, 'fraction_numerical': 0.024676074936040272, 'mean_word_length': 3.974343185550082, 'pattern_counts': {'":': 0, '<': 34, '<?xml version=': 0, '>': 37, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '192116', 'license': 'CC-BY-4.0', 'n_tokens_mistral': 6420, 'n_tokens_neox': 5917, 'n_words': 3620, 'path': 'book/docs/lectures/optimization/software_optimization.ipynb', 'repo_name': 'finsberg/IN1910_H21', 'size': '24257'}