Skip to content

Benchmark

Jump to bottom
Jakub Ziolkowski edited this page Aug 21, 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.301
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 closedness — Polyhedron_IsClosed_Performance

File: Facts/Polyhedron.cs

Method measured:

  • DiGi.Geometry.Spatial.Query.IsClosed<TPolygonalFace3D>(Polyhedron<TPolygonalFace3D>, bool, double)

What changed. The original implementation reconstructed every face edge in world coordinates and paired edges off against each other in a tolerance-sized spatial hash of edges, cancelling matched pairs and declaring the polyhedron closed when the grid emptied. It was replaced by a two-stage pass that welds face vertices into shared integer indices through a spatial hash of vertices, then counts each edge by its (int, int) index pair — the same edge-counting scheme DiGi.Geometry.Core.Classes.Mesh<TPoint>.IsClosed already used.

Editable knob. The extrusion size is the 500 passed to the private helper Polyhedron_IsClosed_Extrusion(int count) in Facts/Polyhedron.cs; repeats in the same test controls how many timed calls are averaged.

Results (Release)

Old and new implementations measured A/B in a single process against the same polyhedron instances, 200 timed repeats for the extrusion and box, 20 for the ellipsoid. Allocation is GC.GetAllocatedBytesForCurrentThread() deltas divided by the repeat count.

Polyhedron Faces Old (µs) New (µs) Speed-up Old (KB) New (KB) Allocation
Box 6 5.6 3.0 1.87× 16.2 13.0 −20 %
500-gon extrusion 502 2 170 884 2.45× 1 775 1 351 −24 %
Ellipsoid 50 × 100 9 800 9 636 6 784 1.42× 20 582 16 695 −19 %

Where the remaining time goes

A phase bisection of the new implementation on the 9 800-face ellipsoid, measured by disabling one stage at a time:

Stage Time (µs) Allocation (KB)
Read every face through the public accessors, nothing else 6 554 16 462
+ project ring points to world coordinates 6 193 16 462
+ weld vertices and count edges (full method) 7 639 16 695
  • The matching phase is now essentially free — welding and edge counting together add ~230 KB, about 1.4 % of the total. Welding measured in isolation on precomputed coordinates costs 961 KB and ~2 ms for 29 400 input points welded down to 4 902 vertices.
  • Everything else is the per-face clone chain. Reading one face allocates through four cloning accessors: Planar<T>.Plane (a fresh Plane, and Plane.AxisX / AxisY cost ~0.5 KB per face between them), Planar<T>.Geometry2D (a deep clone of the whole 2D face including every Point2D), and PolygonalFace2D.Edges (which clones every ring again). One of the four layers was removed here by reading points through the existing non-cloning Segmentable2D.GetPoints(bool clone) overload; the rest need GetX(bool clone) overloads on Planar<T> / IPlanar / PolygonalFace2D / IPolygonalFace2D and are deliberately out of scope. That is where any further gain has to come from — the algorithm itself is no longer the bottleneck.
  • Why the ellipsoid gains least. It is triangulated, so it has the highest face count for its vertex count and therefore the highest ratio of clone cost to matching cost. The extrusion, whose two 500-vertex end caps carry many edges per face read, gains most.
  • The grid is only an accelerator. A match is always confirmed by an explicit squared-distance test, so an extreme coordinate-to-tolerance ratio can degrade the grid and cost time or report open, but can never fabricate a match and report a false closure. An earlier draft added a bounding-box pass to widen the tolerance against cell-index overflow; measurement showed it doubled allocation (31 MB against 16.7 MB per call) to guard a failure mode that cannot occur, and it was removed.

Benchmarking note

Polyhedron_IsClosed_Performance uses 200 repeats. At 20 repeats the measurement sits in tier-0 JIT code and reports a higher per-call cost in Release than in Debug (3 081 µs against 2 479 µs) — a clear signal the run never reached steady state. Absolute numbers also shift by up to ~1.8× between a standalone run of the fact and the same call inside the A/B harness, so treat the ratios in the table above (measured under identical in-process conditions) as the meaningful 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