Skip to content

PERFORMANCE_RESULTS.md

Latest commit

 

History

History
228 lines (167 loc) · 11.2 KB

PERFORMANCE_RESULTS.md

File metadata and controls

228 lines (167 loc) · 11.2 KB

Delaunay Library Performance Results

This file contains performance benchmarks and analysis for the delaunay library. The results are automatically generated and updated by the benchmark infrastructure.

  • Last Updated: 2026-05-21 21:04:39 UTC
  • Generated By: benchmark_utils.py
  • Git Commit: 3456ca96abeeee5efb2ef413c3eb91d57f3921b4
  • Hardware: Apple M4 Max (16 cores)
  • Memory: 64.0 GB
  • OS: macOS
  • Rust: rustc 1.95.0 (59807616e 2026-04-14)

Triangulation Data Structure Performance

Current Criterion Run Information

  • Date: 2026-05-21 21:01:27 UTC
  • Git commit: 3456ca96abeeee5efb2ef413c3eb91d57f3921b4
  • Source: current target/criterion construction results

2D Triangulation Performance

Benchmark ID Vertices Time (mean) Throughput (mean) Simplices Generated
tds_new_2d/tds_new/4000 4000 1154.959 ms 3.463 Kelem/s 7,974
tds_new_2d/tds_new_adversarial/4000 4000 1318.191 ms 3.034 Kelem/s 7,971

3D Triangulation Performance

Benchmark ID Vertices Time (mean) Throughput (mean) Simplices Generated
tds_new_3d/tds_new/750 750 884.208 ms 0.848 Kelem/s 4,663
tds_new_3d/tds_new_adversarial/750 750 1123.063 ms 0.668 Kelem/s 4,726

4D Triangulation Performance

Benchmark ID Vertices Time (mean) Throughput (mean) Simplices Generated
tds_new_4d/tds_new/75 75 901.804 ms 0.083 Kelem/s 1,105
tds_new_4d/tds_new_adversarial/75 75 953.070 ms 0.079 Kelem/s 1,129

5D Triangulation Performance

Benchmark ID Vertices Time (mean) Throughput (mean) Simplices Generated
tds_new_5d/tds_new/25 25 997.657 ms 0.025 Kelem/s 421
tds_new_5d/tds_new_adversarial/25 25 871.978 ms 0.029 Kelem/s 410

Performance Results Summary

Public API Performance Contract (ci_performance_suite)

This suite is the versioned benchmark contract for public Delaunay workflows. It covers construction, hull extraction, validation, incremental insertion, boundary traversal, and explicit bistellar flip roundtrips.

Construction

Public API: DelaunayTriangulation::new_with_options

Benchmark ID Dimension Input Variant Mean 95% CI
tds_new_2d/tds_new/4000 2D 4000 well-conditioned 1.155 s 1.154 s - 1.156 s
tds_new_2d/tds_new_adversarial/4000 2D 4000 adversarial 1.318 s 1.314 s - 1.325 s
tds_new_3d/tds_new/750 3D 750 well-conditioned 884.208 ms 882.600 ms - 886.255 ms
tds_new_3d/tds_new_adversarial/750 3D 750 adversarial 1.123 s 1.121 s - 1.125 s
tds_new_4d/tds_new/75 4D 75 well-conditioned 901.804 ms 889.885 ms - 916.534 ms
tds_new_4d/tds_new_adversarial/75 4D 75 adversarial 953.070 ms 948.482 ms - 957.962 ms
tds_new_5d/tds_new/25 5D 25 well-conditioned 997.657 ms 982.027 ms - 1.025 s
tds_new_5d/tds_new_adversarial/25 5D 25 adversarial 871.978 ms 868.052 ms - 877.029 ms

Boundary facets

Public API: DelaunayTriangulation::boundary_facets

