Trying to outsmart a compiler defeats much of the purpose of using one.

Kernighan and Plauger The Elements of Programming Style.

I have seen many people try to outsmart compilers (sometimes that person was me) and with rare exceptions, the compiler has won every time.

I have seen a programmer who had just read Mike Abrash’s “Zen of Assembly Language” code up their own memcpy routine using all the the clever optimizations in the book, only to discover that the compiler writers know all of these optimizations too. I have seen people try and get clever with switch statements and implement them as jump tables. Steve Johnson’s portable C compiler optimized switch statements automatically in the 80s. I have seen a programmer who was an expert on the 68000 instruction set (and he genuinely was an expert) come unstuck because we were now compiling for the 68040 and the instruction timings had changed.

In the late 90s there was a discussion on one of the games programming newsgroups about using left shift instead of multiply. Rather than this:

j = i * 2;

you’d write:

j = i << 1;

and get a wonderful speed increase. I decided to run some tests on this. I coded up a little test program with two functions:

int multiplyByTwo( int i )
{
    return i * 2;
}

int shiftLeftByOne( int i )
{
    return i << 1;
}

I ran the program through Watcom with our normal release build settings, then looked at the assembler output. Watcom had replaced i * 2 with i << 1, it had realized that the two functions were the same so it had merged them, then it inlined the function. Furthermore, since I was using constants to keep the program simple it calculated the results at compile time. I think that the only thing left by the end was a call to printf with a couple of constants. Compilers are good at this stuff.

There's another problem - if we are going to try doing these replacements ourselves we have to make sure that we get them right. Replacing multiply with a left shift is easy and safe to do, however, dividing by two is not necessarily the same as shifting right by one - under some circumstances you can safely use the shift, but under others you can't. I have always found that a compiler is far more likely to get these things right than I am.

The moral is for us to write code that expresses exactly what we want (if we want a multiplication then we should write a multiplication) and let the compiler do whatever it feels is appropriate. Compilers are really good at peephole optimizations. As programmers we are much better off using our time to replace that O(n^2) algorithm with an O(n log n) algorithm.

There are two hard things in computer science: cache invalidation, naming things, and off-by-one errors.

Phil Karlton

I have seen a number of variations on this quote, and it looks as though the original quote only included two of the three hard things. Martin Fowler quotes Phil Karlton here and there is more discussion of the quote here.

I don’t know whether the original quote concerned hardware caching or software caching. Since I’m not a hardware engineer, I’ll talk about software caching. When implementing software caches I have found it useful to apply the Single Responsibility Principle and divide things up along these lines:

• The thing that calculates (fetches, obtains, looks up etc.) the value we want.
• The thing that actually stores the cached value.
• The thing that decides whether the value should be cached or not.
• The thing that decides whether the cache (or a given cache entry) should be invalidated.

I wish I were better at naming things. Naming is important, good naming can show that similar things are connected and dissimilar things are separate. Good names can show patterns in the code that are otherwise difficult to see. When we’re trying to get acquainted with a new codebase, names can make make our lives heaven or hell.

It isn’t always easy to work out what “similar” means. In this comment on my tbb::concurrent_vector post, Adrian points out that std::vector guarantees contiguous storage whereas tbb::concurrent_vector doesn’t. What are the essential properties of a vector that must be maintained by anything calling itself a vector? The lack of contiguous storage in tbb::concurrent_vector hadn’t occurred to me as being noteworthy – hence I wrote a blog post that was confusing. Having a name that makes sense to you is one thing, having someone else look at it helps identify any assumptions you’ve made that you didn’t know you were making.

There is a particular joy in coming up with a good name. On the odd occasions I experience this joy it is usually because I have forgotten (in the sense of rote learning) the name of something but I’ve been able to reconstruct what the name is. At the very least it shows some consistency – my brain is working the same way now as it was when I originally came up with the name. Sometimes the quality of a name doesn’t come to light until we try and name something that’s similar – if the original name is good, we can easily derive a name for the new, similar, thing.

I am sure that off by one errors will always be with us. The half open ranges used by many languages (including C and C++) make the situation better, but not perfect. My first job was programming in FORTRAN 77 where arrays start at index 1. I had to write more +1 and -1 statements in FORTRAN than I have ever had to in C and C++. Even better was when we were calling between C and FORTRAN. Yes, we knew the array indices were off by one, but it wasn’t always easy to remember whether it was +1 or -1.

I have mentioned this piece by Dijkstra before. As well as his theoretical analysis, he also mentions that the programming language Mesa allowed for all four different range conventions, and that the “half-open, start at zero” convention led to fewer errors.

… I am convinced that the quality of the product can never be established afterwards. Whether the correctness of a piece of software can be guaranteed or not depends greatly on the structure of the thing made. This means that the ability to convince users, or yourself, that the product is good, is closely intertwined with the design process itself.

