Discussion Head Variable Elimination

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 program perfect.

Picture 7: Head Variable Elimination Impact

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.

Comments