Introducing the unrolled-switch anti-pattern


Over the years, I've seen a bunch of coding anti-patterns. I figured maybe I'll share a few.

Today, I'll introduce what I'm calling the unrolled-switch anti-pattern, also known as "Specialization is always faster, right?"

enum Axis
{
    XAxis,
    YAxis,
    ZAxis,
};

// code earlier in the function ensure that
// "axis" is always a valid axis
int newPosition;
switch (axis)
{
case XAxis:
    newPosition = m_position[XAxis] + amount;
    if (newPosition < m_minPosition[XAxis])
        newPosition = m_minPosition[XAxis];
    if (newPosition > m_maxPosition[XAxis])
        newPosition = m_maxPosition[XAxis];
    m_position[XAxis] = amount;
    break;
case YAxis:
    newPosition = m_position[YAxis] + amount;
    if (newPosition < m_minPosition[YAxis])
        newPosition = m_minPosition[YAxis];
    if (newPosition > m_maxPosition[YAxis])
        newPosition = m_maxPosition[YAxis];
    m_position[YAxis] = amount;
    break;
case ZAxis:
    newPosition = m_position[ZAxis] + amount;
    if (newPosition < m_minPosition[ZAxis])
        newPosition = m_minPosition[ZAxis];
    if (newPosition > m_maxPosition[XAxis])
        newPosition = m_maxPosition[XAxis];
    m_position[ZAxis] = amount;
    break;
}

As we all know, special-case code is faster than general-purpose code. Instead of writing slow general-purpose code:

    newPosition = m_position[axis] + amount;
    if (newPosition < m_minPosition[axis])
        newPosition = m_minPosition[axis];
    if (newPosition > m_maxPosition[axis])
        newPosition = m_maxPosition[axis];
    m_position[axis] = amount;

we unroll it into a switch statement, thereby generating highly-optimized special-purpose code, one for each axis.

What makes this anti-pattern particularly frustrating is that you cannot tell at a glance whether all the cases really are the same (just with different axes).

In fact, they aren't.

If you look closely, you'll see that we check the new Z-position against the X-axis maximum rather than the Z-axis maximum. If you're reading this code, you now start to wonder, "Is this a copy/paste bug, or is there some reason that we really do want to check the Z-position against the X-axis minimum?"

A variation on the unrolled-switch is the unrolled-if, used if the item you want to unroll cannot be used in a switch statement:

FruitBasket *BananaBasket;
FruitBasket *AppleBasket;
FruitBasket *PearBasket;
FruitBasket *MangoBasket;

if (basket == BananaBasket) {
  if (!BananaBasket->IsEmpty()) {
    fruit = BananaBasket->TakeFruit();
    if (HaveKnife()) {
      TakeKnife();
      fruit->Peel();
      fruit->Slice();
      fruit->Eat();
      ReplaceKnife();
    } else {
      BananaBasket->AddFruit(fruit);
    }
  }
} else if (basket == AppleBasket) {
  if (!AppleBasket->IsEmpty()) {
    fruit = AppleBasket->TakeFruit();
    if (HaveKnife()) {
      TakeKnife();
      fruit->Peel();
      fruit->Slice();
      fruit->Eat();
      ReplaceKnife();
    } else {
      AppleBasket->AddFruit(fruit);
    }
  }
} else if (basket == PearBasket) {
  if (!PearBasket->IsEmpty()) {
    fruit = PearBasket->TakeFruit();
    if (HaveKnife()) {
      TakeKnife();
      fruit->Slice();
      fruit->Eat();
      ReplaceKnife();
    } else {
      PearBasket->AddFruit(fruit);
    }
  }
} else if (basket == MangoBasket) {
  if (!MangoBasket->IsEmpty()) {
    fruit = MangoBasket->TakeFruit();
    if (HaveKnife()) {
      TakeKnife();
      fruit->Peel();
      fruit->Slice();
      fruit->Eat();
      ReplaceKnife();
    } else {
      BananaBasket->AddFruit(fruit);
    }
  }
}

