Is it useful in C# to apply DeMorgan's theorem to manually optimize boolean expressions in conditional statements (e.g. if conditions)

Question

Back in the day when I did most of my work in C and C++, as a matter of course, I would manually apply deMorgan's theorem to optimize any non-trivial boolean expressions.

Is it useful to do this in C# or does the optimizer render this unnecessary?

Answer 1

On processors this fast, it's virtually impossible for rearranging boolean expressions to make any actual difference in speed. And the C# compiler is very smart, it will optimize it as well. Optimize for readability and clarity!

Answer 2

I guess the compiler will do that already. You can do the test and look at the compiled IL via Reflector.

Optimize for readability and maintainability. Ask yourself if you will understand your clever optimization in a year and if you think, the code could use some comments, make the code self documenting.

Answer 3

Take readability and maintenance into account. If you have a rather complex set of boolean expressions that are difficult to read, DeMorgan's theorm might be a great approach to reducing the expression to something easier to read/maintain but that is still valid/consistent with the original expressiom.

If on the other hand, a more verbose expression is much easier to read and reducing the expression, while logically equivelant, makes it more difficult to understand, leave it as is.

Answer 4

Your first goal should be to optimize such statements for developer comprehension and ease of maintenance.

DeMorgan's theorem can be a useful tool for this.

Answer 5

The optimization in the JIT, in its current form, does not (from what I've read) optimize this for you. If you need to optimize it, you would need to still take this into account.

That being said, this is a fairly small micro-optimization. In general, I'd prefer to write your "non-trivial boolean expressions" in a more expressive form so they are easier to understand. To me, this is more valuable than any very small optimization you'll get from applying deMorgan's theorem.

Answer 6

In almost all practical cases I can think of, the arrangement of boolean operators has no noticeable effect on the overall performance. If your program waits for the database, the network etc. it will spend by far more time there than in those tiny operations. Should you write a program where it really makes a difference, better skip C# and use C++ instead.

Answer 7

I agree with the general statements that Readability and Maintainability are most important when it comes to optimizing boolean expressions these days. Therefore, DeMorgan's theorem is generally very useful.

There is one exception to this rule. If the boolean expression changes a Demorgan's Theorem-optimized expression it might be more difficult to maintain. Consider an expression with several inputs that has been optimized to only show a few boolean conditions. One change to the required boolean logic might force someone to again list out all the possible boolean combinations and then reoptimize. Had the expression been left in an unoptimized format, a change would have taken less steps to complete.

More from an anecdotal perspective, I wonder if educating a team about DeMorgan's Theorem and Karnaugh Maps, etc would reduce unnecessary/inefficient boolean expressions. Perhaps if someone has a good understanding of these methods, he/she will tend to produce better expressions. For example, I recently came across this boolean expression in the code of the software I maintain:

if ({boolean variable} != true && false)

Answer 8

I believe that the correct answer to this question is that the compiler does not (normally) optimize boolean evaluations, simply due to logical short circuiting, for instance:

if (GetFlagA() || GetFlagB())
{
   ...do something
}

The order of that if evaluation can really matter if calling GetFlagA modifies something that GetFlagB relies on (granted this is REALLY bad code practice, but that's a different topic for a different thread.) The problem here is logical short circuiting, if GetFlagA runs and returns true, GetFlagB will never run, as seen here the outcome of GetFlagB is inconsequential to the evaluation of the statement.

A | B | =

F | F | F

F | T | T

T | F | T true regardless of B's return val.

T | T | T true regardless of B's return val.

So in summary, asking if you can optimize by using Demorgan's or anything really is just like the rest of computer science and software engineering. "It depends." if you're using non-functional evaluation, it can probably be optimized. Honestly tho you're talking a few operations on an insanely fast platform, you'd be better off spending your time writing documentation.

I hope this helps.

Answer 9

The only time you should do rearranging, boolean algebra or demorgan's is when the logic is too complex to do it another way. If it is not too complex, keep it readable. There is a case for simplifying the logic.

Sometimes when the logic is tricky I need to create a Karnaugh Map to simplify the logic down to something that I can even write down. Often, using K-Maps can help you to come up with more succinct ways of expressing your logic. The result may or may not make sense, but it will be equivalent.

And I would also say that DeMorgan's itself really isn't an optimization that will make a difference, If more than half of the terms are negative(NOT), you will at best get the performance of removing a few NOT's, which is a single instruction for a CPU per NOT. At worst, you can add as many NOTs as you take away, and if you shouldn't have use DeMorgan's you will get more NOTs than you had in the first place.

If you're going to optimize logic, use some boolean algebra, or my personal favorite K-Maps to reduce the number of terms(if possible). Don't just move the boolean operators around, it's silly.

Answer 10

First deal with maintainability, and high-level optimization.

Then deal with low-level optimization.

Answer 11

DeMorgan by itself may be totally irrelevant in the presence of short circuit evaluation.

return !(exp1 || exp2);
return !exp1 && !exp2;

get compiled to

if(   exp1 ) return !(true); else return !(exp2);
if(!(!exp1)) return   false; else return !(exp2);

with the nots canceled and constants folded, these are identical.

The more important case is order of evaluation; put cheep things that are likely to trigger short circuits at the front of expressions. The compiler can't optimize this for you because it is hard for it to detect semantic issues like side effects or if later expression make assumptions based on earlier ones:

return validState() && checkAssumuingValidState();

Answer 12

For all us non-CS majors:

wikipedia on De Morgan's laws:

De Morgan's laws are rules relating the logical operators "and" and "or" in terms of each other via negation, namely:

NOT (P OR Q) = (NOT P) AND (NOT Q)
NOT (P AND Q) = (NOT P) OR (NOT Q)

Answer 13

De Morgan's law is useful for reducing it to a normal form, e.g. Disjunctive normal form (DNF) or conjunctive normal form (CNF). Basically this means that it's either

DNF: (a and b and c) OR (e and f and g) ...

or

CNF: (a or b or c) AND (e or f or g) ....

You can throw the NOT's in at the lowest level.

I agree with the previous posters that you should optimize for readability and comprehension.

Answer 14

The C# optimizer can't really do too much given the short-circuiting rules for logical expression evaluation. So applying DeMorgan's Law won't do much unless it allows you to see other useful refactorings (and of course it can help make your code clearer).

But there are cases where you can make substantial performance improvements with other kinds of expression optimization. For instance these conditions should be swapped

if ( costly_boolean_function() && cheap_often_false_boolean_function() )

SQL query optimizers do this as a matter of course, since SQL doesn't have short-circuiting. A query optimizer will aggressively rearrange conjunctive WHERE clause predicates (of the form c1 AND c2 AND ... cn) to put the least expensive conditions first, since they may evaluate to false and obviate the need to evaluate the more expensive ones.

Answer 15

Since boolean expressions evaluation uses shortcut semantics, you can move subexpressions that are cheaper to calculate to the front:

if (CountAllFilesOnDrive('C:\') > 7 && useFileScan) { ... }

will run the expensive call anytime the expresison is ewvaluated, even if it isn't needed. Turning around that statement skips the file check if useFileScan is false:

if (useFileScan && CountAllFilesOnDrive('C:\') > 7) { ... }

DeMorgan might help you move "early exits" to the front, and thus get better average performance.

Note that due to the guarantee of left-to-right evaluation, the optimizer doesn't have much freedom to modify the expression.