6 ms·

How to Write Fast Code

143 points by techdog 18y ago

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.
lallysingh 18y ago
I'm glad to see people talking about one of the four stages of optimization: 1. Do we have to optimize this? Time is never free, and opportunity cost in terms of engineering effort is usually very significant. 2. Can we do less work? (this article) 3. What's the bottleneck? CPU, FP, memory bandwidth, lock contention? 4. How do we squeeze out better performance? Assembly, loop unrolling, etc. I usually cringe when I hear about people talking about #4, as very few of them have asked #1, #2, or #3 yet. And usually, you just hear people talking about doing what the compiler's already doing (writing it in assembly? /The compiler already does that/), usually doing a pretty reasonable job at high optimization levels. They just exchange maintainability for the warm fuzzy feeling that they've been as macho as needed.
- stcredzero 18y ago
  Profile, Profile, Profile! Use the 80-20 rule. 80% of your code's time is spent in 20% of the code. Optimizing without good profiling is like painting a portrait blindfolded. Pre-optimizing by coding your system to be "fast" before you get to profile it is like starting to paint a portrait before your model is even sitting. When Kent Beck came in to optimize the Chrysler C3 payroll system, he discovered that one of the biggest time-sinks in the system was string concatenation! It's also useless to optimize before you have a system that runs correctly. Kent also asked how he could validate the C3 system so he could optimize it. He was told it wasn't even producing correct results yet. He replied: "In that case I can make it run really fast!"
  - signa11 18y ago
    one of my very favorite quotes of all times: What are the facts? Again and again and again---what are the facts? Shun wishful thinking, ignore divine revelation, forget what "the stars fortell," avoid opinion, care not what the neighbors think, never mind the unguessable "verdict of history"---what are the facts, and to how many decimal places? You pilot always into an unknown future; facts are your single clue. Get the facts! - lazarus long
    - 18y ago
iamwil 18y ago
Isn't the old adage: "the fastest code is the one you never run?"
- psadauskas 18y ago
  Or the one ezra touts: "No code is faster than no code."
bsaunder 18y ago
I'm personally fascinated by the notion that efficiency and transformation seem to be intertwined. Hard problems can sometimes seem simple with a slight transformation in either the problem description or the data. Even the article is suggesting that to write fast code, transform your perspective of the problem. Do less. There seems to be something fundamental here.
- signa11 18y ago
  and hence Xerox-PARC slogan "point of view is worth 80 iq points"
deleted 18y ago
[deleted]
yawniek 18y ago
"no code is faster than no code" (comes from yehuda katz afair)
10ren 18y ago
I get the feeling that "John" is a literary device for the alter-ego of the author.
zandorg 18y ago
Or split your workload up so it can be run on 200 cores in an instant. Not to advertise, but I'm not affiliated with Nvidia - http://www.nvidia.co.uk/page/tesla_deskside.html http://www.nvidia.co.uk/page/tesla_deskside.html
dualogy 18y ago
Off-topic maybe, but: "How to Write Code Fast", now can someone point me to literature for that? Highly appreciated!
- godDLL 18y ago
  Try the UNSW YouTube lectures with Richard Buckland, one of them mentions "problem solving" through abstraction, targeting and planning; and may well be what you're looking for. http://www.youtube.com/watch?v=q1I7WKncE64 http://www.youtube.com/watch?v=q1I7WKncE64
froo 18y ago
It's an unbelievably simple statement that is applicable to many different situations, not just computer related stuff. For example, right now I'm detailing some design principles for a project I'm working on. I realise there is a limited amount of time to be able to complete the project effectively and to make it look decent, so in the process I've come to make some hard choices. I've found the trying to be creative with less is working out well so far and in the end it should pay off.
ezmobius 18y ago
no code is faster then no code.

143 points by techdog 18y ago

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.

lallysingh 18y ago

I'm glad to see people talking about one of the four stages of optimization: 1. Do we have to optimize this? Time is never free, and opportunity cost in terms of engineering effort is usually very significant. 2. Can we do less work? (this article) 3. What's the bottleneck? CPU, FP, memory bandwidth, lock contention? 4. How do we squeeze out better performance? Assembly, loop unrolling, etc. I usually cringe when I hear about people talking about #4, as very few of them have asked #1, #2, or #3 yet. And usually, you just hear people talking about doing what the compiler's already doing (writing it in assembly? /The compiler already does that/), usually doing a pretty reasonable job at high optimization levels. They just exchange maintainability for the warm fuzzy feeling that they've been as macho as needed.

stcredzero 18y ago
Profile, Profile, Profile! Use the 80-20 rule. 80% of your code's time is spent in 20% of the code. Optimizing without good profiling is like painting a portrait blindfolded. Pre-optimizing by coding your system to be "fast" before you get to profile it is like starting to paint a portrait before your model is even sitting. When Kent Beck came in to optimize the Chrysler C3 payroll system, he discovered that one of the biggest time-sinks in the system was string concatenation! It's also useless to optimize before you have a system that runs correctly. Kent also asked how he could validate the C3 system so he could optimize it. He was told it wasn't even producing correct results yet. He replied: "In that case I can make it run really fast!"
- signa11 18y ago
  one of my very favorite quotes of all times: What are the facts? Again and again and again---what are the facts? Shun wishful thinking, ignore divine revelation, forget what "the stars fortell," avoid opinion, care not what the neighbors think, never mind the unguessable "verdict of history"---what are the facts, and to how many decimal places? You pilot always into an unknown future; facts are your single clue. Get the facts! - lazarus long
  - 18y ago

iamwil 18y ago

Isn't the old adage: "the fastest code is the one you never run?"

psadauskas 18y ago
Or the one ezra touts: "No code is faster than no code."

bsaunder 18y ago

I'm personally fascinated by the notion that efficiency and transformation seem to be intertwined. Hard problems can sometimes seem simple with a slight transformation in either the problem description or the data. Even the article is suggesting that to write fast code, transform your perspective of the problem. Do less. There seems to be something fundamental here.

signa11 18y ago
and hence Xerox-PARC slogan "point of view is worth 80 iq points"

deleted 18y ago

[deleted]

yawniek 18y ago

"no code is faster than no code" (comes from yehuda katz afair)

10ren 18y ago

I get the feeling that "John" is a literary device for the alter-ego of the author.

zandorg 18y ago

Or split your workload up so it can be run on 200 cores in an instant. Not to advertise, but I'm not affiliated with Nvidia - http://www.nvidia.co.uk/page/tesla_deskside.html http://www.nvidia.co.uk/page/tesla_deskside.html

dualogy 18y ago

Off-topic maybe, but: "How to Write Code Fast", now can someone point me to literature for that? Highly appreciated!

godDLL 18y ago
Try the UNSW YouTube lectures with Richard Buckland, one of them mentions "problem solving" through abstraction, targeting and planning; and may well be what you're looking for. http://www.youtube.com/watch?v=q1I7WKncE64 http://www.youtube.com/watch?v=q1I7WKncE64

froo 18y ago

It's an unbelievably simple statement that is applicable to many different situations, not just computer related stuff. For example, right now I'm detailing some design principles for a project I'm working on. I realise there is a limited amount of time to be able to complete the project effectively and to make it look decent, so in the process I've come to make some hard choices. I've found the trying to be creative with less is working out well so far and in the end it should pay off.

ezmobius 18y ago

no code is faster then no code.