Skip to content

Commit 94fe2d5

Browse files
liyafan82emkornfield
liyafan82
authored and
emkornfield
committed
ARROW-6093: [Java] reduce branches in algo for first match in VectorRangeSearcher
This is a follow up Jira for the improvement suggested by Francois Saint-Jacques in the PR for apache#4925 After careful analysis and proof, I found @fsaintjacques 's proposal really works. The idea behind the algorithm is tricky. This PR is the implementation based on @fsaintjacques 's proposal. The benefit of this implementation: 1. the code is much clearer 2. there is fewer branches, which is beneficial for performance. The drawback of this implementation: 1. there can be dumb iterations of the main loop. That is, the while loop may run a few more times after the "solution" is found, just to wait for the loop termination condition is satisfied. However, the time complexity of the algorithm is still O(logn), and the number of dumb iterations can not be large. Closes apache#5011 from liyafan82/fly_0805_range and squashes the following commits: f47a2e7 <liyafan82> reduce branches in algo for first match in VectorRangeSearcher Authored-by: liyafan82 <fan_li_ya@foxmail.com> Signed-off-by: Micah Kornfield <emkornfield@gmail.com>
1 parent 6006a7d commit 94fe2d5

2 files changed

Lines changed: 36 additions & 48 deletions

File tree

‎java/algorithm/src/main/java/org/apache/arrow/algorithm/search/VectorRangeSearcher.java‎

Lines changed: 14 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,8 @@ public static <V extends ValueVector> int getFirstMatch(
4444
V targetVector, VectorValueComparator<V> comparator, V keyVector, int keyIndex) {
4545
comparator.attachVectors(keyVector, targetVector);
4646

47+
int ret = SEARCH_FAIL_RESULT;
48+
4749
int low = 0;
4850
int high = targetVector.getValueCount() - 1;
4951

@@ -57,30 +59,13 @@ public static <V extends ValueVector> int getFirstMatch(
5759
// the key is larger
5860
low = mid + 1;
5961
} else {
60-
// the key equals the mid value, find the lower bound by going left-ward.
61-
62-
// compare with the left neighbour
63-
int left = mid - 1;
64-
if (left == -1) {
65-
// this is the first value in the vector
66-
return mid;
67-
} else {
68-
int leftResult = comparator.compare(keyIndex, left);
69-
if (leftResult > 0) {
70-
// the key is greater than the left neighbour, and equal to the current one
71-
// we find it
72-
return mid;
73-
} else if (leftResult == 0) {
74-
// the left neighbour is also equal, continue to go left
75-
high = mid - 1;
76-
} else {
77-
// the key is larger than the left neighbour, this is not possible
78-
throw new IllegalStateException("The target vector is not sorted ");
79-
}
80-
}
62+
// an equal element is found
63+
// continue to go left-ward
64+
ret = mid;
65+
high = mid - 1;
8166
}
8267
}
83-
return SEARCH_FAIL_RESULT;
68+
return ret;
8469
}
8570

