Final submission (#669)

* more efficient max, min

* optimize pipeline

* apply parallel to both submissions

* fix bug

1 files changed, 62 insertions, 21 deletions

diff --git a/src/main/java/dev/morling/onebrc/CalculateAverage_merykitty.java b/src/main/java/dev/morling/onebrc/CalculateAverage_merykitty.java
index 1f5acf3..502002f 100644
--- a/src/main/java/dev/morling/onebrc/CalculateAverage_merykitty.java
+++ b/src/main/java/dev/morling/onebrc/CalculateAverage_merykitty.java
@@ -75,8 +75,12 @@ public class CalculateAverage_merykitty {
         }
 
         void observe(Aggregator node, long value) {
-            node.min = Math.min(node.min, value);
-            node.max = Math.max(node.max, value);
+            if (node.min > value) {
+                node.min = value;
+            }
+            if (node.max < value) {
+                node.max = value;
+            }
             node.sum += value;
             node.count++;
         }
@@ -109,7 +113,7 @@ public class CalculateAverage_merykitty {
             var node = new Aggregator();
             node.keySize = size;
             this.nodes[bucket] = node;
-            MemorySegment.copy(data, offset, MemorySegment.ofArray(this.keyData), (long) bucket * KEY_SIZE, size);
+            MemorySegment.copy(data, offset, MemorySegment.ofArray(this.keyData), (long) bucket * KEY_SIZE, size + 1);
             return node;
         }
 
@@ -222,11 +226,12 @@ public class CalculateAverage_merykitty {
         var line = ByteVector.fromMemorySegment(BYTE_SPECIES, data, offset, ByteOrder.nativeOrder());
 
         // Find the delimiter ';'
-        int keySize = line.compare(VectorOperators.EQ, ';').firstTrue();
+        long semicolons = line.compare(VectorOperators.EQ, ';').toLong();
 
         // If we cannot find the delimiter in the vector, that means the key is
         // longer than the vector, fall back to scalar processing
-        if (keySize == BYTE_SPECIES.vectorByteSize()) {
+        if (semicolons == 0) {
+            int keySize = BYTE_SPECIES.length();
             while (data.get(ValueLayout.JAVA_BYTE, offset + keySize) != ';') {
                 keySize++;
             }
@@ -235,6 +240,7 @@ public class CalculateAverage_merykitty {
         }
 
         // We inline the searching of the value in the hash map
+        int keySize = Long.numberOfTrailingZeros(semicolons);
         int x;
         int y;
         if (keySize >= Integer.BYTES) {
@@ -260,7 +266,7 @@ public class CalculateAverage_merykitty {
 
             var nodeKey = ByteVector.fromArray(BYTE_SPECIES, aggrMap.keyData, bucket * PoorManMap.KEY_SIZE);
             long eqMask = line.compare(VectorOperators.EQ, nodeKey).toLong();
-            long validMask = -1L >>> -keySize;
+            long validMask = semicolons ^ (semicolons - 1);
             if ((eqMask & validMask) == validMask) {
                 break;
             }
@@ -269,28 +275,63 @@ public class CalculateAverage_merykitty {
         return parseDataPoint(aggrMap, node, data, offset + keySize + 1);
     }
 
-    // Process all lines that start in [offset, limit)
-    private static PoorManMap processFile(MemorySegment data, long offset, long limit) {
-        var aggrMap = new PoorManMap();
-        // Find the start of a new line
-        if (offset != 0) {
-            offset--;
-            while (offset < limit) {
-                if (data.get(ValueLayout.JAVA_BYTE, offset++) == '\n') {
-                    break;
-                }
+    private static long findOffset(MemorySegment data, long offset, long limit) {
+        if (offset == 0) {
+            return offset;
+        }
+
+        offset--;
+        while (offset < limit) {
+            if (data.get(ValueLayout.JAVA_BYTE, offset++) == '\n') {
+                break;
             }
         }
+        return offset;
+    }
 
-        // If there is no line starting in this segment, just return
+    // Process all lines that start in [offset, limit)
+    private static PoorManMap processFile(MemorySegment data, long offset, long limit) {
+        var aggrMap = new PoorManMap();
         if (offset == limit) {
             return aggrMap;
         }
+        int batches = 2;
+        long batchSize = Math.ceilDiv(limit - offset, batches);
+        long offset0 = offset;
+        long offset1 = offset + batchSize;
+        long limit0 = Math.min(offset1, limit);
+        long limit1 = limit;
 
-        // The main loop, optimized for speed
-        while (offset < limit - Math.max(BYTE_SPECIES.vectorByteSize(),
-                Long.BYTES + 1 + KEY_MAX_SIZE)) {
-            offset = iterate(aggrMap, data, offset);
+        // Find the start of a new line
+        offset0 = findOffset(data, offset0, limit0);
+        offset1 = findOffset(data, offset1, limit1);
+
+        long mainLoopMinWidth = Math.max(BYTE_SPECIES.vectorByteSize(), KEY_MAX_SIZE + 1 + Long.BYTES);
+        if (limit1 - offset1 < mainLoopMinWidth) {
+            offset = findOffset(data, offset, limit);
+            while (offset < limit - mainLoopMinWidth) {
+                offset = iterate(aggrMap, data, offset);
+            }
+        }
+        else {
+            while (true) {
+                boolean finish = false;
+                if (offset0 < limit0) {
+                    offset0 = iterate(aggrMap, data, offset0);
+                }
+                else {
+                    finish = true;
+                }
+                if (offset1 < limit1 - mainLoopMinWidth) {
+                    offset1 = iterate(aggrMap, data, offset1);
+                }
+                else {
+                    if (finish) {
+                        break;
+                    }
+                }
+            }
+            offset = offset1;
         }
 
         // Now we are at the tail, just be simple