<div dir="ltr">I did try vectorizing my method with JDK 19 just now... but sadly I got a ~25% speed decrease over the unvectorized version. I have an AMD 4700s.<div><br></div><div>Vectorized function:</div><div><br></div><div><font face="monospace">import jdk.incubator.vector.*;<br><br>static int countDifferingBits_vectorAPI(long[] array1, long[] array2, int i1) {<br>  VectorSpecies<Long> SPECIES = LongVector.SPECIES_PREFERRED;<br>  <br>  int diff = 0;<br>  int n = array1.length;<br>  var upperBound = SPECIES.loopBound(n);<br><br>  var i = 0;<br>  for (; i < upperBound; i += SPECIES.length()) {<br>    var vector1 = LongVector.fromArray(SPECIES, array1, i);<br>    var vector2 = LongVector.fromArray(SPECIES, array2, i1+i);<br>    var xored = vector1.lanewise(VectorOperators.XOR, vector2);<br>    var bitCount = xored.lanewise(VectorOperators.BIT_COUNT);<br>    diff += (int) bitCount.reduceLanes(VectorOperators.ADD);<br>  } <br>  <br>  // Compute elements not fitting in the vector alignment.<br>  for (; i < n; i++)<br>    diff += Long.bitCount(array1[i]^array2[i]);<br><br>  return diff;<br>}</font><br></div><div><br></div><div>Unvectorized function (faster):</div><div><br></div><div><pre id="gmail-theText">static int <a title="countDifferingBits - between 2 byte, int or long arrays" style="text-decoration-line:none;color:black;border-bottom:1px dotted" href="http://code.botcompany.de:8081/tb/show-snippet.php?id=1036047">countDifferingBits</a>(long[] array1, long[] array2, int i1) {
  int n = array1.length;
  int diff = 0;
  for i to n:
    diff += Long.bitCount(array1[i]^array2[i1+i]);
  <span title="short for: return" style="border-bottom:1px dotted">return</span> diff;
}</pre></div><div><br></div><div>Did I do anything wrong or is it the nature of the game that sometimes vectorization doesn't help? The length of array1 is 16, maybe that's too short. I could merge multiple calls of the method into one and see again.</div><div><br></div><div>Greetings,</div><div>Stefan</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, 6 Sept 2022 at 20:57, Stefan Reich <<a href="mailto:stefan.reich.maker.of.eye@googlemail.com">stefan.reich.maker.of.eye@googlemail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hi Paul,<div><br></div><div>that's excellent.</div><div><br></div><div>Thanks,</div><div>Stefan</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, 6 Sept 2022 at 20:47, Paul Sandoz <<a href="mailto:paul.sandoz@oracle.com" target="_blank">paul.sandoz@oracle.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Stefan,<br>
<br>
We added, on supporting hardware, vectorized bit count to the soon to be released API in JDK 19.<br>
<br>
  <a href="https://download.java.net/java/early_access/jdk19/docs/api/jdk.incubator.vector/jdk/incubator/vector/VectorOperators.html#BIT_COUNT" rel="noreferrer" target="_blank">https://download.java.net/java/early_access/jdk19/docs/api/jdk.incubator.vector/jdk/incubator/vector/VectorOperators.html#BIT_COUNT</a><br>
<br>
You should be able to experiment with the EA build if you don’t want to wait:<br>
<br>
  <a href="https://jdk.java.net/19/" rel="noreferrer" target="_blank">https://jdk.java.net/19/</a><br>
<br>
See here for an overview in the history section:<br>
<br>
  <a href="https://openjdk.org/jeps/426" rel="noreferrer" target="_blank">https://openjdk.org/jeps/426</a><br>
<br>
Paul.<br>
<br>
> On Sep 2, 2022, at 5:59 PM, Stefan Reich <<a href="mailto:stefan.reich.maker.of.eye@googlemail.com" target="_blank">stefan.reich.maker.of.eye@googlemail.com</a>> wrote:<br>
> <br>
> Hey tthere,<br>
> <br>
> I'd like to parallelize this function:<br>
> <br>
> static int countDifferingBits(long[] array1, long[] array2) {<br>
>   int n = array1.length;<br>
>   int diff = 0;<br>
>   for (int i = 0; i < n; i++)<br>
>     diff += Long.bitCount(array1[i]^array2[i]);<br>
>   return diff;<br>
> }<br>
> <br>
> The function calculates the difference between two shapes (pixel by pixel) and is the central piece of an image recognition I am making.<br>
> <br>
> Example for a bunch of shapes (these are all the shapes found in the extended latin alphabet, in fact): <a href="https://botcompany.de/images/1103149" rel="noreferrer" target="_blank">https://botcompany.de/images/1103149</a><br>
> Example for a shape comparison: <a href="https://botcompany.de/images/1103151" rel="noreferrer" target="_blank">https://botcompany.de/images/1103151</a><br>
> <br>
> The routine above is already mega-fast as is (thanks to HotSpot!), I can compare two 256 byte arrays in 29 CPU cycles. That's less than one cycle per 64 bit!<br>
> <br>
> But I'd still like to try to vectorize it.<br>
> <br>
> However, I think the bitCount function will prevent this because it doesn't seem to exist in a vectorized form. Or does it? (That would be my main question here.)<br>
> <br>
> Many greetings,<br>
> Stefan<br>
> <br>
> -- <br>
> == Gaz.AI ==<br>
<br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><div dir="ltr"><div><font face="monospace">== <a href="http://Gaz.AI" target="_blank">Gaz.AI</a> ==</font></div></div></div></div></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><font face="monospace">== <a href="http://Gaz.AI" target="_blank">Gaz.AI</a> ==</font></div></div></div></div></div>