C#结构体包装基元索引在Delaunay三角剖分中的性能问询

Let's break down your performance bottlenecks first, then walk through practical solutions that keep your code safe and readable without sacrificing the raw speed of primitive arrays.

Why Your Current Implementations Are Slow #

Let's unpack each approach's performance issues:

1. Point Struct with Delaunay Reference #

Storing a DelaunayTriangulation reference in every Point struct kills performance for two key reasons:

• Increased memory footprint: On 64-bit systems, each Point becomes 16 bytes (4 bytes for int index + 8 bytes for the reference, padded to 16 for alignment). This doubles/triples the data size compared to a bare int, which hurts cache locality—your CPU spends more time fetching data from RAM instead of L1/L2 cache.
• Indirect array access: Every call to GetIncomingHalfEdgeCount or GetIncomingHalfEdge has to dereference the DelaunayTriangulation pointer first, adding extra cycles the bare array approach avoids.

2. Point Struct with Delaunay Passed as Parameter #

This is better, but still 2.5x slower than bare ints likely due to:

• Struct construction overhead: Even though HalfEdge is a value type, creating a new instance in each loop iteration adds small but cumulative overhead (stack allocation + constructor execution) that the bare int return avoids.
• Method call overhead: Without explicit inlining hints, the JIT compiler might not inline your GetIncomingHalfEdge method, leading to repeated call/return cycles.

3. Methods on DelaunayTriangulation Class #

The 3x slowdown here is probably due to how the JIT optimizes class methods vs. struct methods. When passing a Point struct to a class method, the JIT may not optimize away the struct copy (even though it's just 4 bytes) as effectively as when calling a struct's own method. Additionally, class methods sometimes have slightly higher overhead for member access compared to struct methods that directly target the passed-in DelaunayTriangulation.

4. Yield-Based IEnumerable #

Yield creates a state machine behind the scenes, which involves heap allocations (for the enumerator) and extra branching logic. This is a non-starter for high-performance code—you'll always take a massive hit here.

Practical Solutions to Balance All Three Goals #

Here are two approaches that give you compile-time type safety, readable code, and performance nearly identical to bare primitive arrays:

Solution 1: Readonly Structs + Aggressive Inlining + in Parameters #

Lean into C#'s value type optimizations by marking your structs as readonly (to enable JIT optimizations) and forcing method inlining with [MethodImpl(MethodImplOptions.AggressiveInlining)]. Use in parameters for DelaunayTriangulation to avoid unnecessary reference copies and help the JIT optimize further.

using System.Runtime.CompilerServices;

public readonly struct Point
{
    public readonly int Index;

    public Point(int index) => Index = index;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public int GetIncomingHalfEdgeCount(in DelaunayTriangulation delaunay) 
        => delaunay.pointsEdgeStartCount[Index * 2 + 1];

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public HalfEdge GetIncomingHalfEdge(in DelaunayTriangulation delaunay, int i)
    {
        int start = delaunay.pointsEdgeStartCount[Index * 2];
        return new HalfEdge(delaunay.pointsIncomingHalfEdgeIndexes[start + i]);
    }
}

public readonly struct HalfEdge
{
    public readonly int Index;

    public HalfEdge(int index) => Index = index;

    // Add other HalfEdge methods with AggressiveInlining too
}

Call site:

int count = p.GetIncomingHalfEdgeCount(in delaunay);
for (int i = 0; i < count; i++)
{
    var e = p.GetIncomingHalfEdge(in delaunay, i);
    // Work with e
}

This approach eliminates method call overhead and keeps your structs lightweight. The JIT will inline the methods, turning the code into almost identical machine code as the bare array approach.

Solution 2: Type Aliases + Extension Methods (Ultimate Performance) #

If you want performance indistinguishable from bare ints while still having compile-time type safety, use C#'s using alias directive to create semantic index types, then wrap your array access logic in inlined extension methods.

using System.Runtime.CompilerServices;

// Semantic type aliases (compile-time safety, runtime is just int)
using PointIndex = System.Int32;
using HalfEdgeIndex = System.Int32;

public static class DelaunayExtensions
{
    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static int GetIncomingHalfEdgeCount(this DelaunayTriangulation delaunay, PointIndex p)
        => delaunay.pointsEdgeStartCount[p * 2 + 1];

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public static HalfEdgeIndex GetIncomingHalfEdge(this DelaunayTriangulation delaunay, PointIndex p, int i)
    {
        int start = delaunay.pointsEdgeStartCount[p * 2];
        return delaunay.pointsIncomingHalfEdgeIndexes[start + i];
    }
}

Call site:

PointIndex p = ...; // Compile-time check: can't pass a HalfEdgeIndex here
int count = delaunay.GetIncomingHalfEdgeCount(p);
for (int i = 0; i < count; i++)
{
    HalfEdgeIndex e = delaunay.GetIncomingHalfEdge(p, i);
    // Work with e
}

This is the fastest option because:

• The type aliases are just compile-time hints—at runtime, they're still ints, so no extra memory overhead.
• The extension methods are fully inlined, turning the code into direct array accesses exactly like your original bare int approach.
• You still get compile-time safety: you can't accidentally pass a HalfEdgeIndex where a PointIndex is expected.

Final Recommendations #

• Avoid yield-based enumerables entirely for high-performance loops—they're designed for readability, not speed.
• Choose Solution 2 if you need absolute maximum performance and don't need full struct encapsulation.
• Choose Solution 1 if you want a more object-oriented approach with methods attached to your Point/HalfEdge types, while still getting near-bare-metal speed.

You don't have to give up type safety for performance—C#'s low-level optimizations let you have both.

内容的提问来源于stack exchange，提问作者Nayef