Speed

Why are some programs fast and others slow? In this tutorial, we’ll try and discuss two things:

  • Develop general understanding of why code is fast and some is slow, and
  • Develop practical skills for figuring out why your code is slow and how to fix it

General Principles of Speed

There are two primary factors that determine the speed of a program:

  • The number of actions the computer has to take (i.e. the number of commands it has to execute)
  • The amount it has to access and move data around.

Fast languages and slow languages

One of the easiest rules of thumb is that the easier a computer language is to use, the slower the language will be. That’s because languages that are easier to use are easier because behind the scenes, these languages are doing a lot of thinking for us, and that thinking takes time. That’s why languages like C and C++ which are hard to use are very fast, and languages like R and Python which are easy to use tend to be slow.

But while this is a good general rule, there are ways to make code in languages like R and Python fast – it just requires a little extra skill.

De-referencing and Data Structures

[need more here!]

In short: moving data around your computer is basically the most time-consuming thing your computer does.

Practical Skills

Profiling Code

If you take nothing else away from this page, please read and remember this section!

There’s no reason to tune a line of code that is only responsible for 1/100 of your running time, so before you invest in speeding up your code, figure out what’s slowing it down – a process known as “profiling” your code. Thankfully, because this is so important, there are lots of tools (called profilers) for measuring exactly how long your computer is spending doing each step in a block of code. * Profiling in R: the two packages I’ve seen used most are Rprof and lineprof. * Profiling in Python: if you use Jupyter Notebooks or Jupyter Labs, you can use the prun tool. If for some reason you’re not using Jupyter, here’s a guide to a few other tools.

Making Code Faster

AFTER you’ve identified what parts of your code are running really slow by profiling them (as discussed above), the next question is how to make them run faster. The following fixes are provided in the order in which I would suggest pursuing them – the first fixes have high returns and are relatively easy, the later ones are harder to implement and should only be pursued if you’ve tried the preceding options!

  1. Check your memory use When your computer is manipulating data (defining variables, running regressions, etc), what its actually doing is grabbing a little bit of data from storage, moving it to the processor, doing math with it, and then putting it back in storage.

To simplify somewhat, we can think of your computer as having two forms of storage – RAM (sometimes called main memory), and your harddrive. But these two forms of memory are very, very different. Your computer can grab data from RAM 100,000 times faster it can grab data on the harddrive. Because of this, your computer is much happier (and performs faster) when it’s able to keep all the data you’re working with in RAM. Indeed, if you’re moving data back and forth to your harddrive, it’s almost certainly the biggest bottleneck – doing actual computations is almost instantaneous compared to moving data back and forth to your harddrive on modern computers.

Important: Just because your dataset is small enough it seems like it should fit into RAM doesn’t mean this isn’t relevant for you! Programs often make copies of your data when they manipulate it, so even if your dataset is 2gb and your have 8gb of RAM, the program you’re using can very easy end up using all 8gb of RAM!

  1. Use other people’s (compiled) functions

As a general rule, code you write in R or Python is slow. But don’t worry, it’s not your fault; R and Python are fundamentally [[Programming Languages | slow languages]], so ‘’anything’’ written in R or Python is slow.

But interestingly, commands that other people have written that are available in R or Python are actually usually written in faster (“compiled”) languages, like C++. As a result, whenever you have the choice between writing a function yourself or using a function in an established library, you’re almost always better off using the command someone else wrote.

Now, using other people’s functions is not fool-proof – some people write their libraries in R or Python (not a compiled language like C++), so they may run as slowly as your own commands. So if you can, check the documentation for whatever library you want to use to see whether it was written in C / C++ or not!

  1. Vectorization

In R and Python, if you want to apply a function to each item in a matrix or vector, you would just create a loop that extracts each element of the vector, modifies it, and then moves to the next item. This will work in R or Python, but it is very slow. What you want to do instead is “vectorize” your function, which means you use a specific command to tell R or Python that you’re trying to apply your function to each item in the vector. When R/Python knows this is what you want to do, it has ways of making that function execute much more quickly behind the scenes.

Both languages have a number of tools for this:

  • in R, these come in a set of tools with names related to apply() (for example, apply(), lapply(), sapply()), there’s a library called dplyr. But what matters most is not which one, but rather that you use one of them and never run loops over your vectors or matrices!
  • In Python, the relevant tools are the “apply()”, “agg()”, “map()”, and “transform()” functions.
  1. Parallelization

Parallelization (which has it’s own page [[Parallelization]] here) is often the first thing social scientists turn to to speed up code. Whether this is the right decision depends a lot on your situation, but a few facts:

  • Parallelization is “sub-linear”, meaning if you parallelize across two cores, you can except ~1.8x speedup at best. (More generally, for N cores, expect ~0.8*Nx speedups).
  • Improving how your code is written can often yield much higher returns than parallelization, on the order of 5x, 10x, or 100x speed improvements.
  • Using code that was written in C++ by someone else can yield 10x or 100x returns.

So, parallelization certainly isn’t the best way to speed up your code. But if you read this and find yourself thinking “um, I still don’t really what makes code fast versus slow” or “I’ve already tried all that and it’s still too slow!”, it’s a good option.

  1. Compile your own code

So you’re sure you’re only using RAM, you’ve vectorized your functions, and you can’t find a library with the function you need to execute, and when you write it yourself it’s still too slow, even if you parallelize it? The last option is to compile your own code. This is a little complicated for this page, so if you get here, link here

Learn about Data Structures: If you REALLY want to speed up your code

If this were written for computer scientists, this section would be first. Different data structures – lists, matrices, dataframes, dictionaries, etc. – are all very different in terms of how they work at the lowest levels of your computer. As a result, they have ’‘’very’’’ different performance characteristics, and nothing will have more of an effect on the speed of your code than your choice of data structures.

With that said, because most social scientists haven’t been taught much about the inner workings of computers, it is understandably hard for them to know which structure is best in each situation. If you ’‘’really’’’ want to get good performance though, it’s something to look into – [[Data Structures | check out a starter page here]].

= Guides Written By Wiser Minds than Me = [http://adv-r.had.co.nz/Profiling.html Speeding up R Code]

[https://wiki.python.org/moin/PythonSpeed/PerformanceTips Speeding up Python Code (note: written for Python, not Pandas. Pandas has some extra tricks)]

[http://pandas.pydata.org/pandas-docs/stable/enhancingperf.html Improving Pandas (Python) Speed]