Edsger Dijkstra

We don’t get quality by having a week, or even a two or four week, “quality sprint” at the end. We don’t get quality by just talking about quality. We don’t get quality by putting up motivational posters (although we did get a lot of laughs out of the wonderfully cynical graffiti that was added within 24 hours of their appearance).

We get quality by wanting it and engineering for it and caring about it at every stage in the process. We get quality by being prepared to admit that we’re doing something (or everything) wrong and finding a way to do it better. Quality software is bloody difficult to obtain even when we care about it deeply, follow all the industry best practices and invent a few best practices of our own. Quality software is impossible to obtain if we’re not doing everything we possibly can.

Dijkstra talks about the “ability to convince users, or yourself, that the product is good”. One of my first questions to a team is “does your software work”? The vast majority of teams will answer “yes”. Some of them might admit to a qualified “yes”. The next question is “how do you know your software works”? The answer to that question should be wide and deep. It should encompass testing of many flavours – unit, automated, user, white box, black box, integration, system. It should encompass development practices, communication structures, requirements gathering, change management and the attitude of everyone on the team.

The best team I was ever on had a white box QE who looked at every decision with a testing and quality mindset. Whenever we came up with a design for a component he asked how it was going to be tested, how we would know whether it worked or not (the definition of “works” can be surprisingly subtle) and what additional integration tests would be necessary because that component interacted with other components. There were times where that QE was the least popular person in the room. These were also the times when it was incredibly important to keep him in the room and make sure we were all listening to him. That in turn demanded a certain attitude from the rest of us.

Don’t ship the org. chart

Steve Sinofsky

Organizations which design systems are constrained to produce designs which are copies of the communication structures of these organizations. (For example, if you have four groups working on a compiler, you’ll get a 4-pass compiler)

Conway’s Law

If you want a product with certain characteristics, you must ensure that the team has those characteristics before the product’s development.

Jim McCarthy and Michele McCarthy – Software for your Head

Remember Sinofsky’s “don’t ship the org chart”? It is a lie. You cannot avoid it. You always ship the org chart. So the real question is, what is the org. going to look like so that we ship something good-looking? That’s the real purpose of Steve’s rant. No matter how much politicking or boosting you do for this important service-oriented architecture, it doesn’t work unless you have a service-oriented org chart. And Google does not, apparently.

Unknown Amazon engineer on Hacker News

There are many more variations on “don’t ship the org. chart”. The quote I find interesting is the one from the anonymous Amazon engineer who takes a different approach – you will ship the org. chart, so make sure that the org. chart is the one you want to ship.

“Steve’s rant” refers to this post by Steve Yegge. I have never been sure how seriously I should take Steve Yegge’s claim that it was posted accidentally, but it’s a great read.

The only sin is to make a choice without knowing you are making one.

Jonathan Shewchuk

This fits in perfectly with the “Pros and cons” post I put up a few months ago. It’s all about making a conscious decision.

… it looks more or less like the hardware designers have run out of ideas, and that they’re trying to pass the blame for the future demise of Moore’s Law to the software writers by giving us machines that work faster only on a few key benchmarks!

Donald Knuth (Quoted here)

Computer science is no more about computers than astronomy is about telescopes.

Edsger Dijkstra (although disputed)

Real computer scientists despise the idea of actual hardware. Hardware has limitations, software doesn’t. It’s a real shame that Turing machines are so poor at I/O.

Anon

Much as I hate to disagree with Donald Knuth, I think he is being overly harsh to the hardware manufacturers (at least on this particular topic). Chips are now being produced with 14 nm features. Chip designers are faced with some fundamental limits of the universe: quantum effects and the speed of light matter at this scale. They are also having to deal with billions of transistors on a chip. I am always amazed that anything computer based works at all.

I used Donald Knuth’s quote at a talk Chuck Rose and I gave at a domain specific languages conference a few years ago. The talk can be found here. It goes into detail about Pixel Bender, a high performance language for image processing (i.e. very fast, very cool special effects on images), that can use as much parallelism as is available.

As usual, Dijkstra makes the rest of us look like we are banging our heads against the keyboard and accepting whatever results as a valid program. The University of Texas maintains an archive of Dijkstra’s manuscripts. (See also a previous quote of the week).

And finally, while “real computer scientists” might “despise the idea of actual hardware”, some of us have to deal with actual hardware to make a living. I am immensely grateful for the fact that we have top notch thinkers like Knuth and Dijkstra, and I am also grateful that we have engineers at the chip companies doing the hard work necessary to give us processors that work.

How the teacher reacts when something goes wrong tells the class what’s important.

Bruce Hamilton

Bruce is a dance teacher par excellence and originally said this in the context of teaching Scottish and English folk dancing. It also applies to any sort of teacher / student interaction, and any interaction where someone has power or influence over someone else. Let’s paraphrase the quote:

