On the Efficiency of Optimising Shallow Backtracking in Prolog

Carlsson, Mats (1990) On the Efficiency of Optimising Shallow Backtracking in Prolog. [SICS Report]



The cost of backtracking has been identified as one of the bottlenecks in achieving peak performance in compiled Prolog programs. Much of the backtracking in Prolog programs is shallow, i.e. is caused by unification failures in the head of a clause when there are more alternatives for the same procedure, and so special treatment of this form of backtracking has been proposed as a significant optimisation. This paper describes a modified WAM which optimises shallow backtracking. Four different implementation approaches are compared. A number of benchmark results are presented, measuring the relative tradeoffs between compilation time, code size, and run time. The results show that the speedup gained by this optimisation can be significant.

Item Type:SICS Report
Additional Information:Original report number R90003.
ID Code:2080
Deposited By:Vicki Carleson
Deposited On:30 Sep 2009
Last Modified:18 Nov 2009 15:59

Repository Staff Only: item control page