<commit_before>---
layout: single
comments: true
title:  "Tutorial: Performance Engineering for Machine Learning and Scientific Computing"
excerpt: "What you need to know to make your code run faster."
date:   2017-7-7 20:51:00
---
<!-- excerpt: "Your code can probably be way faster. Here's how." -->


<!-- ^ Note that above quotes the whole section of Knuth's paper, which is actually a really good + short commentary about when + what to optimize -->

If you do machine learning, you're probably familiar with the pain of waiting a long time for your code to run. This post is about making your code faster.

Specifically, I'm going to talk about performance engineering on CPUs with an emphasis on ideas most relevant for machine learning and data mining. GPUs are of course also important, but I won't address them since:

 1. If I did, this post would be too long
 2. Many of the principles are the same
 3. If you use TensorFlow, PyTorch, etc (which you hopefully do), most of the details relevant for performance tuning are beyond your control anyway

<!-- If you're not in the mood for reading, I would at least recommend scrolling to the bottom and checking out some of the links to. -->

<!-- This is just a short intro about some of the basic concepts with an emphasis on programming for CPUs. -->

For brevity and readability, this post contains many simplifications. For a more exhaustive treatment, see the slides for MIT's excellent [performance engineering class](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/).

## When and What to Optimize

<!-- No post about performance engineering would be complete without noting that, m -->
Most of the time, you shouldn't be optimizing for performance. And when you actually do have a performance problem, step 1 isn't making everything faster---it's figuring out what part of your code is slow. Only once you know what the bottlenecks are should you spend time optimizing. See this discussion of the classic maxim, "[Premature optimization is the root of all evil](https://softwareengineering.stackexchange.com/a/215671)."

