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%.
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 . But our test programs cannot be viewed as testing perpetual processes since we execute them repeatedly via backtracking.