Saturday, October 29, 2011

F# under the covers XIV -- Match expressions : Does my complexity look big in this?

The code generation in F# in debug builds is fond of adding plenty of extra branch points that will confuse any naive computation of code complexity based on counting branch instructions at the IL level. Let us take the innocent method

The instructions that map to the match alist with context include

where the first branch could be replaced with a brfalse.s IL_0044 and the code at offsets 0xb, 0xc replaced by nops with no change in the semantics -- but as given it adds an extra cycle to the flow of control graph, and hence false complexity.

The release build of the code retains the first two instructions, but then rather than jumping to get and return an empty list, it in-lines that fraction of the code. If we look at it in C#, the release build looks like

where the debug version has a goto in that if clause that jumps to a statement that returns the empty list.

As an aside, it's also worth noting that nowhere in the .pdb information is there a map to any of the match expressions : there is never a source context which matches the | h :: tail -> or | [] ->; it's all collapsed into the match ... with fragment.

For more complex match expressions such as

the debug IL organizes into trying each of the branch criteria in turn, then jumping ahead to the matched expression; this ends up with a series of redundant branches like

culminating in a final triple burst

whereas the release build treats it more as an if..elseif..elseif..else construct.

As I noted yesterday, this means that there can be a factor of at least two difference in the naively computed cyclomatic complexity of a method depending whether the release or debug build is chosen.

No comments :