You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2025/07/23 19:25:41 UTC

(lucene) branch main updated: Simplify ForDeltaUtil's prefix sum. (#14979)

This is an automated email from the ASF dual-hosted git repository.

jpountz pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/main by this push:
     new a2a9a3b375b Simplify ForDeltaUtil's prefix sum. (#14979)
a2a9a3b375b is described below

commit a2a9a3b375b83592407b5486871d427ea6a7b340
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Wed Jul 23 21:25:36 2025 +0200

    Simplify ForDeltaUtil's prefix sum. (#14979)
    
    I remember benchmarking prefix sums quite extensively, and unrolled loops
    performed significantly better than their rolled on counterpart, both on micro
    and macro benchmarks:
    
    ```java
    private static void prefixSum(int[] arr, int len) {
      for (int i = 1; i < len; ++i) {
        arr[i] += arr[i-1];
      }
    }
    ```
    
    However, I recently discovered that rewriting the loop this way performs much
    better, and almost on par with the unrolled variant:
    
    ```java
    private static void prefixSum(int[] arr, int len) {
      int sum = 0;
      for (int i = 0; i < len; ++i) {
        sum += arr[i];
        arr[i] = sum;
      }
    }
    ```
---
 .../generated/checksums/generateForDeltaUtil.json  |   4 +-
 .../lucene/codecs/lucene103/ForDeltaUtil.java      | 115 ++-------------------
 .../lucene/codecs/lucene103/gen_ForDeltaUtil.py    | 115 ++-------------------
 3 files changed, 20 insertions(+), 214 deletions(-)