If you're coding in C/C++, your IDE probably has good tools for performance monitoring. If you're using Python, [LineProfiler](https://github.com/rkern/line_profiler) can be invaluable. If you're using MATLAB, stop.<sup>[1](#matlab)</sup>

## Computer Architecture in Three Paragraphs

Performance engineering is all about using the hardware more effectively. Unfortunately, if you come from a non-EECS background, you might know much about how computers work. Here's a quick overview.<!-- <sup>[2](#overview)</sup> -->

Computers have a few basic operations they know how to perform---adding two numbers together, loading in data from memory, computing the logical OR of bits, etc. These operations are done in a section of the chip called the Arithmetic Logic Unit ([ALU](https://en.wikipedia.org/wiki/Arithmetic_logic_unit)). The basic loop the computer carries out is:

 1. Load data from memory into the ALU
 2. Do some operations to that data
 3. Store the results back in memory

For code to be faster, the computer has to spend less time doing one or more of these steps. <!--  Steps 1 and 3 use the memory hierarchy (described below), while step 2 uses the computer's Arithmetic Logic Unit ([ALU](https://en.wikipedia.org/wiki/Arithmetic_logic_unit)), which has the logic for carrying out the various operations. -->

## Memory Hierarchy

As you might have noticed, 2/3 of the above steps involve memory. Consequently, the processor does everything it can to make the memory fast. There are a lot of low-level details that go into making it fast in general, but the trick that matters most for programmers is *caching*.

Caching is when the processor stores data you're likely to access in a special segment of memory called the *cache*. This memory uses faster hardware, but has to be smaller because:

 1. It requires more chip area per bit stored.
 2. The bigger it is, the farther it is (on average) from the computation logic. This matters because electricity doesn't conduct as fast as we would like.

Modern processors don't just have one cache. They have several, each offering a different size/speed tradeoff. These tradeoffs, along with the relevant statistics for other storage media, are shown in Table 1. Registers, described in the first row, are the temporary storage that the ALU operates on directly.

<!-- Here are some (very approximate) statistics about the memory hierarchy on [Haswell](http://www.7-cpu.com/cpu/Haswell.html)). -->

| Level         | Size      | Latency       | Throughput    |
|:--------------|:----------|:--------------|:--------------|
| Register      | 100B      | None          | N/A                           |
| L1 Cache      | 64KB      | 4 cycles      | 2 64B loads/cycle             |
| L2 Cache      | 256KB     | 10 cycles     | 2 cycle read\*, 5 cycle write  |
| L3 Cache      | 10MB      | 40 cycles     | 5 cycle read\*, 10 cycle write |
| Main Memory   | 10GB      | 100 ns        | 10 GB/s                      |
| SSD           | 1TB       | 100 us        | 500MB/s                       |
| Disk          | 1TB       | 10 ms         | 100MB/s                       |

\* "Read" is defined as "load into L1 cache"

A few notes:

 - These numbers are approximate and vary from chip to chip
 - The above values have been rounded/approximated significantly for ease of recollection.
 - The latencies and throughputs are for random access; memory will be about 2x faster if read sequentially, and disk will be *much* faster.
 - The main memory, SSD, and disk are mostly independent of the processor, so the above are ballpark figures for comparison.
 - The L1 cache is often split so that half is reserved for storing code, and half for storing "data", defined as anything that isn't the code. This means that it effectively stores at most 32KB of parameters, variables, etc.

When the processor needs to load data, it first checks whether it's in the L1 cache; if not, then it checks the L2 cache; if it's not there, it checks the L3 cache, and so on. Finding the data in any cache is called a *cache hit*, and failing to find it is called a *cache miss*. Finding or failing to find it in a particular cache level N is called an *LN cache {hit,miss}* (e.g., "L1 cache hit", "L2 cache miss").

You can't control what data resides in which level of cache directly, but the processor uses a few simple heuristics that generally work well. They're also simple enough that we can structure our code to help them work even better.

The main heuristic is that, when you access data, it probably gets loaded into L1 or L2 cache, and when data gets kicked out of a given cache level ("evicted") to make room for other data, it probably gets moved to the next level down. This means that you can keep much of your data in a given cache level by only operating on an amount of data that fits in that level. E.g., you could operate on <32KB of data to keep most of it in L1 cache.

Other heuristics are discussed below.

### Cache Lines

Part of the challenge that caching hardware faces is keeping track of what data is in which cache. E.g., in a 256KB cache, there are 256,000 individual bytes it has to know are in there at a given time.

To make this easier, the CPU doesn't allow individual bytes to be cached---it instead operates on *cache lines*, which are blocks of 64 adjacent bytes. Entire cache lines are moved into and out of cache levels as necessary.

Grouping bytes is also a heuristic to improve performance, thanks to [locality of reference](https://en.wikipedia.org/wiki/Locality_of_reference)---i.e., if your program just accessed byte 974, it's likely to access byte 975 (or other bytes near there) in the immediate future. Consequently, by loading all the bytes around byte 974 when you ask for 974, the processor can probably avoid some cache misses.

### Prefetching

Another important heuristic the processor uses is *prefetching*, which can roughly be stated as:

> If the program just accessed cache lines (i, i+1, i+2) in that order, load (i+3) into cache immediately"

The details of how many successive accesses are required and how far ahead the prefetching happens will vary, but the point is that the processor will notice when you scan through data in memory order and will be able to avoid cache misses when this happens.

It can also notice when there are multiple sequences of accesses at once; e.g., if you have code that looks like:

```C
for (int i = 0; i < 100*1000*1000; i++) {
    c[i] = a[i] + b[i];
}<commit_msg>FIX broken code block formatting<commit_after>---
layout: single
comments: true
title:  "Tutorial: Performance Engineering for Machine Learning and Scientific Computing"
excerpt: "What you need to know to make your code run faster."
date:   2017-7-7 20:51:00
---
<!-- excerpt: "Your code can probably be way faster. Here's how." -->


<!-- ^ Note that above quotes the whole section of Knuth's paper, which is actually a really good + short commentary about when + what to optimize -->

If you do machine learning, you're probably familiar with the pain of waiting a long time for your code to run. This post is about making your code faster.

Specifically, I'm going to talk about performance engineering on CPUs with an emphasis on ideas most relevant for machine learning and data mining. GPUs are of course also important, but I won't address them since:

 1. If I did, this post would be too long
 2. Many of the principles are the same
 3. If you use TensorFlow, PyTorch, etc (which you hopefully do), most of the details relevant for performance tuning are beyond your control anyway

<!-- If you're not in the mood for reading, I would at least recommend scrolling to the bottom and checking out some of the links to. -->

<!-- This is just a short intro about some of the basic concepts with an emphasis on programming for CPUs. -->

For brevity and readability, this post contains many simplifications. For a more exhaustive treatment, see the slides for MIT's excellent [performance engineering class](https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-172-performance-engineering-of-software-systems-fall-2010/).

## When and What to Optimize

<!-- No post about performance engineering would be complete without noting that, m -->
Most of the time, you shouldn't be optimizing for performance. And when you actually do have a performance problem, step 1 isn't making everything faster---it's figuring out what part of your code is slow. Only once you know what the bottlenecks are should you spend time optimizing. See this discussion of the classic maxim, "[Premature optimization is the root of all evil](https://softwareengineering.stackexchange.com/a/215671)."

If you're coding in C/C++, your IDE probably has good tools for performance monitoring. If you're using Python, [LineProfiler](https://github.com/rkern/line_profiler) can be invaluable. If you're using MATLAB, stop.<sup>[1](#matlab)</sup>

## Computer Architecture in Three Paragraphs

Performance engineering is all about using the hardware more effectively. Unfortunately, if you come from a non-EECS background, you might know much about how computers work. Here's a quick overview.<!-- <sup>[2](#overview)</sup> -->

Computers have a few basic operations they know how to perform---adding two numbers together, loading in data from memory, computing the logical OR of bits, etc. These operations are done in a section of the chip called the Arithmetic Logic Unit ([ALU](https://en.wikipedia.org/wiki/Arithmetic_logic_unit)). The basic loop the computer carries out is:

 1. Load data from memory into the ALU
 2. Do some operations to that data
 3. Store the results back in memory

For code to be faster, the computer has to spend less time doing one or more of these steps. <!--  Steps 1 and 3 use the memory hierarchy (described below), while step 2 uses the computer's Arithmetic Logic Unit ([ALU](https://en.wikipedia.org/wiki/Arithmetic_logic_unit)), which has the logic for carrying out the various operations. -->

## Memory Hierarchy

As you might have noticed, 2/3 of the above steps involve memory. Consequently, the processor does everything it can to make the memory fast. There are a lot of low-level details that go into making it fast in general, but the trick that matters most for programmers is *caching*.

Caching is when the processor stores data you're likely to access in a special segment of memory called the *cache*. This memory uses faster hardware, but has to be smaller because:

 1. It requires more chip area per bit stored.
 2. The bigger it is, the farther it is (on average) from the computation logic. This matters because electricity doesn't conduct as fast as we would like.

Modern processors don't just have one cache. They have several, each offering a different size/speed tradeoff. These tradeoffs, along with the relevant statistics for other storage media, are shown in Table 1. Registers, described in the first row, are the temporary storage that the ALU operates on directly.

<!-- Here are some (very approximate) statistics about the memory hierarchy on [Haswell](http://www.7-cpu.com/cpu/Haswell.html)). -->

| Level         | Size      | Latency       | Throughput    |
|:--------------|:----------|:--------------|:--------------|
| Register      | 100B      | None          | N/A                           |
| L1 Cache      | 64KB      | 4 cycles      | 2 64B loads/cycle             |
| L2 Cache      | 256KB     | 10 cycles     | 2 cycle read\*, 5 cycle write  |
| L3 Cache      | 10MB      | 40 cycles     | 5 cycle read\*, 10 cycle write |
| Main Memory   | 10GB      | 100 ns        | 10 GB/s                      |
| SSD           | 1TB       | 100 us        | 500MB/s                       |
| Disk          | 1TB       | 10 ms         | 100MB/s                       |

\* "Read" is defined as "load into L1 cache"

A few notes:

 - These numbers are approximate and vary from chip to chip
 - The above values have been rounded/approximated significantly for ease of recollection.
 - The latencies and throughputs are for random access; memory will be about 2x faster if read sequentially, and disk will be *much* faster.
 - The main memory, SSD, and disk are mostly independent of the processor, so the above are ballpark figures for comparison.
 - The L1 cache is often split so that half is reserved for storing code, and half for storing "data", defined as anything that isn't the code. This means that it effectively stores at most 32KB of parameters, variables, etc.

When the processor needs to load data, it first checks whether it's in the L1 cache; if not, then it checks the L2 cache; if it's not there, it checks the L3 cache, and so on. Finding the data in any cache is called a *cache hit*, and failing to find it is called a *cache miss*. Finding or failing to find it in a particular cache level N is called an *LN cache {hit,miss}* (e.g., "L1 cache hit", "L2 cache miss").

You can't control what data resides in which level of cache directly, but the processor uses a few simple heuristics that generally work well. They're also simple enough that we can structure our code to help them work even better.

The main heuristic is that, when you access data, it probably gets loaded into L1 or L2 cache, and when data gets kicked out of a given cache level ("evicted") to make room for other data, it probably gets moved to the next level down. This means that you can keep much of your data in a given cache level by only operating on an amount of data that fits in that level. E.g., you could operate on <32KB of data to keep most of it in L1 cache.

Other heuristics are discussed below.

### Cache Lines

Part of the challenge that caching hardware faces is keeping track of what data is in which cache. E.g., in a 256KB cache, there are 256,000 individual bytes it has to know are in there at a given time.

To make this easier, the CPU doesn't allow individual bytes to be cached---it instead operates on *cache lines*, which are blocks of 64 adjacent bytes. Entire cache lines are moved into and out of cache levels as necessary.

Grouping bytes is also a heuristic to improve performance, thanks to [locality of reference](https://en.wikipedia.org/wiki/Locality_of_reference)---i.e., if your program just accessed byte 974, it's likely to access byte 975 (or other bytes near there) in the immediate future. Consequently, by loading all the bytes around byte 974 when you ask for 974, the processor can probably avoid some cache misses.

### Prefetching

Another important heuristic the processor uses is *prefetching*, which can roughly be stated as:

> If the program just accessed cache lines (i, i+1, i+2) in that order, load (i+3) into cache immediately"

The details of how many successive accesses are required and how far ahead the prefetching happens will vary, but the point is that the processor will notice when you scan through data in memory order and will be able to avoid cache misses when this happens.

It can also notice when there are multiple sequences of accesses at once; e.g., if you have code that looks like:

```c
for (int i = 0; i < 100*1000*1000; i++) {
    c[i] = a[i] + b[i];
}
{'fraction_non_alphanumeric': 0.0710134085285147, 'fraction_numerical': 0.016458537146803245, 'mean_word_length': 3.445638270657457, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 29, 'https://': 12, 'lorem ipsum': 0, 'www.': 2, '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}}
{'dir': 'git-commits-cleaned', 'id': '4224086', 'n_tokens_mistral': 4668, 'n_tokens_neox': 4211, 'n_words': 2624}