Even though most performance optimizations are focused on improving algorithms and mechanical sympathy, oftentimes it’s possible to achieve significant wins from simple tweaks that leverage input data characteristics. Binary search and count sort are well-known examples that exploit the fact that input elements are sorted and within a bounded range respectively. But despite being powerful, there are much even simpler ways to improve performance that can be used almost on a daily basis.
Today we are going to cover one such technique - ordering logical clauses to improve chances of short-circuiting. For conjunctions it means putting clauses that are likely to evaluate to false first and for disjunctions, conditions are likely to be true, since
false && expr => false
and
true || expr => true
This is especially useful if these clauses are cheap to evaluate, since we can significantly reduce the number of instructions involved in evaluating the condition.
To make things more concrete, let’s take a look at the following 2 functions:
Semantically they are identical, but the generated assembly has differences reflecting differences in source code:
for likelySecond
vs
for likelyFirst
.
For inputs that are likely to be empty, we’ll need to execute all instructions for the likelySecond and only
for likelyFirst
. To put things into perspective, we’ll use following benchmarks
And the results are:
So we’ve been able to achieve almost 4X speedup simply by simple clause reordering based on the knowledge about which of them is more likely to happen in practice.
This is expected given how much cheaper check for emptiness is than strings.Contains
, but what would happen for equally complex checks? Let’s replace length check with another contains below
The benchmark results are not as impressive as before, but we are still getting 2X speedup
Not bad for such a small change. Ideally these kinds of reorderings would be performed automatically by profile guided optimizations or JIT compilers to make sure our assumptions are kept up-to-date, but in case they are not available, keep this manual option in mind.