Efficiency of cond statements

"Premature optimization is the root of all evil." --Donald Knuth

This is the second point which Walz raised in a comment which I thought deserved a separate blog entry. (You can read the original comment and the first point I liked.)

Walz's second observation is about efficiency:

cond statements [in LISP are] merely a construction for neat multi-branching (as opposed to nested ifs, which get ugly fast with all the parenthesis) ... I would have gone on to assume that this constant time aspect was the fundamental reason for the restrictions on C family switch statements were it not for my experiences with more expressive case statements in Haskell.

He goes on to ask where Ruby's case statement lives in this spectrum.

I should admit up front that I have my own personal demons concerning the switch statement which I need to work out myself (partially through this blog). Walz is pretty much on target here.

Performance of C switch

The restrictions on C's switch statement are definitely for performance reasons. Several years ago I played around with switch and if statements to see how significant the difference was; I wrote up my results.

I plan to revisit those results sometime on this blog and rant further about the switch statement. There are ways to lift the restrictions and keep performance.

The cond expression

My experience with cond comes from Scheme, but I think it also applies to LISP in this case: cond is implemented as a macro which expands into the standard multibranch if. It certainly has those semantics, and so it'll have the same running time.

Scheme also has a case expression which is more along the lines of a C switch statement. (The main difference would be no fall-through behavior.) But even this is turned into a mutlibranch if with member? tests.

Pattern Matching in Haskell

I'm curious though about Walz's comment about Haskell. Are you claiming that pattern matching is expressive or efficient? It's wonderfully expressive, but it must be, in general, as expensive as a multibranch if.

That's because, in general, the patterns can be very, very nested. Since the nested components will be stored as pointers, it'll require traipsing through memory in order to find the proper match. It can't be codified in a simple look-up table (like a switch can).

Ruby's case

Ruby's case is wonderfully expressive, even beyond the cond expression.

case grade
  when 93..100 then "A"
  when 90..92  then "A-"
  when 87..89  then "B+
  ...

You can even put in regular expressions in for the when clauses.

Of course, all this expressiveness means the efficiency is like a multibranch if.

Back to efficiency

So the Scheme case and cond, Haskell pattern matching, and the Ruby case all run (I claim) as multibranch ifs. They don't have to. A clever compiler could recognize when these language features were being used like a switch and generate a look-up table.

The real power is in their expressiveness. Somehow the switch statement keeps us all looking at these constructs in terms of efficiency, and that's a huge double mistake.

It's a mistake because it stinks of "premature optimization" (hence my opening Knuth quote). If a cond is slow but could be made faster but executed only once when the program is started, you gain virtually nothing by optimizing it.

It's also a mistake because in the general, expensive situations, the C code won't be any faster (algorithmically). You just won't be able to use a switch statement.

In terms of expressiveness, they all win, certainly over the return guards—which is what started all this in the first place.