Discussion Clause Indexing

In this section we will provide a critical discussion of the impact of the clause indexing optimi-zation. The average speed up factor is around 94.4%. The best speed up factor is seen for the test program query with 44.4%. We also find test programs with a slowdown. The test program deriv has the worst slowdown factor of 107.6%. The average speed up factor is not overwhelming. Nevertheless it should be noted that this optimization is also important, since it improves the choice point elimination and therefore also the body variable elimination and the stack frame elimination.


Picture 4: Clause Indexing Impact

When the clause indexing picks a non-variable argument it performs a lookup in a hash table. The effort for this lookup can be assumed as a constant effort. The hash table will then return a smaller clause set compared to the full clause set. The smaller this clause set the less effort is needed by the Prolog system finding a matching clause. The clause sets are usually smaller when the hash table has more different keys. As such we can understand our benchmarking results and the good result for query. The predicate area/2 of the query test program does show a great number of different keys.

The other test programs then have hash table keys to varying degree. List processing predicates typically profit from hash table keys for ‘[]’ and ‘.’. These keys help making the necessary case decisions faster since lengthy multiple failed unifications are bypassed. We find here the test programs nrev. The test programs poly and crypt will even make use of clause indexes that span multiple arguments. In the latter case it is not that list processing keys are important, rather the hash table key ‘poly’ is of importance.

But we also find the situation of clauses where an argument position consists of a variable. These clauses are included in all the clause sets of all the hash table keys since a calling goal might match such a clause. This enlarges the size of the clause set and lowers the impact of clause indexing. If the argument position leads to a trivial hash table the argument position is skipped and a better argument position is searched. If no better argument position is found then only overhead is generated.

Comments