How to Write Fast Code | Hacker News Reader

How to Write Fast Code

asserttrue.blogspot.com

143 pointstechdog42 comments

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.

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

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

Nice. :) Clearly, I am a fan!

There is also another step - define what you want. Targets are important.

Preferably, define targets in real (really real) world terms. This is difficult, but "a user should reasonably be able to complete this macro-process in 5 minutes" is the kind of target.

I've seen so many specs that demand "millisecond response time" for the application. Or something ludicrous. (Requirements for business continuity and downtime/etc are usually similarly crazy/unqualified).

When one consultancy I know got a similar requirement forced down their throat contractually -- they simply changed the application so that a process that was a few pages, was now dozens. Much shorter delays! The fact is that the user wouldn't even blink at a several-second delay when submitting (it was a big operation, so you'd expect a delay). The whole process was longer and more cumbersome - they'd optimised the wrong thing entirely.

It's an extreme example I know -- But the upshot is that the target was wrong -- It's not just the people writing the specs. In a lot of places, it's still rare for developers to sit down with actual users. This always seemed crazy to me (half the time it was because companies are worried that developers will go "hey yeah sure, I can implement that in an hour!" -- which does admittedly sometimes happen).

So you're absolutely right! :) Profile, Profile, Profile -- but don't forget to profile your users (imho do this first).

I think all of your points boil down to the same mantra as the article:

1. is the human variant. 3. finding which thing to "do less" of (benchmarking/profiling seem to be the "do less" ways of doing this task). 4 from the low level CPU perspective.

As I see it, all "four stages of optimization" are the application of the same rule just from different perspectives.

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.

and hence Xerox-PARC slogan "point of view is worth 80 iq points"

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

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.

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

Or the one ezra touts: "No code is faster than no code."

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.

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

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

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

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

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

no code is faster then no code.

Reply on news.ycombinator.com