Updates for gamlerhart: Simpler & Faster (#580)

* Update with Rounding Bugfix

* Simplification of Merging Results

* More Plain Java Code for Value Storage

* Improve Performance by Stupid Hash

Drop around 3 seconds on my machine by
simplifying the hash to be ridicules stupid,
but faster.

* Fix outdated comment

1 files changed, 86 insertions, 131 deletions

diff --git a/src/main/java/dev/morling/onebrc/CalculateAverage_gamlerhart.java b/src/main/java/dev/morling/onebrc/CalculateAverage_gamlerhart.java
index 2f73a33..5d0a4bd 100644
--- a/src/main/java/dev/morling/onebrc/CalculateAverage_gamlerhart.java
+++ b/src/main/java/dev/morling/onebrc/CalculateAverage_gamlerhart.java
@@ -24,7 +24,10 @@ import java.nio.ByteOrder;
 import java.nio.channels.FileChannel;
 import java.nio.file.Path;
 import java.util.ArrayList;
+import java.util.Iterator;
 import java.util.TreeMap;
+import java.util.stream.Collector;
+import java.util.stream.Collectors;
 
 import static java.lang.Double.doubleToRawLongBits;
 import static java.lang.Double.longBitsToDouble;
@@ -69,19 +72,16 @@ public class CalculateAverage_gamlerhart {
             ArrayList<Section> sections = splitFileIntoSections(fileSize, fileContent);
 
             var loopBound = byteVec.loopBound(fileSize) - vecLen;
-            PrivateHashMap result = sections.stream()
+            var result = sections.stream()
                     .parallel()
                     .map(s -> {
                         return parseSection(s.start, s.end, loopBound, fileContent);
-                    }).reduce((mine, other) -> {
-                        assert mine != other;
-                        mine.mergeFrom(fileContent, other);
-                        return mine;
-                    })
-                    .get();
+                    });
 
             var measurements = new TreeMap<String, ResultRow>();
-            result.fill(fileContent, measurements);
+            result.forEachOrdered(m -> {
+                m.fillMerge(fileContent, measurements);
+            });
             System.out.println(measurements);
         }
     }
