Optimizing an if statement with over 50 OR's ( || )

Question

Okay, so I'm doing some stuff involving keyboard input. I now have a giant function like this:

return key == BB_KEY_SPACE ||
        key == BB_KEY_ZERO ||
        key == BB_KEY_ONE ||
        key == BB_KEY_TWO ||
        key == BB_KEY_THREE ||
        key == BB_KEY_FOUR ||
        key == BB_KEY_FIVE ||
        key == BB_KEY_SIX ||
        key == BB_KEY_SEVEN ||
        key == BB_KEY_EIGHT ||
        key == BB_KEY_NINE ||
        key == BB_KEY_A ||
        key == BB_KEY_B ||
        key == BB_KEY_C ||
        key == BB_KEY_D ||
        key == BB_KEY_E ||
        key == BB_KEY_F ||
        key == BB_KEY_G ||
        key == BB_KEY_H ||
        key == BB_KEY_I ||
        key == BB_KEY_J ||
        key == BB_KEY_K ||
        key == BB_KEY_L ||
        key == BB_KEY_M ||
        key == BB_KEY_N ||
        key == BB_KEY_O ||
        key == BB_KEY_P ||
        key == BB_KEY_Q ||
        key == BB_KEY_R ||
        key == BB_KEY_S ||
        key == BB_KEY_T ||
        key == BB_KEY_U ||
        key == BB_KEY_V ||
        key == BB_KEY_W ||
        key == BB_KEY_X ||
        key == BB_KEY_Y ||
        key == BB_KEY_Z ||
        key == BB_KEY_NUMPAD0 ||
        key == BB_KEY_NUMPAD1 ||
        key == BB_KEY_NUMPAD2 ||
        key == BB_KEY_NUMPAD3 ||
        key == BB_KEY_NUMPAD4 ||
        key == BB_KEY_NUMPAD5 ||
        key == BB_KEY_NUMPAD6 ||
        key == BB_KEY_NUMPAD7 ||
        key == BB_KEY_NUMPAD8 ||
        key == BB_KEY_NUMPAD9 ||
        key == BB_KEY_MULTIPLY ||
        key == BB_KEY_PLUS ||
        key == BB_KEY_SEPERATOR ||
        key == BB_KEY_MINUS ||
        key == BB_KEY_DECIMAL ||
        key == BB_KEY_DIVIDE ||
        key == BB_KEY_OEM1 ||
        key == BB_KEY_OEMPLUS ||
        key == BB_KEY_OEMCOMMA ||
        key == BB_KEY_OEMMINUS ||
        key == BB_KEY_OEMPERIOD ||
        key == BB_KEY_OEM2 ||
        key == BB_KEY_OEM3 ||
        key == BB_KEY_OEM4 ||
        key == BB_KEY_OEM5 ||
        key == BB_KEY_OEM6 ||
        key == BB_KEY_OEM7 ||
        key == BB_KEY_OEM8 ||
        key == BB_KEY_OEM102;`

Is there a good way to optimize this? I am assuming it takes a bit of processing power to verify all of this if-statement stuff. When looking at diagnostics it seems it's taking up a bit of time too. I'm wondering if there is a smarter way of doing this..

Answer 1

Here's another way, using templates. For fun and education mostly. But maybe there's a use case if you're maintaining, for example, a number of properties related to each key-code value:

#include <array>
#include <type_traits>
#include <limits>
#include <utility>

//
// define our enum of codes
//
enum key_code : char
{
    BB_KEY_SPACE = ' ',
    BB_KEY_ZERO = '0',
    BB_KEY_ONE,
    BB_KEY_TWO,
    BB_KEY_THREE,
//  ...etc...
};

//
// by default we don't want the code to match
//    
template <key_code K> const bool is_wanted = false;

//
// but for these codes we do want a match (extend as needed)
//
template <> const bool is_wanted<BB_KEY_SPACE> = true;
template <> const bool is_wanted<BB_KEY_ZERO> = true;
template <> const bool is_wanted<BB_KEY_ONE> = true;
template <> const bool is_wanted<BB_KEY_TWO> = true;

//
// constexpr function to work out the minimum value of the enum
// (in case it's a signed type)
//    
static constexpr std::size_t min_value() { 
  return std::numeric_limits<std::underlying_type_t<key_code>>::min();
}

//
// constexpr function to work out the maximum value of the enum
// (in case it's a signed type)
//    
static constexpr std::size_t max_value() { 
  return std::numeric_limits<std::underlying_type_t<key_code>>::max();
}

//
// constexpr function to work out the extent of the enum
// so we can build an array to represent the test for every value
//    
static constexpr std::size_t to_index(key_code k)
{
  return std::size_t (int(k) - min_value());
}
//
// convenience function to find the correct position in our array
// for a given key code
//    
static constexpr std::size_t to_index(key_code k)
{
  return std::size_t (int(k) + min_value());
}


namespace detail {
  //
  // this function builds an array of bools. Index positions for
  // enum values which have been specialised above will be true
  // all others will be false
  //
  template<std::size_t...Is>
  static constexpr auto make_wanted_array(std::index_sequence<Is...>)
  -> std::array<bool, range_size()>
  {
    return 
    {
      is_wanted<static_cast<key_code>(Is - min_value())>...
    };
  }
}

//
// interface version simply calls the impl having constructed the
// correct index sequence
//    
static constexpr auto make_wanted_array()
-> std::array<bool, range_size()>
{
  return detail::make_wanted_array(std::make_index_sequence<range_size()>());
}

//
// this is the function to test whether a key is valid or not
bool valid_key(key_code k)
{
  // this will be done at compile time. There is zero runtime overhead.
  static constexpr auto wanted_array = make_wanted_array();
  // this is simply a load from memory address with register offset
  return wanted_array[to_index(k)];
}

Here is the assembler emitted for valid_key from gcc5.3 compiled with -O2:

valid_key(key_code):
        movsx   rdi, dil
        movzx   eax, BYTE PTR valid_key(key_code)::wanted_array[rdi+128]
        ret

Note that it's adjusting by +128. This is because, in this case, the enum is a signed type so the index must be converted to be an unsigned value with base 0.

Answer 2

Break it down. You want functions like

key_isnumpad(), key_isalpha() and so on.

So the function tuurns into

if(key_isnumpad() || key_isalpha() || ...)

and becomes much more readable. That will actually slow it down unless you have a good optimiser. But you can then write the individual functions better, with a range (assuming numbers are contiguous).

Finally place the most likely case first.

Answer 3

Making use of the additional information gleaned from the comments that key is a char type, there are 256 possible values for key. The return value for each of the possible values of key can be stored into a global array indexed by key, and retrieved by simply returning the key'th element of the array.

char arr[256] = { 0 };
arr[BB_KEY_SPACE] = 1;
arr[BB_KEY_ZERO] = 1;
/* ... */
arr[BB_KEY_OEM102] = 1;

bool f(char key)
{
    return arr[(unsigned)key] != 0; /* == 1 for the BB_KEY_* values */
}

---

[ EDIT ] As originally suggested by @Galik in a comment, some memory could be saved (at a negligible speed penalty) by using a std::vector<bool> arr(256); instead of the char array.

---

[ EDIT #2 ] As commented by @Hurkyl and @Danh below, given that arr is an array of known, fixed size, std::bitset could (should?) be used instead of std::vector<bool>.

While this is entirely correct, the choice between them has been the subject of discussions and arguments for a long time. Searching SO and/or google'ing for std::bitset vs std::vector<bool> will find a number of opinions on both sides.

Answer 4

First and foremost, do you really need to optimise this now? Even if you do, I doubt that it is your primary bottleneck. Anyway with that said, it at the very least doesn't look pretty. To frame your question in another light, you are basically asking, how do I perform an if check on a potentially random set of values?

As you know the values in advance, your task then is to model the random data, into something more semantically useful. As mentioned in the comments and answers, you can expose properties of the data like ranges (however, the compiler might be able to manage that).

The best optimisation in my opinion here is to implement a Hash function.

Answer 5

Turn this into a switch statement:

 switch (key) {
 case BB_KEY_SPACE:
 case BB_KEY_ZERO:
 case BB_KEY_ONE:
      // ... and so on

Your compiler is very smart. If these literal constants form just a handful of ranges of consecutive integer values, the compiler will handle optimizing this into a small number of comparisons, to implement the bounds checking for each range of values.

And if not, the compiler will likely use a few other heuristical tools in order to come up with an optimized set of comparisons.

It's also possible that a modern compiler will be smart enough to use the same optimizations for the long-winded if() version, but using the switch statement helps the compiler "see the light of day", and figure out the best way to crunch through all of this.

Answer 6

If there are ranges:

if ((key >= SOME_MIN && key <= SOME_MAX) ||
    (key >= SOM_OTHER_MIN && key <= SOME_OTHER_MAX) ...

Works but you have to dive into the constants which is bad.

I'd put the matching key constants into a set and then I can just say something like if (keySet.contains(key)). Of course you set the set up once at startup, not every time you want to check a key.