(arrow) branch main updated: GH-40796: [Java] set `lastSet` in `ListVector.setNull` to avoid O(n²) in ListVectors with lots of nulls (#40810)

[lidavidm]

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

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


The following commit(s) were added to refs/heads/main by this push:
     new f3c5fb98ae GH-40796: [Java] set `lastSet` in `ListVector.setNull` to 
avoid O(n²) in ListVectors with lots of nulls (#40810)
f3c5fb98ae is described below

commit f3c5fb98ae7673ad94b198b2da4c741013084e46
Author: James Henderson <ja...@jarohen.dev>
AuthorDate: Wed Mar 27 13:33:35 2024 +0000

    GH-40796: [Java] set `lastSet` in `ListVector.setNull` to avoid O(n²) in 
ListVectors with lots of nulls (#40810)
    
    Would benefit from someone with knowledge of the context double-checking 
this doesn't have nuances I'm not aware of - particularly, there's a comment on 
the field: `the maximum index that is actually set` which one _could_ read to 
mean 'excluding nulls'?
    
    ### Are these changes tested?
    
    Yes
    
    ### Are there any user-facing changes?
    
    No
    * GitHub Issue: #40796
    
    Authored-by: James Henderson <ja...@jarohen.dev>
    Signed-off-by: David Li <li.david...@gmail.com>
---
 .../apache/arrow/vector/complex/ListVector.java    |  1 +
 .../org/apache/arrow/vector/TestValueVector.java   | 23 ++++++++++++++++++++++
 2 files changed, 24 insertions(+)

diff --git 
a/java/vector/src/main/java/org/apache/arrow/vector/complex/ListVector.java 
b/java/vector/src/main/java/org/apache/arrow/vector/complex/ListVector.java
index 5154ac1727..7df659e4cc 100644
--- a/java/vector/src/main/java/org/apache/arrow/vector/complex/ListVector.java
+++ b/java/vector/src/main/java/org/apache/arrow/vector/complex/ListVector.java
@@ -856,6 +856,7 @@ public class ListVector extends BaseRepeatedValueVector 
implements PromotableVec
       offsetBuffer.setInt((i + 1) * OFFSET_WIDTH, currentOffset);
     }
     BitVectorHelper.unsetBit(validityBuffer, index);
+    lastSet = index;
   }
 
   /**
diff --git 
a/java/vector/src/test/java/org/apache/arrow/vector/TestValueVector.java 
b/java/vector/src/test/java/org/apache/arrow/vector/TestValueVector.java
index 10091aebdd..ad84882c66 100644
--- a/java/vector/src/test/java/org/apache/arrow/vector/TestValueVector.java
+++ b/java/vector/src/test/java/org/apache/arrow/vector/TestValueVector.java
@@ -2859,6 +2859,29 @@ public class TestValueVector {
     }
   }
 
+  @Test
+  public void testListVectorSetNull() {
+    try (final ListVector vector = ListVector.empty("list", allocator)) {
+      UnionListWriter writer = vector.getWriter();
+      writer.allocate();
+
+      writeListVector(writer, new int[] {1, 2});
+      writeListVector(writer, new int[] {3, 4});
+      writeListVector(writer, new int[] {5, 6});
+      vector.setNull(3);
+      vector.setNull(4);
+      vector.setNull(5);
+      writer.setValueCount(6);
+
+      assertEquals(vector.getObject(0), Arrays.asList(1, 2));
+      assertEquals(vector.getObject(1), Arrays.asList(3, 4));
+      assertEquals(vector.getObject(2), Arrays.asList(5, 6));
+      assertTrue(vector.isNull(3));
+      assertTrue(vector.isNull(4));
+      assertTrue(vector.isNull(5));
+    }
+  }
+
   @Test
   public void testStructVectorEqualsWithNull() {