You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-commits@jackrabbit.apache.org by th...@apache.org on 2015/01/20 13:47:08 UTC
svn commit: r1653241 - in /jackrabbit/oak/branches/1.0/oak-core/src:
main/java/org/apache/jackrabbit/oak/query/FilterIterators.java
test/java/org/apache/jackrabbit/oak/query/IteratorsTest.java
Author: thomasm
Date: Tue Jan 20 12:47:07 2015
New Revision: 1653241
URL: http://svn.apache.org/r1653241
Log:
OAK-2418 int overflow with orderby causing huge slowdown
Modified:
jackrabbit/oak/branches/1.0/oak-core/src/main/java/org/apache/jackrabbit/oak/query/FilterIterators.java
jackrabbit/oak/branches/1.0/oak-core/src/test/java/org/apache/jackrabbit/oak/query/IteratorsTest.java
Modified: jackrabbit/oak/branches/1.0/oak-core/src/main/java/org/apache/jackrabbit/oak/query/FilterIterators.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/branches/1.0/oak-core/src/main/java/org/apache/jackrabbit/oak/query/FilterIterators.java?rev=1653241&r1=1653240&r2=1653241&view=diff
==============================================================================
--- jackrabbit/oak/branches/1.0/oak-core/src/main/java/org/apache/jackrabbit/oak/query/FilterIterators.java (original)
+++ jackrabbit/oak/branches/1.0/oak-core/src/main/java/org/apache/jackrabbit/oak/query/FilterIterators.java Tue Jan 20 12:47:07 2015
@@ -202,9 +202,9 @@ public class FilterIterators {
list.add(x);
checkMemoryLimit(list.size(), maxMemoryEntries);
// from time to time, sort and truncate
- // this should results in O(n*log(2*keep)) operations,
+ // this should need less than O(n*log(3*keep)) operations,
// which is close to the optimum O(n*log(keep))
- if (list.size() > max * 2) {
+ if (list.size() > (long) max * 2) {
// remove tail entries right now, to save memory
Collections.sort(list, orderBy);
keepFirst(list, max);
Modified: jackrabbit/oak/branches/1.0/oak-core/src/test/java/org/apache/jackrabbit/oak/query/IteratorsTest.java
URL: http://svn.apache.org/viewvc/jackrabbit/oak/branches/1.0/oak-core/src/test/java/org/apache/jackrabbit/oak/query/IteratorsTest.java?rev=1653241&r1=1653240&r2=1653241&view=diff
==============================================================================
--- jackrabbit/oak/branches/1.0/oak-core/src/test/java/org/apache/jackrabbit/oak/query/IteratorsTest.java (original)
+++ jackrabbit/oak/branches/1.0/oak-core/src/test/java/org/apache/jackrabbit/oak/query/IteratorsTest.java Tue Jan 20 12:47:07 2015
@@ -25,6 +25,8 @@ import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
+import java.util.Random;
+import java.util.concurrent.atomic.AtomicInteger;
import org.junit.Test;
@@ -98,6 +100,51 @@ public class IteratorsTest {
}
@Test
+ public void sortCompareCalls() {
+ sortCompareCalls(10000, 0);
+ sortCompareCalls(10000, 1);
+ sortCompareCalls(10000, 10);
+ sortCompareCalls(10000, 100);
+ sortCompareCalls(10000, 1000);
+ sortCompareCalls(10000, 10000);
+ sortCompareCalls(10000, 100000);
+ sortCompareCalls(10000, 1000000);
+ sortCompareCalls(10000, Integer.MAX_VALUE);
+ }
+
+ private void sortCompareCalls(int count, int keep) {
+
+ int len = 1000;
+ Random r = new Random(1);
+ Integer[] list = new Integer[len];
+ for (int i = 0; i < len; i++) {
+ list[i] = r.nextInt();
+ }
+ final AtomicInteger compareCalls = new AtomicInteger();
+ Comparator<Integer> comp = new Comparator<Integer>() {
+
+ @Override
+ public int compare(Integer o1, Integer o2) {
+ compareCalls.incrementAndGet();
+ return o1.compareTo(o2);
+ }
+
+ };
+ Iterator<Integer> it = FilterIterators.newSort(it(list), comp, keep, settings);
+ int old = Integer.MIN_VALUE;
+ while (it.hasNext()) {
+ int x = it.next();
+ assertTrue(x >= old);
+ old = x;
+ }
+ // n * log2(n)
+ int maxCompAll = (int) (len * Math.log(len) / Math.log(2));
+ int maxCompKeep = (int) (len * Math.log(3.0 * keep) / Math.log(2));
+ int maxComp = Math.min(maxCompAll, Math.max(0, maxCompKeep));
+ assertTrue(compareCalls.get() <= maxComp);
+ }
+
+ @Test
public void combined() {
// no filtering