Pith. sign in

REVIEW 3 major objections 5 minor 20 references

ArborX: A Performance Portable Geometric Search Library

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read ArborX gives CPUs and GPUs one fast code path for geometric search.

desk verdict A solid, honest systems paper for a useful Kokkos-based geometric search library; the benchmark claims hold for the tested CPU/GPU configurations, though the 'performance portable' title reaches a bit beyond the evidence. read the letter →

arxiv 1908.11807 v2 pith:4EFCVW4B submitted 2019-08-16 cs.DC cs.MS

D. Lebrun-Grandié , A. Prokopenko , B. Turcksin , S.R. Slattery This is my paper · ORCID
classification cs.DCcs.MS
keywords geometricsearchboundingvolumehierarchyperformanceportabilityMortoncodesGPUcomputingnearest-neighborspatialqueriesparallelalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

ArborX is a new C++ library that answers proximity questions—which objects lie within a given distance, or which are the closest—against collections of geometric objects. The paper's central claim is that by building the search structure as a bounding volume hierarchy and implementing it on a portable CPU/GPU execution layer, the same source code runs efficiently on multicore processors and graphics accelerators. In single-thread comparisons the authors find ArborX competitive with two established serial libraries, and on a leadership-class node a single GPU substantially outperforms the full CPU socket. The design targets scientific applications that rebuild the tree repeatedly and issue many queries, where construction and search speed both matter.

What carries the argument

The load-bearing object is a binary bounding volume hierarchy: each geometric object is enclosed in an axis-aligned box, objects are sorted by the Morton code of their box centroids, and the sorted order is partitioned into a tree whose internal node count is exactly one less than the leaf count, permitting static allocation. Construction follows a fully parallel algorithm that computes all internal nodes concurrently; traversal uses an iterative stack, Morton-sorted query order to reduce divergence, and a one-pass/fallback two-pass scheme for spatial queries whose output size is unknown. The portability layer supplies templated memory and execution spaces so the same traversal code compiles for CPU multithreading and GPU execution.

What would settle it

A concrete test would be to run ArborX on an accelerator family it was not tuned for, such as an AMD or Intel GPU, using a real non-uniform workload like molecular-dynamics neighbor lists, and compare per-query time and construction time against a vendor-tuned native search implementation; if the single-codebase version falls far behind or fails to scale, the performance-portability claim is refuted.

Watch

Extended reading notes

Core claim

The discovery is that a linear bounding volume hierarchy, whose leaves are ordered by Morton (Z-order) codes so that every internal node corresponds to a contiguous interval of codes, can be constructed and traversed with enough parallelism and memory locality to make geometric search performance portable. ArborX implements a fully parallel BVH construction, batches queries so each thread handles one query at a time, uses a count-and-fill scheme for spatial queries so results can be stored without dynamic allocation, and sorts queries by Morton code to keep nearby threads traversing the same subtrees. On the tested workloads the resulting library beats or matches both serial baselines at single-thread scale, scales to 16 OpenMP threads, and runs faster on a single GPU than on a full CPU node.

Load-bearing premise

The load-bearing premise is that the two tested machines and the four synthetic point-cloud workloads represent the hardware and data shapes a real scientific search library will encounter; if actual workloads use different accelerators, non-uniform object sizes, or incremental tree updates, the measured speed and portability may not carry over.

Editorial extensions

If this is right

  • The same ArborX source code, with only a backend template parameter changed, runs searches on multicore CPUs and GPUs, so applications do not need separate search implementations per architecture.
  • Because the tree is a linear BVH rebuilt from scratch from sorted Morton codes, rebuilding the search structure each time step is cheap enough for time-dependent scientific simulations.
  • The one-pass spatial query mode lets users who can estimate the maximum result count per query avoid a second tree traversal, roughly halving spatial-query cost in balanced workloads.
  • For large problems on a GPU-equipped supercomputer node, using accelerators is expected to outperform using only CPUs by a wide margin, a gap that grows when all GPUs on the node are used through MPI.
  • Single-threaded ArborX is competitive with the tested serial libraries, so parallel capability does not come at the cost of serial baseline performance.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The benchmarks cover only two systems and four synthetic point clouds; the portability claim would be stronger with results on other accelerator families and with objects that have very different sizes rather than points.
  • Because query sorting by Morton codes helps most when nearby queries cluster, workloads with randomly scattered queries or very small query counts may see sorting overhead dominate; a mode that disables sorting should be studied as a default.
  • The same BVH traversal could be extended to approximate nearest-neighbor or multi-radius queries, and the count-and-fill result storage could naturally feed distributed MPI searches, an extension the authors list as future work.
  • Power-normalized comparison, which the authors could not run, would change the CPU-versus-GPU conclusion; a GPU's raw speed advantage may not survive per-watt accounting.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper introduces ArborX, a header-only C++ geometric search library built on Kokkos, and presents a linear BVH (LBVH) construction and traversal algorithm targeting performance portability across multicore CPUs and GPUs. The authors describe the BVH construction pipeline (AABB computation, Morton-code sorting, Karras parallel hierarchy generation), spatial and nearest-neighbor traversal strategies, query reordering by Morton codes, and a Kokkos-based interface. The experimental section compares ArborX against Boost.Geometry.Index and nanoflann on an Intel Xeon system, reports OpenMP strong-scaling results, and compares OpenMP versus CUDA on a Summit POWER9/V100 node. The central conclusion is that ArborX is competitive with or faster than the two serial libraries in single-thread mode and effectively leverages both multithreaded CPUs and GPUs.

