Avoiding branching based on the return value of the function that is a template argument

Question

Suppose the following policy classes that take care of one aspect of an algorithm:

struct VoidF {
    static void f() {
        ... // some code that has side effects
    }
};

struct BoolF {
    static bool f() {
        bool res = ...; // some computation
        return res;
    }
};

The BoolF policy is "enhancement-aware": when BoolF::f() returns true, the algorithm can exit. VoidF is "enhancement-unaware", hence it returns void (I don't want to force the user of my library to return bool when it does not mean anything to him).

The algorithm is currently written like this:

template <typename F>
struct Algorithm {
    void run() {
        ... // some computation here

        if (std::is_same<decltype(F::f()), bool>::value) {
            if (F::f()) return;
        } else
            F::f(); // If F is VoidF, there should be no branching and some
                    // compiler optimizations will be enabled

        ... // more computation, unless F::f() got rid of it
    }
};

Of course, this does not work if Algorithm is instantiated with VoidF. Is there a way to fix this in a way that there should be no branching in Algorithm<VoidF>::run() as indicated by the comment?

How about `run_method(f, std::is_same{});`, with a suitably overloaded `run_method`, of course. This is known as type tag dispatching. — Konrad Rudolph, Dec 09 '15 at 18:32
Once you get the code to work, there'll be no branching on any modern compiler. `std::is_same<>::value` is a compile-time constant. Since you worry about branching - an issue that's present in assembly output - you can't ask how to avoid it without first looking at said assembly output. — Kuba hasn't forgotten Monica, Dec 09 '15 at 19:13
You may consider a namespace instead of a struct and tag dispatching — , Dec 09 '15 at 19:25
@DieterLücking How does namespace help here? Could you please try to make an answer based on your suggestion? — AlwaysLearning, Dec 09 '15 at 22:05

score 3 · Answer 1 · answered Dec 09 '15 at 20:44

Here is my own attempt to do it without SFINAE:

template <typename F>
struct Algorithm {
    void run() {
        ... // some computation here

        myRun(std::integral_constant<
              bool, std::is_same<decltype(F::f()), bool>::value>());
    }

private:
    void myRun(std::true_type) {
        if (F::f()) return;
        moreComputation();
    }

    void myRun(std::false_type) {
        F::f();
        moreComputation();
    }

    void moreComputation() { ... }
};

you could flip it and use `is_void` to shorten it a bit. – Ryan Haining Dec 13 '15 at 04:50 — Ryan Haining, Dec 13 '15 at 04:50

Guillaume Racicot · Accepted Answer · 2015-12-09T19:08:06.650

2

You should use SFINAE instead of branching at runtime.

You function run should look like this:

template <typename F>
struct Algorithm {

    void run() {
        ... // some computation here

        doRun();
    }

    template<std::enable_if_t<std::is_same<decltype(F::f()), bool>::value, int> = 0>
    void doRun() {
        if (F::f()) {
            // do some more computations if needed or simply remove the if and return
        }
    }

    template<std::enable_if_t<!std::is_same<decltype(F::f()), bool>::value, int> = 0>
    void doRun() {
        F::f();

        ... // more computation, unless F::f() got rid of it
    }
};

edited Dec 09 '15 at 19:08

answered Dec 09 '15 at 18:35

Guillaume Racicot

39,621
9
77
141

This means that I need to factor out all the other stuff from the `run` function to avoid duplication of code, which is awkward, will necessitate more argument passing and may preclude compiler optimizations if things are not inlined back in... Is there a way to get away without having two different `run` functions? – AlwaysLearning Dec 09 '15 at 18:44
Do not repeat yourself, that's for sure. The compiler will be able to optimize the additionnal function call, especially if you use perfect forwarding for your arguments. – Guillaume Racicot Dec 09 '15 at 18:48
Edited the answer, it should better suit your code now – Guillaume Racicot Dec 09 '15 at 18:53
This does not perform the enhancement: the last part of the `run` function is executed even when `F::f()` returns `true`. – AlwaysLearning Dec 09 '15 at 18:55
@AlwaysLearning: If you're worried about an extra function call, then you might need to put the functionality for your pre and post-processing into a macro, and then use that macro in your specializations. – AndyG Dec 09 '15 at 19:07
I changed where the `...` so it removes the need of always excuting the last part. I also added a comment that you can also remove the if altogether if you always return when the return type is bool – Guillaume Racicot Dec 09 '15 at 19:10
@AlwaysLearning: What you are asking for is precisely the subject of the [C++17 proposal for `constexpr_if`](http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2015/p0128r0.html). So it's not possible to do it exactly as you want in C++14. For now, you have to use the SFINAE method. – Nicol Bolas Dec 09 '15 at 19:18
@GuillaumeRacicot Oh, I see. Wouldn't it be simpler to do tag dispatch on `::value`? (i.e. `doRun` would be a non-template function with a tag parameter) – AlwaysLearning Dec 09 '15 at 20:23
Depend on what you want to do. tag dispatching is indeed convenient but require that both function are compatible with the bool AND the void return type, because the compiler will compile both expression on template initialization. That's why I usually go for sfinae – Guillaume Racicot Dec 09 '15 at 20:30
@GuillaumeRacicot Not sure I understand. I meant a solution as in my answer: http://stackoverflow.com/a/34188605/2725810 – AlwaysLearning Dec 09 '15 at 20:45
@AlwaysLearning The compiler will have to compile both method for each template initializations. Sometimes, that's not something you want. Both answers are equally good with the informations and goals you given in this question. – Guillaume Racicot Dec 09 '15 at 20:53
@GuillaumeRacicot The compiler compiles only the methods of the template class that get called -- the other methods don't ever get instantiated, do they? – AlwaysLearning Dec 09 '15 at 21:32
I think you're right on this one indeed. Sorry if I momentarily misleading you. – Guillaume Racicot Dec 09 '15 at 21:35

score 0 · Answer 3 · edited May 23 '17 at 12:03

0

A variation of Guillaume Racicot's answer:

template <typename F>
struct Algorithm {

    void run() {
        ... // some computation here

        if(doRun())
            return;

        ... // more computation, unless F::f() got rid of it
    }

    template<std::enable_if_t<std::is_same<decltype(F::f()), bool>::value, int> = 0>
    bool doRun() {
        return F::f();
    }

    template<std::enable_if_t<!std::is_same<decltype(F::f()), bool>::value, int> = 0>
    bool doRun() {
        F::f();
        return false;
    }
};

The type of F is known at compile time. So in case of VoidF the compiler knows that doRun will always return false and thus should remove all branching code during optimization.

Update: So you're not guaranteed that there will be no branch. But it should be a pretty easy case for the optimizer.

edited May 23 '17 at 12:03

Community

1
1

answered Dec 09 '15 at 19:09

m3tikn0b

1,298
8
16

With tag dispatching it might be easier to call a helper function to simplify the template constraining. For example: http://coliru.stacked-crooked.com/a/03a86e336355c50e However this approach always branches, which is the problem the OP is trying to solve. Good point about the optimizer, though. – AndyG Dec 09 '15 at 19:14
This is what I wanted to do originally. See my earlier post: http://stackoverflow.com/q/34185286/2725810 – AlwaysLearning Dec 09 '15 at 20:26

Avoiding branching based on the return value of the function that is a template argument

3 Answers3

Linked