Skip to content

Benchmark

Jump to bottom
Jakub Ziolkowski edited this page Aug 25, 2026 · 4 revisions

Benchmark

Performance and correctness benchmarks for DiGi.Geometry.

All benchmarks live as [Fact] tests in the DiGi.Geometry.xUnit test project (DiGi.Test/DiGi.Geometry.xUnit/Facts/), so they can be re-run and re-verified at any time rather than treated as a one-off snapshot.

Test machine spec

Component Specification
CPU AMD Ryzen 9 9950X, 16 cores / 32 threads (Environment.ProcessorCount = 32)
RAM 61.4 GB
OS Windows 11 Pro (10.0.26200)
.NET SDK 10.0.400
Build config Release (unless noted)

Numbers are machine-specific — re-run the benchmarks on your own hardware before drawing conclusions for a different environment.

Vertex mean vs. area centroid — AverageAndCentroid_ScalingBenchmark

File: Facts/OptimizationPerformance.cs

Methods compared:

  • DiGi.Geometry.Planar.Query.Average(IEnumerable<Point2D>) — the vertex mean center, C = (1/n) · Σ Pᵢ; a single pass accumulating x/y (≈ 2 additions per vertex).
  • DiGi.Geometry.Planar.Query.Centroid(IEnumerable<Point2D>) — the area centroid (polygon centre of mass), C = 1/(6A) · Σ (Pᵢ + Pᵢ₊₁)(xᵢyᵢ₊₁ − xᵢ₊₁yᵢ); the shoelace-weighted sum (≈ 4 multiply-adds per vertex).

Both are O(n) single-pass queries. The benchmark sweeps the point count over {100, 1 000, 10 000, 100 000, 1 000 000} — a regular polygon inscribed in a circle of radius 10 centred on the origin — and reports the per-call time at each scale. A warm-up call precedes the measured loop (JIT), and the number of repeats is scaled inversely with the point count (repeats = Max(1, 2 000 000 / count)) so the total measured work stays comparable across scales. Each scale also asserts both queries resolve to the origin (correctness), so the timings compare equivalent work.

Context: DiGi.Geometry.Planar.Query.InternalPoint uses the area centroid as its primary internal-point candidate and the vertex mean (Average) as the intermediate fallback before the NetTopologySuite InteriorPoint path — this benchmark quantifies the cost of that fallback.

Results (Release build)

points Average (µs/call) Centroid (µs/call) ratio (Centroid / Average)
100 3.38 2.76 0.82×
1,000 28.59 26.50 0.93×
10,000 48.10 56.64 1.18×
100,000 251.16 709.93 2.83×
1,000,000 2,452.20 3,984.75 1.62×

Results (Debug build, for reference)

points Average (µs/call) Centroid (µs/call) ratio (Centroid / Average)
100 1.33 2.42 1.82×
1,000 12.83 22.80 1.78×
10,000 129.11 224.17 1.74×
100,000 1,304.80 2,629.66 2.02×
1,000,000 12,171.55 20,470.20 1.68×

Analysis

  • Both scale linearly — per-call time grows ~10× for each 10× increase in point count, confirming the O(n) single-pass behaviour of both queries with no scale-dependent surprise.
  • Average does strictly less work per vertex — ~2 additions versus the shoelace sum's ~4 multiply-adds — and, for a List<Point2D> input, it also avoids the internal ToArray() copy that Centroid incurs (its point2Ds as Point2D[] array fast-path misses for a List). So Average is both fewer FLOPs and one fewer O(n) allocation.
  • Debug (no JIT optimisation) shows that raw work gap uniformly: Average is ~1.7–2× faster at every size.
  • Release (JIT-optimised) tells a more nuanced story. At tiny inputs (≤ 1 000 points) both finish in a few µs and per-call enumeration / measurement overhead dominates, so the ratio is noise and can even invert (~0.8–0.9×). Average's advantage emerges in the mid-range (1.18× at 10 000, ~2.8× at 100 000) and stays positive at 1 000 000 (~1.5–2×), though that top row is the noisiest — only 2 timed repeats, run-to-run variance ≈ ±20%.
  • Takeaway for InternalPoint: on realistic polygons both centres are trivially cheap (single-digit µs), so the vertex mean is essentially free to try as an intermediate fallback. It is chosen there for correctness/robustness — being a convex combination of the vertices it lands strictly inside more often — and the modest constant-factor speed edge is a bonus, not the reason. The centroid is not slow; the ordering is a quality decision, and the timings just confirm the extra fallback adds negligible cost.