Significance. If the claims are accepted, the paper provides a useful open-source contribution: a Kokkos-based BVH search library that can be used interchangeably on CPUs and GPUs through a single interface, with benchmark evidence showing large speedups over nanoflann and Boost.Geometry.Index for nearest-neighbor queries on synthetic point clouds and good OpenMP scaling on large problems. The paper is honest about its limitations, including the sorting bottleneck for small per-thread workloads, the absence of power-normalized comparisons, and the lack of multi-GPU support in Kokkos at the time. The main weakness is that the performance-portability claim is demonstrated on only two backends (OpenMP and CUDA) and on synthetic uniform/boundary-concentrated point clouds, which is a narrower evidence base than the title-level claim suggests.

major comments (3)
  1. [Section 3.4 and Conclusion] The central claim of performance portability is supported only for OpenMP on two CPU architectures and CUDA on a single NVIDIA V100 GPU. Kokkos is designed to target a range of backends, and the paper itself mentions APUs and FPGAs as future targets, but no non-NVIDIA accelerator is exercised. The title and conclusion claim 'performance portable' without this qualification. I recommend either adding a benchmark on at least one additional backend (e.g., HIP or SYCL) or explicitly narrowing the claim to 'multicore CPUs and NVIDIA GPUs' and discussing the remaining portability risk.
  2. [Sections 3.1 and 3.2] The benchmark corpus consists solely of four synthetic point-cloud distributions (filled and hollow cube and sphere) with equal source and target counts and with k=10 and a radius calibrated to produce about 10 neighbors on average. The paper motivates applications such as cosmology halo finding, contact detection, and mesh-free data transfer, which are likely to have non-uniform densities, variable object sizes, and repeated tree rebuilds. The tested distributions are favorable to a Morton-code LBVH, so the generality of the performance and competitiveness claims is not established. I would like to see at least one non-uniform or realistic workload, or a clear statement that the reported results apply primarily to near-uniform point clouds.
  3. [Section 3.2 and Figures 5-7] All performance results are reported as medians from Google Benchmark, with no error bars, quartiles, or statement of the number of repetitions. Because some comparisons are close (for example, construction time between ArborX and Boost.Geometry.Index in Figure 5a), the reader cannot assess whether the observed differences are statistically significant. Please report the variance or distribution of the measurements and the number of repetitions used to compute the median.
minor comments (5)
  1. [Section 3.1 and Tables 1-2] The notation is inconsistent: Section 3.1 defines m source points and n target points, but Tables 1 and 2 use 'n' to label the number of source points. Please use m consistently or clarify the notation in the table captions.
  2. [Section 2.2.1] The description of the 1P approach is confusing: 'only do the second pass once the pre-allocated memory is exceeded' suggests the second pass is sometimes done, but the next sentences describe falling back to 2P. Rephrase to make clear that 1P performs a single pass when the user-provided buffer size is an upper bound, and falls back to two passes otherwise.
  3. [Figure 7] The caption says 'spatial search rates' but does not state the units. Add units such as queries per millisecond or millions of queries per second.
  4. [Section 3.2] The exact ArborX version or commit hash is not specified, while the nanoflann hash and Boost version are given. Pinning the ArborX version would improve reproducibility of the benchmark results.
  5. [References] Several references use only '[n. d.]' as the date (e.g., the Boost Geometry, Exascale Computing Project, Google Benchmark, and OLCF Summit entries). Providing access dates or version numbers would be helpful.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: empirical benchmark paper with external baselines.

