Which is the more efficient syntax for NAND (not both true) in C#?

11,437

Solution 1

It is not quite as simple. The C# language doesn't model a NAND gate at all with the && operator. That operator has short-circuiting behavior, very convenient in a C# program. And common behavior for the curly-brace languages, an expression like this doesn't crash your code:

arr[] = somefunction();
int ix = foo;
if (ix < arr.Length && arr[ix] == 42) {
    EmailBookRecommendation();
}

But that's a very inefficient version of the expression, this one is way more performant:

if (ix < arr.Length & arr [ix] == 42) 

Which is a perfectly legal expression, the & operator works just fine with boolean operands. But unfortunately this one crashes your code. It evaluates the array indexing expression and that goes Kaboom! with IndexOutOfRangeException.

That's not ever a problem with a NAND gate, it doesn't crash when the first input is F :) There are many possible C# expressions where that's not a problem. You really should favor the & operator for those. It makes a huge difference. So always write something like this:

if (ix >= 1 & ix <= 42) 

Which of course can never fail. To understand why the && operator is so much more inefficient than the & operator, you have to understand branch prediction. That's covered very well in this answer.

Solution 2

Neither. They both have exactly the same short circuiting behavior, and the compiler will turn both into MSIL requesting a test of A, followed by a conditional branch. The branch where A was true will then have a test of B.

What you should be worrying about is:

!(A && B)

vs

!(B && A)

which are different in case either A or B causes side effects or complicated calculations.

The possible exception to both being the same is if you have a custom definition of operator!, in which case they aren't actually equivalent at all.

Share:
11,437

Related videos on Youtube

Matthew
Author by

Matthew

I love creating elegant software solutions to novel problems. Data is the future. Optimization is not our enemy.

Updated on September 15, 2022

Comments

  • Matthew
    Matthew about 1 year

    The NAND logic gate for two conditions (A and B) is true as long as either condition is true, or none of the conditions is true; and it is false if both conditions are true.

    F NAND F = T
    F NAND T = T
    T NAND F = T
    T NAND T = F
    

    In C# I can write this in at least two ways:

    !(A && B)
    

    or

    (!A || !B)
    

    Which is more efficient?

    It seems to me that if(A) then B is always tested and if(!A) then B is never tested.

    But then the first condition must invert the result....

    • Ben Voigt
      Ben Voigt over 10 years
      inverting the result is the same as swapping the code in the else with the code in the if... no actual runtime instruction needed
  • Matthew
    Matthew over 10 years
    assuming A and B are both bool then there is no functional difference?
  • Ben Voigt
    Ben Voigt over 10 years
    @Matthew: Assuming both A and B are local variables of type bool, there should not be any difference in the generated code.
  • Matthew
    Matthew over 10 years
    I was thinking it would depend on the likelihood of A being true but you're telling me they compile to identical code? Interesting.
  • Ben Voigt
    Ben Voigt over 10 years
    @Matthew: The definition of && and || both require the compiler to skip testing B if A is found to be false.
  • Matthew
    Matthew over 10 years
    I don't think so... A || B will test B if A is false .. It will not test B is A is true.
  • Ben Voigt
    Ben Voigt over 10 years
    @Matthew: In your question I see (!A) || (!B), not A || B. So it will test B if (!A) is false, which means only if A is true.
  • Matthew
    Matthew over 10 years
    I have edited my question, trying to explain why your assertion that they compile to the same code is confusing. I accept that they have the same short-circuit... but then doesn't the first need an additional operation to invert the result?
  • Ben Voigt
    Ben Voigt over 10 years
    @Matthew: There are two blocks of code, a then-part and an else-part. For both, the compiler will jump straight to the then-part if A is true, otherwise test B, and jump to the then-part if B is true (if not, jump to else-part). There's no operation to invert an if-statement, it just switches the jump to either the then-part or the else-part. If you wrote C = !(A || B);, it might be different, but probably not.
  • Ben Voigt
    Ben Voigt over 10 years
    @Matthew: If you do find any differences in the generated MSIL, please post them and we'll take a closer look.
  • user1703401
    user1703401 over 10 years
    This answer completely misses the point, the OP asked about efficiency.
  • Matthew
    Matthew over 10 years
    In my particular case, I am comparing integer values to literals. So it's something like if(Foo.A==CONST1 NAND Foo.B==CONST2){Bar();} So I could easily use the "&" rather than "&&" without procedural complication or slowdown. If I read you correctly it is more performant to use "&" and "predict" the resulting condition? I'm not quite sure I follow.
  • Ben Voigt
    Ben Voigt over 10 years
    @Hans: If you can't understand that two pieces of source code which compile to the same thing therefore have the same efficiency...
  • Ben Voigt
    Ben Voigt over 10 years
    Except that (1) the question didn't ask about &, and (2) && is not "much more inefficient than the & operator", it depends completely on the expressions involved.
  • Piedone
    Piedone almost 7 years
    Can you elaborate on "huge difference"?
  • Tim
    Tim almost 3 years
    I think the second answer in the question you linked to actually explains why && is good to use, or rather that sorting data intelligently pays dividends. But it depends on context. It certainly augments the first answer, and both (and the question) were informative. Why wouldn't you just write (A !& B) though? Assuming you're working with two boolean variables and not testing expressions that could have negative consequences.