10

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?

15 Answers 15

32

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!

5
  • 7
    +1. I frequently de-optimize the boolean tests in my code, specifically for readability.
    – Cheeso
    Jun 11, 2009 at 15:45
  • 4
    A compiler cannot optimize the logic of expressions without causing evaluation at different times. See firoso's answer. It may be smart enough to know when it is not smart enough though.
    – Kekoa
    Jun 11, 2009 at 16:06
  • 3
    I can agree that there are situations in which the compiler can safely optimize, but as a general rule, it can't and won't. This question is not very helpful, it's much closer to a warm fuzzy "don't worry about it" feel good answer.
    – Firoso
    Jun 11, 2009 at 16:14
  • 1
    Actually compilers can, if they can determine by walking the AST that the expression has no side-effects or is constant, they are free to rearrange the expression. Just like if I write "if (false || false && true)", the compiler can simplify the expression to "if (false)", then never take the branch
    – Ana Betts
    Jun 11, 2009 at 22:19
  • "Optimization is the art of lying --- and not getting caught."
    – Jim Blandy
    Sep 9, 2010 at 16:21
8

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.

7

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.

7

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.

3
  • 1
    Demorgan's shouldn't change the execution. Because the logic gets flipped around. !(!A && !B) still only executes B if A is false. Jun 11, 2009 at 18:26
  • @BenjaminAutin I was wondering about that. Is the behavior you described typical in most languages which implement short-circuiting, or unique to C#? May 30, 2016 at 9:40
  • Should be, once the end result is set, why do any more work than necessary? May 31, 2016 at 16:16
3

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.

3

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.

3

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 expression is evaluated, even if it isn't needed. Turning around that statement skips the file check if useFileScan is false:

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

DeMorgan's 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.

2

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.

2

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.

1
  • 2
    the counter example is fnThatHitsDB && flagVar c# will hit the db before it checks the local variable.
    – BCS
    Jun 11, 2009 at 17:00
2

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();
1

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)
2
  • 1
    Whoever wrote that isn't ready for de Morgan and Karnaugh yet. Let's get the basic stupidities out of the way, and then write for readability. Jun 11, 2009 at 16:32
  • Yikes! I suppose the "&& false" could be left-over debugging logic ('temporarily' ensuring that the if block isn't executed), but it's surprising how often you run across cruft like this. Jul 3, 2013 at 4:48
1

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.

0

First deal with maintainability, and high-level optimization.

Then deal with low-level optimization.

0

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.

0

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)

Your Answer

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

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