full rationale

This is an empirical systems paper rather than a derivation-based study, so there is no chain in which an output quantity is defined in terms of its own inputs. The construction and traversal algorithms in Sections 2.1 and 2.2 are presented as implementations of externally published methods (e.g., Karras 2012; Lauterbach et al. 2009; Patwary et al. 2016), and the central performance claims in Sections 3.2 through 3.4 are benchmarked against external libraries (nanoflann and Boost.Geometry.Index) on fixed hardware and synthetic datasets. No fitted parameter is relabeled as a prediction: the '1P' buffer_size argument is a user-supplied performance hint, and the radius and nearest-neighbor counts used in the experiments are fixed experimental setup parameters, not derived quantities. The only self-citation (Slattery 2016) appears in the introduction as a motivational example of multiphysics data transfer and is not load-bearing for any result. The paper also openly acknowledges its limitations, including lack of power measurements and the sorting scalability issue, which further supports that the claims are empirical and externally falsifiable rather than circular.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The ledger is small: the paper introduces no new physical entities and relies on well-established algorithmic components (Morton codes, LBVH, AABB) and the Kokkos portability layer. The main free parameters are benchmark configuration choices (query radius, k, buffer size) rather than model parameters. The load-bearing assumptions are that Kokkos abstracts hardware efficiently and that synthetic point-cloud datasets represent HPC search workloads.

free parameters (3)
  • spatial query radius r = Not numerically stated; chosen so that on average there are k=10 neighbors within radius r in the filled cube shape
    Section 3.1: the radius determines the number of results per query and therefore the spatial search workload; it is fitted to the filled cube dataset.
  • 1P buffer_size = Not stated; described as a user-provided upper bound estimate
    Section 2.2.1 and Figure 4: buffer_size controls whether the 1P or 2P traversal is used; the 1P benchmark results depend on this user-chosen value.
  • number of neighbors k = 10
    Section 3.1: 'The number of neighbors k for the nearest search is fixed to 10 in all experiments.' This choice affects nearest-search performance.
assumptions (4)
  • domain assumption Kokkos provides performance portability across CPU and GPU backends without significant overhead
    The entire library design is built on Kokkos (Edwards et al. 2014). If Kokkos does not deliver similar efficiency across backends, ArborX's portability claim weakens.
  • standard math The Karras (2012) LBVH construction algorithm produces a valid and efficient hierarchy for the tested datasets
    Section 2.1 states 'We implement the original algorithm with only minor changes', relying on the correctness and efficiency of that published algorithm.
  • domain assumption Axis-aligned bounding boxes are an adequate bounding volume for the target scientific workloads
    Section 2 argues that AABBs are 'often a good choice' due to low storage and fast intersection tests, but this is a modeling choice that may not fit all object distributions.
  • domain assumption The synthetic datasets from Elseberg et al. are representative of HPC search workloads
    Section 3.1 uses filled and hollow cube and sphere point clouds. If real workloads have different distributions or object sizes, the measured performance may not transfer.

how reviews work

0 comments
Cite this review

Pith. "Pith review of ArborX: A Performance Portable Geometric Search Library." pith.science (2026). https://pith.science/paper/4EFCVW4B

@misc{pith2026190811807,
  author       = {Pith},
  title        = {Pith review of: ArborX: A Performance Portable Geometric Search Library},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4EFCVW4B}},
  note         = {Machine review of arXiv:1908.11807}
}
read the original abstract

Searching for geometric objects that are close in space is a fundamental component of many applications. The performance of search algorithms comes to the forefront as the size of a problem increases both in terms of total object count as well as in the total number of search queries performed. Scientific applications requiring modern leadership-class supercomputers also pose an additional requirement of performance portability, i.e. being able to efficiently utilize a variety of hardware architectures. In this paper, we introduce a new open-source C++ search library, ArborX, which we have designed for modern supercomputing architectures. We examine scalable search algorithms with a focus on performance, including a highly efficient parallel bounding volume hierarchy implementation, and propose a flexible interface making it easy to integrate with existing applications. We demonstrate the performance portability of ArborX on multi-core CPUs and GPUs, and compare it to the state-of-the-art libraries such as Boost.Geometry.Index and nanoflann.

Figures

Figures reproduced from arXiv: 1908.11807 by the authors.

