(lucene) 01/02: Add comment to the SIMD intersection logic. (#14073)

[jp...@apache.org]

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

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

commit b74b2bfedf881258d60ddcc70a2b6c127f782ddf
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Mon Dec 23 09:38:50 2024 +0100

    Add comment to the SIMD intersection logic. (#14073)
    
    I did not know it when I checked in the code, but this is almost exactly the v1
    intersection algorithm from the "SIMD compression and the intersection of
    sorted integers" paper.
---
 .../apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/lucene/core/src/java21/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java b/lucene/core/src/java21/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java
index 9273f7c5a81..1369aa5e3f4 100644
--- a/lucene/core/src/java21/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java
+++ b/lucene/core/src/java21/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java
@@ -771,6 +771,10 @@ final class PanamaVectorUtilSupport implements VectorUtilSupport {
   @Override
   public int findNextGEQ(int[] buffer, int target, int from, int to) {
     if (ENABLE_FIND_NEXT_GEQ_VECTOR_OPTO) {
+      // This effectively implements the V1 intersection algorithm from
+      // D. Lemire, L. Boytsov, N. Kurz SIMD Compression and the Intersection of Sorted Integers
+      // with T = INT_SPECIES.length(), ie. T=8 with AVX2 and T=16 with AVX-512
+      // https://arxiv.org/pdf/1401.6399
       for (; from + INT_SPECIES.length() < to; from += INT_SPECIES.length() + 1) {
         if (buffer[from + INT_SPECIES.length()] >= target) {
           IntVector vector = IntVector.fromArray(INT_SPECIES, buffer, from);