Comparison operators for range and id don't return bool

[Pennycook]

The comparison operators (<, >, <=, >=) for range are defined in 4.9.1.1 as:

  // OP is: +, -, *, /, %, <<, >>, &, |, ^, &&, ||, <, >, <=, >=
  friend range operatorOP(const size_t& lhs, const range& rhs) { /* ... */
  }

The equivalent operators for id are similarly defined in 4.9.1.3 as:

  // OP is: +, -, *, /, %, <<, >>, &, |, ^, &&, ||, <, >, <=, >=
  friend id operatorOP(const id& lhs, const id& rhs) { /* ... */
  }
  friend id operatorOP(const id& lhs, const size_t& rhs) { /* ... */
  }

I find this behavior confusing. I understand that imposing a strict ordering on these multi-dimensional objects doesn't make a lot of sense, which makes it impossible to return a bool in general. But in the 1-dimensional case we could return a bool, and in the multi-dimensional case a developer will always have to loop through the resulting range (so it's unclear if this operator would actually make their code any simpler).

Is there a use-case for the multi-dimensional comparisons? It seems like only allowing comparisons for the one-dimensional cases would be simpler.

[tomdeakin]

One sane default for id is to compare the linearised number for ID, but there is more than one way to think about this so it wouldn’t suit all cases. If we think an execution space given by a range is an ordered vector space, lexigraphical ordering can be defined with the most common being (a,b,c) <= (d,e,f) iff a<=d and b<=e and c <= f. We probably have enough to define the other operators from this and the ability to say an id is equal if all elements are the same. This definition wouldn’t match the linearisation option though.

I’m not sure range has an equivalent that makes sense within the framework we have now. Just comparing the product of the extents is possibly the nearest equivalent to the linearisation option, and comparing element wise would match the second option for id.

I guess we either need to ban them in multi-dimensions as @Pennycook says, or define a meaning.

[gmlueck]

The operators on id and range currently echo the same operators on marray and vec, which also do element-wise operations and return a result with the same number of dimensions. There are also other operators on id and range aside from the comparisons (e.g. + and the other mathematical operators). Wouldn't it be weird to change the comparison operators for id and range to return a scalar bool if we did not also change the other operators?

Note that you can already write code like this:

int main() {
  sycl::id i1{1};
  sycl::id i2{2};
  if (i1 == i2)
    std::cout << "Same!\n";
  if (i1 < i2)
    std::cout << "Less\n";
}

This works because there is an implicit conversion to size_t when dimension is 1.

Maybe we could allow that same sort of code for multi-dimensional id and range by adding an implicit conversion to bool when dimension is >1? That conversion would return true only if all elements were non-zero. This would make sense for equality comparisons. I'm not sure if it returns a sensible result for > and <. Does it make sense that i1 > i2 only if each element in i1 is greater than the corresponding element in i2?

[TApplencourt]

This is the ruby approach for array comparison:

Arrays are compared in an “element-wise” manner; the first element of ary is compared with the first one of other_ary using the <=> operator, then each of the second elements, etc… As soon as the result of any such comparison is non zero (i.e. the two corresponding elements are not equal), that result is returned for the whole array comparison.

