[vector] Infinite loop in SIMD binary search

[Adam Pocock]

Hi Razvan,

I'm running the binary search with the same key vector on the same float[][] array, just in a loop counting up iterations. So the algorithm executes correctly producing the same output for the first few thousand iterations before dying which is why I suspect a compiler issue. It executes all the iterations correctly with “-XX:-UseVectorApiIntrinsics”.

I’ll try the patch for comparisons next week and see what effect that has. I’ll also write some unit tests comparing the output to that of Arrays.binarySearch and see if I can root out any bugs in the implementation.

Thanks,

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

> On 9 Mar 2018, at 17:38, Lupusoru, Razvan A <razvan.a.lupusoru at intel.com> wrote:
> 
> 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
>