# Speculation chained comparison optimization (possibly with outlining)

**URL:** <https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354>\
**Category:** Offtopic\
**Created:** [January 8, 2017, 5:09pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354 "2017-01-08T17:09:06Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [January 8, 2017, 5:09pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/1 "2017-01-08T17:09:06Z")

</div>

[I first saw the word outlining the other day, I assume it’s the opposite of inlining.]

It would come in handy here:

[I’m trying to fix this post, discourse messed it up]

> [@A != b != c](https://discourse.julialang.org/t/a-b-c/1347/17):
>
> It should be in all cases (as logic dictates), the expand you showed, only shows what the current implementations of Julia does. In case when you do not have transitive, e.g. a \< b \> c, or != or the sneaky ≈ (isapprox), then for the optimizer, should split up and optimize the left and right of it separately. “so there is nothing (except for sanity) stopping you from defining a non-transitive \<” Can that possibility be disallowed so the optimizer does not have to consider that case?

> [@A != b != c](https://discourse.julialang.org/t/a-b-c/1347/19):
>
> You’re now actively spreading misinformation. Please stop.

when the “functions”, aren’t really.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [January 8, 2017, 3:55pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/2 "2017-01-08T15:55:03Z")

</div>

> [@A != b != c](https://discourse.julialang.org/t/a-b-c/1347/4):
>
> point is that \< is an arbitrary user-defined function,[…]
> 
> The a \< b \< c implementation does not compare a \< c, it only compares a \< b and b \< c.

Some future Julia implementation could check a \< c first (and probably a better strategy for speed). [I guess you’re saying the current 0.5 or 0.6 doesn’t] but while not done now, not ruled out in the future(?).

Comparison chaining for: a op b op c … is not defined for any possibly op-function, right, only a limited set e.g. \<, \<=, \> etc. all functions that are transitive (and also defined as operators).

Limiting those functions to only transitive is a good idea, but can it (is?) be enforced? If not either the optimized can’t use the default, or it must figure out if had been overloaded and block optimizations otherwise. I’m not sure I would trust a compiler to be that brainy.

Since I’m here,

> **[Short-circuit evaluation](https://en.wikipedia.org/wiki/Short-circuit_evaluation)**
>
> Short-circuit evaluation, minimal evaluation, or McCarthy evaluation (after John McCarthy) is the semantics of some Boolean operators in some programming languages in which the second argument is executed or evaluated only if the first argument does not suffice to determine the value of the expression: when the first argument of the AND function evaluates to false, the overall value must be false; and when the first argument of the OR function evaluates to true, the overall value must be true.
> I...

Footnote 2. on C++ (seemed insane), then I noticed 4. [Do you know the story behind it? Early versions of Fortran with eager, then short-circuit adopted from Lisp? Or is eager allowed (for old compatibility) but other allowed (considered a superset?); either used in the same compiler of different code parts?!]:

1. When overloaded, the operators && and || are eager and can return any type.  
[…]
2. Fortran operators are neither short-circuit nor eager: the  
language specification allows the compiler to select the method for  
optimization.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [January 8, 2017, 4:17pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/3 "2017-01-08T16:17:18Z")

</div>

> [@A != b != c](https://discourse.julialang.org/t/a-b-c/1347/16):
>
> The Julia implementation could check a \< c first (and probably a better strategy for speed)

I am not sure I understand how this would improve speed.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [January 8, 2017, 4:26pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/4 "2017-01-08T16:26:31Z")

</div>

> [@A != b != c](https://discourse.julialang.org/t/a-b-c/1347/16):
>
> a \< b \< c

If I write:

a \< b \< c

I’m kind of expecting it to be true (well, at least checking).

It of course depends on the values, and I expect c to be farther from a than b is.

Maybe I have it all backwards, but I’m looking into alternatives that short-circuit from left-to-right [evaluation order].

There are exponentially many possible ways to check, and then some more… and I’m looking at the best way to find one.

An example from previously:

‘a’ \<= c \<= ‘z’ # In the uppercase function I was looking at.

I guess the compiler didn’t consider that range to by tiny subset of the full Unicode codepoint range (or from UInt32)…

Often then width of the ranges, could be taken into account (helpful?), yes, here that might actually be bad… as English is more common, or at least English letters in e.g. my language Icelandic.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [January 8, 2017, 5:00pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/5 "2017-01-08T17:00:11Z")

</div>

> [@A != b != c](https://discourse.julialang.org/t/a-b-c/1347/18):
>
> a \< b \< c
> 
> I’m kind of expecting it to be true (well, at least checking).
> 
> […]
> 
> Maybe I have it all backwards

Even if I’m not thinking clearly, note that in general you have something like:

a(x1) \< b(x2) \< c(x3) \< d(x4) …

Where the functions are actual functions (or just alternatively code above generating the), temporary variables, or constants.

Let’s say you have:

fast(x) \< slow(x) \< slow2(x) \< constant

do you want to evaluate the two slow functions or possibly just the fast one?

Do compilers do this (since chaining is just syntactic sugar and not really new)? I’m not sure comparison chaining is in C++ (or C) now, wasn’t when I used. I learned it from Python, and all the scripting languages can’t/won’t do [whole] program analysis.

Swift (and Rust) is also new, reuses LLVM. I’m just skeptical LLVM or GCC have this as first made for C/C++/Fortran.

---

<div class="post-metadata">

**Author:** ![giordano](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/giordano/32/2166_2.png) [@giordano](https://discourse.julialang.org/u/giordano)\
**Post date:** [January 8, 2017, 6:32pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/6 "2017-01-08T18:32:49Z")

</div>

> [@A != b != c](https://discourse.julialang.org/t/a-b-c/1347/16):
>
> The Julia implementation could check a \< c first (and probably a better strategy for speed).

Nothing prevents you from testing the condition

```julia
1 < -3 < 4

```

in this case there is no performance gain, on the contrary you’ll have performed one extra test.

In addition, the parser should know in advance that the operator `<` is transitive, it can’t assume transitivity in all cases such this. Consider the case `a < b > c`, the parser should know that `<` and `>` are opposite, so transitivity can’t be assumed there. It won’t work with arbitrary comparison operators. Is all this worth?

---

<div class="post-metadata">

**Author:** ![ihnorton](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ihnorton/32/26_2.png) [@ihnorton](https://discourse.julialang.org/u/ihnorton)\
**Post date:** [January 8, 2017, 9:22pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/7 "2017-01-08T21:22:34Z")

</div>



---

<div class="post-metadata">

**Author:** ![ihnorton](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ihnorton/32/26_2.png) [@ihnorton](https://discourse.julialang.org/u/ihnorton)\
**Post date:** [January 9, 2017, 2:21pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/8 "2017-01-09T14:21:19Z")

</div>



---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [January 9, 2017, 2:21pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/9 "2017-01-09T14:21:36Z")

</div>

A. Continuing the discussion from [Does Julia ever do outlining?](https://discourse.julialang.org/t/does-julia-ever-do-outlining/1354/6):

@giordano

> Nothing prevents you from testing the condition

> `1 < -3 < 4`

> in this case there is no performance gain, on the contrary you’ll have performed one extra test.

In that case, with constants no, but in general, could be. See may race idea of (long) chaining of || (converted from [implicit] &&) at:

> <https://github.com/JuliaLang/julia/issues/19933#issuecomment-271257127>
>
> What @Ismael-VC wants with https://github.com/JuliaLang/julia/pull/19788 are str…ict aliases. There are other options, the problem may not be with his code though.\*
> 
> If taken at face-value, left short-circuiting disallows running first the (or only) right-side:
> 
> \`\`\`
> if slow\_function!(x) && fast\_function!(y)
> takes\_a\_long\_time\_getting\_here
> else
> or\_takes\_a\_long\_time\_getting\_here
> end
> \`\`\`
> 
> I have some ideas to fix that, they may be strictly implementations details, NOT incompatible with left short-circuiting, but then you need lots of prove-work to show absence of "side-effects".
> 
> There are two options:
> \* Disallow calling functions with side-effects (braking change for && and || but not new operators).
> \* Ignoring side-effects!
> 
> if fun1!(x) and fun2!(x) # note x-es are repeated, not y as above
> 
> is even worse \[maybe the other if can work despite the !s \]
> 
> If we announce \`and\` and \`or\` not promising too much, maybe reusing his code (mostly; changes would be elsewhere, and in NEWS.md), then his code could possibly work.
> 
> I want to allow running, either side, or both (as &), or even neither (yes, that's a possibility..). And running both sides at once in separate thread, possibly killing them half-way through.
> 
> \* I'm unclear on:
> 
> \`(define is-prec-comparison?
> (augment-prec-with-infix prec-comparison 'in 'isa))
> 
> \[..\]
> 
> (put! prec-table 'in (get prec-table '== 0)) ; add \`in\` to the prec-table
> (put! prec-table 'isa (get prec-table '== 0)) ; add \`isa\` to the prec-table\`

B. @ihnorton You merged into the outlining (and closed it! EDIT: I see the “no” now…). I guess I was a little off-topic at the other thread you merged from. The outlining question wasn’t closed, so I guess you may have made a mistake on closing (who has the priv. to undo?)?

Didn’t you also merge into the wrong thread…?

---

<div class="post-metadata">

**Author:** ![giordano](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/giordano/32/2166_2.png) [@giordano](https://discourse.julialang.org/u/giordano)\
**Post date:** [January 9, 2017, 12:28pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/10 "2017-01-09T12:28:50Z")

</div>

[quote=“Palli, post:1, topic:1364, full:true”]  
@giordano

> Nothing prevents you from testing the condition

> `1 < -3 < 4`

> in this case there is no performance gain, on the contrary you’ll have performed one extra test.

In that case, with costants no, but in general, could be.[/quote]  
Of course I didn’t mean to use literal constants but variables with those values:

```julia
a, b, c = 1, -3, 4
a < b < c

```

I was showing you that your proposal was faster in some cases, but slower in others, with no overall speed-up.

---

<div class="post-metadata">

**Author:** ![ihnorton](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ihnorton/32/26_2.png) [@ihnorton](https://discourse.julialang.org/u/ihnorton)\
**Post date:** [January 9, 2017, 2:53pm UTC](https://discourse.julialang.org/t/speculation-chained-comparison-optimization-possibly-with-outlining/1354/11 "2017-01-09T14:53:29Z")

</div>

@Palli the discussion rules here should be considered the same as on the mailing list: please strive to maximize the level of consideration before posting, and minimize the length of replies.

See the following old posts on the mailing list for suggestions given regarding question formation, as well as potential alternative venues for extended discussion.

[https://groups.google.com/d/msg/julia-users/OGUyEb3xq8s/-4gl7v3hAwAJ](https://groups.google.com/d/msg/julia-users/OGUyEb3xq8s/-4gl7v3hAwAJ)

[https://groups.google.com/forum/#!topic/julia-users/hbWb0pZjk3Q](https://groups.google.com/forum/#!topic/julia-users/hbWb0pZjk3Q)