4 ms·

This is the kind of advice that points at something so obvious that you really never thought about it and feel silly once someone points it out :)

by arien 18y ago

cperciva 18y ago
Unfortunately, this advice falls into a very common category: Simple, obvious in hindsight, and completely wrong. Modern CPUs do not "execute a fixed number of instructions per second"; even leaving aside the fact that certain instructions are faster than others, factors such as the order in which you access memory locations and the predictability of branches can easily result in a tenfold difference in performance. In many cases, code can be made faster by executing more instructions; I recently dealt with some code where changing a (theoretically) O(N) algorithm to an O(N log N) algorithm and increasing the number of operations by a factor of 10 nevertheless resulted in the code running twice as fast. Now, this was an extreme case -- the code went from accessing completely random memory locations to accessing completely sequential memory locations -- but it demonstrates the importance of memory access patterns.
- Anon84 18y ago
  This is a great introduction to memory access and management by one of the Red Hat gurus http://people.redhat.com/drepper/cpumemory.pdf http://people.redhat.com/drepper/cpumemory.pdf
  - yan 18y ago
    The rest of the stuff on his site (http://people.redhat.com/drepper/ http://people.redhat.com/drepper/) is very good also
- axod 18y ago
  >> Modern CPUs do not "execute a fixed number of instructions per second" Very true for x86, but AFAIK things like ARM based chips are quite a bit closer to 'fixed number of instructions per second'. Still penalties for badly thought out memory access etc though.
- calambrac 18y ago
  The punchline, "To go fast, do less", is certainly not completely wrong. Sure, there may be exceptions here and there, but in general, this is good advice (and if you know enough to know when it's bad advice, you probably didn't need it anyways). If you're using a higher-level language like Python or Ruby, worrying about things like locality should be pretty low on your performance checklist.
  - cperciva 18y ago
    If you're using a higher-level language like Python or Ruby, worrying about things like locality should be pretty low on your performance checklist. If you're using Python or Ruby for CPU-intensive applications, you probably don't have a performance checklist.
    - calambrac 18y ago
      If you think that this advice applies only to CPU-intensive applications, you're missing the point. Unfocus your programmer brain and look past the fact that he said anything about some processor being able to perform a fixed number of instructions per second, and absorb the larger message: to go fast, do less. This could include IO, this could include retabulating some statistic just when it's needed instead of on every insertion, this could include handling special cases ahead outside of a loop body, etc. CPU-level optimization should usually be one of the very last things you care about (and yes, this depends, and again, if you already know the exceptions, you don't need this advice). And Python and Ruby both have excellent C bindings, you can rewrite CPU-intensive portions of your application pretty much anytime you need to.
      - cperciva 18y ago
        And Python and Ruby both have excellent C bindings, you can rewrite CPU-intensive portions of your application pretty much anytime you need to. Of course. But at that point you're writing your CPU-intensive code in C, not in Python or Ruby. Saying "Python and Ruby are fast because they can call C code" makes no more sense than saying "Humans are really good at arithmetic because they can use calculators".
- lsb 18y ago
  The creator of bzip lamented this very fact, at a conference about the "b" transform that powers it, the Burrows-Wheeler Blocksort. With gzip, the output comes from looking up strings in a hash table, and just streaming it out, but bzip sorts (and unsorts) blockwise, quasi-randomly accessing locations for 1MB of memory, and as we get more and more layers of caching, it'll just get slower and slower.
  - Retric 18y ago
    Could you explain that a little more? If it only needs 1MB of memory I would assume it fit's on most modern CPU's L2 cache. At which point I don't see why it would get slower if you added L3 cache etc.
    - lsb 18y ago
      This was back in the summer of 2004; I don't remember historical cache sizes, but I do remember Wheeler saying something about cache misses (because the BWT sorts things by blockwise context -- all the "_he quick brown fox" strings get arranged by position -- it tends to jump around a bit more), but he never addressed multicore capacity, in which bzip2 shines, because each block can go onto a different core, and you're just limited by memory bandwidth. Most chips only had 1 core in those days. IIRC, the blocksorting algorithm requires more than 1MB; the figure 12n for the suffix sort sticks in my head, but I don't recall the specifics.
      - cperciva 18y ago
        There are much better suffix sorting algorithms available now than when bzip2 was first written. I'm sure bzip2 could be sped up considerably by using one of them if anyone wanted to bother.
    - kragen 18y ago
      Adding L3 cache to a machine won't make it (noticeably) slower, but if the memory behavior is random and bigger than the L3 (which it isn't in bzip2's case but anyway) it won't make it faster either. But the point at which you want to add L3 is when main memory is very slow relative to L2, and that's the case when random memory access loses. But hey, you can merge-sort a million records in only 20 sequential passes! Not sure how to apply that to BWT though.
- anamax 18y ago
  To first order, the number of instructions executed is not at the top of the list of things that make programs slow. IO is. And, if you're not IO bound, you're probably memory bound. Yes, caches help a lot, but a memory cache miss is 1-400 cycles and IO is far more expensive. In other words, cosine is faster than a cache miss.
- Hexstream 18y ago
  Well, if your code now runs much faster because it accesses contiguous memory locations instead of random ones, it's because the computer does less because it avoids expensive cache misses. Similarly with the branch prediction problem. So I don't see much contradiction of the article.
- jcromartie 18y ago
  In your example you've written more code to make the machine do less, which fits the spirit of the advice just fine. Memory-access optimizations are just another way of making the hardware do less in some cases.
  - neilc 18y ago
    you've written more code to make the machine do less Not really: if you're improving the program's memory access behavior, the machine really is "doing more": by removing a memory stall, you're replacing a situation in which the processor was idling with a situation in which the processor is doing useful work. Prefetching and speculative execution are other examples of the "do more work, spend less time idling" theme.
- dfj225 18y ago
  Not only that, but on modern processors, the order of operations tends to be important. For instance, the FFT algorithm executes a fixed number of floating point calculations, but can perform very differently based on the ordering of these calculations with respect to memory access. For projects that take advantage of this, see: http://spiral.net http://spiral.net http://www.fftw.org/ http://www.fftw.org/
- lutorm 18y ago
  changing a (theoretically) O(N) algorithm to an O(N log N) algorithm and increasing the number of operations by a factor of 10 nevertheless resulted in the code running twice as fast Your N is 10^10? That's a big problem.
  - cperciva 18y ago
    The implicit constants in the O() expressions are different.

This is the kind of advice that points at something so obvious that you really never thought about it and feel silly once someone points it out :)

by arien 18y ago

This is the kind of advice that points at something so obvious that you really never thought about it and feel silly once someone points it out :)

cperciva 18y ago

Unfortunately, this advice falls into a very common category: Simple, obvious in hindsight, and completely wrong. Modern CPUs do not "execute a fixed number of instructions per second"; even leaving aside the fact that certain instructions are faster than others, factors such as the order in which you access memory locations and the predictability of branches can easily result in a tenfold difference in performance. In many cases, code can be made faster by executing more instructions; I recently dealt with some code where changing a (theoretically) O(N) algorithm to an O(N log N) algorithm and increasing the number of operations by a factor of 10 nevertheless resulted in the code running twice as fast. Now, this was an extreme case -- the code went from accessing completely random memory locations to accessing completely sequential memory locations -- but it demonstrates the importance of memory access patterns.

Anon84 18y ago
This is a great introduction to memory access and management by one of the Red Hat gurus http://people.redhat.com/drepper/cpumemory.pdf http://people.redhat.com/drepper/cpumemory.pdf
- yan 18y ago
  The rest of the stuff on his site (http://people.redhat.com/drepper/ http://people.redhat.com/drepper/) is very good also
axod 18y ago
>> Modern CPUs do not "execute a fixed number of instructions per second" Very true for x86, but AFAIK things like ARM based chips are quite a bit closer to 'fixed number of instructions per second'. Still penalties for badly thought out memory access etc though.
calambrac 18y ago
The punchline, "To go fast, do less", is certainly not completely wrong. Sure, there may be exceptions here and there, but in general, this is good advice (and if you know enough to know when it's bad advice, you probably didn't need it anyways). If you're using a higher-level language like Python or Ruby, worrying about things like locality should be pretty low on your performance checklist.
- cperciva 18y ago
  If you're using a higher-level language like Python or Ruby, worrying about things like locality should be pretty low on your performance checklist. If you're using Python or Ruby for CPU-intensive applications, you probably don't have a performance checklist.
  - calambrac 18y ago
    If you think that this advice applies only to CPU-intensive applications, you're missing the point. Unfocus your programmer brain and look past the fact that he said anything about some processor being able to perform a fixed number of instructions per second, and absorb the larger message: to go fast, do less. This could include IO, this could include retabulating some statistic just when it's needed instead of on every insertion, this could include handling special cases ahead outside of a loop body, etc. CPU-level optimization should usually be one of the very last things you care about (and yes, this depends, and again, if you already know the exceptions, you don't need this advice). And Python and Ruby both have excellent C bindings, you can rewrite CPU-intensive portions of your application pretty much anytime you need to.
    - cperciva 18y ago
      And Python and Ruby both have excellent C bindings, you can rewrite CPU-intensive portions of your application pretty much anytime you need to. Of course. But at that point you're writing your CPU-intensive code in C, not in Python or Ruby. Saying "Python and Ruby are fast because they can call C code" makes no more sense than saying "Humans are really good at arithmetic because they can use calculators".
lsb 18y ago
The creator of bzip lamented this very fact, at a conference about the "b" transform that powers it, the Burrows-Wheeler Blocksort. With gzip, the output comes from looking up strings in a hash table, and just streaming it out, but bzip sorts (and unsorts) blockwise, quasi-randomly accessing locations for 1MB of memory, and as we get more and more layers of caching, it'll just get slower and slower.
- Retric 18y ago
  Could you explain that a little more? If it only needs 1MB of memory I would assume it fit's on most modern CPU's L2 cache. At which point I don't see why it would get slower if you added L3 cache etc.
  - lsb 18y ago
    This was back in the summer of 2004; I don't remember historical cache sizes, but I do remember Wheeler saying something about cache misses (because the BWT sorts things by blockwise context -- all the "_he quick brown fox" strings get arranged by position -- it tends to jump around a bit more), but he never addressed multicore capacity, in which bzip2 shines, because each block can go onto a different core, and you're just limited by memory bandwidth. Most chips only had 1 core in those days. IIRC, the blocksorting algorithm requires more than 1MB; the figure 12n for the suffix sort sticks in my head, but I don't recall the specifics.
    - cperciva 18y ago
      There are much better suffix sorting algorithms available now than when bzip2 was first written. I'm sure bzip2 could be sped up considerably by using one of them if anyone wanted to bother.
  - kragen 18y ago
    Adding L3 cache to a machine won't make it (noticeably) slower, but if the memory behavior is random and bigger than the L3 (which it isn't in bzip2's case but anyway) it won't make it faster either. But the point at which you want to add L3 is when main memory is very slow relative to L2, and that's the case when random memory access loses. But hey, you can merge-sort a million records in only 20 sequential passes! Not sure how to apply that to BWT though.
anamax 18y ago
To first order, the number of instructions executed is not at the top of the list of things that make programs slow. IO is. And, if you're not IO bound, you're probably memory bound. Yes, caches help a lot, but a memory cache miss is 1-400 cycles and IO is far more expensive. In other words, cosine is faster than a cache miss.
Hexstream 18y ago
Well, if your code now runs much faster because it accesses contiguous memory locations instead of random ones, it's because the computer does less because it avoids expensive cache misses. Similarly with the branch prediction problem. So I don't see much contradiction of the article.
jcromartie 18y ago
In your example you've written more code to make the machine do less, which fits the spirit of the advice just fine. Memory-access optimizations are just another way of making the hardware do less in some cases.
- neilc 18y ago
  you've written more code to make the machine do less Not really: if you're improving the program's memory access behavior, the machine really is "doing more": by removing a memory stall, you're replacing a situation in which the processor was idling with a situation in which the processor is doing useful work. Prefetching and speculative execution are other examples of the "do more work, spend less time idling" theme.
dfj225 18y ago
Not only that, but on modern processors, the order of operations tends to be important. For instance, the FFT algorithm executes a fixed number of floating point calculations, but can perform very differently based on the ordering of these calculations with respect to memory access. For projects that take advantage of this, see: http://spiral.net http://spiral.net http://www.fftw.org/ http://www.fftw.org/
lutorm 18y ago
changing a (theoretically) O(N) algorithm to an O(N log N) algorithm and increasing the number of operations by a factor of 10 nevertheless resulted in the code running twice as fast Your N is 10^10? That's a big problem.
- cperciva 18y ago
  The implicit constants in the O() expressions are different.