@@ -160,11 +160,22 @@ public class CalculateAverage_gamlerhart {
         // Encoding:
         // - Key: long
         // - 48 bits index, 16 bits length
-        // - min: double
-        // - max: double
-        // - sum: double
-        // - double: double
-        final long[] keyValues = new long[SIZE * 5];
+        final long[] keys = new long[SIZE];
+        final Value[] values = new Value[SIZE];
+
+        private class Value {
+            public Value(double min, double max, double sum, long count) {
+                this.min = min;
+                this.max = max;
+                this.sum = sum;
+                this.count = count;
+            }
+
+            public double min;
+            public double max;
+            public double sum;
+            public long count;
+        }
 
         // int debug_size = 0;
 
@@ -179,43 +190,40 @@ public class CalculateAverage_gamlerhart {
         }
 
         private static int calculateHash(MemorySegment file, long pos, int len) {
-            int hashCode = 1;
-            int i = 0;
-            int intBound = (len / 4) * 4;
-            for (; i < intBound; i += 4) {
-                int v = file.get(INT_UNALIGNED_BIG_ENDIAN, pos + i);
-                hashCode = 31 * hashCode + v;
+            if (len > 4) {
+                return file.get(INT_UNALIGNED_BIG_ENDIAN, pos) + 31 * len;
             }
-            for (; i < len; i++) {
-                int v = file.get(JAVA_BYTE, pos + i);
-                hashCode = 31 * hashCode + v;
+            else {
+                int hashCode = len;
+                int i = 0;
+                for (; i < len; i++) {
+                    int v = file.get(JAVA_BYTE, pos + i);
+                    hashCode = 31 * hashCode + v;
+                }
+                return hashCode;
             }
-            return hashCode;
         }
 
         private void doAdd(MemorySegment file, int hash, long pos, int len, double val) {
             int slot = hash & MASK;
             for (var probe = 0; probe < 20000; probe++) {
-                var iSl = ((slot + probe) & MASK) * 5;
-                var slotEntry = keyValues[iSl];
+                var iSl = ((slot + probe) & MASK);
+                var slotEntry = keys[iSl];
 
                 var emtpy = slotEntry == 0;
                 if (emtpy) {
                     long keyInfo = pos << SHIFT_POS | len;
-                    long valueBits = doubleToRawLongBits(val);
-                    keyValues[iSl] = keyInfo;
-                    keyValues[iSl + 1] = valueBits;
-                    keyValues[iSl + 2] = valueBits;
-                    keyValues[iSl + 3] = valueBits;
-                    keyValues[iSl + 4] = 1;
+                    keys[iSl] = keyInfo;
+                    values[iSl] = new Value(val, val, val, 1);
                     // debug_size++;
                     return;
                 }
                 else if (isSameEntry(file, slotEntry, pos, len)) {
-                    keyValues[iSl + 1] = doubleToRawLongBits(Math.min(longBitsToDouble(keyValues[iSl + 1]), val));
-                    keyValues[iSl + 2] = doubleToRawLongBits(Math.max(longBitsToDouble(keyValues[iSl + 2]), val));
-                    keyValues[iSl + 3] = doubleToRawLongBits(longBitsToDouble(keyValues[iSl + 3]) + val);
-                    keyValues[iSl + 4] = keyValues[iSl + 4] + 1;
+                    var vE = values[iSl];
+                    vE.min = Math.min(vE.min, val);
+                    vE.max = Math.max(vE.max, val);
+                    vE.sum = vE.sum + val;
+                    vE.count++;
                     return;
                 }
                 else {
@@ -268,118 +276,65 @@ public class CalculateAverage_gamlerhart {
             return true;
         }
 
-        public PrivateHashMap mergeFrom(MemorySegment file, PrivateHashMap other) {
-            for (int slot = 0; slot < other.keyValues.length / 5; slot++) {
-                int srcI = slot * 5;
-                long keyE = other.keyValues[srcI];
-                if (keyE != 0) {
-                    long oPos = (keyE & MASK_POS) >> SHIFT_POS;
-                    int oLen = (int) (keyE & MASK_LEN);
-                    addMerge(file, other, srcI, oPos, oLen);
-                }
-            }
-            return this;
-        }
-
-        private void addMerge(MemorySegment file, PrivateHashMap other, int srcI, long oPos, int oLen) {
-            int slot = calculateHash(file, oPos, oLen) & MASK;
-            for (var probe = 0; probe < 20000; probe++) {
-                var iSl = ((slot + probe) & MASK) * 5;
-                var slotEntry = keyValues[iSl];
-
-                var emtpy = slotEntry == 0;
-                // var debugKey = new String(file.asSlice(oPos, oLen).toArray(JAVA_BYTE));
-                if (emtpy) {
-                    // if (debugKey.equals("Cabo San Lucas")) {
-                    // System.out.println("=> VALUES (init) " + debugKey + "@" + iSl + " max: " + longBitsToDouble(other.keyValues[srcI + 2]) + "," + longBitsToDouble(keyValues[iSl + 2]));
-                    // }
-                    keyValues[iSl] = other.keyValues[srcI];
-                    keyValues[iSl + 1] = other.keyValues[srcI + 1];
-                    keyValues[iSl + 2] = other.keyValues[srcI + 2];
-                    keyValues[iSl + 3] = other.keyValues[srcI + 3];
-                    keyValues[iSl + 4] = other.keyValues[srcI + 4];
-                    // debug_size++;
-                    return;
-                }
-                else if (isSameEntry(file, slotEntry, oPos, oLen)) {
-                    // if (debugKey.equals("Cabo San Lucas")) {
-                    // System.out.println("=> VALUES (merge) " + "@" + iSl + debugKey + " max: " + longBitsToDouble(other.keyValues[srcI + 2]) + ","
-                    // + longBitsToDouble(keyValues[iSl + 2]) + "=> "
-                    // + Math.max(longBitsToDouble(keyValues[iSl + 2]), longBitsToDouble(other.keyValues[srcI + 2])));
-                    // }
-                    keyValues[iSl + 1] = doubleToRawLongBits(Math.min(longBitsToDouble(keyValues[iSl + 1]), longBitsToDouble(other.keyValues[srcI + 1])));
-                    keyValues[iSl + 2] = doubleToRawLongBits(Math.max(longBitsToDouble(keyValues[iSl + 2]), longBitsToDouble(other.keyValues[srcI + 2])));
-                    keyValues[iSl + 3] = doubleToRawLongBits(longBitsToDouble(keyValues[iSl + 3]) + longBitsToDouble(other.keyValues[srcI + 3]));
-                    keyValues[iSl + 4] = keyValues[iSl + 4] + other.keyValues[srcI + 4];
-                    // if (debugKey.equals("Cabo San Lucas")) {
-                    // System.out.println("=> VALUES (after-merge) self: "+ "@" + iSl + System.identityHashCode(this) + ":"+ debugKey + " max: " +
-                    // + longBitsToDouble(keyValues[iSl + 2]) + "=> ");
-                    // }
-                    return;
-                }
-                else {
-                    // long keyPos = (slotEntry & MASK_POS) >> SHIFT_POS;
-                    // int keyLen = (int) (slotEntry & MASK_LEN);
-                    // System.out.println("Colliding " + new String(file.asSlice(pos,len).toArray(ValueLayout.JAVA_BYTE)) +
-                    // " with key" + new String(file.asSlice(keyPos,keyLen).toArray(ValueLayout.JAVA_BYTE)) +
-                    // " hash " + hash + " slot " + slot + "+" + probe + " at " + iSl);
-                    // debug_reprobeMax = Math.max(debug_reprobeMax, probe);
-                }
-            }
-            throw new IllegalStateException("More than 20000 reprobes");
-        }
-
-        public void fill(MemorySegment file, TreeMap<String, ResultRow> treeMap) {
-            for (int i = 0; i < keyValues.length / 5; i++) {
-                var ji = i * 5;
-                long keyE = keyValues[ji];
+        public void fillMerge(MemorySegment file, TreeMap<String, ResultRow> treeMap) {
+            for (int i = 0; i < keys.length; i++) {
+                var ji = i;
+                long keyE = keys[ji];
                 if (keyE != 0) {
                     long keyPos = (keyE & MASK_POS) >> SHIFT_POS;
                     int keyLen = (int) (keyE & MASK_LEN);
                     byte[] keyBytes = new byte[keyLen];
                     MemorySegment.copy(file, JAVA_BYTE, keyPos, keyBytes, 0, keyLen);
                     var key = new String(keyBytes);
-                    var min = longBitsToDouble(keyValues[ji + 1]);
-                    var max = longBitsToDouble(keyValues[ji + 2]);
-                    var sum = longBitsToDouble(keyValues[ji + 3]);
-                    var count = keyValues[ji + 4];
-                    treeMap.put(key, new ResultRow(min, sum / count, max));
+                    var vE = values[ji];
+                    var min = vE.min;
+                    var max = vE.max;
+                    var sum = vE.sum;
+                    var count = vE.count;
+                    treeMap.compute(key, (k, e) -> {
+                        if (e == null) {
+                            return new ResultRow(min, max, sum, count);
+                        }
+                        else {
+                            return new ResultRow(Math.min(e.min, min), Math.max(e.max, max), e.sum + sum, e.count + count);
+                        }
+                    });
                 }
             }
         }
 
-        public String debugPrint(MemorySegment file) {
-            StringBuilder b = new StringBuilder();
-            for (int i = 0; i < keyValues.length / 5; i++) {
-                var ji = i * 5;
-                long keyE = keyValues[ji];
-                if (keyE != 0) {
-                    long keyPos = (keyE & MASK_POS) >> SHIFT_POS;
-                    int keyLen = (int) (keyE & MASK_LEN);
-                    byte[] keyBytes = new byte[keyLen];
-                    MemorySegment.copy(file, JAVA_BYTE, keyPos, keyBytes, 0, keyLen);
-                    var key = new String(keyBytes);
-                    var min = longBitsToDouble(keyValues[ji + 1]);
-                    var max = longBitsToDouble(keyValues[ji + 2]);
-                    var sum = longBitsToDouble(keyValues[ji + 3]);
-                    var count = keyValues[ji + 4];
-                    b.append("{").append(key).append("@").append(ji)
-                            .append(",").append(min)
-                            .append(",").append(max)
-                            .append(",").append(sum)
-                            .append(",").append(count).append("},");
-                }
-            }
-            return b.toString();
-        }
+        // public String debugPrint(MemorySegment file) {
+        // StringBuilder b = new StringBuilder();
+        // for (int i = 0; i < keyValues.length / 5; i++) {
+        // var ji = i * 5;
+        // long keyE = keyValues[ji];
+        // if (keyE != 0) {
+        // long keyPos = (keyE & MASK_POS) >> SHIFT_POS;
+        // int keyLen = (int) (keyE & MASK_LEN);
+        // byte[] keyBytes = new byte[keyLen];
+        // MemorySegment.copy(file, JAVA_BYTE, keyPos, keyBytes, 0, keyLen);
+        // var key = new String(keyBytes);
+        // var min = longBitsToDouble(keyValues[ji + 1]);
+        // var max = longBitsToDouble(keyValues[ji + 2]);
+        // var sum = longBitsToDouble(keyValues[ji + 3]);
+        // var count = keyValues[ji + 4];
+        // b.append("{").append(key).append("@").append(ji)
+        // .append(",").append(min)
+        // .append(",").append(max)
+        // .append(",").append(sum)
+        // .append(",").append(count).append("},");
+        // }
+        // }
+        // return b.toString();
+        // }
     }
 
     record Section(long start, long end) {
     }
 
-    private static record ResultRow(double min, double mean, double max) {
+    private static record ResultRow(double min, double max, double sum, long count) {
         public String toString() {
-            return round(min) + "/" + round(mean) + "/" + round(max);
+            return round(min) + "/" + round(((Math.round(sum * 10.0) / 10.0) / count)) + "/" + round(max);
         }
 
         private double round(double value) {