A fixed-size companion test, AverageAndCentroid_PerformanceComparison (same file, 10 000 points), asserts both queries agree on the origin and that Average is not slower than Centroid beyond a generous noise margin, guarding against a future regression that would invert this relationship.

Polyhedron closure — Polyhedron_IsClosed_Benchmark

File: Facts/Polyhedron_IsClosed_Comparison.cs

Methods compared — four implementations of the same question, run on identical inputs in one process:

  • DiGi.Geometry.Spatial.Query.IsClosed<TPolygonalFace3D>(Polyhedron<TPolygonalFace3D>?, bool, double) — shipped. Every ring segment becomes a half-edge and no vertex is ever merged; two half-edges are compatible when their endpoints match pairwise within the tolerance in either traversal direction, and the solid is closed when the compatibility graph admits a perfect matching.
  • Facts.IsClosed_VertexWeld<TPolygonalFace3D>(...) — the previous implementation, kept verbatim in the test file. Welds face vertices into shared integer indices through a tolerance-sized spatial hash, then counts each edge by its (int, int) index pair.
  • Facts.IsClosed_Greedy<TPolygonalFace3D>(...) — the greedy two-pass edge matching proposed first on issue #1.
  • Facts.IsClosed_ComponentMatching<TPolygonalFace3D>(...) — the component perfect matching proposed second on the same issue.

Why it was replaced. Welding mutates topology, so the tolerance did not only forgive gaps — it destroyed genuine features. Raising it past the size of a real feature collapsed that feature and broke the edge counts, so closure was not monotonic: a solid closed at one tolerance could be reported open at a coarser one. The measured consequence is in the monotonicity table below.

Editable knobs — all at the top of the benchmark method's class in Facts/Polyhedron_IsClosed_Comparison.cs:

  • Polyhedron_IsClosed_Benchmark_Operations (600 000) — total half-edge evaluations each scenario aims for; the repeat count of every row is max(1, Operations / half-edges), so every figure is per call.
  • Polyhedron_IsClosed_Benchmark_Batches (5) — timed batches per measurement; the fastest is reported.
  • Polyhedron_IsClosed_Benchmark_WarmUp (60) — minimum warm-up calls before timing.
  • Polyhedron_IsClosed_Extrusion(int count) in Facts/Polyhedron.cs — the extrusion size.

Results (Release)

Per call, microseconds. Lower is better.

Scenario Half-edges Vertex weld (previous) Greedy edge matching Component matching Shipped Shipped / previous
500-gon extrusion 3 000 354.1 1 515.9 1 692.7 565.3 1.60×
9 800-face ellipsoid 29 400 6 389.4 15 226.9 27 946.5 3 829.2 0.60×
Open cube, 5 faces 20 2.3 3.6 4.9 4.1 1.76×
0.03 m step, tolerance 0.05 36 3.7 4.7 9.3 1.9 0.51×
0.1 m slot, tolerance 0.15 48 4.9 6.4 12.5 9.8 2.01×
Two thin slabs, tolerance 0.05 48 4.7 6.8 13.7 11.6 2.45×

Monotonicity of the default criterion

Swept over 1E-06, 1E-05, 0.0001, 0.001, 0.005, 0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.09, 0.1, 0.11, 0.15, 0.2, 0.5; T = closed. A watertight solid must read T everywhere, and no row may ever go from T back to ..

Scenario Vertex weld (previous) Shipped
500-gon extrusion TTTTTTTTTTTTTT... TTTTTTTTTTTTTTTTT
9 800-face ellipsoid TTTTT............ TTTTTTTTTTTTTTTTT
Open cube, 5 faces ................. .................
0.03 m step TTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTT
0.1 m slot TTTTTTTTTTTTTTT.. TTTTTTTTTTTTTTTTT
Two thin slabs TTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTT
Two stacked boxes TTTTTTTTTTTTTTTTT TTTTTTTTTTTTTTTTT
Box, top lifted 0.05 ..........TTTTTTT ..........TTTTTTT