8671
/**
@@ -97,6 +82,8 @@ public static <V extends ValueVector> int getLastMatch(
9782
V targetVector, VectorValueComparator<V> comparator, V keyVector, int keyIndex) {
9883
comparator.attachVectors(keyVector, targetVector);
9984

85+
int ret = SEARCH_FAIL_RESULT;
86+
10087
int low = 0;
10188
int high = targetVector.getValueCount() - 1;
10289

@@ -110,29 +97,12 @@ public static <V extends ValueVector> int getLastMatch(
11097
// the key is larger
11198
low = mid + 1;
11299
} else {
113-
// the key equals the mid value, find the upper bound by going right-ward.
114-
115-
// compare with the right neighbour
116-
int right = mid + 1;
117-
if (right == targetVector.getValueCount()) {
118-
// this is the last value in the vector
119-
return mid;
120-
} else {
121-
int rightResult = comparator.compare(keyIndex, right);
122-
if (rightResult < 0) {
123-
// the key is smaller than the right neighbour, and equal to the current one
124-
// we find it
125-
return mid;
126-
} else if (rightResult == 0) {
127-
// the right neighbour is also equal, continue to go right
128-
low = mid + 1;
129-
} else {
130-
// the key is smaller than the right neighbour, this is not possible
131-
throw new IllegalStateException("The target vector is not sorted ");
132-
}
133-
}
100+
// an equal element is found,
101+
// continue to go right-ward
102+
ret = mid;
103+
low = mid + 1;
134104
}
135105
}
136-
return SEARCH_FAIL_RESULT;
106+
return ret;
137107
}
138108
}

‎java/algorithm/src/test/java/org/apache/arrow/algorithm/search/TestVectorRangeSearcher.java‎

Lines changed: 22 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,9 @@
1919

2020
import static org.junit.Assert.assertEquals;
2121

22+
import java.util.Arrays;
23+
import java.util.Collection;
24+
2225
import org.apache.arrow.algorithm.sort.DefaultVectorComparators;
2326
import org.apache.arrow.algorithm.sort.VectorValueComparator;
2427
import org.apache.arrow.memory.BufferAllocator;
@@ -28,14 +31,23 @@
2831
import org.junit.After;
2932
import org.junit.Before;
3033
import org.junit.Test;
34+
import org.junit.runner.RunWith;
35+
import org.junit.runners.Parameterized;
3136

3237
/**
3338
* Test cases for {@link VectorRangeSearcher}.
3439
*/
40+
@RunWith(Parameterized.class)
3541
public class TestVectorRangeSearcher {
3642

3743
private BufferAllocator allocator;
3844

45+
private int repeat;
46+
47+
public TestVectorRangeSearcher(int repeat) {
48+
this.repeat = repeat;
49+
}
50+
3951
@Before
4052
public void prepare() {
4153
allocator = new RootAllocator(1024 * 1024);
@@ -49,7 +61,6 @@ public void shutdown() {
4961
@Test
5062
public void testGetLowerBounds() {
5163
final int maxValue = 100;
52-
final int repeat = 5;
5364
try (IntVector intVector = new IntVector("int vec", allocator)) {
5465
// allocate vector
5566
intVector.allocateNew(maxValue * repeat);
@@ -79,7 +90,6 @@ public void testGetLowerBounds() {
7990
@Test
8091
public void testGetLowerBoundsNegative() {
8192
final int maxValue = 100;
82-
final int repeat = 5;
8393
try (IntVector intVector = new IntVector("int vec", allocator);
8494
IntVector negVector = new IntVector("neg vec", allocator)) {
8595
// allocate vector
@@ -114,7 +124,6 @@ public void testGetLowerBoundsNegative() {
114124
@Test
115125
public void testGetUpperBounds() {
116126
final int maxValue = 100;
117-
final int repeat = 5;
118127
try (IntVector intVector = new IntVector("int vec", allocator)) {
119128
// allocate vector
120129
intVector.allocateNew(maxValue * repeat);
@@ -144,7 +153,6 @@ public void testGetUpperBounds() {
144153
@Test
145154
public void testGetUpperBoundsNegative() {
146155
final int maxValue = 100;
147-
final int repeat = 5;
148156
try (IntVector intVector = new IntVector("int vec", allocator);
149157
IntVector negVector = new IntVector("neg vec", allocator)) {
150158
// allocate vector
@@ -175,4 +183,14 @@ public void testGetUpperBoundsNegative() {
175183
}
176184
}
177185
}
186+
187+
@Parameterized.Parameters(name = "repeat = {0}")
188+
public static Collection<Object[]> getRepeat() {
189+
return Arrays.asList(
190+
new Object[]{1},
191+
new Object[]{2},
192+
new Object[]{5},
193+
new Object[]{10}
194+
);
195+
}
178196
}

0 commit comments

Comments
 (0)