search

cartographer-project / point_cloud_viewer

View billions of points in your browser.
Apache License 2.0
339 stars 98 forks source link

Unbox culling in FilteredIterator, speed up queries by 5-10% #422

Closed nnmm closed 4 years ago

nnmm commented 4 years ago

As measured by cargo bench. There is a lot of noise, but I measured multiple times, and it seems a consistent improvement.

This branch:

running 10 tests
test all_query_octree                    ... bench:  31,434,767 ns/iter (+/- 11,293,380)
test all_query_s2                        ... bench:   9,550,422 ns/iter (+/- 1,418,958)
test box_query_octree                    ... bench:  35,456,909 ns/iter (+/- 13,735,925)
test box_query_s2                        ... bench:  10,144,345 ns/iter (+/- 2,517,079)
test cell_union_query_octree             ... bench:  14,741,911 ns/iter (+/- 7,004,745)
test cell_union_query_s2                 ... bench:   1,050,060 ns/iter (+/- 54,704)
test frustum_query_octree                ... bench:  10,293,622 ns/iter (+/- 3,861,021)
test frustum_query_s2                    ... bench:   1,387,529 ns/iter (+/- 42,514)
test obb_query_octree                    ... bench:  21,454,109 ns/iter (+/- 7,254,611)
test obb_query_s2                        ... bench:  10,351,365 ns/iter (+/- 2,528,672)

master:

test all_query_octree                    ... bench:  34,120,871 ns/iter (+/- 11,120,812)
test all_query_s2                        ... bench:  10,393,351 ns/iter (+/- 2,161,491)
test box_query_octree                    ... bench:  32,754,022 ns/iter (+/- 11,243,470)
test box_query_s2                        ... bench:  11,083,706 ns/iter (+/- 2,661,391)
test cell_union_query_octree             ... bench:  15,775,600 ns/iter (+/- 7,386,356)
test cell_union_query_s2                 ... bench:   1,056,599 ns/iter (+/- 45,337)
test frustum_query_octree                ... bench:  11,328,703 ns/iter (+/- 4,065,432)
test frustum_query_s2                    ... bench:   1,450,282 ns/iter (+/- 65,645)
test obb_query_octree                    ... bench:  24,830,127 ns/iter (+/- 11,016,393)
test obb_query_s2                        ... bench:  11,130,904 ns/iter (+/- 4,173,619)
nnmm commented 4 years ago

meow @catevita

nnmm commented 4 years ago

Thanks! I'll add a comment to explain this in the code as well.