8
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ What do you mean by short circuiting? Do you want to write b = INT_MIN <= ; instead of either b = true ; or b = INT_MIN <= x;? Or do you simply want the result to be computed at compile time? $\endgroup$
    – jmoreno
    Oct 2, 2023 at 0:11
  • $\begingroup$ Of course the compilers simply use the proper truth value there; is that short enough? ;-) $\endgroup$ Oct 2, 2023 at 2:31
  • 2
    $\begingroup$ I don't think this is short-circuiting; this is constant folding $\endgroup$
    – Seggan
    Oct 2, 2023 at 17:54
  • 5
    $\begingroup$ @Seggan Nope. I was referring to values that are not compile time constants but could be INT_MIN etc. No where in the question did I say the left-hand operands were constants. $\endgroup$
    – CPlus
    Oct 2, 2023 at 17:56

6 Answers 6

31
$\begingroup$

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.

$\endgroup$
10
  • 7
    $\begingroup$ While the intent is clear for stack1.pop() <= stack2.pop(), I should note that the order of the pop()s for the same stack is likely unspecified, and could be subject to change with a different compiler/version. $\endgroup$
    – Ángel
    Oct 1, 2023 at 14:29
  • 12
    $\begingroup$ @Ángel It may be unspecified in old languages like C, but every modern language I know of specifies left-to-right evaluation order if it matters. I think C should be seen as an outlier in this regard. $\endgroup$
    – kaya3
    Oct 1, 2023 at 16:45
  • 7
    $\begingroup$ @leftaroundabout C++ definitely counts as an "old language like C" :-) $\endgroup$
    – Bergi
    Oct 2, 2023 at 9:06
  • 3
    $\begingroup$ @leftaroundabout Languages which don't specify the behaviour of valid programs are confusing and bug-prone; languages which allow users to write bad code are (checks notes) all of them. $\endgroup$
    – kaya3
    Oct 2, 2023 at 17:16
  • 1
    $\begingroup$ @kaya3 "In practice this is hard to track" - yes, side effects are generally hard to track, which is one of the reasons I prefer purely functional programming! In Haskell, changing a <- pop stack; b <- pop stack; if a<=b then... to if pop stack <= pop stack then ... is a type error. $\endgroup$ Oct 2, 2023 at 18:05
11
$\begingroup$

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.

$\endgroup$
14
  • $\begingroup$ "suppression of the right side effect" ... null == x || x.f() heavens to murgatroyd! $\endgroup$
    – Steve
    Oct 1, 2023 at 8:04
  • 1
    $\begingroup$ @Steve something like if (null == incoming || incoming.isEmpty()) node.predecessors = emptySet else ... $\endgroup$
    – feldentm
    Oct 1, 2023 at 9:20
  • 8
    $\begingroup$ @Steve It's extremely common to write this kind of code (relying on short-circuiting to first check an operation is safe and then perform it) in Java, C#, Javascript/Typescript and many other languages; Typescript in particular is interesting because it does control-flow type narrowing including for short-circuiting logical operators, so x !== undefined && x.foo() eliminates undefined from x in the second operand, if it is a union type. I would guess that somewhere in the range of a quarter to three quarters of the time I use a short-circuiting logical operator, it's like this. $\endgroup$
    – kaya3
    Oct 1, 2023 at 10:14
  • 1
    $\begingroup$ Yes, this kind of expression normally appears in an if, while or other statement taking a condition. Though in dynamically-typed languages people do use them for things like let x = something() || something_else(); where something() might return null (i.e. using || as a null-coalescing operator). Only minifiers tend to use the short-circuiting logical operators in free-standing expressions, and if a human wrote this (outside of the context of code golf) then it would be smelly. $\endgroup$
    – kaya3
    Oct 1, 2023 at 12:58
  • 8
    $\begingroup$ This answer could be more direct: The question has it backwards. It is not "why do relational operators not short circuit" but why on Earth do the logical ones short-circuit if it is both slower and more complicated? Because you want to suppress the right evaluation in an elegant fashion. $\endgroup$ Oct 2, 2023 at 2:36
6
$\begingroup$

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).

$\endgroup$
2
  • 3
    $\begingroup$ Haskell is a lazy functional language, so effectively everything short circuits -- there are no side effects and things are only computed when needed. So there's notthing special about relations or booleans or anything else. $\endgroup$
    – Chris Dodd
    Oct 1, 2023 at 23:38
  • 3
    $\begingroup$ @ChrisDodd You have to be careful with what you mean by "needed", though. If (||) had been defined as False || x = x; True || True = True; True || False = True, it wouldn't short-circuit, for example. $\endgroup$
    – amalloy
    Oct 2, 2023 at 18:52
3
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ The example with printf doesn't seem related to short-circuiting, since with short-circuiting semantics it is only the right-hand-side which is conditionally evaluated; the left side will still always be evaluated. Your point would apply equally to a statement like printf("hello, world!"); where the compiler would be just as wrong to say "this expression's result isn't used, so it doesn't need to be evaluated". $\endgroup$
    – kaya3
    Oct 1, 2023 at 18:01
  • $\begingroup$ @kaya3 An optimizer would optimize either 0 <= returnsUnsigned() or returnsUnsigned() >= 0 the same. However, if you’re imagining short-circuiting that works exactly like && and ||, flip the operands. $\endgroup$
    – Davislor
    Oct 1, 2023 at 21:36
2
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ The examples in the question are meant to illustrate the situations at runtime where short-circuiting could happen. The idea is x <= y would short-circuit if x evaluates to INT_MIN. Not just for INT_MIN <= y where the left-side is a compile-time constant. $\endgroup$
    – kaya3
    Oct 1, 2023 at 10:15
  • $\begingroup$ @kaya3: If I'm understanding correctly, that turns one comparison into two when evaluating on normal hardware. (Except when the RHS has no side-effects so compilers can skip the short-circuiting). if (x < foo()) would have to get compiled like C if (x != INT_MIN && x < foo()), with two compare-and-branch operations, the first one before a function call, the second after. This is horrible, and as your answer says, will take extra branch-prediction entries and isn't free for front-end throughput. $\endgroup$ Oct 1, 2023 at 15:34
  • $\begingroup$ @peter: if (x != INT_MAX && x < foo()), the exceptional value for strict < is INT_MAX not INT_MIN $\endgroup$
    – Ben Voigt
    Oct 3, 2023 at 17:04
2
$\begingroup$

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".

$\endgroup$
1
  • $\begingroup$ Or the compiler just applies constant folding on it $\endgroup$
    – Seggan
    Oct 2, 2023 at 18:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .