Discussion Stack Frame Elimination

In this section we will provide a critical discussion of the impact of the stack frame elimination optimization. The average speed up factor is around 57.4%. The best speed up factor is around 12.4% for deriv. deriv and to some extend calc are the only test programs that excel over the average. A couple of other test programs such as nrev, qsort and perfect saw also some significant speed up. The later test programs heavily making use of some typical tail recursive programming patterns. The worst slow-down was for tictac with 100.9%.

Picture 6: Stack Frame Elimination Impact

We can more or less identify a clear trend between the groups of deterministic and non-deterministic test programs. Test programs from the non-deterministic group show practically no impact from stack frame elimination. The reason is simple: Stack frame elimination cannot be applied to a non-deterministic clause since the parent stack frame with the call-site goal is needed during backtracking. A positive impact might be seen when the test program combines deterministic and non-deterministic predicates. This is for example the case for the benchmark program query, but the impact is not severe.

But it is not enough to detect the situation that the stack frame can be eliminated and then to shorten the call chain. We must also see to it that the stack frame is not anymore referenced by some variable place holders. For this purpose our stack frame elimination also invokes the disposal of the remaining variables of the calling clause. This disposal corresponds to the body variable elimination after the last goal of the calling clause, but it is done before the last call and not only when the last call succeeds. The stack frame elimination is therefore an additional enabler for body variable elimination.

Unfortunately the body variable elimination before the last call is also subject to the problems already identified in the previous section. Namely currently the display itself cannot be reclaimed as long as some variable is still in use. This is for example the case when there are structure result arguments. What has become known as tail recursion optimization can be viewed as a combination of our stack frame elimination and our body variable elimination.  Tail recursion optimization is often found in Prolog systems since it is beneficial to perpetual processes [8]. But our test programs cannot be viewed as testing perpetual processes since we execute them repeatedly via backtracking.

Comments