How the manager reacts when something goes wrong tells the team what’s important.

or perhaps:

How the senior developer reacts when something goes wrong tells the junior developers what’s important.

I have had the misfortune to work on several teams where one person (usually, but not always, the manager) had to have their ego maintained at all costs. If anything went wrong it was not their fault, and any attempt to get them to take responsibility was doomed to (very unpleasant) failure. It was very clear what was most important – their ego. Because of that, entry #2 on the importance scale was for the rest of the team to protect themselves from the egoist. If we were lucky, entry #3 might involve producing a quality product.

If there’s one thing worse than a program that doesn’t work when it should, it’s a program that does work when it shouldn’t.

Bob Archer

I am sure that someone said this long before I did, but I can’t find a quote expressing quite the same sentiments.

At least with a program that doesn’t work you know it doesn’t work. You might not know why it doesn’t work, or how to fix it but you still have the knowledge that it doesn’t work. A program that does work when it shouldn’t will, of course, work right up until that big demo to the CEO or a major customer. Or, it will start exhibiting a problem right before code freeze and, upon tracking down the source of the problem, the poor engineer will discover code that has never worked and needs to be completely rethought.

The interesting thing is why the code appears to work. Sometimes two bugs cancel each other out (mostly), sometimes (as in my most recent example) it’s accessing memory after it was freed (very shortly after it was freed) – that worked on 7 out of 8 platforms. Sometimes the code isn’t being called at all – I have often been surprised at a break point that wasn’t hit, or looked at the profiler results to discover that a function that should be called thousands of times hasn’t been called at all.

… distortions in one market … can justify government intervention in other, related markets. Second-best arguments have a dubious reputation in economics, because the right policy is always to eliminate the primary distortion, if you can.

Paul Krugman, The big green test

Before jumping into my commentary, I want to emphasize that this is not intended to be a political “quote of the week”, and any comments that are political rather than technical will not be approved. Actually, since I haven’t put up the page with my moderation policy yet, I will point out that any comments that are religious rather than technical will also be consigned to /dev/null. Of course, if Pope Francis or President Obama ever venture an opinion on lambdas vs. std::bind feel free to comment on that subject.

I suggest reading the whole piece since I had to mangle the quote to get it into a reasonable form. The reason I am quoting Paul Krugman at all is that I think that the economic distortions he is talking about have an equivalent in code. Something big is wrong (call it X) and can’t be changed (or someone with some authority believes it can’t be changed) so the team spends the rest of the project working around it, usually with increasingly fragile hacks.

I believe that the cost of not changing X is routinely underestimated. The cost doesn’t come in one big lump, it is spread out over weeks and months of having to work around X – a colleague of mine referred to these problems as “sharp corners”. They don’t actually stop you from doing something but they make it unpleasant enough that you try to avoid the sharp corners. That leads to second best solutions which then lead to further sharp corners and more second best solutions. Changing X costs you in the short term, not changing it results in long term smaller, cumulative costs.

You need to know why you can’t change X. The reasons are important, the reasons might apply now, they might not apply in 6 months. Take the long view – do you still want to be dealing with X in 2 years (or 5 years or 10 years)? Even if you can’t change X right now, perhaps there are incremental changes you can make so that it will be possible to change X at a future date.

Think about what X would look like if you could change it. How close can you get to that? You might be able to wrap X, although wrapping comes with costs of its own. I have worked on systems that wrapped almost everything and they were a pain to deal with.

I have been on teams that fail to get to grips with their version of X, and I have been on teams where we did manage to handle X well. It is wonderful when you can take something that was causing constant pain and eliminate it – it’s like a toothache that you get treated.

Comparing to another activity is useful if it helps you formulate questions, it’s dangerous when you use it to justify answers.

Martin Fowler

I like analogies, probably more than I should. One of my favourite analogies is to compare code quality to the three different types of equilibrium I was taught in physics class.

Stable equilibrium is like a cherry in the bottom of a bowl. You can push the cherry slightly and it will return to its original position at the bottom of the bowl. It’s like well written code that can be changed without breaking in unexpected ways – perhaps the team followed the “Don’t Repeat Yourself” rule so that when a constant needed to be changed it was changed in one place and the change percolated correctly through the system.

Unstable equilibrium is when the bowl is overturned. With care you can balance the cherry on the top of the bowl, but the moment the cherry is disturbed it will roll off. I have seen lots of multithreaded code that was tweaked and tuned and hacked around until it “worked”. The moment anything changed, often something innocuous, the program would fall apart.

The third type of equilibrium is neutral equilibrium. Imagine that the bowl is filled with jelly (jello to our American readers) and the cherry is suspended inside the jelly. I think this proves a corollary to Martin Fowler’s original statement – you can only push an analogy so far before it breaks down (although if someone does manage to come up with a decent code analogy to neutral equilibrium I’d love to hear it).