You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by kw...@apache.org on 2016/05/05 11:54:23 UTC
lucene-solr:master: LUCENE-7241: More performance improvements.
Repository: lucene-solr
Updated Branches:
refs/heads/master 551d267ff -> 382ffdb63
LUCENE-7241: More performance improvements.
Project: http://git-wip-us.apache.org/repos/asf/lucene-solr/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucene-solr/commit/382ffdb6
Tree: http://git-wip-us.apache.org/repos/asf/lucene-solr/tree/382ffdb6
Diff: http://git-wip-us.apache.org/repos/asf/lucene-solr/diff/382ffdb6
Branch: refs/heads/master
Commit: 382ffdb63677ea694c35c26ff29ac8d5032dba17
Parents: 551d267
Author: Karl Wright <Da...@gmail.com>
Authored: Thu May 5 07:54:09 2016 -0400
Committer: Karl Wright <Da...@gmail.com>
Committed: Thu May 5 07:54:09 2016 -0400
----------------------------------------------------------------------
.../spatial3d/geom/GeoComplexPolygon.java | 66 +++++++++++++++++---
.../apache/lucene/spatial3d/geom/GeoPoint.java | 2 +-
.../lucene/spatial3d/geom/PlanetModel.java | 2 +-
3 files changed, 58 insertions(+), 12 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/382ffdb6/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
index f2d2424..3ecc5a7 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoComplexPolygon.java
@@ -132,7 +132,7 @@ class GeoComplexPolygon extends GeoBasePolygon {
// If we're right on top of any of the test planes, we navigate solely on that plane.
if (testPointFixedYPlane.evaluateIsZero(thePoint)) {
// Use the XZ plane exclusively.
- final LinearCrossingEdgeIterator crossingEdgeIterator = new LinearCrossingEdgeIterator(testPointFixedYPlane, testPointFixedYAbovePlane, testPointFixedYBelowPlane, testPoint, thePoint);
+ final LinearCrossingEdgeIterator crossingEdgeIterator = new LinearCrossingEdgeIterator(testPointFixedYPlane, testPointFixedYAbovePlane, testPointFixedYBelowPlane, thePoint);
// Traverse our way from the test point to the check point. Use the y tree because that's fixed.
if (!yTree.traverse(crossingEdgeIterator, testPoint.y)) {
// Endpoint is on edge
@@ -141,7 +141,7 @@ class GeoComplexPolygon extends GeoBasePolygon {
return ((crossingEdgeIterator.crossingCount & 1) == 0)?testPointInSet:!testPointInSet;
} else if (testPointFixedXPlane.evaluateIsZero(thePoint)) {
// Use the YZ plane exclusively.
- final LinearCrossingEdgeIterator crossingEdgeIterator = new LinearCrossingEdgeIterator(testPointFixedXPlane, testPointFixedXAbovePlane, testPointFixedXBelowPlane, testPoint, thePoint);
+ final LinearCrossingEdgeIterator crossingEdgeIterator = new LinearCrossingEdgeIterator(testPointFixedXPlane, testPointFixedXAbovePlane, testPointFixedXBelowPlane, thePoint);
// Traverse our way from the test point to the check point. Use the x tree because that's fixed.
if (!xTree.traverse(crossingEdgeIterator, testPoint.x)) {
// Endpoint is on edge
@@ -150,7 +150,7 @@ class GeoComplexPolygon extends GeoBasePolygon {
return ((crossingEdgeIterator.crossingCount & 1) == 0)?testPointInSet:!testPointInSet;
} else if (testPointFixedZPlane.evaluateIsZero(thePoint)) {
// Use the XY plane exclusively.
- final LinearCrossingEdgeIterator crossingEdgeIterator = new LinearCrossingEdgeIterator(testPointFixedZPlane, testPointFixedZAbovePlane, testPointFixedZBelowPlane, testPoint, thePoint);
+ final LinearCrossingEdgeIterator crossingEdgeIterator = new LinearCrossingEdgeIterator(testPointFixedZPlane, testPointFixedZAbovePlane, testPointFixedZBelowPlane, thePoint);
// Traverse our way from the test point to the check point. Use the z tree because that's fixed.
if (!zTree.traverse(crossingEdgeIterator, testPoint.z)) {
// Endpoint is on edge
@@ -159,6 +159,9 @@ class GeoComplexPolygon extends GeoBasePolygon {
return ((crossingEdgeIterator.crossingCount & 1) == 0)?testPointInSet:!testPointInSet;
} else {
+ // This is the expensive part!!
+ // Changing the code below has an enormous impact on the queries per second we see with the benchmark.
+
// We need to use two planes to get there. We don't know which two planes will do it but we can figure it out.
final Plane travelPlaneFixedX = new Plane(1.0, 0.0, 0.0, -thePoint.x);
final Plane travelPlaneFixedY = new Plane(0.0, 1.0, 0.0, -thePoint.y);
@@ -186,7 +189,15 @@ class GeoComplexPolygon extends GeoBasePolygon {
for (final GeoPoint p : XIntersectionsY) {
// Travel would be in YZ plane (fixed x) then in XZ (fixed y)
- final double newDistance = Math.abs(testPoint.x - p.x) + Math.abs(thePoint.y - p.y);
+ // We compute distance we need to travel as a placeholder for the number of intersections we might encounter.
+ //final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
+ final double tpDelta1 = testPoint.x - p.x;
+ final double tpDelta2 = testPoint.z - p.z;
+ final double cpDelta1 = thePoint.y - p.y;
+ final double cpDelta2 = thePoint.z - p.z;
+ final double newDistance = tpDelta1 * tpDelta1 + tpDelta2 * tpDelta2 + cpDelta1 * cpDelta1 + cpDelta2 * cpDelta2;
+ //final double newDistance = (testPoint.x - p.x) * (testPoint.x - p.x) + (testPoint.z - p.z) * (testPoint.z - p.z) + (thePoint.y - p.y) * (thePoint.y - p.y) + (thePoint.z - p.z) * (thePoint.z - p.z);
+ //final double newDistance = Math.abs(testPoint.x - p.x) + Math.abs(thePoint.y - p.y);
if (newDistance < bestDistance) {
bestDistance = newDistance;
firstLegValue = testPoint.y;
@@ -202,7 +213,14 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
for (final GeoPoint p : XIntersectionsZ) {
// Travel would be in YZ plane (fixed x) then in XY (fixed z)
- final double newDistance = Math.abs(testPoint.x - p.x) + Math.abs(thePoint.z - p.z);
+ //final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
+ final double tpDelta1 = testPoint.x - p.x;
+ final double tpDelta2 = testPoint.y - p.y;
+ final double cpDelta1 = thePoint.y - p.y;
+ final double cpDelta2 = thePoint.z - p.z;
+ final double newDistance = tpDelta1 * tpDelta1 + tpDelta2 * tpDelta2 + cpDelta1 * cpDelta1 + cpDelta2 * cpDelta2;
+ //final double newDistance = (testPoint.x - p.x) * (testPoint.x - p.x) + (testPoint.y - p.y) * (testPoint.y - p.y) + (thePoint.y - p.y) * (thePoint.y - p.y) + (thePoint.z - p.z) * (thePoint.z - p.z);
+ //final double newDistance = Math.abs(testPoint.x - p.x) + Math.abs(thePoint.z - p.z);
if (newDistance < bestDistance) {
bestDistance = newDistance;
firstLegValue = testPoint.z;
@@ -218,7 +236,14 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
for (final GeoPoint p : YIntersectionsX) {
// Travel would be in XZ plane (fixed y) then in YZ (fixed x)
- final double newDistance = Math.abs(testPoint.y - p.y) + Math.abs(thePoint.x - p.x);
+ //final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
+ final double tpDelta1 = testPoint.y - p.y;
+ final double tpDelta2 = testPoint.z - p.z;
+ final double cpDelta1 = thePoint.x - p.x;
+ final double cpDelta2 = thePoint.z - p.z;
+ final double newDistance = tpDelta1 * tpDelta1 + tpDelta2 * tpDelta2 + cpDelta1 * cpDelta1 + cpDelta2 * cpDelta2;
+ //final double newDistance = (testPoint.y - p.y) * (testPoint.y - p.y) + (testPoint.z - p.z) * (testPoint.z - p.z) + (thePoint.x - p.x) * (thePoint.x - p.x) + (thePoint.z - p.z) * (thePoint.z - p.z);
+ //final double newDistance = Math.abs(testPoint.y - p.y) + Math.abs(thePoint.x - p.x);
if (newDistance < bestDistance) {
bestDistance = newDistance;
firstLegValue = testPoint.x;
@@ -234,7 +259,14 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
for (final GeoPoint p : YIntersectionsZ) {
// Travel would be in XZ plane (fixed y) then in XY (fixed z)
- final double newDistance = Math.abs(testPoint.y - p.y) + Math.abs(thePoint.z - p.z);
+ //final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
+ final double tpDelta1 = testPoint.x - p.x;
+ final double tpDelta2 = testPoint.y - p.y;
+ final double cpDelta1 = thePoint.x - p.x;
+ final double cpDelta2 = thePoint.z - p.z;
+ final double newDistance = tpDelta1 * tpDelta1 + tpDelta2 * tpDelta2 + cpDelta1 * cpDelta1 + cpDelta2 * cpDelta2;
+ //final double newDistance = (testPoint.x - p.x) * (testPoint.x - p.x) + (testPoint.y - p.y) * (testPoint.y - p.y) + (thePoint.x - p.x) * (thePoint.x - p.x) + (thePoint.z - p.z) * (thePoint.z - p.z);
+ //final double newDistance = Math.abs(testPoint.y - p.y) + Math.abs(thePoint.z - p.z);
if (newDistance < bestDistance) {
bestDistance = newDistance;
firstLegValue = testPoint.z;
@@ -250,7 +282,14 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
for (final GeoPoint p : ZIntersectionsX) {
// Travel would be in XY plane (fixed z) then in YZ (fixed x)
- final double newDistance = Math.abs(testPoint.z - p.z) + Math.abs(thePoint.x - p.x);
+ //final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
+ final double tpDelta1 = testPoint.y - p.y;
+ final double tpDelta2 = testPoint.z - p.z;
+ final double cpDelta1 = thePoint.y - p.y;
+ final double cpDelta2 = thePoint.x - p.x;
+ final double newDistance = tpDelta1 * tpDelta1 + tpDelta2 * tpDelta2 + cpDelta1 * cpDelta1 + cpDelta2 * cpDelta2;
+ //final double newDistance = (testPoint.y - p.y) * (testPoint.y - p.y) + (testPoint.z - p.z) * (testPoint.z - p.z) + (thePoint.y - p.y) * (thePoint.y - p.y) + (thePoint.x - p.x) * (thePoint.x - p.x);
+ //final double newDistance = Math.abs(testPoint.z - p.z) + Math.abs(thePoint.x - p.x);
if (newDistance < bestDistance) {
bestDistance = newDistance;
firstLegValue = testPoint.x;
@@ -266,7 +305,14 @@ class GeoComplexPolygon extends GeoBasePolygon {
}
for (final GeoPoint p : ZIntersectionsY) {
// Travel would be in XY plane (fixed z) then in XZ (fixed y)
- final double newDistance = Math.abs(testPoint.z - p.z) + Math.abs(thePoint.y - p.y);
+ //final double newDistance = p.arcDistance(testPoint) + p.arcDistance(thePoint);
+ final double tpDelta1 = testPoint.x - p.x;
+ final double tpDelta2 = testPoint.z - p.z;
+ final double cpDelta1 = thePoint.y - p.y;
+ final double cpDelta2 = thePoint.x - p.x;
+ final double newDistance = tpDelta1 * tpDelta1 + tpDelta2 * tpDelta2 + cpDelta1 * cpDelta1 + cpDelta2 * cpDelta2;
+ //final double newDistance = (testPoint.x - p.x) * (testPoint.x - p.x) + (testPoint.z - p.z) * (testPoint.z - p.z) + (thePoint.y - p.y) * (thePoint.y - p.y) + (thePoint.x - p.x) * (thePoint.x - p.x);
+ //final double newDistance = Math.abs(testPoint.z - p.z) + Math.abs(thePoint.y - p.y);
if (newDistance < bestDistance) {
bestDistance = newDistance;
firstLegValue = testPoint.y;
@@ -666,7 +712,7 @@ class GeoComplexPolygon extends GeoBasePolygon {
public int crossingCount = 0;
- public LinearCrossingEdgeIterator(final Plane plane, final Plane abovePlane, final Plane belowPlane, final Vector testPoint, final Vector thePoint) {
+ public LinearCrossingEdgeIterator(final Plane plane, final Plane abovePlane, final Plane belowPlane, final Vector thePoint) {
this.plane = plane;
this.abovePlane = abovePlane;
this.belowPlane = belowPlane;
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/382ffdb6/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPoint.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPoint.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPoint.java
index 662a056..a63dd8f 100755
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPoint.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/GeoPoint.java
@@ -121,7 +121,7 @@ public class GeoPoint extends Vector {
* @param v is the second point.
* @return the angle, in radians, between the two points.
*/
- public double arcDistance(final GeoPoint v) {
+ public double arcDistance(final Vector v) {
return Tools.safeAcos(dotProduct(v)/(magnitude() * v.magnitude()));
}
http://git-wip-us.apache.org/repos/asf/lucene-solr/blob/382ffdb6/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/PlanetModel.java
----------------------------------------------------------------------
diff --git a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/PlanetModel.java b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/PlanetModel.java
index f5ab8d8..e720b21 100644
--- a/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/PlanetModel.java
+++ b/lucene/spatial3d/src/java/org/apache/lucene/spatial3d/geom/PlanetModel.java
@@ -242,7 +242,7 @@ public class PlanetModel {
* @param pt1 is the first point.
* @param pt2 is the second point.
* @return the adjusted angle, when multiplied by the mean earth radius, yields a surface distance. This will differ
- * from GeoPoint.arcDistance() only when the planet model is not a sphere. @see {@link GeoPoint#arcDistance(GeoPoint)}
+ * from GeoPoint.arcDistance() only when the planet model is not a sphere. @see {@link GeoPoint#arcDistance(Vector)}
*/
public double surfaceDistance(final GeoPoint pt1, final GeoPoint pt2) {
final double L = pt2.getLongitude() - pt1.getLongitude();