Discriminated Union dispatch overhead with complex Active Patterns

Question

F# utilizes internal integer tags for Discriminated Unions (DUs), typically resulting in O(1) dispatch time via jump tables. However, the introduction of Active Patterns allows for custom logic to be executed during the pattern matching process, shifting the dispatch mechanism from a simple tag check to a function call.

When integrating complex Active Patterns into high-frequency matching loops, there is a potential performance trade-off between the flexibility of the pattern and the raw speed of standard DU tag matching. It is unclear at what level of complexity an Active Pattern begins to significantly degrade the instruction cache efficiency or introduce measurable overhead compared to a standard match expression.

Does the F# compiler apply any specific optimizations to simplify Active Patterns back into tag-based jumps when the logic is deterministic?
  What is the performance delta between a standard DU match and a Partial Active Pattern when processing large datasets?

Tasadduq Burney · Answer

Answer
The F# compiler does not automatically turn arbitrary active patterns into tag‑based jump tables; only trivial patterns (constants or simple property accesses) can be inlined, so a complex active pattern remains a normal function call.
Confirmed facts

Discriminated unions are compiled to integer tags; a plain match becomes a switch/jump table, giving O(1) dispatch with minimal overhead.
A partial active pattern is emitted as a call to a function that returns option<_>; the JIT treats it like any other method call.

Likely explanation
Because the compiler cannot guarantee that an active pattern’s logic is side‑effect‑free and deterministic enough to replace with a constant tag, it preserves the pattern as a separate delegate. Only when the pattern is marked [] or consists of a constant comparison does the optimizer have a chance to inline it back into the switch.
Steps to measure the overhead for your case

Define a representative DU (e.g., type Shape = Circle of float | Rect of float * float).
Write a partial active pattern that captures the complexity you care about (e.g., let (|Positive|_|) x = if x > 0.0 then Some () else None).
Create two tight‑loop functions: one that matches the DU with a standard match, another that uses the active pattern in each iteration.
Run them with BenchmarkDotNet on a large array (≥10⁷ elements) and record the mean time per element.
Inspect the generated IL (via ildasm or dotnet peek) to verify that the standard match is a switch while the active pattern compiles to a call.

If your active pattern is trivial (constant or simple property) and marked [], the compiler may inline it and the overhead will disappear; otherwise expect roughly 4‑8 ns extra per element for a basic integer comparison, and an order‑of‑magnitude slowdown for more elaborate patterns (string parsing, regex, list traversal).
Please confirm whether the active pattern you are using is trivial (constant or simple property) or involves non‑trivial computation, as this determines if the compiler can inline it.

Discriminated Union dispatch overhead with complex Active Patterns

1 answer

Answer

Confirmed facts

Likely explanation

Steps to measure the overhead for your case

Your perspective belongs here.

0 question comments