Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have 3 simple predicates and 3 simple actions to be taken based on those predicates. In my actual application they are not based on integer arithmetic, and in fact are rather expensive to compute (in comparison to the actions taken), but their dependency chain is the same.

#include <iostream>
#include <tuple>

bool pred1(int x) { return x % 30 == 0; }
bool pred2(int x) { return x % 15 == 0; }
bool pred3(int x) { return x %  5 == 0; }

void fun1(int x) { std::cout << "divisible by 30 \n"; }
void fun2(int x) { std::cout << "divisible by 15 \n"; }
void fun3(int x) { std::cout << "divisible by  5 \n"; }

void fun(int x)
{
    if (pred1(x)) { 
        fun1(x);
        fun2(x);
        fun3(x);
        return;
    }
    if (pred2(x)) {
        fun2(x);
        fun3(x);
        return;
    }
    if (pred3(x)) 
        fun3(x);
}

Note that pred1 requires all 3 actions, pred2 the last 2 actions, and pred3 only the 3rd action. I was not happy with this code: while efficient in avoiding extra work, it seems overly repetitive.

However, the following straightforward try at refactoring is a lot more concise but also less efficient as it computes all 3 predicates for all inputs:

// exposition only: will compute pred1, pred2 and pred3 for all inputs
void hun(int x)
{
    if (pred1(x)) fun1(x);
    if (pred2(x)) fun2(x);
    if (pred3(x)) fun3(x);        
}

So I came up with the idea of caching the predicate values in a std::tuple and dispatch the various actions based on that:

using Triple = std::tuple<bool, bool, bool>;

auto preds(int x) -> Triple
{
    if (pred1(x)) return Triple{ true,  true, true };
    if (pred2(x)) return Triple{ false, true, true };
    return Triple{ false, false, pred3(x) };
}

void gun(int x)
{
    auto const p = preds(x);
    if (std::get<0>(p)) fun1(x);
    if (std::get<1>(p)) fun2(x);
    if (std::get<2>(p)) fun3(x);
}

Live Example.

So the repetitive logic is hidden inside the repeated values of true in the std::tuple, and the duplicate predicate computation is now reduced to simple lookups into the std::tuple.

Looking at the assembler from gcc.godbolt.org, it seems that the compiler even optimizes away all unnecessary calls to std::get in gun() (e.g. it sees that the remaining fields of the std::tuple will be true if the first one is), essentially reducing the code to that of fun().

Questions:

  • are there other approaches to simplying the logic of overlapping predicates?
  • is the gun() version considered more readable and maintainable than the fun() original?
  • how smart are compilers in eliminating unnecessary lookups when the underying predicates and actions are not so trivial as the ones above?
share|improve this question

3 Answers 3

It seems to me that the primary role of the programmer is to write clear and correct code and that it's largely the job of the compiler to turn that into efficient machine code. With that said, it seems to me that the first fun() version is both clear and effective in that it avoids the needless overhead of computing conditions that don't need to be computed, and is sufficiently clear about the results of each predicate.

Your gun() version separates the predicates from the actions using an intermediary Triple and while it produces the same result, it makes the job of interpreting the code (for a human) a little bit harder. So I would advocate not doing it that way.

If you'd like to reduce the repetition, the way to do that would be to create subfunctions such as this:

void do123(int x) {
    fun1(x);
    fun2(x);
    fun3(x);
}

Once this is done, the multiple if statements become a bit shorter and easier to read, although at some possible expense in clarity.

If the predicates and functions are dealing solely with integers it doesn't much matter, but if they are dealing with larger items, and particularly objects with constructors and destructors, it would be helpful to use references and const as much as possible to avoid useless object copies.

share|improve this answer
    
I like this, but only if you would define it like do123(int x) { fun1(x); do23(x); } etc. –  TemplateRex Jul 20 at 6:28

Yes, the repetition is not great. But I think the bigger problem is that fun, hun, gun all need intimate knowledge of the predicate, how to respond when predicate X is true. Even worse, they need to know the relationships between the predicates (if pred1 is true, no need to call the others).

How about building a map of predicates to list of functions:

typedef std::list<void(*)(int)> lt_fun;
typedef std::map<bool(*)(int), lt_fun> mt_pred_fun;

void fun(mt_pred_fun functions, int x) {
    for (mt_pred_fun::iterator it = functions.begin(); it != functions.end(); ++it) {
        if (it->first(x)) {
            lt_fun fx = it->second;
            for (lt_fun::iterator it = fx.begin(); it != fx.end(); ++it) {
                (*it)(x);
            }
            return;
        }
    }
}

int main() {
    mt_pred_fun functions;

    functions[pred1] = lt_fun();
    functions[pred1].push_back(fun1);
    functions[pred1].push_back(fun2);
    functions[pred1].push_back(fun3);

    functions[pred2] = lt_fun();
    functions[pred2].push_back(fun2);
    functions[pred2].push_back(fun3);

    functions[pred3] = lt_fun();
    functions[pred3].push_back(fun3);

    std::cout << 60 << std::endl;
    fun(functions, 60);
    std::cout << 45 << std::endl;
    fun(functions, 45);
    std::cout << 65 << std::endl;
    fun(functions, 65);
}

Granted, there is still the duplication of adding the same functions to the lists of multiple predicates. But at least now they are all defined in one place, and fun doesn't need to know anything about the predicates, or the order in which to evaluate them, or which functions to run.

share|improve this answer
1  
If there were a large number of predicates or actions, I'd be inclined to use a std::map as you've done, but with a smaller number as in the original code, I'd be inclined to keep it confined to the single function fun. In either case, though, I agree that isolating this knowledge to a single place is good design. –  Edward Jul 19 at 22:34
    
I like this kind of table-driven approach, but only in situations where the logic is possibly run-time dependent (e.g. in games or other simulation loops). For my code it's a little overkill. Also: please use range-for loops! –  TemplateRex Jul 20 at 6:31
up vote 1 down vote accepted

After looking in more detail to the assembler output, I think this is one of the very rare cases where the use of goto might actually be warranted (which is what the compiler is reducing the original code to):

void hun(int x)
{
    if (pred1(x)) goto START1;
    if (pred2(x)) goto START2;
    if (pred3(x)) goto START3;

    return;

    START1: fun1(x);
    START2: fun2(x);
    START3: fun3(x);
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.