Why do relational comparison operators never short-circuit?

Question

I just thought about the possibility for the less-than and-greater than operators to short-circuit. That is, they can skip evaluating their second operand if the value of the second operand logically makes no impact on the overall result. Short-circuit evaluation is generally limited to logical OR and logical AND, because for OR, if the first operand is true, the result will be true regardless the value of the second operand, so it does not need to be evaluated. Similar goes for logical AND.

However, what if the first operand of a less-than-or-equal happens to be the minimum value of a type? Or if the first operand of a greater-than happens to be said minimum value? In these cases, there is no value of the second operand that will make the value anything other than true or false respectively. Here are more examples:

INT_MIN <= x; // true
INT_MIN > x; // false
INT_MAX >= x; // true
INT_MAX < x; // false

Note that here INT_MIN or INT_MAX indicate the values at runtime, not compile-time constants.

These expressions will hold no matter the value of X. So why is it that no language I have know of seems to have short-circuiting behavior for relational comparisons?

Answer 1

The saving is rare

The benefit of short-circuiting is that you don't have to compute the second operand. But there is only one value the first operand can have where short-circuiting is possible ─ either INT_MIN or INT_MAX depending on the comparison operator ─ and the most commonly-compared types (ints and doubles) have so many possible values that this one specific value is very rare. Or in many cases, that specific value might never occur, due to what the number is supposed to represent. (But the compiler won't know this.)

But in order to short-circuit, another comparison like == INT_MIN must be done, and there must be a branch on the result of that comparison. Even if the branch predictor figures out that the short-circuiting branch is never (or very rarely) taken, that extra comparison isn't free, and it can only very rarely be beneficial to do it.

The saved computation is usually cheap

The way humans think about code, means that we tend to write things like something <= 100 or something() <= something_else, where the second operand is a constant or a simple load. This way of writing code is much more common than e.g. 100 >= something.

So the second operand is usually fast to evaluate, and there is little benefit in eliding it; most of the time, evaluating the second operand will be faster than the extra == INT_MIN comparison you would have to do in order to short-circuit it.

People expect the second operand's side-effects to be unconditional

Suppose you have something like stack.pop() <= stack.pop(), where the second operand has a side-effect. Humans who read or write code like this will expect two values to be popped from the stack. Short-circuiting behaviour in this case would be a source of subtle, rare bugs.

This argument only applies if short-circuiting is part of the semantics of the comparison operators; there'd be no such problem in an optimising compiler which only inserts the short-circuit when it can prove the second operand is side-effect-free.

Answer 2

The primary reason for the existence and popularity of && and || is suppression of the right side effect, not efficiency. If you know that your hardware can evaluate both sides efficiently, it is likely faster to replace them with their eager variants. Most people do not understand this and I've encountered style guides as a professional developer that forced me to revert such changes.

The primary use case of such operators is something like null == x || x.f(). Also, && is essentially chaining of nested if statements without else.

Performing your proposed optimization at runtime is more expensive than the eager operator and I do not see any common pattern that would make it useful to drop the side effect in comparisons. Most index uses are offloaded to library functions anyway.

I would expect that most compilers will transform comparisons that are known to be true or false to just the side effect and the result.

Answer 3

It is not the case that relational comparison operators never short-circuit in any language. We can define this toy Haskell type and its comparison relationship to illustrate:

newtype IndexList a = IndexList [Int] deriving (Show, Eq)
instance Ord (IndexList a) where
  IndexList [] <= _ = True
  _ <= IndexList [] = False
  IndexList (h1:t1) <= IndexList (h2:t2) = if h1 /= h2 then h1 < h2 else IndexList t1 <= IndexList t2

This type is a specialised list of integers, and it's defined to compare lexicographically with empty lists less than all other values. It could be any user-defined type, including those with nontrivial structure and comparison logic.

We can test whether this short-circuits or not:

ghci> IndexList [] <= undefined
True
ghci> IndexList [1..] <= IndexList []
False