diff --git a/lucene/core/src/generated/checksums/generateForDeltaUtil.json b/lucene/core/src/generated/checksums/generateForDeltaUtil.json
index 9d70786985f..f328dee58b7 100644
--- a/lucene/core/src/generated/checksums/generateForDeltaUtil.json
+++ b/lucene/core/src/generated/checksums/generateForDeltaUtil.json
@@ -1,4 +1,4 @@
 {
-    "lucene/core/src/java/org/apache/lucene/codecs/lucene103/ForDeltaUtil.java": "dc896d5df4b2a091918bfa14b30aad417feaffac",
-    "lucene/core/src/java/org/apache/lucene/codecs/lucene103/gen_ForDeltaUtil.py": "d622cc9f9a13987a07c2472a1c5b0111a3a7bc62"
+    "lucene/core/src/java/org/apache/lucene/codecs/lucene103/ForDeltaUtil.java": "7e14917412c0f4e29453c5b604bf4dddf08d40d1",
+    "lucene/core/src/java/org/apache/lucene/codecs/lucene103/gen_ForDeltaUtil.py": "82845dcc4b25af1b944bffcaf44d1fdf53e126a0"
 }
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene103/ForDeltaUtil.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene103/ForDeltaUtil.java
index 03cf99e387f..e577ce81aaf 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene103/ForDeltaUtil.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene103/ForDeltaUtil.java
@@ -75,7 +75,7 @@ public final class ForDeltaUtil {
     // When the number of bits per value is 4 or less, we can sum up all values in a block without
     // risking overflowing an 8-bits integer. This allows computing the prefix sum by summing up 4
     // values at once.
-    innerPrefixSum8(arr);
+    prefixSum(arr, ONE_BLOCK_SIZE_FOURTH, 0);
     expand8(arr);
     final int l0 = base;
     final int l1 = l0 + arr[ONE_BLOCK_SIZE_FOURTH - 1];
@@ -94,7 +94,7 @@ public final class ForDeltaUtil {
     // When the number of bits per value is 11 or less, we can sum up all values in a block without
     // risking overflowing an 16-bits integer. This allows computing the prefix sum by summing up 2
     // values at once.
-    innerPrefixSum16(arr);
+    prefixSum(arr, HALF_BLOCK_SIZE, 0);
     expand16(arr);
     final int l0 = base;
     final int l1 = base + arr[HALF_BLOCK_SIZE - 1];
@@ -105,112 +105,15 @@ public final class ForDeltaUtil {
   }
 
   private static void prefixSum32(int[] arr, int base) {
-    arr[0] += base;
-    for (int i = 1; i < BLOCK_SIZE; ++i) {
-      arr[i] += arr[i - 1];
-    }
-  }
-
-  // For some reason unrolling seems to help
-  private static void innerPrefixSum8(int[] arr) {
-    arr[1] += arr[0];
-    arr[2] += arr[1];
-    arr[3] += arr[2];
-    arr[4] += arr[3];
-    arr[5] += arr[4];
-    arr[6] += arr[5];
-    arr[7] += arr[6];
-    arr[8] += arr[7];
-    arr[9] += arr[8];
-    arr[10] += arr[9];
-    arr[11] += arr[10];
-    arr[12] += arr[11];
-    arr[13] += arr[12];
-    arr[14] += arr[13];
-    arr[15] += arr[14];
-    arr[16] += arr[15];
-    arr[17] += arr[16];
-    arr[18] += arr[17];
-    arr[19] += arr[18];
-    arr[20] += arr[19];
-    arr[21] += arr[20];
-    arr[22] += arr[21];
-    arr[23] += arr[22];
-    arr[24] += arr[23];
-    arr[25] += arr[24];
-    arr[26] += arr[25];
-    arr[27] += arr[26];
-    arr[28] += arr[27];
-    arr[29] += arr[28];
-    arr[30] += arr[29];
-    arr[31] += arr[30];
+    prefixSum(arr, BLOCK_SIZE, base);
   }
 
-  // For some reason unrolling seems to help
-  private static void innerPrefixSum16(int[] arr) {
-    arr[1] += arr[0];
-    arr[2] += arr[1];
-    arr[3] += arr[2];
-    arr[4] += arr[3];
-    arr[5] += arr[4];
-    arr[6] += arr[5];
-    arr[7] += arr[6];
-    arr[8] += arr[7];
-    arr[9] += arr[8];
-    arr[10] += arr[9];
-    arr[11] += arr[10];
-    arr[12] += arr[11];
-    arr[13] += arr[12];
-    arr[14] += arr[13];
-    arr[15] += arr[14];
-    arr[16] += arr[15];
-    arr[17] += arr[16];
-    arr[18] += arr[17];
-    arr[19] += arr[18];
-    arr[20] += arr[19];
-    arr[21] += arr[20];
-    arr[22] += arr[21];
-    arr[23] += arr[22];
-    arr[24] += arr[23];
-    arr[25] += arr[24];
-    arr[26] += arr[25];
-    arr[27] += arr[26];
-    arr[28] += arr[27];
-    arr[29] += arr[28];
-    arr[30] += arr[29];
-    arr[31] += arr[30];
-    arr[32] += arr[31];
-    arr[33] += arr[32];
-    arr[34] += arr[33];
-    arr[35] += arr[34];
-    arr[36] += arr[35];
-    arr[37] += arr[36];
-    arr[38] += arr[37];
-    arr[39] += arr[38];
-    arr[40] += arr[39];
-    arr[41] += arr[40];
-    arr[42] += arr[41];
-    arr[43] += arr[42];
-    arr[44] += arr[43];
-    arr[45] += arr[44];
-    arr[46] += arr[45];
-    arr[47] += arr[46];
-    arr[48] += arr[47];
-    arr[49] += arr[48];
-    arr[50] += arr[49];
-    arr[51] += arr[50];
-    arr[52] += arr[51];
-    arr[53] += arr[52];
-    arr[54] += arr[53];
-    arr[55] += arr[54];
-    arr[56] += arr[55];
-    arr[57] += arr[56];
-    arr[58] += arr[57];
-    arr[59] += arr[58];
-    arr[60] += arr[59];
-    arr[61] += arr[60];
-    arr[62] += arr[61];
-    arr[63] += arr[62];
+  private static void prefixSum(int[] arr, int len, int base) {
+    int sum = base;
+    for (int i = 0; i < len; ++i) {
+      sum += arr[i];
+      arr[i] = sum;
+    }
   }
 
   private final int[] tmp = new int[BLOCK_SIZE];
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene103/gen_ForDeltaUtil.py b/lucene/core/src/java/org/apache/lucene/codecs/lucene103/gen_ForDeltaUtil.py
index eccf30d28d8..290a6a29e23 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene103/gen_ForDeltaUtil.py
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene103/gen_ForDeltaUtil.py
@@ -101,7 +101,7 @@ public final class ForDeltaUtil {
     // When the number of bits per value is 4 or less, we can sum up all values in a block without
     // risking overflowing an 8-bits integer. This allows computing the prefix sum by summing up 4
     // values at once.
-    innerPrefixSum8(arr);
+    prefixSum(arr, ONE_BLOCK_SIZE_FOURTH, 0);
     expand8(arr);
     final int l0 = base;
     final int l1 = l0 + arr[ONE_BLOCK_SIZE_FOURTH - 1];
@@ -120,7 +120,7 @@ public final class ForDeltaUtil {
     // When the number of bits per value is 11 or less, we can sum up all values in a block without
     // risking overflowing an 16-bits integer. This allows computing the prefix sum by summing up 2
     // values at once.
-    innerPrefixSum16(arr);
+    prefixSum(arr, HALF_BLOCK_SIZE, 0);
     expand16(arr);
     final int l0 = base;
     final int l1 = base + arr[HALF_BLOCK_SIZE - 1];
@@ -131,112 +131,15 @@ public final class ForDeltaUtil {
   }
 
   private static void prefixSum32(int[] arr, int base) {
-    arr[0] += base;
-    for (int i = 1; i < BLOCK_SIZE; ++i) {
-      arr[i] += arr[i-1];
-    }
-  }
-
-  // For some reason unrolling seems to help
-  private static void innerPrefixSum8(int[] arr) {
-    arr[1] += arr[0];
-    arr[2] += arr[1];
-    arr[3] += arr[2];
-    arr[4] += arr[3];
-    arr[5] += arr[4];
-    arr[6] += arr[5];
-    arr[7] += arr[6];
-    arr[8] += arr[7];
-    arr[9] += arr[8];
-    arr[10] += arr[9];
-    arr[11] += arr[10];
-    arr[12] += arr[11];
-    arr[13] += arr[12];
-    arr[14] += arr[13];
-    arr[15] += arr[14];
-    arr[16] += arr[15];
-    arr[17] += arr[16];
-    arr[18] += arr[17];
-    arr[19] += arr[18];
-    arr[20] += arr[19];
-    arr[21] += arr[20];
-    arr[22] += arr[21];
-    arr[23] += arr[22];
-    arr[24] += arr[23];
-    arr[25] += arr[24];
-    arr[26] += arr[25];
-    arr[27] += arr[26];
-    arr[28] += arr[27];
-    arr[29] += arr[28];
-    arr[30] += arr[29];
-    arr[31] += arr[30];
+    prefixSum(arr, BLOCK_SIZE, base);
   }
 
-  // For some reason unrolling seems to help
-  private static void innerPrefixSum16(int[] arr) {
-    arr[1] += arr[0];
-    arr[2] += arr[1];
-    arr[3] += arr[2];
-    arr[4] += arr[3];
-    arr[5] += arr[4];
-    arr[6] += arr[5];
-    arr[7] += arr[6];
-    arr[8] += arr[7];
-    arr[9] += arr[8];
-    arr[10] += arr[9];
-    arr[11] += arr[10];
-    arr[12] += arr[11];
-    arr[13] += arr[12];
-    arr[14] += arr[13];
-    arr[15] += arr[14];
-    arr[16] += arr[15];
-    arr[17] += arr[16];
-    arr[18] += arr[17];
-    arr[19] += arr[18];
-    arr[20] += arr[19];
-    arr[21] += arr[20];
-    arr[22] += arr[21];
-    arr[23] += arr[22];
-    arr[24] += arr[23];
-    arr[25] += arr[24];
-    arr[26] += arr[25];
-    arr[27] += arr[26];
-    arr[28] += arr[27];
-    arr[29] += arr[28];
-    arr[30] += arr[29];
-    arr[31] += arr[30];
-    arr[32] += arr[31];
-    arr[33] += arr[32];
-    arr[34] += arr[33];
-    arr[35] += arr[34];
-    arr[36] += arr[35];
-    arr[37] += arr[36];
-    arr[38] += arr[37];
-    arr[39] += arr[38];
-    arr[40] += arr[39];
-    arr[41] += arr[40];
-    arr[42] += arr[41];
-    arr[43] += arr[42];
-    arr[44] += arr[43];
-    arr[45] += arr[44];
-    arr[46] += arr[45];
-    arr[47] += arr[46];
-    arr[48] += arr[47];
-    arr[49] += arr[48];
-    arr[50] += arr[49];
-    arr[51] += arr[50];
-    arr[52] += arr[51];
-    arr[53] += arr[52];
-    arr[54] += arr[53];
-    arr[55] += arr[54];
-    arr[56] += arr[55];
-    arr[57] += arr[56];
-    arr[58] += arr[57];
-    arr[59] += arr[58];
-    arr[60] += arr[59];
-    arr[61] += arr[60];
-    arr[62] += arr[61];
-    arr[63] += arr[62];
+  private static void prefixSum(int[] arr, int len, int base) {
+    int sum = base;
+    for (int i = 0; i < len; ++i) {
+      sum += arr[i];
+      arr[i] = sum;
+    }
   }
 
   private final int[] tmp = new int[BLOCK_SIZE];