Analysis

  • The correctness result is the ellipsoid row. The previous implementation reports an exactly watertight 9 800-face ellipsoid as open from a tolerance of 0.01 upwards, having reported it closed at every finer value — welding past the edge length of the tessellation collapses whole triangles. The 500-gon loses it at 0.15 and the slot solid at 0.2. All three are pinned by Polyhedron_IsClosed_Comparison_Monotonicity.
  • Both designs proposed on the issue are 3–7× slower than what shipped, and the gap is structural rather than incidental: each probes the 27 cells around every half-edge. The shipped fast path does one lookup per half-edge on a plain 64-bit key, and the full pass walks occupied cells rather than half-edges and probes only the 13 forward neighbours, so every unordered pair is still examined exactly once at a quarter of the lookups.
  • The fast path is a shortcut to the same answer, not a weaker one. Each half-edge carries one key derived from its two endpoints; a bucket of exactly two compatible half-edges is a matched pair, and once every half-edge is matched a perfect matching of the whole graph is in hand — which is the closure criterion itself. Anything it cannot resolve falls through to the full pass, so it can only save work, never decide wrongly.
  • Two hash details decide whether it fires at all. The cell index is rounded, not floored: flooring puts the cell boundary on every exact multiple of the tolerance, which is exactly where clean geometry sits, so a face at z = 0 whose neighbour reprojects to -1E-16 was keyed one cell apart and nearly every pair was split. And the three ordinates are mixed one at a time, each exclusive-or followed by a multiply: an exclusive-or of multiplied ordinates collided 108 of the 1 500 edge keys of the 500-gon, and combining two ordinates before the first multiply collided 694 of them — a polygon on a circle carries the vertex with its two ordinates swapped, and exclusive-or is symmetric. Either was enough to send the whole solid down the slow path.
  • Where the shipped predicate costs more, it is buying the right answer. The slot and thin-slab rows are solids whose features sit at the tolerance, so the fast path cannot resolve them and the full pass runs — roughly 2× the previous cost on inputs of a few dozen half-edges. That is the geometry the previous implementation answered incorrectly.
  • The remaining floor is the per-face clone chain, not the algorithm. Reading one face allocates through Planar<T>.Plane (a fresh Plane, plus Plane.AxisX, which recomputes a cross product, and AxisY), Planar<T>.Geometry2D (a deep clone of the whole 2D face including every Point2D) and PolygonalFace2D.Edges (which clones every ring a second time). Measured in isolation it is ~24 % of the previous implementation's time on both the 500-gon and the ellipsoid, and every implementation in the table pays it identically. Removing it needs GetX(bool clone) overloads on Planar<T> / IPlanar / PolygonalFace2D / IPolygonalFace2D and is deliberately out of scope — that is where any further gain has to come from.

Benchmarking note

Timings for this method are worthless without warm-up. Measured with a bare Stopwatch loop the same implementation reported 2 052 µs and 373 µs in two harnesses that differed only in how many calls preceded the timer, and the ranking of two implementations inverted between them. The benchmark therefore warms every implementation past the call count at which the runtime promotes it to optimised code, then reports the fastest of five batches. Treat the ratios, measured under identical in-process conditions, as the result and the absolute figures as environment-specific.

Adding a new benchmark

  1. Add a [Fact] under Facts/ in DiGi.Geometry.xUnit, following the repo's test conventions (partial class Facts, XML <summary>, explicit types, warm-up-then-Stopwatch).
  2. Expose the sweep size(s) as a single const/static readonly field at the top of the class so the benchmark can be scaled up for a stress run and back down for fast everyday runs.
  3. Warm up (small input) before timing to exclude JIT cost.
  4. Assert cross-implementation agreement (result values / counts) so timing covers equivalent work.
  5. Run in Release for representative numbers, and capture the current machine spec.
  6. Record the machine spec, fully namespace-qualified method names, the result table(s), and the analysis on this page.

See also: the DiGi.ComputeSharp Benchmark page (GPU vs. CPU), which follows the same standard.

Clone this wiki locally