8000 Vertex optimizations, first pass by nrabinowitz · Pull Request #422 · uber/h3 · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Vertex optimizations, first pass #422

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 5 commits into from
Jan 22, 2021
Merged

Vertex optimizations, first pass #422

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
5 commits
Select commit Hold shift + click to select a range
533eab7
Optimizations for cellToVertex
Jan 21, 2021
a4b855b
Consolidate less
Jan 21, 2021
d91c3bb
More benchmarks and optimizations
Jan 21, 2021
ef00e57
Add test coverage for missing line/branch
Jan 22, 2021
9038f7d
Fix H3_EXPORT wrapper
Jan 22, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
14 changes: 12 additions & 2 deletions src/apps/benchmarks/benchmarkVertex.c
View file
Open in desktop
8000
Original file line number Diff line number Diff line change
Expand Up @@ -19,6 +19,10 @@

// Fixtures. Cells are arbitrary, except that ring2 is all hexagons and
// ring2Pent is centered on a pentagon.

H3Index hex = 0x89283080ddbffff;
H3Index pentagon = 0x89080000003ffff;

H3Index ring2[] = {
0x89283081083ffff, 0x8928308109bffff, 0x8928308108bffff, 0x8928308108fffff,
0x89283081087ffff, 0x89283081097ffff, 0x89283081093ffff, 0x89283081467ffff,
Expand All @@ -38,13 +42,19 @@ BEGIN_BENCHMARKS();

H3Index* vertexes = calloc(6, sizeof(H3Index));

BENCHMARK(cellToVertexes, 10000, {
BENCHMARK(cellToVertexes, 10000, { H3_EXPORT(cellToVertexes)(hex, vertexes); });

BENCHMARK(cellToVertexesPent, 10000, {
H3_EXPORT(cellToVertexes)(pentagon, vertexes);
});

BENCHMARK(cellToVertexesRing, 10000, {
for (int i = 0; i < ring2Count; i++) {
H3_EXPORT(cellToVertexes)(ring2[i], vertexes);
}
});

BENCHMARK(cellToVertexesPent, 10000, {
BENCHMARK(cellToVertexesRingPent, 10000, {
for (int i = 0; i < ring2PentCount; i++) {
H3_EXPORT(cellToVertexes)(ring2Pent[i], vertexes);
}
Expand Down
27 changes: 26 additions & 1 deletion src/apps/testapps/testVertex.c
View file
Open in desktop
10000
Original file line number Diff line number Diff line change
Expand Up @@ -86,6 +86,19 @@ SUITE(Vertex) {
"invalid pent vertex should return invalid direction");
}

TEST(cellToVertex_badVerts) {
H3Index origin = 0x823d6ffffffffff;

t_assert(H3_EXPORT(cellToVertex)(origin, -1) == H3_NULL,
"negative vertex should return null index");
t_assert(H3_EXPORT(cellToVertex)(origin, 6) == H3_NULL,
"invalid vertex should return null index");

H3Index pentagon = 0x823007fffffffff;
t_assert(H3_EXPORT(cellToVertex)(pentagon, 5) == H3_NULL,
"invalid pent vertex should return null index");
}

TEST(isValidVertex_hex) {
H3Index origin = 0x823d6ffffffffff;
H3Index vert = 0x2222597fffffffff;
Expand All @@ -98,7 +111,19 @@ SUITE(Vertex) {
}
}

TEST(isValidVertex_badOwner) {
TEST(isValidVertex_invalidOwner) {
H3Index origin = 0x823d6ffffffffff;
int vertexNum = 0;
H3Index vert = H3_EXPORT(cellToVertex)(origin, vertexNum);

// Set a bit for an unused digit to something else.
vert ^= 1;

t_assert(H3_EXPORT(isValidVertex)(vert) == 0,
"vertex with invalid owner is not valid");
}

TEST(isValidVertex_wrongOwner) {
H3Index origin = 0x823d6ffffffffff;
int vertexNum = 0;
H3Index vert = H3_EXPORT(cellToVertex)(origin, vertexNum);
Expand Down
104 changes: 71 additions & 33 deletions src/h3lib/lib/vertex.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -172,6 +172,17 @@ Direction directionForVertexNum(const H3Index origin, const int vertexNum) {
NUM_HEX_VERTS];
}

/** @brief Directions in CCW order */
static const Direction DIRECTIONS[NUM_HEX_VERTS] = {
J_AXES_DIGIT, JK_AXES_DIGIT, K_AXES_DIGIT,
IK_AXES_DIGIT, I_AXES_DIGIT, IJ_AXES_DIGIT};

/** @brief Reverse direction from neighbor in each direction,
* given as an index into DIRECTIONS to facilitate rotation
*/
static const int revNeighborDirectionsHex[NUM_DIGITS] = {
INVALID_DIGIT, 5, 3, 4, 1, 0, 2};

/**
* Get a single vertex for a given cell, as an H3 index, or
* H3_NULL if the vertex is invalid
Expand All @@ -181,44 +192,71 @@ Direction directionForVertexNum(const H3Index origin, const int vertexNum) {
H3Index H3_EXPORT(cellToVertex)(H3Index cell, int vertexNum) {
int cellIsPentagon = H3_EXPORT(h3IsPentagon)(cell);
int cellNumVerts = cellIsPentagon ? NUM_PENT_VERTS : NUM_HEX_VERTS;
int res = H3_GET_RESOLUTION(cell);

// Get the left neighbor of the vertex, with its rotations
Direction left = directionForVertexNum(cell, vertexNum);
if (left == INVALID_DIGIT) return H3_NULL;
int rRotations = 0;
H3Index leftNeighbor = h3NeighborRotations(cell, left, &rRotations);

// Get the right neighbor of the vertex, with its rotations
// Note that vertex - 1 is the right side, as vertex numbers are CCW
Direction right = directionForVertexNum(
cell, (vertexNum - 1 + cellNumVerts) % cellNumVerts);
// This case should be unreachable; invalid verts fail the left side first
if (right == INVALID_DIGIT) return H3_NULL; // LCOV_EXCL_LINE
int lRotations = 0;
H3Index rightNeighbor = h3NeighborRotations(cell, right, &lRotations);

// Determine the owner. By convention, this is the cell with the
// lowest numerical index.
H3Index owner = cell;
if (leftNeighbor < owner) owner = leftNeighbor;
if (rightNeighbor < owner) owner = rightNeighbor;
// Check for invalid vertexes
if (vertexNum < 0 || vertexNum > cellNumVerts - 1) return H3_NULL;

// Determine the vertex number for the owner cell
// Default the owner and vertex number to the input cell
H3Index owner = cell;
int ownerVertexNum = vertexNum;

if (owner == leftNeighbor) {
Direction dir = directionForNeighbor(owner, cell);
< DC47 /td> // For the left neighbor, we need the second vertex of the
// edge, which may involve looping around the vertex nums
ownerVertexNum = vertexNumForDirection(owner, dir) + 1;
if (ownerVertexNum == NUM_HEX_VERTS ||
(H3_EXPORT(h3IsPentagon)(owner) &&
ownerVertexNum == NUM_PENT_VERTS)) {
ownerVertexNum = 0;
// Determine the owner, looking at the three cells that share the vertex.
// By convention, the owner is the cell with the lowest numerical index.

// If the cell is the center child of its parent, it will always have
// the lowest index of any neighbor, so we can skip determining the owner
if (res == 0 || H3_GET_INDEX_DIGIT(cell, res) != CENTER_DIGIT) {
// Get the left neighbor of the vertex, with its rotations
Direction left = directionForVertexNum(cell, vertexNum);
// This case should be unreachable; invalid verts fail earlier
if (left == INVALID_DIGIT) return H3_NULL; // LCOV_EXCL_LINE
int lRotations = 0;
H3Index leftNeighbor = h3NeighborRotations(cell, left, &lRotations);
// Set to owner if lowest index
if (leftNeighbor < owner) owner = leftNeighbor;

// As above, skip the right neighbor if the left is known lowest
if (res == 0 || H3_GET_INDEX_DIGIT(leftNeighbor, res) != CENTER_DIGIT) {
// Get the right neighbor of the vertex, with its rotations
// Note that vertex - 1 is the right side, as vertex numbers are CCW
Direction right = directionForVertexNum(
cell, (vertexNum - 1 + cellNumVerts) % cellNumVerts);
// This case should be unreachable; invalid verts fail earlier
if (right == INVALID_DIGIT) return H3_NULL; // LCOV_EXCL_LINE
int rRotations = 0;
H3Index rightNeighbor =
h3NeighborRotations(cell, right, &rRotations);
// Set to owner if lowest index
if (rightNeighbor < owner) {
owner = rightNeighbor;
Direction dir =
H3_EXPORT(h3IsPentagon)(owner)
? directionForNeighbor(owner, cell)
: DIRECTIONS[(revNeighborDirectionsHex[right] +
rRotations) %
NUM_HEX_VERTS];
ownerVertexNum = vertexNumForDirection(owner, dir);
}
}

// Determine the vertex number for the left neighbor
if (owner == leftNeighbor) {
int ownerIsPentagon = H3_EXPORT(h3IsPentagon)(owner);
Direction dir =
ownerIsPentagon
? directionForNeighbor(owner, cell)
: DIRECTIONS[(revNeighborDirectionsHex[left] + lRotations) %
NUM_HEX_VERTS];

// For the left neighbor, we need the second vertex of the
// edge, which may involve looping around the vertex nums
ownerVertexNum = vertexNumForDirection(owner, dir) + 1;
if (ownerVertexNum == NUM_HEX_VERTS ||
(ownerIsPentagon && ownerVertexNum == NUM_PENT_VERTS)) {
ownerVertexNum = 0;
}
}
} else if (owner == rightNeighbor) {
Direction dir = directionForNeighbor(owner, cell);
ownerVertexNum = vertexNumForDirection(owner, dir);
}

// Create the vertex index
Expand Down
0