Optimize S2Cell::GetDistance

[jmr]

@ericveach Do you remember what you had in mind with

This could be optimized to be at least 5x faster by pruning the set of possible closest vertex/edge pairs using the faces and (u,v) ranges of both cells.

?

s2geometry/src/s2/s2cell.cc

Lines 508 to 526 in a538e02

	// Otherwise, the minimum distance always occurs between a vertex of one
	// cell and an edge of the other cell (including the edge endpoints). This
	// represents a total of 32 possible (vertex, edge) pairs.
	//
	// TODO(ericv): This could be optimized to be at least 5x faster by pruning
	// the set of possible closest vertex/edge pairs using the faces and (u,v)
	// ranges of both cells.
	S2Point va[4], vb[4];
	for (int i = 0; i < 4; ++i) {
	va[i] = GetVertex(i);
	vb[i] = target.GetVertex(i);
	}
	S1ChordAngle min_dist = S1ChordAngle::Infinity();
	for (int i = 0; i < 4; ++i) {
	for (int j = 0; j < 4; ++j) {
	S2::UpdateMinDistance(va[i], vb[j], vb[(j + 1) & 3], &min_dist);
	S2::UpdateMinDistance(vb[i], va[j], va[(j + 1) & 3], &min_dist);
	}
	}

[jmr]

@ivan-gerasimov

[jmr]

I attempted the TODO in #479, but I didn't fully understand it. Where does the 5x faster come from?

[ericveach]

Hi Jesse, Your code is definitely on the right track. The 5x estimate came from reducing the number of distance calculations from 32 down to 4. If you're only seeing 2x, branch prediction could definitely be the issue. You also may want to make sure that the benchmarks are focused on the case where both cells are on the same face, since in real-world applications the two cells are almost always close together. You might want to try something like this as an alternative to your code: ```c++ if (face_ == target.face_) { // Find the index "ai" of an edge of A (if any) such that B lies strictly // on the other side of that edge. int ai = -1; if (uv_[0][1] < target.uv_[0][0]) ai = kRightEdge; if (uv_[0][0] > target.uv_[0][1]) ai = kLeftEdge; if (uv_[1][1] < target.uv_[1][0]) ai = kTopEdge; if (uv_[1][0] > target.uv_[1][1]) ai = kBottomEdge; if (ai < 0) { // A and B intersect (including edge and vertex intersections). return S1ChordAngle::Zero(); } // Otherwise the minimum distance always occurs between an endpoint of the // edge "ai" and the opposite edge (ai ^ 2) of B, or symmetrically, an // endpoint of the opposite edge of B and the edge "ai". int bi = ai ^ 2; S2::UpdateMinDistance(va[ai], vb[bi], vb[bi + 1], &min_dist); S2::UpdateMinDistance(va[ai + 1], vb[bi], vb[bi + 1], &min_dist); S2::UpdateMinDistance(vb[bi], va[ai], va[ai + 1], &min_dist); S2::UpdateMinDistance(vb[bi + 1], va[ai], va[ai + 1], &min_dist); return min_dist; } ``` I haven't tested this and don't even have a setup that makes it easy to code or test anything right now, but it should do better with respect to branch prediction than your current code. Other optimizations are possible, e.g. it's possible to do something similar even when A and B are on different faces, and it's also not too hard to test for the condition where the minimum distance is attained between two vertices rather than a vertex and an edge. But I suspect that both of those optimizations would have a significantly smaller impact. Unfortunately I still don't have much time. It should be a bit better after Dec. 10. Cheers, Eric

[jmr]

it's also not too hard to test for the condition where the minimum distance is attained between two vertices rather than a vertex and an edge.

Would this be testing one pair of vertices or multiple pairs? If the former, that sounds very good.

[jmr]

This doesn't quite work for the same reason I needed 8 comparisons in https://github.com/google/s2geometry/pull/479/files.

When A is both above and to the left of B, it's not obvious to me which direction to check.
The counterexamples (or at least the worst ones) are all very close in one direction and far in the other, so maybe there's a fix.

TEST(S2Cell, GetDistanceToCellProjectionExample2) {
  // In uv space, `cell1` is far to the left of `cell2` and slightly below it.
  // The minimum distance is achieved with the *upper* left vertex of `cell2`,
  // even though `cell1` is below `cell2`.
  // After projection onto the sphere, both cells are shaped like:
  //    ╱╲
  //   ╱  ╲
  //   ╲  ╱
  //    ╲╱
  S2Cell cell1(S2CellId::FromDebugString("2/11033230030133"));
  S2Cell cell2(S2CellId::FromDebugString("2/222"));
  S1ChordAngle expected = GetDistanceToCellBruteForce(cell1, cell2);
  S1ChordAngle actual = cell1.GetDistance(cell2);
  EXPECT_NEAR(expected.radians(), actual.radians(), 1e-15)
    << std::hex << cell1.id().id() << " " << cell2.id().id()
    << " " << cell1.GetBoundUV() << " " << cell2.GetBoundUV();
}