Benchmark ID Dimension Input Variant Mean 95% CI
boundary_facets/boundary_facets_2d/4000 2D 4000 well-conditioned 1.694 ms 1.690 ms - 1.698 ms
boundary_facets/boundary_facets_2d_adversarial/4000 2D 4000 adversarial 1.694 ms 1.690 ms - 1.698 ms
boundary_facets/boundary_facets_3d/750 3D 750 well-conditioned 1.492 ms 1.489 ms - 1.496 ms
boundary_facets/boundary_facets_3d_adversarial/750 3D 750 adversarial 1.511 ms 1.505 ms - 1.518 ms
boundary_facets/boundary_facets_4d/75 4D 75 well-conditioned 498.7 µs 493.5 µs - 504.7 µs
boundary_facets/boundary_facets_4d_adversarial/75 4D 75 adversarial 503.2 µs 499.1 µs - 507.4 µs
boundary_facets/boundary_facets_5d/25 5D 25 well-conditioned 241.6 µs 239.1 µs - 244.0 µs
boundary_facets/boundary_facets_5d_adversarial/25 5D 25 adversarial 234.2 µs 230.7 µs - 238.1 µs

Convex hull

Public API: ConvexHull::from_triangulation

Benchmark ID Dimension Input Variant Mean 95% CI
convex_hull/from_triangulation_2d/4000 2D 4000 well-conditioned 1.700 ms 1.698 ms - 1.703 ms
convex_hull/from_triangulation_2d_adversarial/4000 2D 4000 adversarial 1.694 ms 1.690 ms - 1.698 ms
convex_hull/from_triangulation_3d/750 3D 750 well-conditioned 1.489 ms 1.485 ms - 1.494 ms
convex_hull/from_triangulation_3d_adversarial/750 3D 750 adversarial 1.512 ms 1.508 ms - 1.517 ms
convex_hull/from_triangulation_4d/75 4D 75 well-conditioned 505.6 µs 501.9 µs - 509.6 µs
convex_hull/from_triangulation_4d_adversarial/75 4D 75 adversarial 518.8 µs 514.0 µs - 523.4 µs
convex_hull/from_triangulation_5d/25 5D 25 well-conditioned 242.6 µs 239.1 µs - 246.7 µs
convex_hull/from_triangulation_5d_adversarial/25 5D 25 adversarial 233.8 µs 231.8 µs - 236.0 µs

Validation

Public API: DelaunayTriangulation::validate

Benchmark ID Dimension Input Variant Mean 95% CI
validation/validate_3d/750 3D 750 well-conditioned 34.983 ms 34.853 ms - 35.141 ms
validation/validate_3d_adversarial/750 3D 750 adversarial 45.030 ms 44.832 ms - 45.262 ms
validation/validate_4d/75 4D 75 well-conditioned 70.964 ms 70.685 ms - 71.272 ms
validation/validate_4d_adversarial/75 4D 75 adversarial 68.111 ms 67.652 ms - 68.595 ms
validation/validate_5d/25 5D 25 well-conditioned 62.154 ms 62.044 ms - 62.266 ms
validation/validate_5d_adversarial/25 5D 25 adversarial 58.031 ms 57.786 ms - 58.297 ms

Incremental insert

Public API: DelaunayTriangulation::insert

Benchmark ID Dimension Input Variant Mean 95% CI
incremental_insert/insert_2d/10 2D 10 well-conditioned 4.551 ms 4.537 ms - 4.569 ms
incremental_insert/insert_2d_adversarial/10 2D 10 adversarial 7.049 ms 6.915 ms - 7.241 ms
incremental_insert/insert_3d/10 3D 10 well-conditioned 6.189 ms 6.151 ms - 6.233 ms
incremental_insert/insert_3d_adversarial/10 3D 10 adversarial 45.273 ms 45.073 ms - 45.459 ms
incremental_insert/insert_4d/6 4D 6 well-conditioned 47.436 ms 46.955 ms - 47.968 ms
incremental_insert/insert_4d_adversarial/6 4D 6 adversarial 145.440 ms 144.901 ms - 146.033 ms
incremental_insert/insert_5d/4 5D 4 well-conditioned 619.248 ms 615.715 ms - 622.850 ms
incremental_insert/insert_5d_adversarial/4 5D 4 adversarial 635.775 ms 634.427 ms - 637.273 ms

