My awesome brother-in-law is learning coding generally and Ruby specifically lately, so we decided to check out ScreenHero and try some remote pairing.
One thing led to another, and next think you know he was asking me how you know when to use a
case statement versus when to use
if/elsif. We chatted about logic and clean design, and then started wondering if there really was a performance difference between
(Yes, yes, this sort of micro-optimization is usually way less important than readable and easy to maintain code. But it’s still fun to think about!)
“If you find you’re looking to optimize that intensely you probably don’t want an interpreted language.
I generally try to avoid case statements simply because it makes it easy for me or another programmer to come along in the future and add another case, increasing the branching in a bit of code that should probably have only done one thing in the first place.” – Jonan S.
Yep. Agreed on both points. And now that we’ve acknowledged that this exploration is just for funsies, let’s move on.
Midwire ran a few benchmarks and concluded that
if/elsif is faster than
case “implicitly compares using the more expensive === operator”.
It’s true –
case totally uses threequal under the hood! (I mean, there’s a reason we say that threequal is for case equality.) But that doesn’t feel like the end of the story, so let’s see what else we can figure out here.
In some languages,
case statements are implemented as hash tables to gain performance over
if/elsif chains. Is that true in Ruby? If not, what is going on here? And where can we look for the answers?
THE RUBY DOCS AIN’T GONNA CUT IT THIS TIME
To be honest, I started this exploration by looking through the Ruby docs and clicking to toggle source on
case, but there was nothing there.
case are so fundamental that they can’t actually be defined as functions and thus can’t be explained by looking at the Ruby sourcecode. We have to look at the parser and compiler to figure out what’s going on with them.
Why? Well, scroll down to SICP Exercise 1.6.
Let us assume for the sake of argument that Ruby had
if as a language keyword, but wanted to define
case in terms of
Let’s pretend cond is just if, and rewrite this example…
(define (new-if predicate then-clause else-clause) (cond (predicate then-clause) (else else-clause)))
Well, okay. Now, what if we tried to use it like this?
Whoops! The then_clause and else_clause get evaluated before being passed in as arguments. That’s no good. Okay, fine, what if we set up new_if to take clauses as lambdas instead?
Cool, but what about scoping? We want the clause that ends up evaluated to be able to change variables from the scope outside the conditional. Good thing that’s not actually a problem in Ruby, where closures include bindings and don’t just close over values from the outer scope.
If that seems deeply weird to you, you might want to check out this post on how bindings and closures work in Ruby.
But anyways, we know that case doesn’t have to take lambdas in Ruby, so we know that this can’t be how it works. And if it’s not a function defined in Ruby, but is a language keyword instead, we can’t really quite figure out what’s going on with it just by reading through the docs as usual. Bah, humbug. Where should we look next?
LUCKY FOR US, MRI IS OPEN SOURCE
When in doubt, it’s time to refer to primary source materials.
ADD_INSN1(cond_seq, nd_line(vals), checkmatch, INT2FIX(VM_CHECKMATCH_TYPE_CASE | VM_CHECKMATCH_ARRAY)); ADD_INSNL(cond_seq, nd_line(vals), branchif, l1);
VM_CHECKMATCH_TYPE_CASE? Turns out it’s
check `patten === target'.
And just look a bit further down in
insns.def and we find
DEFINE_INSN checkmatch. Of course, it turns out that
check_match, which checks case equality with
idEqq, which (again) turns out to be :===.
That was pretty neat. Now, what about this
branchif business? Well, it seems to be defined here. Seems pretty straightforward. It looks like both
if/elsif are implemented as sequences of conditionals and gotos in Ruby, so we can’t expect to get the sort of performance boost with
case in Ruby like we see in languages where
case statements are implemented as hash tables instead.
That doesn’t really answer the initial question, though. Threequal, got it, sure. But what if we use === in our
if/elsif statements? Is there any other performance difference between
OPENING UP THE HOOD WITH RubyVM::InstructionSequence
Oh, to hell with primary source materials. Let’s just open up the hood ourselves. Have you played with
RubyVM::InstructionSequence yet? Seriously, it’s just about the niftiest thing around.
Want to see the YARV (“Yet Another Ruby Virtual machine”) bytecode your code really ends up translated into? Sure, no prob.
RubyVM::InstructionSequence::compile_file “[t]akes file, a String with the location of a Ruby source file, reads, parses and compiles the file, and returns iseq, the compiled InstructionSequence with source location metadata set.”
We can verify stuff pretty easily this way. Let’s start by testing out a
Let’s pause for a moment and make some predictions. What do you think this all might mean?
(a/k/a Dear rabbit hole: I’m in you.)
Personally, I’m pretty intrigued by the fact that
branchif. Based on that alone, I’d expect
if/elsif to be faster in situations where one of the first few possibilities is a match, and for
case to be faster in situations where a match is found only way further down the list (when
if/elsif would have to make more jumps along the way on account of all those
BENCHMARK ALL THE THINGS
To hell with reading the bytecode. Let’s just benchmark some shit.
Here’s my rough little benchmarking code. I actually tested
if/elsif twice: once with ==, and once with ===.
I tested each option with a list of 15 predicates, ranging from 15 as the first down to 1 as the last. So according to my prediction,
case should be fastest if I test with n == 1, and slowest when n == 15.
I ran the benchmark a bunch of times, and got results pretty consistently along these lines:
Benchmarking seems to mostly confirm our theory, except note that that threequal_if (a sequence of
if/elsifs comparing with ===) was the slowest in both cases. It was slower by an order of magnitude when the last clause matched (n == 1), where both
branchunless and the expensive === comparison were slowing it down, and even when the first clause matched (n == 15), when my guess is that the slowness of === outweighed the slowness of the single extra jump
case had to make because of
(When I was initially writing this post, I had some messed up benchmarking and ended up way down the rabbit hole reading about branch prediction optimization, which your CPU deals with. This paper was interesting, too. But never mind that now.)
Anyways. None of this is dispositive, but we have some evidence and a better understanding of how things are implemented here, which is ultimately the real point.
And speaking of rabbit holes, I wonder why
if/elsif have that different branching… something about different assumptions about how they’d be used, maybe? What about
As one might expect,
case, and unlike
And there you have it. Any conclusions I might draw from that would be pure speculation, so I’ll leave the facts to stand on their own merits. Knowing is half the battle &c.
Hope this answers your question, Dan! And gives you a few extra tools for looking into the next few as well. ^^ Hooray for rabbit holes!