Any problems if discriminated union has lots of options?

Question

Yes, a trivial question, but I couldn't find an expert opinion on it.

I am using computation expressions to sequence server-side processes. It helps me tremendously when my functions have the same signature, so I have a discriminated union with different combinations defined within it. I have a couple of quick, beginners' questions.

1. Is there a recommended upper limit to the number of options that a DU can have? Currently my DU has nine options, but this number will increase as the project progresses. What if I hit 30 or 40 by the end of the project?

2. Might there be a problem if some of the options get "long"? Currently, the average option has about four or five basic types--something like bool * string * XElement * int * string--but the longest one has the following definition:

   bool * int * int * int * string * XElement * XElement * DateTime option * DateTime option * string * Dictionary * Dictionary

I don't expect many options to be anywhere near this long. But am I setting myself up for a world of pain in terms of performance?

Thanks in advance.

Answer 1

I think you can safely assume that things will work well if the size of your data type is similar to the sizes of data types used by the F# compiler - the performance of the F# compiler is something that the F# team has definitely looked at and so I think they also did a few experiments to make sure the discriminated unions they use work efficiently.

• As for the number of cases, the SynExpr discriminated union (see source code) has over 50 cases, so I think this should be fine.

  Pattern matching on discriminated union is compiled by using the switch IL opcode on an integer, so you can try doing some research on the efficiency of this, if you want to make sure. Also, if you just use match to find one specific case, then that should just be a single integer comparison, regardless of the number of other cases.

• As for the number of fields, the longest case of SynExpr has some 7 fields, but I suppose you can find other DUs where the length is longer. (I think a bigger problem with this number of attributes is readability - because the attributes are unnamed. So I think using a record for large number of attributes that logically belong together might be better.)

I think the size of DUs you described should be fine, but I have not done any performance testing myself - so if you really want to make sure, you need to measure it. (But as I said, I'm pretty sure this is something that has been tested as part of the F# compiler development)

Answer 2

If memory serves me, I believe there were some performance issues with deeply nested pattern matches on DUs with a lot of cases / fields-per-case, but that was pre-2.0 and I believe they fixed the implementation such that currently such scenarios are well-optimized and have no glaring performance issues. (sorry, no citation).

But even when optimized, DUs de-sugar into quite a large amount of code. So even though they may perform as well (and likely better) than any equivalent hand-coded control flow, there is the possibility that you could stack-overflow on the sheer number of instructions emitted for a function / method body (but this would be quite an extreme scenario since the .NET default stack size is ~1MB, however, it could certainly lead to earlier than usual stack overflow in non-tail recursive method / function involving matching of the large DU, but again not likely to the degree that you should actual fear this scenario).

I don't believe it will change the performance characteristics (since we are talking about heap allocated objects in either case), but for maintainability / readability it sometimes helps to wrap your DU case data in a record type so that data fields are named and pattern matching on a subset of data fields is easier (e.g. {Name="Stephen"} instead of (_,_,_,_,_,_,_,"Stephen",_,_,_,_,_)). (@TomasPetricek beat me to this suggestion, didn't see that on my first read through his answer)