Switching on a tuple: Sneaky trick


This is a sneaky trick, but it's sometimes a handy sneaky trick.

Suppose you have two values, and you want to switch on the tuple. In other words, you want a switch statement for something like this:

if (val1 == 1 && val2 == 0) {
 Thing_1_0();
} else if ((val1 == 1 && val2 == 1 ||
           (val1 == 1 && val2 == 2)) {
 Thing_1_12();
} else if (val1 == 2 && val2 == 0) {
 Thing_2_0();
} ... etc ...

You could try writing

switch (val1, val2) {
case 1, 0:
    Thing_1_0();
    break;
case 1, 1:
case 1, 2:
    Thing_1_12();
    break;
case 2, 0:
    Thing_2_0();
    break;
...
}

but that doesn't do what you think it does. (Because that comma is a comma operator.)

The sneaky trick is to pack the two values into a single value that you can then switch on.

switch (MAKELONG(val1, val2)) {
case MAKELONG(1, 0):
    Thing_1_0();
    break;
case MAKELONG(1, 1):
case MAKELONG(1, 2):
    Thing_1_12();
    break;
case MAKELONG(2, 0):
    Thing_2_0();
    break;
...
}

Note that there are dangers here beyond craziness. You have to make sure that your packing function is injective (i.e., that it does not assign the same packed value to two different inputs). If you use MAKE­LONG as your packing function, then the two values to be packed must fit into 16-bit integers.

Comments (31)
  1. SI says:

    I have found this useful for WM_COMMAND messages in the past.

  2. M. Dudley says:

    Missing closing parentheses on line 3 of your first code example, right before the || operator.

  3. DWalker says:

    Sometimes the values are characters; you can concatenate them with a carefully-chosen delimiter (which looks messy but sometimes works).

    If the two values are 32-bit integers, you can of course make them into a 64-bit integer... And so on.

  4. Diego F. says:

    F# :) Other languages should implement it as well.

    match val1, val2 with

    | 1, 0 -> thing_1_0 ()

    | 1, 1 -> thing_1_1 ()

    | 1, 2 -> thing_1_2 ()

    | 2, 0 -> thing_2_0 ()

    | _ -> whatever ()

    [Feel free to submit your proposal to the C language committee. -Raymond]
  5. Jason Warren says:

    This pattern both impresses and disgusts my sensibilities. Well done!

  6. Brian_EE says:

    @M_Dudley: Since the example isn't meant to be working code in the first place, your nitpicking is for naught.

    Back on topic.... this concept has been well known in the hardware description language (HDL) community for ages. You pack indidivual bits into a bit vector and compare against that to decide what to do (useful in hardware state machines).

  7. Kevin says:

    @Aaron: Or, y'know, just use a sane language like Python:

       lookup = {(1,0): Thing_1,

                 (1,1): Thing_2, # etc.

                }

       try:

           func = lookup[val1, val2]

       except KeyError:

           # Handle it

       else:

           func()

    ["Oh, the way to solve this problem is to throw away your current code base and rewrite it in this other language." -Raymond]
  8. Henri Hein says:

    @DWalker:

    Tootling my own horn a bit, but I feel compelled to point to an article I wrote on the subject:

    http://www.codeguru.com/.../Using-a-Pair-Class-as-Efficient-Key-Objects.htm

    I had to optimize a code base which used concatenated strings as keys.  I was surprised at the speed improvement when I converted that to a tuple-like construct.

  9. not important says:

    I used a similar trick when parsing MPEG files (I should mention I did this for a personal project). MPEG files consist of atoms and each atom is marked with four characters (for ex. the data atom is marked with "mdat"). Guess what datatype fits in 32 bits and can be used to test for equality:)???

  10. Kevin says:

    @Raymond: I was trying to make fun of Aaron for using such a complicated solution (hint: Python is at least a whole (binary) order of magnitude slower than equivalent C).  Unfortunately, it didn't come through very well.

  11. Adam Rosenfield says:

    [This creates a data structure at run time and uses a linear search. The switch statement is built at compile time and can use a binary search or table dispatch. -Raymond]

    In this case, you likely won't get a table dispatch unless several of your values have the similar low words and the same high word in MAKELONG(low, high), since a table dispatch only makes sense when you use a dense range of consecutive integers.  Of course, the results depend highly on the compiler's implementation details.

  12. John Ludlow says:

    Since we're suggesting other languages that can do this sort of thing in overly complicated ways:

    // C#

         var dict = new Dictionary<object, Action> {

           { new { a=1, b=2 }, () => Console.WriteLine("FOO")},

           { new { a=2, b=2 }, () => Console.WriteLine("BAR")}

         };

         dict[new { a=1, b=2 }]();

    Ok, I know this works because I have actually used it

  13. Harald van Dijk says:

    > but that doesn't do what you think it does. (Because that comma is a comma operator.)

    << case 1, 2: >> is a syntax error. A comma is not allowed by the syntax in that context, as an operator or otherwise, in either C or in C++. Most compilers reject it as such, complaining that they expected : where they got ,. At least two do accept it as a valid extension to the syntax, indeed treating it like a comma operator like you suggest. In the latest of their currently released versions, both of those compilers still implement the rule that a constant expression cannot contain comma operators, so still issue an error message, and don't cause your code to behave unexpectedly at run-time. Are you using a build that is not an official release, perhaps? Or did I miss a relevant compiler in my testing?

    It's an entirely different story for << case (1, 2): >>, so your point is valid even today and it still pays to turn up your compiler's warning level.

    I like your suggested approach and have used it in the past, switching on four characters packed into a 32-bit integer. Strictly speaking, that isn't 100% portable, but it'll only break in the extremely unlikely case of a non-ASCII non-EBCDIC implementation with more than 8 bits per byte, so it's good enough for practical purposes.

  14. parkrrrr says:

    Though in the case of this specific code, since all of the cases just call functions, I'd also consider using a 2-dimensional array of function pointers. But, while that would be smaller and faster, it would be far more likely to break junior programmers.

  15. mappu says:

    What other methods are there of packing two ints into one?

    For arbitrary-size ints, i thought of

    - interleave binary bits

    - Define a parametric space-filling curve over x/y and use its t parameter as the result. E.g. a diagonal path starting from (0,0) and repeating upward

    - abusing empty space in higher bases: function(int a, int b) { return base11_to_10( a + "A" + b ); }

    Some unoptimised implementations at code.ivysaur.me/tupac.html .

  16. mh says:

    I do hope that C++ example was meant to be a joke; there's obviously not enough boilerplate in it.  The REAL way is to write the numbers into a string, convert it to XML, and then parse the XML.

  17. Aaron says:

    Here is the much simpler way to do it:

    struct Key

    {

       int a; int b;

       int operator==(const Key& that) { return (that.a == this->a) && (that.b == this->b); }

    };

    typedef void(*ThingFunc)();

    // Isn't this far, far easier to read that a big switch-case block??

    LookupTable<Key, ThingFunc> option[] =

    { {1,0}, Thing_1_0    },

     {1,1}, Thing_1_1or2 },

     {1,2}, Thing_1_2or2 },

     {2,2}, Thing_2_2    }

    };

    ThingFunc* pFunc = option->Lookup(Key{val1,val2}, _countof(option));

    if (pFunc == NULL)

    {

       // Error, that entry not found in the lookup table!

    }

    else

    {

       (*pFunc)(); // Actually call the function found in the lookup table.

    }

    And, implementation of the LookupTable:

    template<class KT, class VT>

    struct LookupTable

    {

    KT key;

    VT value;

    // returns NULL if key was not found.

    // returns pointer to matching value when key is found.

    VT* Lookup(KT key, size_t size)

    {

    VT* pF = NULL;

    for (size_t i = 0; i < size; ++i)

    {

    if (key == this[i].key)

    {

    pF = &(this[i].value);

    break;

    }

    }

    return pF;

    }

    };

    [This creates a data structure at run time and uses a linear search. The switch statement is built at compile time and can use a binary search or table dispatch. -Raymond]
  18. cheong00 says:

    @Diego F.: In C# we have Tuple type, although it's not supported in switch statement.

    I do hope one day they'll permit it in switch statement, if all parameters in Tuple are "switch permitted" types.

  19. parkrrrr says:

    Whenever I've needed to do this, I've gone with

    switch (val1) {

     case 1:

        switch( val2) {

           case 0:   /* 1,0 */

               Thing_1_0();

               break;

           case 1: /* 1,1 */

           case 2: /* 1,2 */

               Thing_1_12();

                break;

          }

         break;

      case 2:   /* 2,x */

          switch( val2) {

              case 0:  /* 2,0 */

                  Thing_2_0();

                  break;

               // etc.

           }

          break;

    }

    That seems far more likely to use table lookups, and hopefully less likely to break junior programmers. It's a little wordy, perhaps, but not horrible.

    [It gets ugly if you have a Thing_12_0, though. -Raymond]
  20. Jason T. Miller says:

    @not important: In case you didn't know, these sorts of identifiers, which also appear in many other contexts going back at least as far as the original (1984) Mac system software, are defined to be four characters long with exactly this "trick" in mind.

  21. boogaloo says:

    I don't agree it's sneaky, it seems perfectly obvious to me.

    However in this circumstance I'd expect the compiler to use a sequential search, a binary search or jump table is likely to be slower. Sometimes the compiler will pick the slower method and optimisation has to be achieved by forcing it not to.

    I have seen

    switch (value >> 24)

    {

    case 0:

    case 1:

    case 2:

    etc

    }

    sped up by replacing it with

    switch (value & 0xff000000)

    {

    case 0<<24:

    case 1<<24:

    case 2<<24:

    etc

    }

    It very much depends on the compiler you are using, so if you are working on cross platform source code then you have to be even sneakier. I'd expect this blog to be MSVC focused, but gcc/icc/clang all behave differently. It can also depend on the CPU you are using. One time I managed to write code that performed amazingly well on gcc + Intel P4, when everyone elses code was better using icc + P4 or gcc + AMD.

  22. Silly says:

    For arbitrary data I'd just compute a hash and hope for the best.

  23. Andre says:

    [This creates a data structure at run time and uses a linear search. The switch statement is built at compile time and can use a binary search or table dispatch. -Raymond]

    I think the statement "// Isn't this far, far easier to read that a big switch-case block??" has big, red warning lights on that scream SARCASM. He's just demonstrating how C++ solutions easily degenerate into huge, unreadable meta-programming blocks for the most trivial of things. Only the F# variant beats your C in conciseness.

  24. JamesJohnston says:

    I'm not sure if table dispatch would just happen here.  Seems like you'd need to nest the switch statements like parkrrr did in order to have consecutive integers, like Adam Rosenfield says.  In other words, a table dispatch to another table dispatch, where each table corresponds to one of the tuple values.  Otherwise you probably end up with a binary search, unless compilers are much smarter than I give them credit for.

  25. Joshua says:

    I wonder why none of the reference compilers used binary search when it was obvious table dispatch was not reasonable.

  26. Mark Y says:

    This is a seriously neat trick!  If it weren't for the fact that I don't like C switch statements, I'd probably use it!

  27. MikeBMcL says:

    > [Feel free to submit your proposal to the C language committee. -Raymond]

    Some very smart and influential folks in the C++ community are working on pattern matching with an eye towards (probably) proposing it for standardization in the future. At the ISO/IEC C++ Committee meeting in Urbana last year, two of the three co-authors of the proof-of-concept Mach7 library, Bjarne Stroustrup and Gabriel Dos Reis (I don't remember whether Yuriy Solodkyy, the third co-author was also there) gave an evening session presentation about it which was fascinating.

    You can have a look at Mach 7 here, github.com/.../Mach7 , and view Yuriyy's talk on it at C++ Now 2014 here, http://www.youtube.com/watch . Do note that there is no formal proposal yet and that if/when there is one, its syntax would not be the exactly the same as Mach7's syntax (Mach7 is a library that works with C++ as it is now whereas a formal proposal could include modifications to the core language syntax itself in addition to library APIs and the such).

    > [This creates a data structure at run time and uses a linear search. The switch statement is built at compile time and can use a binary search or table dispatch. -Raymond]

    I am not familiar enough with Mach7 to competently address all aspects of its efficiency, but a design goal was to have it be as efficient as existing functionality (including 'switch') and that the authors considered performance and discuss it in great detail in the various presentations.

  28. boogaloo says:

    "Otherwise you probably end up with a binary search, unless compilers are much smarter than I give them credit for."

    @JamesJohnston The problem for compiler writers is that even when they have written code to detect where jump tables can be used, they aren't necessarily the fastest solution. It's not 1985, your cpu doesn't fetch an instruction then execute it. Writing code that makes the most of the cpu's branch prediction is hard.

    Users of functional programming languages have an even bigger expectation that the compiler is able to pull off miracles. Functional can be faster if the procedural source code is terrible.

  29. boogaloo says:

    @Joshua A binary search isn't always better,

    web.archive.org/.../switch

    "I wonder why none of the reference compilers used binary search when it was obvious table dispatch was not reasonable."

  30. Adam Rosenfield says:

    > Writing code that makes the most of the cpu's branch prediction is hard.

    Not only that, but doing it effectively across a large class of CPUs with different timing characteristics is even harder.  A binary search might be faster on one CPU type, a linear search might be faster on another CPU type, and a table dispatch might be faster on a third CPU type.  A perfect optimizing compiler will either have to generate code that's optimal only for certain CPUs, or generate multiple code paths and choose one at runtime at startup (i.e. like a fat/universal binary).

  31. James Curran says:

    I have in the past, used this often for two letter codes, and, I believe, one for a 4-letter code:

    // In production, this would have more parenthesis

    #define MAKECODE(p) (p[0]*0x01000000 + p[1]*0x010000 + p[2]*0x0100 + p[3])

        switch(MAKECODE(input_buffer))

    The cool thing is that you can give it a string, and it yields a compile-time constant:

        case MAKECODE("OPEN"):

              //

              break;

        case MAKECODE("EXIT"):

              //

              break;

Comments are closed.

Skip to main content