In this section we will provide a critical discussion of the
impact of the head variable elimination optimization. The head
variable elimination might reduce the number of instructions in
the case of temporary variables. Also the head variable
elimination shortens the size of the display in the case of extra
variables. The average speed up factor is around 89.8%. We
observed the worst speed-up of 101.8% for the test program query.
In the best case we observed a speed up of 71.2% for the test
The benefits of the head variable elimination are quickly eaten
up by non-extra temporary variables. These variables are unified
over and over again during backtracking which would explain the
performance penalty for the test program query. On the other hand
when such variables occur in the context of guards there is a
clear advantage. This would explain the positive impact on the DCG
calculator since the factor testing works in the form of a digit
guard and eventually also the positive impact on perfect since the
between1/3 predicate makes use of a >/2 guard.
Further there is a geometric argument which can explain some of the positive examples. The current head variable elimination most often only applies to facts. Facts form the leaves of a proof tree. The number of leaves depends on the shape of the proof tree. The lowest number of leaves is found in a linear proof such as found in the concatenate/3 predicate. The number of leaves is there of order O(1) relative to the total number of proof steps n. More leaves are found in a quadratic proof such as rev/2. It is of order O(n0.5). Finally a tree shaped proof such as sort/3 has the highest number of leaves. It is close to the order of O(n/2).
The head variable elimination is redundant to the body variable
elimination. The effect of sparing a variable place holder
allocation is already archived by the body variable elimination.
The body variable elimination would first create and then later
dispose the variables after the unification. Nevertheless the head
variable elimination has the advantage of bypassing these runtime
steps and reducing the code already at compile time.