1

I have this code

class Foo {

private:

    enum class Heuristic {
        ONE,
        TWO,
        THREE
    };

    Heuristic h;

    void select();

};


void Foo::select() {
    if (h == Heuristic::ONE)
        selectONE();
    else if (h == Heuristic::TWO)
        selectTWO();
    else
        selectTHREE();
}

void selectONE() {};
void selectTWO() {};
void selectTHREE() {};

Based on the value of heuristic I want to call a specific function in select(). I don't know the value of heuristic at compile time, as it depends on user input. To avoid the conditional check in select() I would like to use templates. How can I accomplish this?

Improve this question
7
  • 1
    Why don't you want conditions checks? What's wrong with them? If you don't know it at compile time, there s no performance improvement or so. Commented Jan 26, 2021 at 14:34
  • 2
    You can't avoid checking the value, but you can use a switch statement instead which the compiler can potentially optimize better via jump table. Commented Jan 26, 2021 at 14:35
  • @Mgetz By using a lookup array you can avoid checking the value. It becomes a simple pointer arithmetic addition instead, so there is no branching and it's probably as fast as it can get. Commented Jan 26, 2021 at 15:31
  • @TedLyngmo that's basically what a jump table is, but it doesn't require construction. Commented Jan 26, 2021 at 15:44
  • @Mgetz True - the best thing for speed would probably be to avoid that completely and to just store the the selected function in a function pointer. Commented Jan 26, 2021 at 16:02

3 Answers 3

Reset to default
4

As it depends on runtime values there is no way to get rid of some sort of runtime checks. Which are either done by you with if, switch, … or by a container like std::map, std::unordered_map

Due to that, your concern there should be readability and maintainability.

I would - like already suggested in a comment - use switch instead of if, but not because the compiler can optimize it better (IMHO the compiler will be able to generate the same code for both), but to allow the static analyzer to warn you about not used enums.

If the question is about performance concerns, then this should only be a problem if you call these functions at a high frequency. So if this is the case you could create a template-based entry point to your task, to which you pass the function as template argument based on the user selection:

template<auto SelectedHeuristic>
void Foo::task() {
   for( /* … */ ) {
      SelectedHeuristic();
   }
}

void Foo::select() {
    switch(h) {
       case Heuristic::ONE:
          Foo::task<selectONE>();
          break;
       case Heuristic::TWO:
          Foo::task<selectTWO>();
          break;
       case Heuristic::THREE:
          Foo::task<selectTHREE>();
          break;
    }
}

void selectONE() {};
void selectTWO() {};
void selectTHREE() {};
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Yes, this question is mainly about performance concerns. I'm writing a SAT solver for a university class, so speed is all that matters. The literal selection heuristic is chosen by the user, but it doesn't change throughout the execution of the program. That's why I wanted to avoid a if or switch statement, as this function will be executed very frequently and the heuristic doesn't change anyways.
@philhimself In that case you would make the entry point to your solver template-based, and pass the heuristic to it as template argument, based on the user selection.
@philhimself it seems you're asking a bit of an X/Y problem question then. As what it sounds like you really need to do is find a way to cache these decisions after the user has made them. v-tables aren't a bad way to do it etc. But honestly, I'd profile before I try to micro-optimize anyway
@philhimself the auto in template<auto SelectedHeuristic> is a c++17 feature which might be important to know.
vtable can be a problem (depending on what those functions do) with respect to optimization/inlining. But there might not be a big difference between the if/switch version and the template-based version. But yes there the only way to figure that out is profiling @Mgetz
2

To avoid the conditional check in select() [...]

A simple way to avoid all conditional checks (hidden or otherwise) in select() could be to create an array of pointers to your functions. You then look the function up by using its current Heuristic value (which must start at 0 and not have any gaps). If the Heuristic value changes rarely, you can even move the lookup out of select() completely.

Example:

##include <iostream>

void selectONE() { std::cout << "one\n"; };
void selectTWO() { std::cout << "two\n"; };
void selectTHREE() { std::cout << "three\n"; };

using func_ptr_t = void(*)(); // the signature of your functions

class Foo {
public:
    enum class Heuristic {
        ONE,
        TWO,
        THREE
    };

    void set_heuristic(Heuristic); // a function to do the lookup
    void select();

private:
    Heuristic h;
    func_ptr_t current_func;       // a  pointer to the selected function 
};

void Foo::set_heuristic(Heuristic value) {
    // a simple map from Heuristic value to function pointer
    static const func_ptr_t funcmap[] = {
        &selectONE,
        &selectTWO,
        &selectTHREE,
    };

    h = value; // perhaps not needed?

    // look up the function pointer based on "h"
    current_func = funcmap[static_cast<unsigned>(h)];
}

void Foo::select() {
    // a pretty fast callsite:
    current_func();
}

int main() {
    Foo bar;
    bar.set_heuristic(Foo::Heuristic::ONE);
    bar.select();   // prints "one"
}
Improve this answer

4 Comments

Doesn't a static function variable give some additional runtime costs? A static member of the class would be my first choice.
@super It costs when it's first used. Nothing after that if I'm not mistaken. If it's not used, it won't cost anything.
The cost of a static inside a function can be high, though, since it has to be initialized in a thread safe manner (i.e. it has to lock a mutex). It would be much better to initialize that table at compile time. If you want to protect it, use an unnamed namespace.
@AlexisWilke Yes, if this was a threaded program, it'd probably be cheaper to make the initialization of the map outside the function.
0

define a map<Heuristic, lambdas> where the lambdas are defined as void and taking no parameters

void f()

then take the user input and get the value of that input key and trigger the lambda

Improve this answer

8 Comments

I recommend unordered_map, which has O(k) access, not O(log(n))
This doesn't really get rid of the compare, it just hides it and potentially creates other issues if they add more values later. Wouldn't a switch be a better answer?
@ΦXocę웃Пepeúpaツ "in a map you dont have to compare" - Not for equality, but operator< is used to compare the keys.
You don't but the map is doing compares, so it doesn't actually remove that. It also has the issues with default values (or lack there of).
... probably making code unnecessary complex. I think it's better to help the OP realize that nothing is wrong with a conditional statement.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.