(https://ruby-doc.org/core-2.7.0/Array.html#method-i-3C-3D-3E) I considered ruby to be a pretty sane language, so following their conversion may be a path forward

[gmlueck]

This would be a breaking change to the SYCL spec, though.

[nliber]

(Sorry about that. Didn't mean to close the issue...)

[nliber]

I agree with @Pennycook on this. If we don't have use cases for these operators with dimensions > 1, we should deprecate and eventually remove them. Even if we add an explicit or implicit conversion to bool to those types which don't already convert to something similar, it won't be obvious what that conversion means outside the context of these operators.

[nliber]

@gmlueck

Does it make sense that i1 > i2 only if each element in i1 is greater than the corresponding element in i2?

No (for dimensions > 1), because !(i1 > i2) && !(i2 > i1) would no longer imply (i1 == i2).

[TApplencourt]

(did the same mistake as Nevin... Friday are hard)

No (for dimensions > 1), because !(i1 > i2) && !(i2 > i1) would no longer imply (i1 == i2).

It's ok, I think. Like everything, when you generalize, you lose some properties. Matrix multiplication is non-commutative for example. It's just that adding a general formula for <=> on all our multidimensional objects will be a breaking change.

[Pennycook]

The operators on id and range currently echo the same operators on marray and vec, which also do element-wise operations and return a result with the same number of dimensions. There are also other operators on id and range aside from the comparisons (e.g. + and the other mathematical operators). Wouldn't it be weird to change the comparison operators for id and range to return a scalar bool if we did not also change the other operators?

I think these classes represent a very different use-case. marray and vec exist as convenience classes for applying the same operation(s) to lots of data, so applying the operators element-wise makes sense.

id represents a point in a multi-dimensional space, and range represents the extent of a multi-dimensional space. It's not obvious to me that element-wise comparison of those quantities is meaningful.

For 1-dimensional cases, the comparison operators are clearly meaningful and map to this mental model:

• id1 < id2 => id1 is "to the left" of id2 in the space
• r1 < r2 => r1 represents a smaller (linear) space than r2
• id1 > 0 and id1 < r1 => id1 is in the space described by r1

Extending that to two dimensions might give something like:

• id1 < id2 => id1 is "above" or "to the left" of id2 in the space
• r1 < r2 => r1 contains fewer points than r2 (as @tomdeakin noted, this is comparing the product of extents)
• id1 > (0, 0) and id1 < r1 => id1 is in the space described by r1

I'm not saying we should do the above, because without real use-cases this would just be adding unnecessary complexity into the definitions of these types. But this is what I think a developer might expect the operators to "mean".

Note that you can already write code like this:

int main() {
  sycl::id i1{1};
  sycl::id i2{2};
  if (i1 == i2)
    std::cout << "Same!\n";
  if (i1 < i2)
    std::cout << "Less\n";
}

This works because there is an implicit conversion to size_t when dimension is 1.

This works for sycl::id, but not for sycl::range (which is how I found out about this behavior). The compiler error you currently get for range (from DPC++) is:

range-comparison.cpp:10:7: error: no viable conversion from 'range<1>' to 'bool'
  if (r1 < r2)

...which is really confusing. I hadn't considered we could fix this by adding a conversion operator for range.

[nliber]

@TApplencourt Just to be clear, for:

a = (2, 3) b = (2, 5)

that definition gives us

b > a is false a > b is false a == b is false (presuming == is defined as all elements being equal)

And it gets worse if you define < in a similar way: b < a is false a < b is false

Finishing up the set: b <= a is true a <= b is true

b >= a is true b <= a is true

[TApplencourt]

irb(main):003:0> a = [2,3]
=> [2, 3]
irb(main):004:0> b = [2,5]
=> [2, 5]
irb(main):005:0> a <=> b
=> -1
irb(main):006:0> b <=> a
=> 1

So everything makes sense to me (note that ruby didn't choose to implement < and > for array, just the starship operator)

...which is really confusing. I hadn't considered we could fix this by adding a conversion operator for range.

I think it's the cleanest way for now. Will not change the semantics, and will allow 1d code to work "as expected" for comparison purposes. We "just" need to add a conversion operator to a scalar for all our 1d multi-dimension object

[nliber]

@TApplencourt Sure, but that isn't the same as:

Does it make sense that i1 > i2 only if each element in i1 is greater than the corresponding element in i2?

Like == and !=, you can do a <=> between each of the elements and it works because those operators are symmetric, even in C++. That doesn't hold for <, >, <= and >=, because they are not symmetric, so you have to do double the comparisons to make it work the same way.

Optimizations aside, the canonical way to write > in terms of > for all its elements is:

if (l[0] > r[0]) return true;
if (r[0] > l[0]) return false;
if (l[1] > r[1]) return true;
if (r[1] > l[1]) return false;
//...
return false;

This is essentially what the guts of std::lexicographical_compare does.

[TApplencourt]

Sorry, I'm missing something. You are saying that we cannot compute the <=> of the array (returning the first nonzero elements size) and then derive from this the value that > or < should return?

I think we are talking past each other :)

Some Example with the ruby probosal a = [1,4] ; b = [1,3] => a > b is True and b > a is False a = [4,1] ; b = [8,3] => a > b is False and b > a is True

[nliber]

@TApplencourt

We "just" need to add a conversion operator to a scalar for all our 1d multi-dimension object

Just to be clear: regardless of what operator<(range<1>, range<1>) returns, it still makes sense that range<1> is convertible to bool. If that is true (I think it is), then we just have the question of whether the conversion operator should be explicit or implicit.

[TApplencourt]

Oh I was tinkin that we wanted range<1> to be converting to size_t so we can do range<1>{2} > range<1>{4}

[nliber]

@TApplencourt you can do it, but not in the way that @gmlueck had said in his question.

[nliber]

@TApplencourt you only need to convert to bool, not convert to size_t. If there is another use case where we want more information than returned by an ordered comparison, that's a different story (which is not related to the comparison operators, but might be related to the other operators).

Non-spaceship comparison operators should return something convertible to bool. (C++ spaceship is more complicated, as it returns the kind of ordering.)

[keryell]

This is the ruby approach for array comparison:

What about looking at C++ then? Cf clause 3-6 of https://en.cppreference.com/w/cpp/container/array/operator_cmp ;-)

[keryell]

This has already been discussed for years without strong consensus inside Khronos https://gitlab.khronos.org/sycl/Specification/-/issues/148 Note that (not compliant) triSYCL returns a bool by implementing @TApplencourt beloved semantics.