Does using single-case discriminated union types have implications on performance?

Question

It is nice to have a wrapper for every primitive value, so that there is no way to misuse it. I suspect this convenience comes at a price. Is there a performance drop? Should I rather use bare primitive values instead if the performance is a concern?

Boulevardier

Answer 1

Yes, there's going to be a performance drop when using single-case union types to wrap primitive values. Union cases are compiled into classes, so you'll pay the price of allocating (and later, collecting) the class and you'll also have an additional indirection each time you fetch the value held inside the union case.

Depending on the specifics of your application, and how often you'll incur these additional overheads, it may still be worth doing if it makes your code safer and more modular.

I've written a lot of performance-sensitive code in F#, and my personal preference is to use F# unit-of-measure types whenever possible to "tag" primitive types (e.g., ints). This keeps them from being misused (thanks to the F# compiler's type checker) but also avoids any additional run-time overhead, since the measure types are erased when the code is compiled. If you want some examples of this, I've used this design pattern extensively in my fsharp-tools projects.

Harrington

@bonomo You can, but it's a little hacky. You should also keep in mind that since unit-of-measure types are erased, they're not enforced at run-time; if you need that, you're stuck creating the union cases or some other type to wrap your values. See this discussion for more info: Compile-time constraints for strings in F#, similar to Units of Measure - is it possible? – Harrington

"...allocating...indirection..." and the write barrier when you mutate a reference type in the heap. – Radiophone

you can't shadow the constructor or force validation on units of measure types, right? such that -1<celcius> can't be instantiated? – Retentivity

F# 4.1 now has struct single case discriminated unions, using the [<Struct>] annotation, see RFC FS-1014: github.com/fsharp/fslang-design/blob/master/FSharp-4.1/… -- performance is greatly increased – Zygo

Answer 2

Jack has much more experience with writing high-performance F# code than I do, so I think his answer is absolutely right (I also think the idea to use units of measure is pretty interesting).

Just to put things in context, I wrote a really basic test (using just F# Interactive - so things may differ in Release mode) to compare the performance. It allocates an array of wrapped (vs. non-wrapped) int values. This is probably the scenario where non-wrapped types are really a good choice, because the array will be just a continuous block of memory.

#time
// Using a simple wrapped `int` type
type Foo = Foo of int
let foos = Array.init 1000000 Foo
// Add all 'foos' 1k times and ignore the results
for i in 0 .. 1000 do 
  let mutable total = 0
  for Foo f in foos do total <- total + f

On my machine, the for loop takes on average something around 1050ms. Now, the unwrapped version:

let bars = Array.init 1000000 id    
for i in 0 .. 1000 do 
  let mutable total = 0
  for b in bars do total <- total + b

On my machine, this takes about 700ms.

So, there is certainly some performance penalty, but perhaps smaller than one would expect (some 33%). And this is looking at a test that does virtually nothing else than unwrap the values in a loop. In code that does something useful, the overhead would be a lot smaller.

This may be an issue if you're writing high-performance code, something that will process lots of data or something that takes some time and the users will run it frequently (like compiler & tools). On the other hand, if you application is not performance critical, then this is not likely to be a problem.

Dud

There is no such thing as discriminated unions in C#. One can use a visitor pattern instead which involves creating a visitor and making a virtual function call (may be more than one) every time you need to resolve an abstract instance to a concrete one. I have no idea what the internal dispatching mechanism of the discriminated unions is. I wish I knew it so I can make more conscious decisions on using them. I will appreciate it if you have any insights on that. – Shetrit

Somebody has decompiled a discriminated union. It is indeed based on inheritance although dispatching is done by checking the boolean properties and type casing (I suspect) which is fine for few cases but can be a problem a big number multi-case. bugfree.dk/blog/2012/06/23/… – Shetrit

The pattern matching is compiled using the Tag property (so it is essentially switch over an integer value). This is perfectly fine for multiple cases - discriminated unions let you add new functions easily, which is not possible using virtual methods. The main benefit of visitors is maintainability - that's not an issue for compiler-generated code. – Dud

Array.init 1000000 (fun n -> Foo -n) |> Array.sort is 90x slower than Array.init 1000000 (fun n -> -n) |> Array.sort. – Radiophone

@JonHarrop I wonder if that is because the automatically generated comparison on discriminated unions is inefficient. It would be interesting to compare this with Array.sortBy (fun (Foo n) -> -n). That might be more realistic. – Dud

@TomasPetricek: That is certainly part of it. Your solution is 20x faster, although I'm not sure why. I also compared with a struct and that is also much faster than a union despite having compiler-generated comparison. – Radiophone

@TomasPetricek: The problem seems to be that Array.sort has not been defined as let inline sort xs = Array.sortWith compare xs but, rather, discards compile-time type info and then uses generic comparison at run time. – Radiophone

Answer 3

From F# 4.1 onwards adding the [<Struct>] attribute to suitable single case discriminated unions will increase the performance and reduce the number of memory allocations performed.

Zygo