Discussion Choice Point Elimination

In this section we will provide a critical discussion of the impact of the choice point elimination optimization. The choice point elimination already causes a speed-up in the average. We observe an average speed-up factor of 95.2%. The choice point elimination is the worst optimization. There are other optimizations down the pipeline which show a better speed-up. The best speed up factor of around 83.0% was observed for the test program deriv. The worst slow-down factor of around 110.9% was observed for the test program calc.

Picture 3: Choice Point Elimination Impact

Bare bone choice point elimination has two advantages. First a list of clauses will not need a choice point for the last clause so that the corresponding space and time can be saved. Second a cut itself does not create a choice point anymore so that again space and time can be saved. If we sum up these two advantages then all programs should see some speed up, but this cannot be verified in the present case. We speculate that there are a couple of reasons for this phenomenon.

One reason is that non-deterministic programs might not enough profit from choice point elimination. Backtracking has the same effect since it will also force a predicate to remove choice points. Therefore the early elimination of choice points does not give any advantage since the choice points are anyway not long living and quickly returned to the Java memory management by the garbage collection. The choice point elimination only incurs an overhead here by the additional checks needed.

It should be noted that choice point elimination is an enabler for a couple of subsequent optimizations. When we switch off these optimizations, some code branches will be nevertheless executed when choice point elimination is on. There is a problem of ordering additional checks. What we currently do in the current implementation we always first check for determinism and then go through all the enabled subsequent optimizations. Choice point elimination causes the determinism check to succeed more often. If no subsequent optimization is enabled, then only overhead is incurred.

Kommentare