You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by no...@apache.org on 2016/03/18 09:30:02 UTC
[15/50] lucene-solr:apiv2: LUCENE-7097: let IntroSorter go 2X deeper
in quicksort before switching to heapsort
LUCENE-7097: let IntroSorter go 2X deeper in quicksort before switching to heapsort
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/8cbe4713
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/8cbe4713
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/8cbe4713
Branch: refs/heads/apiv2
Commit: 8cbe4713775565a3194e29b90747f59fe2ffe3f1
Parents: 3c7e55d
Author: Mike McCandless <mi...@apache.org>
Authored: Mon Mar 14 06:03:17 2016 -0400
Committer: Mike McCandless <mi...@apache.org>
Committed: Mon Mar 14 06:03:17 2016 -0400
----------------------------------------------------------------------
lucene/CHANGES.txt | 3 +++
lucene/core/src/java/org/apache/lucene/util/IntroSorter.java | 6 +-----
2 files changed, 4 insertions(+), 5 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/8cbe4713/lucene/CHANGES.txt
----------------------------------------------------------------------
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index cd9fac2..4998eb0 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -21,6 +21,9 @@ Optimizations
* LUCENE-7099: LatLonPoint's newDistanceQuery supports two-phase
iteration. (Robert Muir)
+* LUCENE-7097: IntroSorter now recurses to 2 * log_2(count) quicksort
+ stack depth before switching to heapsort (Adrien Grand, Mike McCandless)
+
Other
* LUCENE-7087: Let MemoryIndex#fromDocument(...) accept 'Iterable<? extends IndexableField>'
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/8cbe4713/lucene/core/src/java/org/apache/lucene/util/IntroSorter.java
----------------------------------------------------------------------
diff --git a/lucene/core/src/java/org/apache/lucene/util/IntroSorter.java b/lucene/core/src/java/org/apache/lucene/util/IntroSorter.java
index d9cdd62..498c06a 100644
--- a/lucene/core/src/java/org/apache/lucene/util/IntroSorter.java
+++ b/lucene/core/src/java/org/apache/lucene/util/IntroSorter.java
@@ -28,17 +28,13 @@ package org.apache.lucene.util;
*/
public abstract class IntroSorter extends Sorter {
- static int ceilLog2(int n) {
- return Integer.SIZE - Integer.numberOfLeadingZeros(n - 1);
- }
-
/** Create a new {@link IntroSorter}. */
public IntroSorter() {}
@Override
public final void sort(int from, int to) {
checkRange(from, to);
- quicksort(from, to, ceilLog2(to - from));
+ quicksort(from, to, 2 * MathUtil.log(to - from, 2));
}
void quicksort(int from, int to, int maxDepth) {