Bistellar flips

Public API: BistellarFlips

Benchmark ID Dimension Input Variant Mean 95% CI
bistellar_flips_4d/k1_roundtrip 4D roundtrip well-conditioned 189.6 µs 187.8 µs - 191.1 µs
bistellar_flips_4d/k2_roundtrip 4D roundtrip well-conditioned 186.0 µs 184.4 µs - 187.9 µs
bistellar_flips_4d/k3_roundtrip 4D roundtrip well-conditioned 186.5 µs 185.0 µs - 187.8 µs

Circumsphere Predicate Performance

This focused predicate suite tracks la-stack-backed circumsphere and insphere query performance independently from full triangulation workflows.

Version 0.7.8 Results (2026-05-21)

Single Query Performance (2D)

Test Case insphere insphere_distance insphere_lifted Winner
Basic 2D 18 ns 23 ns 8 ns insphere_lifted
Boundary vertex 1 ns 24 ns 209 ns insphere
Far vertex 17 ns 24 ns 8 ns insphere_lifted

Single Query Performance (3D)

Test Case insphere insphere_distance insphere_lifted Winner
Basic 3D 2.1 µs 26 ns 18 ns insphere_lifted
Boundary vertex 1 ns 26 ns 436 ns insphere
Far vertex 2.1 µs 26 ns 18 ns insphere_lifted

Single Query Performance (4D)

Test Case insphere insphere_distance insphere_lifted Winner
Basic 4D 5.3 µs 56 ns 2.9 µs insphere_distance
Boundary vertex 2 ns 54 ns 1.4 µs insphere
Far vertex 3.3 µs 54 ns 1.8 µs insphere_distance

Single Query Performance (5D)

Test Case insphere insphere_distance insphere_lifted Winner
Basic 5D 8.4 µs 83 ns 4.9 µs insphere_distance
Boundary vertex 2 ns 81 ns 2.3 µs insphere
Far vertex 5.2 µs 81 ns 2.9 µs insphere_distance

Implementation Notes

Dimension-Dependent InSphere Predicate Performance

The tables above are the source of truth for predicate timing. insphere_lifted shows advantages in lower dimensions such as 2D/3D, while insphere_distance often wins in 4D/5D; boundary cases may favor insphere because of early exits.

Benchmark Structure

The ci_performance_suite.rs benchmark is the primary regression and release-summary suite. It emits a versioned api_benchmark_manifest and covers public construction, hull, validation, insertion, boundary, and bistellar-flip workflows across supported dimensions.

The circumsphere_containment.rs benchmark includes:

  • Random queries: Batch processing performance with 1000 random test points
  • Dimensional tests: Performance across 2D, 3D, 4D, and 5D simplices
  • Edge cases: Boundary vertices and far-away points
  • Numerical consistency: Agreement analysis between all methods

Performance Data Updates

This file is automatically generated from benchmark results. For release-facing updates:

just bench-perf-summary

For manual diagnostics without the release recipe, use the underlying CLI:

# Re-render from currently available Criterion data
uv run benchmark-utils generate-summary

# Run fresh perf-profile public API and circumsphere benchmarks
uv run benchmark-utils generate-summary --run-benchmarks --profile perf

# Generate baseline results for regression testing
uv run benchmark-utils generate-baseline

Customization

For manual updates or custom analysis, modify the PerformanceSummaryGenerator class in scripts/benchmark_utils.py. This provides enhanced control over dynamic vs static content organization and supports parsing numerical accuracy data from live benchmark runs.