Speculation chained comparison optimization (possibly with outlining)

[Palli]

[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

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

You’re now actively spreading misinformation. Please stop.

when the “functions”, aren’t really.

[Palli]

A != b != c

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

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?!]:

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

[Tamas_Papp]

A != b != c

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.

[Palli]

A != b != c

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.

[Palli]

A != b != c

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.

[giordano]

A != b != c

The Julia implementation could check a < c first (and probably a better strategy for speed).

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 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?

[ihnorton]

[ihnorton]

[Palli]

A. Continuing the discussion from Does Julia ever do outlining?:

@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:

Issue: Reserve/add `and` and `or` with relaxed semantics from [left] only short-circuiting, e.g. allowing & or |

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…?

[giordano]

[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:

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.

[ihnorton]

@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/forum/#!topic/julia-users/hbWb0pZjk3Q