Vectorizing POPCNT (Long.bitCount)

[Paul Sandoz]

AFAICT AMD 4700s only supports AVX2:

  http://valid.x86.fr/cevdtl

Where as vpopcntq requires CPUID flags AVX512VPOPCNTDQ

  https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#ig_expand=5436,5436,5427,5418,5433,5424,5436&text=vpopcntq

The code looks good, but you could also perform the reduction outside the loop e.g. before entering the loop initialize a sum vector to zero and add the bit count to that. On supporting hardware that should improve things.

Paul.

> On Sep 6, 2022, at 2:21 PM, Stefan Reich <stefan.reich.maker.of.eye at googlemail.com> wrote:
> 
> 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.
> 
> Vectorized function:
> 
> import jdk.incubator.vector.*;
> 
> static int countDifferingBits_vectorAPI(long[] array1, long[] array2, int i1) {
>   VectorSpecies<Long> SPECIES = LongVector.SPECIES_PREFERRED;
>   
>   int diff = 0;
>   int n = array1.length;
>   var upperBound = SPECIES.loopBound(n);
> 
>   var i = 0;
>   for (; i < upperBound; i += SPECIES.length()) {
>     var vector1 = LongVector.fromArray(SPECIES, array1, i);
>     var vector2 = LongVector.fromArray(SPECIES, array2, i1+i);
>     var xored = vector1.lanewise(VectorOperators.XOR, vector2);
>     var bitCount = xored.lanewise(VectorOperators.BIT_COUNT);
>     diff += (int) bitCount.reduceLanes(VectorOperators.ADD);
>   } 
>   
>   // Compute elements not fitting in the vector alignment.
>   for (; i < n; i++)
>     diff += Long.bitCount(array1[i]^array2[i]);
> 
>   return diff;
> }
> 
> Unvectorized function (faster):
> 
> static int countDifferingBits
> (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]);
>   
> return
>  diff;
> }
> 
> 
> 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.
> 
> Greetings,
> Stefan
> 
> On Tue, 6 Sept 2022 at 20:57, Stefan Reich <stefan.reich.maker.of.eye at googlemail.com> wrote:
> Hi Paul,
> 
> that's excellent.
> 
> Thanks,
> Stefan
> 
> On Tue, 6 Sept 2022 at 20:47, Paul Sandoz <paul.sandoz at oracle.com> wrote:
> Hi Stefan,
> 
> We added, on supporting hardware, vectorized bit count to the soon to be released API in JDK 19.
> 
>   https://download.java.net/java/early_access/jdk19/docs/api/jdk.incubator.vector/jdk/incubator/vector/VectorOperators.html#BIT_COUNT
> 
> You should be able to experiment with the EA build if you don’t want to wait:
> 
>   https://jdk.java.net/19/
> 
> See here for an overview in the history section:
> 
>   https://openjdk.org/jeps/426
> 
> Paul.
> 
> > On Sep 2, 2022, at 5:59 PM, Stefan Reich <stefan.reich.maker.of.eye at googlemail.com> wrote:
> > 
> > Hey tthere,
> > 
> > I'd like to parallelize this function:
> > 
> > static int countDifferingBits(long[] array1, long[] array2) {
> >   int n = array1.length;
> >   int diff = 0;
> >   for (int i = 0; i < n; i++)
> >     diff += Long.bitCount(array1[i]^array2[i]);
> >   return diff;
> > }
> > 
> > The function calculates the difference between two shapes (pixel by pixel) and is the central piece of an image recognition I am making.
> > 
> > Example for a bunch of shapes (these are all the shapes found in the extended latin alphabet, in fact): https://botcompany.de/images/1103149
> > Example for a shape comparison: https://botcompany.de/images/1103151
> > 
> > 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!
> > 
> > But I'd still like to try to vectorize it.
> > 
> > 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.)
> > 
> > Many greetings,
> > Stefan
> > 
> > -- 
> > == Gaz.AI ==
> 
> 
> 
> -- 
> == Gaz.AI ==
> 
> 
> -- 
> == Gaz.AI ==