www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - More on vectorized comparisons

reply "bearophile" <bearophileHUGS lycos.com> writes:
Some time ago I have suggested to add support to vector 
comparisons in D, because this is sometimes useful and in the 
modern SIMD units there is hardware support for such operations:


double[] a = [1.0, 1.0, -1.0, 1.0, 0.0, -1.0];
bool[] t = a[] > 0;
assert(t == [true, true, false, true, false, false]);

Usable instructions like (here shows the intrinsic):
http://msdn.microsoft.com/en-us/library/11dy102s%28v=vs.80%29.aspx


Now on Reddit I have found a small discussion about a slides pack 
by Intel:
http://www.reddit.com/r/programming/comments/ym8m6/parallel_programming_for_c_and_c_done_right/

The slides:
https://speakerdeck.com/u/multicoreworld/p/james-reinders-intel-united-states

Link to the PDF:
https://speakerd.s3.amazonaws.com/presentations/5006069136af010002005325/Reinders_KEYNOTE_C_done_right.pdf

At page 69 of those slides there is some code that looks 
interesting, I think this is a reduced version of part of it, 
that shows another way to use vectorized comparisons:


void main() {
     double[] a = [1.0, 1.0, -1.0, 1.0, 0.0, -1.0];
     double[] b = [10,   20,   30,  40,  50,   60];
     double[] c = [1,     2,    3,   4,   5,    6];
     if (a[] > 0)
         b[] += c[];
}


I think that code is semantically equivalent to:

void main() {
     double[] a = [1.0, 1.0, -1.0, 1.0, 0.0, -1.0];
     double[] b = [10,   20,   30,  40,  50,   60];
     double[] c = [1,     2,    3,   4,   5,    6];
     foreach (i; 0 .. a.length)
         if (a[i] > 0)
             b[i] += c[i];
}


After that code b is:
[11, 22, 30, 44, 50, 60]


This means the contents of the 'then' branch of the vectorized 
comparison is done only on items of b and c where the comparison 
has given true.

This looks useful. Is it possible to implement this in D, and do 
you like it?

Bye,
bearophile
Aug 22 2012
next sibling parent reply Sean Cavanaugh <WorksOnMyMachine gmail.com> writes:
On 8/22/2012 7:19 PM, bearophile wrote:
 Some time ago I have suggested to add support to vector comparisons in
 D, because this is sometimes useful and in the modern SIMD units there
 is hardware support for such operations:


 I think that code is semantically equivalent to:

 void main() {
      double[] a = [1.0, 1.0, -1.0, 1.0, 0.0, -1.0];
      double[] b = [10,   20,   30,  40,  50,   60];
      double[] c = [1,     2,    3,   4,   5,    6];
      foreach (i; 0 .. a.length)
          if (a[i] > 0)
              b[i] += c[i];
 }


 After that code b is:
 [11, 22, 30, 44, 50, 60]


 This means the contents of the 'then' branch of the vectorized
 comparison is done only on items of b and c where the comparison has
 given true.

 This looks useful. Is it possible to implement this in D, and do you
 like it?