If the right-hand side were evaluated, there would be an exception reported on the first line (because that's what undefined does when you evaluate it), and the second would never terminate if the left-hand side were fully evaluated.

I'm not sure which of those you'd consider short-circuiting, but in both one side of the relational operator is left unevaluated due to the result being predetermined by the other side. It's exactly how False && undefined short-circuits too.

---

This arises out of Haskell's non-strict (~lazy) evaluation, and any language following this evaluation strategy could have the same behaviour. It is possible to create it in R, for example, although a little more awkwardly. This is a more general effect than purely the relational operators, but they are an obvious case where it can come up. That generality also means many of the associated costs are already paid.

The built-in primitive types in GHC aren't defined this way (they implement the alternative compare method, which returns less/equal/greater and very infrequently has a short-circuitable answer), likely for efficiency of compilation in typical cases, but it can come up in other types. Any situation where there is a clear base case is liable to be defined in a similar way to above, and thus to short-circuit, as is any with recursive comparison logic (like the built-in list type).

Answer 4

You Might Surprise the Programmer by Preventing Side-Effects

Let’s say your C compiler reads the line:

if (printf("hello, world!") > 0) {

and (metaphorically) thinks, “I’m so smart, I know for a fact that this implementation of printf() on this format string will always return a positive value. So, the comparison is always true. No need to call printf()!” Is this the intended behavior?

Note: if you’re only considering the form of “short-circuiting” that calculates the left operand first, checks it at runtime, and evaluates the right operand only if necessary, this introduces a host of problems over and above the kind of optimization I’m talking about. (And, in that case, just flip the operands in my example.)

So your new language could only optimize out a pure functional expression, which cannot have observable side-effects. It would only potentially be useful to do that if both sides of the comparison are not trivial. Even then,

This Optimization is Unlikely to Pay Off

Checking for the maximum or minimum value of a type at runtime takes at least one compare and branch. If the value is drawn from a uniform distribution over a 32-bit type, it will pay off only one time in 4.3 billion, and even then only if the other operand takes significantly more time to calculate than that. And it isn’t always possible to predict whether, say, the memory it accesses is in the cache.

It’s a lot more common in the real world, though, for computations to have a much narrower range than the type that holds them, which means the check would never pay off. If the left-hand side is i % n, a runtime check for whether it holds the maximum possible value is just a waste.

Answer 5

You've only given examples of what are essentially degenerate cases of short-circuiting - cases where compile-time constants determine the result, and the test could therefore be struck out of the source code.

Like these cases:

1 OR x    //always true
0 AND x   //always false

Unlike those cases, the real value of short-circuiting only arises when both operands are variables, and those variables are in turn both calculated, meaning that the cost of calculating one branch of the expression can be saved if another branch has already determined the result (given the properties of the operator which joins the two branches).

In other words, where you have an expression of the form:

(w OP x) OP (y OP z)

Where the result of the first level of operators form the arguments for the second level (which is intended to be the short-circuiting level), and the question is whether the results of evaluating the first branch, make evaluating the second branch unnecessary.

In the case of operators which take Boolean operands and are amenable to short-circuiting, there are only two possible cases to consider in determining whether to short-circuit or not - one case means short-circuiting can occur, the other not.

Therefore, checking whether to short-circuit an operator with Boolean operands may be a reasonable penalty to save the cost of evaluating the second branch of the expression, because it's a simple one-case test to resolve the question, and the short-circuit probably happens often enough to be worthwhile trying.

However, with the range comparison operators on integers (and other number types), there are a large range of possible values, and only a small number of cases in which the short-circuit could be triggered (such as one operand being at the most extreme value). A case where the short-circuit is actually hit, perhaps wouldn't happen even once in a programmer's career.

In the unusual case where it would still be worthwhile to check for the possibility of short-circuiting, the programmer could roll their own - as they might well in the broader cases where a knowledge of the application logic makes it possible to short-circuit a series of evaluations.

Answer 6

For completeness, if the relational comparison can be decided at compile time (as in your examples INT_MIN <= x and so on), rather than short-circuiting, some compilers flag it as probably an error and emit a warning such as "comparison is always true".