Figure 1
Figure 1. Bounding volumes and corresponding BVH tree for a set of eight geometric objects [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Effect of query ordering on nearest traversal. [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. BVH construction interface. // Create the View for the spatial-based queries Kokkos::View<ArborX::Within *, DeviceType> queries("queries", n_queries); // Fill in the queries using ExecutionSpace = typename DeviceType::execution_space; Kokkos::parallel_for("setup_queries", Kokkos::RangePolicy<ExecutionSpace>(0, n_queries), KOKKOS_LAMBDA(int i) { queries(i) = ArborX::within(query_points(i), radius); }); // Perform the… view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: BVH search interface (spatial queries). in the tree. A value in the matrix is nonzero (black) when a thread accesses a bounding box of a corresponding node. As one can see, using the original ordering of search queries results in little correlation of accessed nodes of…
Figure 5
Figure 5. Figure 5: Comparison of libraries for the filled case. The speedup is shown with respect to [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]
Figure 6
Figure 6. Figure 6: Comparison of libraries for the hollow case. The speedup is shown with respect [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 7
Figure 7. Figure 7: Spatial search rates for the libraries. similarly, while nanoflann starts to lose its competitiveness for large number of objects. Comparing the query performance of the libraries, we observe that for the nearest search (Figures 5b and 6b), ArborX significantly outperf…
Figure 8
Figure 8. Figure 8: ArborX scaling for filled case. two-dimensional objects thus having a significantly higher density than in 3D for the same number of points. As expected, the rate for the hollow variant is significantly faster than that of the filled variant due to most queries returni…
Figure 9
Figure 9. Figure 9: ArborX scaling for hollow case [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]
Figure 10
Figure 10. Figure 10: Comparison of OpenMP and CUDA on Summit for filled cube source and filled [PITH_FULL_IMAGE:figures/full_fig_p014_10.png]
Figure 11
Figure 11. Figure 11: Comparison of OpenMP and CUDA on Summit for hollow cube source and [PITH_FULL_IMAGE:figures/full_fig_p015_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 12 canonical work pages

  1. [7]

    Kokkos: Enabling manycore perfor- mance portability through polymorphic memory access patterns. J. Parallel and Distrib. Comput. 74, 12 (2014), 3202–3216. https://doi.org/10.1016/j.jpdc.2014.07.003 J. Elseberg, S. Magnenat Rol, and S. A. N¨ uchter

    doi:10.1016/j.jpdc.2014.07.003 2014

  2. [13]

    IEEE Access PP (07 2019), 1–1

    Parallel BVH Construction Using Locally-Density Clustering. IEEE Access PP (07 2019), 1–1. https://doi.org/10. 1109/ACCESS.2019.2932151 T. Karras. [n. d.]a. Thinking Parallel, Part I: Collision Detection on the GPU. https: //devblogs.nvidia.com/thinking-parallel-part-i-collision-detection-gpu . T. Karras. [n. d.]b. Thinking Parallel, Part II: Tree Travers...

    arXiv 2019

  3. [14]

    In Proceedings of the Fourth ACM SIGGRAPH / Eurographics Conference on High-Performance Graphics (EGGH-HPG’12)

    Maximizing Parallelism in the Construction of BVHs, Octrees, and k- d Trees. In Proceedings of the Fourth ACM SIGGRAPH / Eurographics Conference on High-Performance Graphics (EGGH-HPG’12) . Eurographics Association, Goslar Ger- many, Germany, 33–37. https://doi.org/10.2312/EGGH/HPG12/033-037 C. Lauterbach, M. Garland, S. Sengupta, D. Luebke, and D. Manocha

    doi:10.2312/eggh/hpg12/033-037

  4. [18]

    https://doi.org/10.1145/3231578.3231581 J

    Association for Computing Machinery, New York, NY, USA, Article Article 6, 4 pages. https://doi.org/10.1145/3231578.3231581 J. L. Bentley

    work page arXiv

  5. [19]

    In 2015 IEEE 5th Symposium on Large Data Analysis and Visualization (LDAV)

    Utilizing many-core ac- celerators for halo and center finding within a cosmology simulation. In 2015 IEEE 5th Symposium on Large Data Analysis and Visualization (LDAV) . IEEE, 91–98. S. R. Slattery

    work page 2015

  6. [20]

    Mesh-free data transfer algorithms for partitioned multiphysics prob- lems: Conservation, accuracy, and parallelism. J. Comput. Phys. 307 (2016), 164–188. https://doi.org/10.1016/j.jcp.2015.11.055 M. Vinkler, J. Bittner, and V. Havran

    work page doi:10.1016/j.jcp.2015.11.055 2016

  7. [256]

    https://doi.org/10.1109/34.121791 J. L. Blanco and P. K. Rai

    doi:10.1109/34.121791

  8. [1975]

    Communication of the ACM 18, 9 (September 1975), 509–517

    Multidimensional Binary Search Trees Used for Associative Searching. Communication of the ACM 18, 9 (September 1975), 509–517. https://doi.org/10. 1145/361002.361007 P. J. Besl and N. D. McKay

    arXiv 1975

Show all 20 references
  1. [1984]

    In Proceed- ings of the 1984 ACM SIGMOD International Conference on Management of Data (SIG- MOD ’84)

    R-trees: A Dynamic Index Structure for Spatial Searching. In Proceed- ings of the 1984 ACM SIGMOD International Conference on Management of Data (SIG- MOD ’84) . ACM, New York, NY, USA, 47–57. https://doi.org/10.1145/602259. 602266 H. Haverkort

    1984 doi

  2. [1992]

    IEEE Transactions on Pattern Analysis and Machine Intelligence 14, 2 (February 1992), 239–

    A Method for Registration of 3-D Shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence 14, 2 (February 1992), 239–

    1992

  3. [1997]

    In Proceedings 13th International Conference on Data Engineering

    STR: A Simple and Efficient Algorithm for R-Tree Packing. In Proceedings 13th International Conference on Data Engineering. 497–506. https://doi.org/10.1109/ICDE.1997.582015 Muja M. and D. G. G. Lowe

    1997

  4. [1998]

    In Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems (GIS ’98)

    A Greedy Algorithm for Bulk Loading R-trees. In Proceedings of the 6th ACM International Symposium on Advances in Geographic Information Systems (GIS ’98) . ACM, New York, NY, USA, 163–164. https://doi.org/10.1145/288692.288723 16 A. Guttman

  5. [2002]

    Internat

    An augmented spatial digital tree algorithm for contact detection in computational mechanics. Internat. J. Numer. Methods Engrg. 55, 2 (2002), 159–176. K. Garanzha, J. Pantaleoni, and D. McAllister

    2002

  6. [2011]

    Journal of Machine Learning Research 12 (2011), 2825–2830

    Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research 12 (2011), 2825–2830. C. Sewell, L. Lo, K. Heitmann, S. Habib, and J. Ahrens

    2011

  7. [2012]

    Journal of Software Engineering for Robotics (2012), 2–12

    Comparison of nearest-neighbor- search strategies and implementations for efficient shape registration. Journal of Software Engineering for Robotics (2012), 2–12. Y. T. Feng and D. R. J. Owen

    2012

  8. [2014]

    In Computer Graph- ics and Visual Computing (CGVC) , Rita Borgo and Wen Tang (Eds.)

    Fast and Simple Agglomerative LBVH Construction. In Computer Graph- ics and Visual Computing (CGVC) , Rita Borgo and Wen Tang (Eds.). The Eurographics Association. https://doi.org/10.2312/cgvc.20141206 C. Benthin, I. Wald, S. Woop, and A. T. ´Afra

    doi

  9. [2015]

    In Proceedings of the 7th Conference on High-Performance Graphics (HPG ’15)

    Bounding Volume Hierarchy Optimization Through Agglomerative Treelet Restructuring. In Proceedings of the 7th Conference on High-Performance Graphics (HPG ’15) . ACM, New York, NY, USA, 13–20. https: //doi.org/10.1145/2790060.2790065 H. C. Edwards, C. R. Trott, and D. Sunderland

  10. [2016]

    In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS)

    PANDA: Extreme Scale Parallel K-Nearest Neighbor on Distributed Architectures. In 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS). 494–503. https://doi.org/10.1109/ IPDPS.2016.57 17 F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O...

    2016

  11. [2017]

    In Proceedings of High Performance Graphics (HPG ’17)

    Extended Morton Codes for High Performance Bounding Volume Hierarchy Construction. In Proceedings of High Performance Graphics (HPG ’17). ACM, New York, NY, USA, Article 9, 8 pages. https://doi.org/10.1145/ 3105762.3105782 18

  12. [2019]

    Computational Materials Science 164 (2019), 139–146

    Quantized bounding volume hierarchies for neighbor search in molecular simulations on graphics processing units. Computational Materials Science 164 (2019), 139–146. Y. Hu, W. Wang, D. Li, Q. Zeng, and Y. Hu

    2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.