Well, right now the binary operators == != >= <= > and < are required to return bool instead of allowing a user defined type, which prevents a lot of the sugar you would want to make the code nice to write. Without the sugar the code would ends up this: foreach(i; 0 .. a.length) { float4 mask = greaterThan(a[i], float4(0,0,0,0)); b[i] = select(mask, b[i] + c[i], b[i]); } in GPU shader land this expression is at least simpler to write: foreach(i; 0 .. a.length) { b[i] = (b[i] > 0) ? (b[i] + c[i]) : b[i]; } All of these implementations are equivalent and remove the branch from the code flow, which is pretty nice for the CPU pipeline. In SIMD the comparisons generate masks into a register which you can immediately use. On modern (SSE4) CPUs the select is a single instruction, on older ones it takes three: (mask & A) | (~mask & B), but its all better than a real branch. If you have a large amount of code needing a branch, you can take the mask generated by the compare, and extract it into a CPU register, and compare it for 0, nonzero, specific or any bits set. a float4 comparison ends up generating 4 bits, so the code with a real branch is like: if (any(a[i] > 0)) { // do stuff if any of a[i] are greater than zero } if (all(a[i] > 0)) { // do stuff if all of a[i] are greater than zero } if ((getMask(a[i] > 0) & 0x7) == 0x7) { // do stuff if the first three elements are greater than zero }
Aug 23 2012
parent reply Don Clugston <dac nospam.com> writes:
On 24/08/12 00:13, bearophile wrote:
 Sean Cavanaugh:

 Well, right now the binary operators == != >= <= > and < are required
 to return bool instead of allowing a user defined type, which prevents
 a lot of the sugar you would want to make the code nice to write.

The hypothetical D sugar I was looking for is this, where 'a', 'b' and 'c' are normal dynamic arrays of doubles (not of float[4] of double[2]) (currently this code is a syntax error): if (a[] > 0) b[] += c[]; The front-end is able to implement those two lines of code as it likes, like seeing those normal arrays as arrays of double[2] (or double[4] on more modern CPUs) and put there all the needed intrinsics or assembly needed to implement that semantics. So what's the problem the > operator causes in this code? Bye, bearophile

It's just syntax sugar for a very obscure operation, and it's somewhat ambiguous -- is it allowed to use short-circuit evaluation? Mathematically, it doesn't make sense. You can compare scalars, but ordered comparison of vectors is a bit nonsensical, unless it is element-wise. Usually, a[] > 0, a[] < 0, and a[] == 0 will all be false. Most likely, you really meant dot(a[]) > 0. Something like if ( all( a[] > 0 ) ) b[] += c[]; is more reasonable. But an implicit 'reduce' in a vector operation has little to commend it, I think.
Aug 24 2012
parent reply Don Clugston <dac nospam.com> writes:
On 24/08/12 15:57, bearophile wrote:
 It's just syntax sugar for a very obscure operation,<

It's an operation included in Cilk Plus, I think Intel devs know enough what they are doing. And I think code like this is a common need: if (a[] > 0) { // ... }
 and it's somewhat ambiguous -- is it allowed to use short-circuit
 evaluation?<

That code means: foreach (i; 0 .. a.length) { if (a[i] > 0) { // ... } } Here I don't see problems caused by short circuit evaluation.

Wow. Then I misunderstood, and it's even less appropriate for D than I thought. vote -= int.max; Worst syntax I've seen in a very long time.
Aug 27 2012
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 8/27/12 8:06 AM, Don Clugston wrote:
 vote -= int.max;

Beware of wraparound :o). Andrei
Aug 27 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Sean Cavanaugh:

 Well, right now the binary operators == != >= <= > and < are 
 required to return bool instead of allowing a user defined 
 type, which prevents a lot of the sugar you would want to make 
 the code nice to write.

The hypothetical D sugar I was looking for is this, where 'a', 'b' and 'c' are normal dynamic arrays of doubles (not of float[4] of double[2]) (currently this code is a syntax error): if (a[] > 0) b[] += c[]; The front-end is able to implement those two lines of code as it likes, like seeing those normal arrays as arrays of double[2] (or double[4] on more modern CPUs) and put there all the needed intrinsics or assembly needed to implement that semantics. So what's the problem the > operator causes in this code? Bye, bearophile
Aug 23 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
It's just syntax sugar for a very obscure operation,<

It's an operation included in Cilk Plus, I think Intel devs know enough what they are doing. And I think code like this is a common need: if (a[] > 0) { // ... }
and it's somewhat ambiguous -- is it allowed to use 
short-circuit evaluation?<

That code means: foreach (i; 0 .. a.length) { if (a[i] > 0) { // ... } } Here I don't see problems caused by short circuit evaluation.
You can compare scalars, but ordered comparison of vectors is a 
bit nonsensical, unless it is element-wise.<

It's a comparison element-wise between each item and a constant, it's similar to: a[] = a[] + 5; Probably you have misunderstood the semantics of what I am discussing. Bye, bearophile
Aug 24 2012
prev sibling next sibling parent "tn" <no email.com> writes:
On Thursday, 23 August 2012 at 00:19:39 UTC, bearophile wrote:
 At page 69 of those slides there is some code that looks 
 interesting, I think this is a reduced version of part of it, 
 that shows another way to use vectorized comparisons:


 void main() {
     double[] a = [1.0, 1.0, -1.0, 1.0, 0.0, -1.0];
     double[] b = [10,   20,   30,  40,  50,   60];
     double[] c = [1,     2,    3,   4,   5,    6];
     if (a[] > 0)
         b[] += c[];
 }


 I think that code is semantically equivalent to:

 void main() {
     double[] a = [1.0, 1.0, -1.0, 1.0, 0.0, -1.0];
     double[] b = [10,   20,   30,  40,  50,   60];
     double[] c = [1,     2,    3,   4,   5,    6];
     foreach (i; 0 .. a.length)
         if (a[i] > 0)
             b[i] += c[i];
 }

The proposed syntax looks weird. Wouldn't the followind be more intuitive: foreach (i; a[i] > 0) b[i] += c[i]; Or alternatively it would be nice to be able to do it like in Matlab: i = (a[] > 0); b[i] += c[i];
Aug 24 2012
prev sibling next sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Friday, 24 August 2012 at 13:57:42 UTC, bearophile wrote:
 That code means:

 foreach (i; 0 .. a.length) {
      if (a[i] > 0) {
          // ...
      }
 }

How could this possibly be useful? It's like the loop, but you lose the index variable. I can't see how you could possibly do anything with this. Can you show an example of some code that uses this?
Aug 27 2012
prev sibling next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
Peter Alexander:

 How could this possibly be useful? It's like the loop, but you 
 lose the index variable. I can't see how you could possibly do 
 anything with this.

I think this feature is a part of Cilk+. Maybe I have not fully understood this feature, or maybe some Intel developers are mad :-) I think in code like this: if (a[] >= 0) b[] += c[]; The 'b' and 'c' arrays receive the implicit index of the items of 'a' that aren't negative. I think its semantics is a bit like this (assuming zip() supports ref iteration), you see no index variable here: parallel_foreach (ai, ref bi, ci; zip(a, b, c)) if (ai > 0) bi += ci; I think it's something commonly useful.
 Can you show an example of some code that uses this?

On the net I have found two examples of Cilk+ code that uses that feature. One of them is referenced in the first email of this thread. With Google you can find the full code from Intel that piece of code comes from. Bye, bearophile
Aug 27 2012
prev sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Monday, 27 August 2012 at 20:29:29 UTC, bearophile wrote:
 I think in code like this:

 if (a[] >= 0)
     b[] += c[];

 The 'b' and 'c' arrays receive the implicit index of the items 
 of 'a' that aren't negative.

Ok, I can see the use of this, but I find the syntax *very* confusing. Expressions shouldn't be able to mess with code semantics like that. If you wanted to do something like that, I could live with this syntax: b[] += (a[] >= 0 ? c[] : 0); The a[] >= 0 returns a vector of booleans, and then the ternary operator acts element-wise with those booleans as the condition.
Aug 27 2012