What is the fastest algorithm for permuting three conditions?

Question

Can someone help me regarding the fastest method for evaluating three conditions in minimal steps? I have three conditions, and if either of the two is true, then the whole expression will become true else false .

I tried two methods:

 if ((condition1 && condition2) || (condition1 && condition3) || (condition2 && condition3)) 

Another way is to introduce the variable i and

 i = 0; if (condition1) i++; if (condition2) i++; if (condition3) i++; if (i >= 2) //do something 

I want any other effective method better than the previous ones.

I work in a limited memory environment (Atmeta8 with 8 KB of flash memory) and need a solution that works in C.

Answer 1

It is always difficult to give just the “best” solution (better in what respect - lines of code, readability, speed of execution, number of bytes of machine code instructions ...?), But since you are asking about speed of execution in this case, we can focus on this .

You can enter this variable that you propose and use it to reduce the conditions to simple, less than the conditions, as soon as the answer is known. Less than conditions trivially translate into two machine code commands on most architectures (for example, CMP (cf.), followed by JL (jump, if less) or JNL (jump, if not less) on Intel IA-32). With little success, the compiler will notice (or you can do it yourself, but I prefer clarity, which has the same pattern everywhere), that trues < 2 will always be true in the first two if() operations and will optimize it.

 int trues = 0; if (trues < 2 && condition1) trues++; if (trues < 2 && condition2) trues++; if (trues < 2 && condition3) trues++; // ... if (trues >= 2) { // do something } 

This, as soon as the answer is known, reduces the possible complex evaluation of conditionN to a simple smaller one than the comparison, due to the logical short circuit of most languages.

