In the previous blog post in this series (see also here) we described how to profile the code in Python. But knowing which lines of code are slow is just the start – the next step is to make them faster. Code optimization is a grand topic in software development and much ink has been spent on describing various methods. Hence, I picked the brain of a senior pythonista: my Southampton colleague and the local go-to person for all Python enquiries: Max Albert . We have divided the optimisation techniques into two sections: (predominantly Max’s) thoughts on deep optimisation and some quick fixes we both came across during our time with Python. For those with formal computer science education many of the points may sound trivial but if, like many of us, you’ve learned to code out of necessity and therefore in a rather haphazard way, this post may be of interest.
Deep Code Optimisation
1. ‘Premature optimisation is the root of all evil’ said Donald Knuth in 1974 and the statement still holds true 40 years later. The correct order of actions in any code development is: first make the code run, then make it do what you want it to do, then check that’s what it’s actually doing under all conditions (test it), only then profile it and start optimising. Otherwise you’re running a risk of making the code unnecessarily complicated and wasting time on optimising bits that you blind guessed are slow but which actually take insignificant amounts of time.
2. There are no points for spending hours on developing DIY solutions. In fact it has been suggested that coding should be renamed ‘googling stack overflow’ (as a joke, but it wouldn’t be funny if it wasn’t so true). The chances are that whatever you want to do, someone has done it before, and has done it better. Google it. The chances are that one of the stack overflow gurus had nothing better to do in their spare time and developed an algorithm that will fit your needs just fine and run at turbospeed.
3. Think through what you’re doing. Use a correct algorithm and correct data structures. Don’t hang on that one algorithm that you developed some time ago for one task and that you have been tweaking ever since to do a number of other tasks. Similarly, even if lists are your favourite, check if a dictionary won’t be more efficient.
4. Think with the program – that is step through the code in the same order as it is going to be executed. If you don’t have a beautiful mind and cannot easily follow computer logic, use a debugger. It will take you through the code step by step. It will show you what repeats and how many times as well as when and where things are stored. Sometimes it’s worth storing things in the memory, sometimes it makes sense to recompute them – you can test what’s quicker by profiling the code with different implementations.
Quick fixes
There are a few things that one can do straight away and, apparently, they should increase performance instantaneously. I say ‘apparently’ because with each new version of Python the uberpythonistas make things better and more efficient so it is likely that some of these tricks are not as effective as they used to be in the version of Python (and its libraries) you are using at the moment. Either way, it’s always worth trying out alternatives and profiling them to find the fastest option.
1. Remove any possible calculations from your ‘if’ and ‘for’ loops. If there is anything you can pre-calculate and attach to a variable (as in a = b – 45 / c and then use only ‘a’ in the loop), DO IT! It may add extra lines of code but remember that whatever is inside the loop will be repeated with each iteration (and if you have 10 000 agents in 100 000 steps then that’s a hell of a lot of looping).
2. Use as many built-in functions as possible. They are actually written in C (the fast language) so anything you write in Python is likely to be slower. A good example is Numpy – the ‘numerical python’ library which has arrays and a wide range of operations you can run on them, instead of building list. See this little essay about why this is the case. A more advanced version of this approach is to try Cython – Python extension, which with a few relatively simple changes, could boost your code to near-C speed.
3. Try using list comprehension instead of manually looping through lists. Sounding more scary than it actually is – list comprehension is an easy, compact and sometimes faster than looping way of doing calculations on lists. Check out the documentation here – the examples will teach you all you need to know in less than an hour. Even better, use the map function, as it’s supposed to be the speediest one – check out the tutorial here.
4. Since we’re on lists: you probably know about the deep and shallow copying. If you don’t, the gist is that when you assign a name to data, it is a reference to the data and not a copy. Try the following code:
a = [1, 2, 3]
b = a
print a, b
a.append(4)
print a, b
Whoa, isn’t it? Check out this fantastic talk by Ned Batchelder at PyCon2015 about why it is this way. To avoid the potentially serious bugs you can deep copy:
list_2 = list_1[:]
Or:
list_2 = list(list_1)
There seems to be a bit of disagreement as for which method is faster (compare here & here) and I personally got mixed results depending on the length of the list and its components (floats, integers, etc.) so test the alternative implementations code as the gain on this little change may be considerable.
In general, deep copying is costly so there is a balance to strike here – go for safe but computationally expensive or spend some time ensuring that shallow copying does not produce any unintended behaviour.
5. Division may potentially be expensive, but can be easily swapped with multiplication. For example, if you’re dividing by 2 – try multiplying by 0.5 instead. If you need to divide by funny numbers (as in ‘the odd ones’) try this trick: a = b * (1.0 / 7.0), it’s supposed to be quicker than a straightforward division. Again, try and time different implementations – depending on the version of Python, the number of operations and the type of data (integers, floats) the results may differ.
6. Trying is cheaper, Ifing is expensive. From this fantastic guide to optimisation in python comes a simple rule that should speed up the defensive parts of the code.
If your code looks like this:
if somethingcrazy_happened:
uhOhBetterDoSomething()
else:
doWhatWeNormallyDo()
The following version is speedier:
try:
doWhatWeNormallyDo()
except SomethingCrazy:
uhOhBetterDoSomething()
To push your optimisation effort even further, there are quite a few optimisation tutorials online, with many more techniques. I particularly recommend these three:
- Python wiki on optimisation – this is quite ‘dry’ so only do it if you’re happy with loads of python jargon.
- Dive into Python – nice tutorial with an example code, shows the scary truth that more often than not it’s difficult to predict which implementation will actually be quicker.
- A comprehensive Stack Overflow answer the the ultimate question ‘how do I make my code go faster?’
Top image: Alan Cleaver on Flickr flickr.com/photos/alancleaver/2661425133/in/album-72157606825074174/
simulatingcomplexity 