[vector] Infinite loop in SIMD binary search

[Lupusoru, Razvan A]

Hey Adam,

Ideally, we want all of your algorithms tested with default build because it is very helpful since it uncovers bugs and helps us guide priority on performance improvements.

That said, I think it would useful to confirm that your own algorithm is doing the semantically correct thing. Use the flag -XX:-UseVectorApiIntrinsics to disable intrinsification. It will run more slowly by using default java implementation, but at least you can confirm whether your own algorithm is working as expected.

I also would like to point out a couple more things:
- I have successfully executed your algorithm [1] with latest branch + patch from http://cr.openjdk.java.net/~rlupusoru/panama/webrev_veccompares_04/
  - I have tested even large array sizes [8][10000] and repeated searches with no infinite loop situation
- As it stands, there are some instructions which are not intrinsified (like not) and we are actively working on it
- When I run with disabled intrinsification, it seems that algorithm is not finding indices correctly. So it leads me to believe that version I have [1] is not correctly implemented or default java implementation of vector api has a bug.

Anyway, let us know how it goes with using the -XX:-UseVectorApiIntrinsics flag.

Thanks,
Razvan

[1]
    public static <S extends Vector.Shape> IntVector<S> binarySearchCDF(IntVector.IntSpecies<S> ispec,
                                                                        FloatVector.FloatSpecies<S> fspec, float[][] input,
                                                                        int fromIndex, int toIndex, FloatVector<S> key) {
        IntVector<S> low = ispec.broadcast(fromIndex);
        IntVector<S> high = ispec.broadcast(toIndex - 1);
        IntVector<S> one = ispec.broadcast(1);

        Vector.Mask<Float,S> mask = key.species().trueMask();

        int[] indicesBuffer = new int[key.length()];
        float[] valuesBuffer = new float[key.length()];

        while (mask.anyTrue()) {
            IntVector<S> mid =
                    low.add(high,mask.rebracket(ispec)).shiftR(1);
            mid.intoArray(indicesBuffer,0);
            for (int i = 0; i < valuesBuffer.length; i++) {
                valuesBuffer[i] = input[i][indicesBuffer[i]];
            }
            FloatVector<S> values =
                    key.species().fromArray(valuesBuffer,0);

            Vector.Mask<Integer,S> lessThanKey = values.lessThan(key).and(mask).rebracket(ispec);
            low = low.blend(mid.add(one),lessThanKey);
            Vector.Mask<Integer,S> greaterThanKey = values.greaterThan(key).and(mask).rebracket(ispec);
            high = high.blend(mid.sub(one),greaterThanKey);
            Vector.Mask<Integer,S> equalsKey = values.equal(key).and(mask).rebracket(ispec);
            low = low.blend(mid,equalsKey);
            mask = mask.and(equalsKey.rebracket(fspec).not());
            mask = mask.and(low.lessThan(high).rebracket(fspec));
        }

        return low;
    }

-----Original Message-----
From: panama-dev [mailto:panama-dev-bounces at openjdk.java.net] On Behalf Of Adam Pocock
Sent: Friday, March 09, 2018 1:45 PM
To: panama-dev at openjdk.java.net
Subject: [vector] Infinite loop in SIMD binary search

I'm still attempting to debug my binary search, which now doesn't crash, but occasionally loops infinitely after it gets deoptimised (assuming I'm reading the -XX:+PrintCompilation output correctly).

It's the same code as before, running on the head of the vectorIntrinsics branch (changeset:   49340:279620461bde). Running my test example which repeatedly performs the same binary search using 8 lanes on the same input array (a float[8][60]), at some point around
10,000 iterations the search itself goes into an infinite loop. The arrays being searched are 60 elements long, smaller sized arrays don't seem to trigger this, but I've not found a specific point that triggers it. I may not be giving smaller arrays enough time to hit the same compilation point. When it hits the infinite loop with print compilation turned on it says:

     832  849       3
com.oracle.labs.mlrg.topicmodel.util.vector.BinarySearch::binarySearchCDF
(277 bytes)   made not entrant

or something similar in terms of timestamps, plus a few other methods that look unrelated and change with each run.

This behaviour occurs on both release and fastdebug builds on Linux.

What other information can I provide to help diagnose this?

Thanks,

Adam

--
Adam Pocock
Principal Member of Technical Staff
Machine Learning Research Group
Oracle Labs, Burlington, MA