3

The C# language has two "AND" operators when dealing with Boolean values, & and &&. (Leaving aside the bit-wise operators.)

When the left-hand value is False, the difference between these two operators regards the evaluation of the right operand.

Consider (false && x) vs (false & x)
&& means the right hand side must not be evaluated.
& means the right hand side must be evaluated.

Decades ago, you'd always use the equivalent of && because it would avoid spending the time uselessly processing that right-hand-side when we already know the answer. In this day and age however, we have CPUs that are already processing the next line of code before the previous line has finished. This has to come to a stop when a branch is reached, so you might want to use & to avoid that branch in the code and allow the CPU to speed ahead unimpeded.

(Two quick side-bars: Sometimes, you need to use && because the left hand side protects against unwanted side effects of the right hand side, such as checking NULL to avoid a null-reference error. I'll also acknowledge that the compiler may be smart enough to sometimes know that the right-hand of a && operation is side-effect-free so it can eliminate the branch instruction. These are beyond the scope of this question.)

So there's the background, here's my question.

Are there any languages or environments that have established a compromise between && and & that leave it up to the compiler/run-time to decide if the right-hand side needs to be evaluated?

Given a AND b, the programmer would be saying that the compiler/run-time may evaluate b if a branch is too costly, but is also explicitly permitted to branch around the work of evaluating b if doing so would be greater than the work of the branch instruction.

4
  • 5
    "This has to come to a stop when a branch is reached" - Not necessarily. Some CPUs can do speculative execution, basically executing both branches, but not committing the results until the correct branch is determined. Branch prediction is another variant of speculative execution, in which the CPU predicts which branch is more likely and goes ahead and executes that one, only later learning if it was right. This is cheaper than executing both, but means a misprediction is as slow as just waiting until the branch instruction finishes.
    – 8bittree
    Jul 28, 2017 at 17:25
  • @8bittree - Indeed. The point is though that a branch introduces a cost that would be worthwhile avoiding if possible, and small optimizations like that are best done by the compiler instead of me choosing between && and &.
    – billpg
    Jul 29, 2017 at 9:53
  • @8bittree You should not be using & as a substitute for &&, under any circumstance. You're complicating your code, and it can be easy to miss that the right hand side is being evaluated. I certainly wouldn't let it pass code review. & has a purpose for bit manipulation, and it's good for that. It is not meant to be part of your control flow logic like this.
    – Alexander
    Jul 30, 2017 at 17:32
  • @Alexander I think you @-mentioned the wrong person, since my comment said nothing about & nor &&.
    – 8bittree
    Jul 30, 2017 at 17:38

1 Answer 1

6

There are languages like Haskell which make very little guarantees about evaluation. Haskell only guarantees that evaluation is non-strict, i.e. that

f a b = b
f undefined 2

evaluates to 2. That is pretty much everything Haskell guarantees. Any (sub-)expression may be evaluated any number of times (or never).

However, languages which do this are usually pure, which means that you cannot actually tell how often any particular (sub-)expression was evaluated.

This is also done in some superscalar or parallel CPUs, where the condition of a branch may depend on some data that is computed by some other (part of the) CPU and isn't available yet, and instead of stalling the pipeline, the CPU will execute both branches and simply throw away one of two execution strands as soon as the condition becomes available. This is called speculative execution.

An extremely aggressive implementation of this is found in Intel's Itanium CPUs, which may on some benchmarks throw away up to 80% of results. (This is one of the reasons they are so power hungry, after all, this means that it produces 5 times more heat than necessary to compute the result.)

Your Answer

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

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