Hacker News Reader

Comment by arien | Hacker News Reader

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 :)

View on HN

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.

This is a great introduction to memory access and management by one of the Red Hat gurus http://people.redhat.com/drepper/cpumemory.pdf

The rest of the stuff on his site (http://people.redhat.com/drepper/) is very good also

>> 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.

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.

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.

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.

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".

I didn't say "Python and Ruby are fast because they can call C code". I responded to your claim that people using Python or Ruby for their applications don't have performance checklists, which is bullshit - part of that checklist (towards the bottom, hopefully) is refactor important bits to C.

That's ridiculous.

We'll see about that. As of yesterday I have started writing performance-critical software in Python. It's a large application, and many components might go slow in Python. However, my suspicion is that one part of the code will be particularly slow. I will then optimize that part by writing it as a C module.

By using Python I can write the application quicker, test for correctness, and optimize the most important pieces without wasting time writing the entire thing in C.

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.

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.

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.

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.

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.

Assuming the issue is memory latency not bandwidth adding cache to a system with random memory access can sill increase performance. Granted if your accessing 10 times as much memory as will fit into you're cache you would be limited to a 10% increase in speed which might be eaten up by overhead.

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.

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.

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.

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.

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://www.fftw.org/

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.

The implicit constants in the O() expressions are different.

Reply on news.ycombinator.com