Yesterday’s blog post contains a glaring error. Thanks to Eamon Nerbonne for point this out, his comments are very insightful so rather than reiterating them its best you read them for yourself. The basic problem was that the measurements of the speed of + - * operators was wrong since the compiler had spotted that the results of the operation was not used and therefore had not generated code for the loop. I was a little suspicious that the loops were happening too fast, but didn’t investigate further assumed that no optimization was happening as the loop that tested the / operator was clearly taking place (if there was optimization of a loop contain a / operator then why would there be optimization of a loop containing a + - or * operator?) and also I was expecting a big difference to make it worth mentioning in the disruptor technical paper.
Anyway, as my assumptions turned out to be wrong, I decided to investigate the question “if there was optimization of a loop contain a / operator then why would there be optimization of a loop containing a + - or * operator?” First I checked the generated IL and here I found something interesting, the compiler F# had generated IL code for the / and % loops but not for the others. This was pretty luck; it means the optimization takes place in the F# compiler and not in the .NET JIT compiler. The F# compiler is open source so it’s much easier to check out why certain optimizations happen and others do not.
Next I checked the source file opt.fs which I knew contained the compiler optimizations of IL code. There’s a type definition at the head of the file “OptimizationSettings” which contains a member method “EliminateUnusedBindings”. I did a quick search for this and it landed me close to a function “IlAssemblyCodeInstrHasEffect”. Here’s the functions definition:
let IlAssemblyCodeInstrHasEffect i =
match i with
| ( AI_nop | AI_ldc _ | AI_add | AI_sub | AI_mul | AI_xor | AI_and | AI_or
| AI_ceq | AI_cgt | AI_cgt_un | AI_clt | AI_clt_un | AI_conv _ | AI_shl
| AI_shr | AI_shr_un | AI_neg | AI_not | AI_ldnull )
| I_ldstr _ | I_ldtoken _ -> false
| _ –> true
The function uses pattern matching over the discriminating union which represents the IL op code (defined in il.fsi). Here we see that the AI_add, AI_sub, and AI_mul instructions, which represent the + – * operators, are classified amongst effect free. We see no mention of the AI_div or AI_rem instructions, that represent / and % operators, so they must fall into the everything else category that is considered effectful. I would guess if you add these two instructions to the effect free group then you would see that loops that contain nothing other than a single / or % operation are also removed by the optimization process. However, I don’t have a copy of the F# compiler source that compiles on this machine so I cannot confirm this. I’ll leave it as an exercise to the reader.
Why are the AI_div or AI_rem instructions not classified as effect free? I don’t know IL well enough to state for certain that they are side effect free but I would guess that this is the case. If so they may have been removed to optimize the speed of the compiler, reduce the amount of comparisons it needed to do, but I doubt this, it seems more likely that it’s a simple oversight.
Is this useful information? The knowledge about unused bindings being removed is probably not so useful. Unused bindings should be removed from your code as good practice, you shouldn’t rely on the compiler to do it for you. It is however useful to have some understanding of the optimizations the compiler will perform for you and I think opt.fs is a good place to start looking at these. More importantly it’s a useful lesson that you should always check your assumption. It also shows that designing a good performance test is hard, create a test that is too micro and the test can easily become unrealistic, create a test that is too marco and the results can become very hard to interpret.
Feedback was imported from my only blog engine, it’s no longer possible to post feedback here.
re: F# Compiler IL Optimizations - Eamon Nerbonne
Hey, thanks for the mention ;-). I was wondering about that too yesterday, but didn't think to investigate. But given that the function name suggests it's about possible side effects, I'd guess it's intentional: integer division can cause divide by zero, after all; and the compiler probably just doesn't special case constants.
That's kind of interesting actually; I suspect this means it won't reorder over such instructions either limiting further optimization possibilities.
re: F# Compiler IL Optimizations - Robert Pickering
Yes your right, an exception is definitely a observable side effect so the compiler can't optimize away a division even if 99% of the time you probably wouldn't want the divide by zero exception.