When I pointed out in an aside to the customer that this could be simplified (after fixing the copy/paste errors) to

if (!basket->IsEmpty()) {
  fruit = basket->TakeFruit();
  if (HaveKnife()) {
    TakeKnife();
    fruit->Peel();
    fruit->Slice();
    fruit->Eat();
    ReplaceKnife();
  } else {
    basket->AddFruit(fruit);
  }
}

the response was, "Hey, that's a neat trick. I didn't realize you could do that."

I wonder if this person also programs loops like this:

switch (limit)
{
case 0:
  break;
case 1:
  do_something(array[0]);
  break;
case 2:
  for (int i = 0; i < 2; i++) do_something(array[i]);
  break;
case 3:
  for (int i = 0; i < 3; i++) do_something(array[i]);
  break;
case 4:
  for (int i = 0; i < 4; i++) do_something(array[i]);
  break;
case 5:
  for (int i = 0; i < 5; i++) do_something(array[i]);
  break;
case 6:
  for (int i = 0; i < 6; i++) do_something(array[i]);
  break;
...
case 999:
  for (int i = 0; i < 999; i++) do_something(array[i]);
  break;
default:
  FatalError("Need more cases to handle larger array");
  break;
}
Comments (39)
  1. Anonymous says:

    Throw a for loop around that and you've got the for-switch anti-pattern, a variant of the for-if anti-pattern (blogs.msdn.com/…/10251210.aspx).

  2. Anonymous says:

    When the array lookup is a static variable, and you're doing something very time sensitive, the unrolled switch can be faster, because the array indexing gets done by the compiler.  If you're on an embedded processor, the extra math needed by the general purpose code (esp. if it requires a multiply) might be horrifically expensive.

    Of course, with the array being a member variable of some class/struct, you already are having to do arithmetic, so the unrolled switch buys you almost nothing.

  3. You've got a typo in the ZAxis case, the m_maxPosition check is using XAxis…

  4. Ignore my previous comment…

  5. Anonymous says:

    My hope is to one day have a tool that 1) compiles the code and optimizes it so it's no longer brain-damaged; 2) reverse translates the resulting code; 3) gives an error with "here's what you wanted to write instead".

    That said, I prefer code we can all point and laugh at to code we can all point at and cry over. If improving your code is so simple a computer could do it, you can get better. But if improving your code is so complicated no human could do it, you can only get worse.

  6. steven says:

    The typos in the copy-pasted code are quite frequent. Andrey Karpov wrote some articles on viva64.com (syndicated on codeguru and codeproject, iirc) entitled "How to make fewer errors at the stage of code writing" extolling the virtues of static code analysis, obviously promoting their own PVS Studio in the process, which seems to catch many such errors. Unfortunately, such analysers are rather expensive for small shops and even if they weren't, I doubt the people who write such code are savvy enough to do SCA.

  7. If only people would leave micro-optimization to the compiler. I've been amazed already years ago how a loop-unroling by the compiler is very efficient, while keeping readable code. using shift operations and addition instead of multiplication when certain constants are involved. Don't try to beat the compiler, the effort invested by experts in making these things optimal is hardly to beat by writing "efficient" code.

    [This code wasn't the result of micro-optimization. It was somebody who didn't realize that you could use variables to represent constants. -Raymond]
  8. Anonymous says:

    Yep, the usual advice applies. Write it clearly. Then, if your testing (You do testing, don't you?) or production reveals a performance problem, do profiling. Then, optimize only the parts of the code the profiling reveals to be a problem.

    (And the typical response will be "BOCATOE". However, I suspect that if you actually do the profiling, most of the cases people expect to be exceptional, will actually be wasted "optimization".)

  9. Anonymous says:

    Sorry, that should have been "BOCTAOE".

  10. steven says:

    BTW, is the link for "Specialization is always faster" correct? If so, I don't get it…

    [Now that you mention it, I don't get it either… -Raymond]
  11. Anonymous says:

    Was the omission of peeling the pear a deliberate test?

  12. if (!basket->IsEmpty()) {

     fruit = basket->TakeFruit();

     if (HaveKnife()) {

       TakeKnife();

       if (basket == PearBasket) {fruit->Peel();}

       fruit->Slice();

       fruit->Eat();

       ReplaceKnife();

     } else {

       basket->AddFruit(fruit);

     }

    }

    Maybe it was an example of where a catchall pattern falls short, when a specific instance has atypical behaviour?

    Either that or put a stub function Peel() in the pear that does nothing but gives an identical signature to the other fruit?

  13. Also, bananas aren't fruit, they're herbs.

    I'm going to end up on the Nitpickers' Naughty Step now, aren't I :(

  14. Anonymous says:

    Knowledge is knowing that a tomato is a fruit. Wisdom is not putting one in your fruit salad.

  15. Anonymous says:

    Sadly, this customer cannot be given the response he deserves.

  16. Anonymous says:

    @Maxim and @Lockwood: Oh wow, I didn't even notice not peeling the pear. I thought the test was wondering why mangoes were being moved to the banana basket if you didn't have the knife. I think this would be a shame, because bananas are delicious and mangoes are yucky, so they shouldn't be mixed.

  17. Anonymous says:

    @Harvey: Botanically, tomato is a fruit, but culinarily, it's a vegetable.

  18. Anonymous says:

    @Lockwood: bananas are an herbaceous fruit.

  19. Anonymous says:

    Does the first example come from actual code? There's another bug there besides, which is that newPosition is not even used, and m_position[axis] is set to amount, completely ignoring the bounds checking done.

    [All examples are made-up, but are inspired by actual code. -Raymond]
  20. @Lockwood: did you mean "if (basket != PearBasket) { fruit->Peel(); }"?

  21. The pear hack can be avoided, for example by extending the interface on the Fruit object to have a ShouldBePeeled() member function.

  22. Anonymous says:

    Clearly this is a case for pear programming!

  23. MikeBMcL says:

    @Steven Don

    All versions of VS11 (including Express) will have SCA. The Express SKUs will only have a subset consisting of the most critical warnings and all others will have all the rules. For more see blogs.msdn.com/…/what-s-new-in-code-analysis-for-visual-studio-11.aspx . Here's hoping people will use it (and thus make the world of computing that much better)!

  24. Anonymous says:

    This is just a special case of the "can't be bothered to factor" anti-pattern which I have seen afflict even otherwise sensible developers. It's a darn shame.

  25. Anonymous says:

    @Adam Rosenfield: That makes no sense at all, since you use tomato the same way you use fruit in the kitchen. You eat it raw whole, like apples, or chopped in sauce like apples in curry, purified and boiled like pumpkin or as a juice like apple or citrus fruit, or as a desert.

  26. I kind of "legitimately" did this for a large interrupt handler on an embedded microcontroller.  There were three interrupts, all of which had to be handled virtually identically – the only difference being that the code used the interrupt number as a parameter.  Putting the code into a shared function that was called by each interrupt was too slow – the generated code took much too long because it had to be prepared to handle any number in its input.  Copying/pasting the interrupt code from the shared function directly into each interrupt's handler fixed the issue, as the variable could be replaced by a constant.  The code ran much faster.

    Except I left it to the compiler to commit this atrocity, by declaring the function "inline" and letting it do a nice optimization since the function parameter was known in advance.  (Code size was not an issue; performance was.)

  27. Anonymous says:

    @MikeBMcl: So many companies, like my employer, can't use VS 2012 because the output won't work on XP.  VS 2012 has a lot of neat stuff, but we're just stuck as long as at least a quarter of our customers are on XP.

  28. Anonymous says:

    >It was somebody who didn't realize that you could use variables to represent constants.

    It seems worse than that. He apparently realises that you can use a variable to represent a constant *some of the time* (after all, axis somehow got set to something before the switch statement) but then decides that you can't use a variable at other times (i.e., array indexing).  Which is especially weird, since imagine how useless arrays are if the index can only be a constant.

    In short, "clueless".

  29. Anonymous says:

    Reading the title, I was sure this was going to be about Duff's Device. But this was actually so much worse.

  30. Anonymous says:

    It's a small variant called the "Duff" device!

  31. Anonymous says:

    The pear hack can be avoided, for example by extending the interface on the Fruit

    object to have a ShouldBePeeled() member function.

    Or by genetically modifying pears to have really thick skins.

  32. Anonymous says:

    I've found calls to operator delete in C++ to feature this over the years. The reason may be due to a design which requires downcasts in other situations, leading in some cases to the code presented in the article.

    Given:

       class Base, with a virtual destructor since first appearance in source control.

       classes A and B, derived from Base.

    I've seen:

       switch( pointerToBase->GetUniqueId() )

       {

           case A::UniqueId: delete (A *)p; break;

           case B::UniqueId: delete (B *)p; break;

       } // repeated in multiple modules. Too bad for newly added C and D

  33. Anonymous says:

    I sign in and nothing happens. Maybe xpclient's threat to remove me from the blogs was legit.

    Anyway…

    @Timothy Byrd: Yes, that's what I meant. I had initally done a different test with a (!foo == bar) style construct and realised I was not thinking clearly.

    That did leave the == artefact behind.

    @Paul: That's a good point, I'd missed that.

    We'll work on the assumption that IFruit is untouchable, therefore we can't put a Peel() that returns false or a ShouldBePeeled() function into it.

    We're maintaining backwards compatibility at the expense of a nice simple fix, and are matching the original behaviour bug-for-bug.

    AIUI, the code should read now thus:

    if (!basket->IsEmpty()) {

    fruit = basket->TakeFruit();

    if (HaveKnife()) {

      TakeKnife();

      if (basket != PearBasket) {fruit->Peel();}

      fruit->Slice();

      fruit->Eat();

      ReplaceKnife();

    } else {

      if (basket != MangoBasket) {

         BananaBasket->AddFruit(fruit);

      } else {

         basket->AddFruit(fruit);

      }

    }

    }

  34. Anonymous says:

    Your AddFruit calls are swapped at the end, only mangos (and bananas) should go in the banana basket.

  35. DWalker59 says:

    "If you're reading this code, you now start to wonder, "Is this a copy/paste bug, or is there some reason that we really do want to check the Z-position against the X-axis minimum?" "

    That's why it is SO CRUCIAL to write meaningful comments inside code.  I have written comments that say "The apparent simplification of doing this part in such-and-such a way won't work, for the following reason…"

    Some programmers are bad at writing comments, beyond just not writing them at all.  If the code says foo = foo + 1, the comment should say WHY foo is being incremented, rather than saying "add 1 to foo".  It should be clear from the earlier comments in the same code, what foo represents.

  36. Anonymous says:

    It is better to NAME the variable properly instead of 'foo':

    LinesInCache = LinesInCache + 1;

    Then there is no need for the WHY comment.

  37. Anonymous says:

    @AsmGuru62:  Personally I think it's odd that you're giving your cache an extra line and your naming convention, while descriptive, tells me nothing about why you're doing it.

  38. Anonymous says:

    Many years ago, pre-Microsoft, I worked with somebody who built unit tests using the unrolled switch anti-pattern. It was in a proprietary variant of Pascal which I no longer remember, but the gist was:

    switch (test_case)

    {

       case 'a' : test('a'); break;

       case 'b' : test('b'); break;

       case 'c' : test('c'); break;

       case 'd' : test('d'); break;

       …

       case 'z' : test('z'); break;

    } // no default case!!!

    In the clearest example I have ever seen of the Dilbert principle, this dev was promoted to lead in order to reduce the amount of time he spent coding.

  39. JamesNT says:

    I'm guilty of stuff like this once in a while.  It's the result of me just overthinking a problem.

    JamesNT

Comments are closed.