RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
Richard Startin
github.com+16439049+richardstartin at openjdk.java.net
Mon Sep 13 17:28:45 UTC 2021
On Thu, 13 May 2021 10:22:57 GMT, Laurent Bourgès <lbourges at openjdk.org> wrote:
>> Hi @iaroslavski I'm unconvinced that this work was from 14/06/2020 - I believe this work derives from an unsigned radix sort I implemented on 10/04/2021 https://github.com/richardstartin/radix-sort-benchmark/commit/ab4da230e1d0ac68e5ee2cee38d71c7e7d50f49b#diff-6c13d3fb74f38906677dbfa1a70a123c8e5baf4a39219c81ef121e078d0013bcR226 which has numerous structural similarities to this work:
>> * Producing all four histograms in one pass
>> * Skipping passes based on detecting the total in the histogram
>> * Bailing out of the skip detection if a nonzero value not equal to the total is encountered
>> * Manually unrolling the LSD radix sort loop in order to avoid array copies
>>
>> My implementation from 10th April is below for reference:
>>
>> public static void unrollOnePassHistogramsSkipLevels(int[] data) {
>> int[] histogram1 = new int[257];
>> int[] histogram2 = new int[257];
>> int[] histogram3 = new int[257];
>> int[] histogram4 = new int[257];
>>
>> for (int value : data) {
>> ++histogram1[(value & 0xFF) + 1];
>> ++histogram2[((value >>> 8) & 0xFF) + 1];
>> ++histogram3[((value >>> 16) & 0xFF) + 1];
>> ++histogram4[(value >>> 24) + 1];
>> }
>> boolean skipLevel1 = canSkipLevel(histogram1, data.length);
>> boolean skipLevel2 = canSkipLevel(histogram2, data.length);
>> boolean skipLevel3 = canSkipLevel(histogram3, data.length);
>> boolean skipLevel4 = canSkipLevel(histogram4, data.length);
>>
>> if (skipLevel1 && skipLevel2 && skipLevel3 && skipLevel4) {
>> return;
>> }
>> int[] copy = new int[data.length];
>>
>> int[] source = data;
>> int[] dest = copy;
>>
>> if (!skipLevel1) {
>> for (int i = 1; i < histogram1.length; ++i) {
>> histogram1[i] += histogram1[i - 1];
>> }
>> for (int value : source) {
>> dest[histogram1[value & 0xFF]++] = value;
>> }
>> if (!skipLevel2 || !skipLevel3 || !skipLevel4) {
>> int[] tmp = dest;
>> dest = source;
>> source = tmp;
>> }
>> }
>>
>> if (!skipLevel2) {
>> for (int i = 1; i < histogram2.length; ++i) {
>> histogram2[i] += histogram2[i - 1];
>> }
>> for (int value : source) {
>> dest[histogram2[(value >>> 8) & 0xFF]++] = value;
>> }
>> if (!skipLevel3 || !skipLevel4) {
>> int[] tmp = dest;
>> dest = source;
>> source = tmp;
>> }
>> }
>>
>> if (!skipLevel3) {
>> for (int i = 1; i < histogram3.length; ++i) {
>> histogram3[i] += histogram3[i - 1];
>> }
>> for (int value : data) {
>> dest[histogram3[(value >>> 16) & 0xFF]++] = value;
>> }
>> if (!skipLevel4) {
>> int[] tmp = dest;
>> dest = source;
>> source = tmp;
>> }
>> }
>>
>> if (!skipLevel4) {
>> for (int i = 1; i < histogram4.length; ++i) {
>> histogram4[i] += histogram4[i - 1];
>> }
>> for (int value : source) {
>> dest[histogram4[value >>> 24]++] = value;
>> }
>> }
>> if (dest != data) {
>> System.arraycopy(dest, 0, data, 0, data.length);
>> }
>> }
>>
>> private static boolean canSkipLevel(int[] histogram, int dataSize) {
>> for (int count : histogram) {
>> if (count == dataSize) {
>> return true;
>> } else if (count > 0) {
>> return false;
>> }
>> }
>> return true;
>> }
>>
>>
>> Moreover, @bourgesl forked my repository on 11/04/2021 and communicated with me about doing so. On 25/04/2021 there was a new implementation of `DualPivotQuicksort` with a signed radix sort but the same structural similarities, and with the same method and variable names in places https://github.com/bourgesl/radix-sort-benchmark/commit/90ff7e427da0fa49f374bff0241fb2487bd87bde#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R607-R609
>>
>>
>> // TODO add javadoc
>> private static void radixSort(Sorter sorter, int[] a, int low, int high) {
>> int[] b;
>> // LBO: prealloc (high - low) +1 element:
>> if (sorter == null || (b = sorter.b) == null || b.length < (high - low)) {
>> // System.out.println("alloc b: " + (high - low));
>> b = new int[high - low];
>> }
>>
>> int[] count1, count2, count3, count4;
>> if (sorter != null) {
>> sorter.resetRadixBuffers();
>> count1 = sorter.count1;
>> count2 = sorter.count2;
>> count3 = sorter.count3;
>> count4 = sorter.count4;
>> } else {
>> // System.out.println("alloc radix buffers(4x256)");
>> count1 = new int[256];
>> count2 = new int[256];
>> count3 = new int[256];
>> count4 = new int[256];
>> }
>>
>> for (int i = low; i < high; ++i) {
>> --count1[ a[i] & 0xFF ];
>> --count2[(a[i] >>> 8) & 0xFF ];
>> --count3[(a[i] >>> 16) & 0xFF ];
>> --count4[(a[i] >>> 24) ^ 0x80 ];
>> }
>>
>> boolean skipLevel4 = canSkipLevel(count4, low - high);
>> boolean skipLevel3 = skipLevel4 && canSkipLevel(count3, low - high);
>> boolean skipLevel2 = skipLevel3 && canSkipLevel(count2, low - high);
>>
>> count1[255] += high;
>> count2[255] += high;
>> count3[255] += high;
>> count4[255] += high;
>>
>> // 1 todo process LSD
>> for (int i = 255; i > 0; --i) {
>> count1[i - 1] += count1[i];
>> }
>>
>> for (int i = low; i < high; ++i) {
>> b[count1[a[i] & 0xFF]++ - low] = a[i];
>> }
>>
>> if (skipLevel2) {
>> System.arraycopy(b, 0, a, low, high - low);
>> return;
>> }
>>
>> // 2
>> for (int i = 255; i > 0; --i) {
>> count2[i - 1] += count2[i];
>> }
>>
>> //for (int value : b) {
>> // a[count2[(value >> 8) & 0xFF]++] = value;
>> for (int i = low; i < high; ++i) {
>> a[count2[(b[i] >> 8) & 0xFF]++] = b[i];
>> }
>>
>> if (skipLevel3) {
>> return;
>> }
>>
>> // 3
>> for (int i = 255; i > 0; --i) {
>> count3[i - 1] += count3[i];
>> }
>>
>> for (int i = low; i < high; ++i) {
>> b[count3[(a[i] >> 16) & 0xFF]++ - low] = a[i];
>> }
>>
>> if (skipLevel4) {
>> System.arraycopy(b, 0, a, low, high - low);
>> return;
>> }
>>
>> // 4
>> for (int i = 255; i > 0; --i) {
>> count4[i - 1] += count4[i];
>> }
>>
>> // for (int value : b) {
>> // a[count4[ (value >>> 24) ^ 0x80]++] = value;
>> for (int i = low; i < high; ++i) {
>> a[count4[ (b[i] >>> 24) ^ 0x80]++] = b[i];
>> }
>> }
>>
>> // TODO: add javadoc
>> private static boolean canSkipLevel(int[] count, int total) {
>> for (int c : count) {
>> if (c == 0) {
>> continue;
>> }
>> return c == total;
>> }
>> return true;
>> }
>>
>>
>> Later, the name of the method `canSkipLevel` changed to `skipByte`: https://github.com/bourgesl/radix-sort-benchmark/commit/a693b26b2e2c14cfeedf9c753c9d643096b0e38d#diff-397ce8fd791e2ce508cf9127201bc9ab46264cd2a79fd0487a63569f2e4b59b2R719 - this is the name of the method in the version of this sort you committed on 05/01/2021 https://github.com/richardstartin/sorting/commit/f076073b8b819a9687613903a164e3ed71821769#diff-4b4d68fc834c2ad12a9fb9d316a812221af7c398338ed2ee907d0a795e7aadafR601-R604
>>
>>
>> // TODO add javadoc
>> // private
>> static void radixSort(Sorter sorter, int[] a, int low, int high) {
>> //System.out.println(" Radix !!!");
>> int[] count1 = new int[256];
>> int[] count2 = new int[256];
>> int[] count3 = new int[256];
>> int[] count4 = new int[256];
>>
>> for (int i = low; i < high; ++i) {
>> count1[ a[i] & 0xFF ]--;
>> count2[(a[i] >>> 8) & 0xFF ]--;
>> count3[(a[i] >>> 16) & 0xFF ]--;
>> count4[(a[i] >>> 24) ^ 0x80 ]--;
>> }
>> boolean skipByte4 = skipByte(count4, low - high, high, true);
>> boolean skipByte3 = skipByte(count3, low - high, high, skipByte4);
>> boolean skipByte2 = skipByte(count2, low - high, high, skipByte3);
>> boolean skipByte1 = skipByte(count1, low - high, high, skipByte2);
>>
>> if (skipByte1) {
>> //Main.check(a, low, high - 1); // todo
>> return;
>> }
>> // int xorA = Main.getXor(a, low, high);
>>
>> int[] b; int offset = low;
>>
>> if (sorter == null || (b = (int[]) sorter.b) == null) {
>> b = new int[high - low];
>> } else {
>> offset = sorter.offset;
>> //System.out.println(" !!!! offset: " + offset);
>> }
>> int start = low - offset;
>> int last = high - offset;
>>
>>
>> // 1 todo process LSD
>> for (int i = low; i < high; ++i) {
>> b[count1[a[i] & 0xFF]++ - offset] = a[i];
>> }
>>
>> // if (xorA != Main.getXor(a, low, high)) System.out.println("6K_4 1 xor changed");
>>
>> if (skipByte2) {
>> System.arraycopy(b, start, a, low, high - low);
>> //Main.check(a, low, high - 1); // todo
>> return;
>> }
>>
>> // 2
>> for (int i = start; i < last; ++i) {
>> a[count2[(b[i] >> 8) & 0xFF]++] = b[i];
>> }
>>
>> // if (xorA != Main.getXor(a, low, high)) System.out.println("6K_4 2 xor changed");
>>
>> if (skipByte3) {
>> //Main.check(a, low, high - 1); // todo
>> return;
>> }
>>
>> // 3
>> for (int i = low; i < high; ++i) {
>> b[count3[(a[i] >> 16) & 0xFF]++ - offset] = a[i];
>> }
>>
>> // if (xorA != Main.getXor(a, low, high)) System.out.println("6K_4 3 xor changed");
>>
>> if (skipByte4) {
>> System.arraycopy(b, start, a, low, high - low);
>> //Main.check(a, low, high - 1); // todo
>> return;
>> }
>>
>> // if (xorA != Main.getXor(a, low, high)) System.out.println("6K_4 4 xor changed");
>> // 4
>> for (int i = start; i < last; ++i) {
>> a[count4[(b[i] >>> 24) ^ 0x80]++] = b[i];
>> }
>> // if (xorA != Main.getXor(a, low, high)) System.out.println("6K_4 5 xor changed");
>> //Main.check(a, low, high - 1); // todo
>> }
>>
>> // TODO: add javadoc
>> private static boolean skipByte(int[] count, int total, int high, boolean prevSkip) {
>> if (prevSkip) {
>> for (int c : count) {
>> if (c == 0) {
>> continue;
>> }
>> if (c == total) {
>> return true;
>> }
>> break;
>> }
>> }
>> // todo create historgam
>> count[255] += high;
>>
>> for (int i = 255; i > 0; --i) {
>> count[i - 1] += count[i];
>> }
>> return false;
>> }
>>
>>
>> `skipByte` was later renamed to `passLevel` here, which is the name used in this PR: https://github.com/richardstartin/sorting/commit/22357e407d3ae7a1e159e06fe4afbb2c57f7d34c#diff-4b4d68fc834c2ad12a9fb9d316a812221af7c398338ed2ee907d0a795e7aadaf
>>
>> Given the structural similarities mentioned, the chronological order of these commits, and the demonstrable provenance of the method name `passLevel` from `canSkipLevel` and since you have patented sort algorithms in the past, I want to make sure that it is recognised that this work is derived from my own.
>
> You misunderstood my approach:
> - vladimir & tagir discussed radix sorts since previous work on DPQS in 2019
> - I enjoyed reading your blog post testing the performance of your radix sort vs Arrays.sort()
> - I tested and forked your radix-sort-benchmark to reproduce your experiments on openjdk16 (dpqs 19.11)
> - Vladimir proposed his own radixsort()
> - I did port DPQS impls in my fork of your benchmark to make a global comparison: dpqs 11, 19, 21 vs yours + arrays.sort(): it helped comparing implementations and decide when radix sort wins depending on dataset presortness
> - I tried many variants on my github repositories, but Vladimir never merged any of my change as he is not a regular github user (clone, fork, merge).
>
> Our goal is not to underestimate your work (sort + benchmark) but Vladimir wrote his own code, me many experiments (tests, benchmarks) to obtain this original patch, written by Vladimir, with his radix sort implementation working on any int/long/float/double arrays, following the GPLv2 license.
>
> You gave me motivation to make Arrays.sort() faster and we worked hard to write, test and benchmark this patch to be ready for OpenJDK 17
Perhaps we can resolve this issue in private - my email address is on my profile (or in the commits in `radix-sort-benchmark`)?
-------------
PR: https://git.openjdk.java.net/jdk/pull/3938
More information about the core-libs-dev
mailing list