Another possible option, if your language allows you to use a logical condition for an integer, is to use it to reduce the number of lines of source code. However, you will still evaluate each condition.

 if( (int)(condition1) + (int)(condition2) + (int)(condition3) >= 2) { // do something } 

This works on the assumption that casting the boolean value FALSE to an integer results in 0, and the result of TRUE results is 1. You can also use the conditional operator for the same effect, although keep in mind that it may introduce additional branching.

 if( ((condition1) ? 1 : 0) + ((condition2) ? 1 : 0) + ((condition3) ? 1 : 0) >= 2) { // do something } 

Depending on how smart the compiler optimizer is, it can determine that as soon as any two conditions evaluate to true, the whole condition will always be evaluated as true and optimized based on this.

• Please note that if you have not really profiled your code and identified it as the culprit , this is probably a case of premature optimization. Always strive to ensure that code is read by human programmers in the first place and quickly executed by a second computer, unless you can show conclusive evidence that the particular piece of code that you are looking at is the actual performance bottleneck. Find out how this profiler works and uses it well. Keep in mind that in most cases, the programmer’s time is much more expensive than the processor’s time, and smart methods take longer for the maintenance programmer to analyze.
• In addition, compilers are really smart pieces of software; sometimes they actually discover the intent of the written code and may use specific constructs designed to speed up these operations, but rely on the fact that they can determine what you are trying to do. A great example of this is replacing two variables using an intermediate variable, which on IA-32 can be done using XCHG , which excludes the intermediate variable, but the compiler should be able to determine that you are actually doing this, and not something smart, which may give a different result in some cases .
• Since the vast majority of written implicitly deferred software spends most of its life in maintenance mode (and a lot of the written software that was written was lively and well last year than previously thought), it makes sense to optimize for maintainability if it does not bring unacceptable costs in other respects. Of course, if you evaluate these conditions a trillion times in a tight loop, targeted optimization can make sense very well. But the profiler will tell you exactly what parts of your code need to be carefully studied in terms of performance, which means that you avoid unnecessarily complicating the code.

And the above warnings said that I am working on a code that has been making changes lately, which at first glance will almost certainly be considered premature detailed optimization. If you have a high performance requirement and using a profiler to determine which parts of the code are bottlenecks, then optimization is not premature. (However, they may be dishonest depending on the specific circumstances.)

Answer 2

This can be reduced to:

 if((condition1 && (condition2 || condition3)) || (condition2 && condition3)) //do something 

Depending on the likelihood of each condition, you can optimize the order to get shorter faults (although this is likely to be premature optimization ...)

Answer 3

Depending on your language, I may resort to something like:

 $cond = array(true, true, false); if (count(array_filter($cond)) >= 2) 

or

 if (array_reduce($cond, function ($i, $k) { return $i + (int)$k; }) >= 2) 

Answer 4

There is no absolute answer to this question. It depends a lot on the underlying architecture. For example. if you program some hardware circuit in VHDL or Verilog, then the first one will probably give you the fastest result. I assume that your goal is some kind of processor, but even here a lot will depend on the target processor, the instructions that it supports, and what time they will receive. Also, you will not indicate your target language (for example, your first approach may be shortened, which can greatly affect speed).

If I don’t know anything, I would recommend the second solution - only for the reason that your intentions (at least 2 conditions must be true) are better reflected in the code.

The difference in speed between the two solutions will not be very high - if it is just some kind of logic, and not part of some inner cycle that runs many times, I even guess about premature optimization and try to optimize somewhere else.

Answer 5

Since we are not deeply pipelined, there is probably no value in preventing branching, which typically drives the optimizations offered by desktop developers. Short cuts here are golden.

If you go for:

 if ((condition1 && (condition2 || condition3)) || (condition2 && condition3)) 

then you probably have a better chance, without any additional information, to get the best machine code from the compiler. It is possible in the assembly to make it as if the second evaluation of condition2 returned to the first evaluation of condition3 to reduce the size of the code, but there is no reliable way to express this in C.

If you know that you usually fail the test, and you know which of the two conditions usually cause this, then you may prefer to write:

 if ((rare1 || rare2) && (common3 || (rare1 && rare2))) 

but there are still good chances that the compiler will completely rebuild this and use its own shortcut layout.

You may like to comment things out with __builtin_expect() or _Rarely() or whatever your compiler provides to indicate the likely outcome of the condition.

However, it is much more likely to significantly increase productivity - it is the recognition of any common factors between conditions or in any way in which conditions can be tested in such a way as to simplify the overall test.

For example, if the tests are simple, then in the assembly you can almost certainly make some basic hyphenation tricks to quickly copy the conditions. Porting back to C is sometimes viable.

Answer 6

You might consider adding simpy. If you use masroses from the standard stdbool.h , then true is 1, and (condition1 + condition2 + condition3) >= 2 is what you want.

But this is still a simple microoptimization, usually you do not get a lot of performance with these tricks.

Answer 7

You seem to want to evaluate all the conditions, since you yourself have proposed such a solution in your question. If conditions are very complex formulas that take many CPU cycles to calculate (for example, on the order of hundreds of milliseconds), then you can consider evaluating all three conditions at the same time as threads to get acceleration. Something like:

 pthread_create(&t1, detached, eval_condition1, &status); pthread_create(&t2, detached, eval_condition2, &status); pthread_create(&t3, detached, eval_condition3, &status); pthread_mutex_lock(&status.lock); while (status.trues < 2 && status.falses < 2) { pthread_cond_wait(&status.cond, &status.lock); } pthread_mutex_unlock(&status.lock); if (status.trues > 1) { /* do something */ } 

Whether this will give you acceleration depends on how expensive the calculation of conditions is. Calculation time should dominate overhead creation and synchronization flows.

Answer 8

Try the following:

 unsigned char i; i = condition1; i += condition2; i += condition3; if (i & (unsigned char)0x02) { /* At least 2 conditions are True 0b00 - 0 conditions are true 0b01 - 1 conditions are true 0b11 - 3 conditions are true 0b10 - 2 conditions are true So, Checking 2nd LS bit is good enough. */ }