2.17 Just-in-time clause indexing

SWI-Prolog provides `just-in-time' indexing over multiple arguments.<sup>20JIT indexing was added in version 5.11.29 (Oct. 2011).</sup> `Just-in-time' means that clause indexes are not built by the compiler (or asserta/1 for dynamic predicates), but on the first call to such a predicate where an index might help (i.e., a call where at least one argument is instantiated). This section describes the rules used by the indexing logic. Note that this logic is not `set in stone'. The indexing capabilities of the system will change. Although this inevitably leads to some regressing on some particular use cases, we strive to avoid significant slowdowns.

The list below describes the clause selection process for various predicates and calls. The alternatives are considered in the order they are presented.

• Special purpose code
  Currently two special cases are recognised by the compiler: static code with exactly one clause and static code with two clauses, one where the first argument is the empty list ([]) and one where the first argument is a non-empty list ([_|_]).

• Linear scan on first argument
  The principal clause list maintains a key for the first argument. An indexing key is either a constant or a functor (name/arity reference). Calls with an instantiated first argument and less than 10 clauses perform a linear scan for a possible matching clause using this index key.

• Hash lookup
  If none of the above applies, the system considers the available hash tables for which the corresponding argument is instantiated. If a table is found with acceptable characteristics, it is used. Otherwise, there are two cases. First, if no hash table is available for the instantiated arguments, it assesses the clauses for all instantiated arguments and selects the best candidate for creating a hash table. Arguments that cannot be indexed are flagged to avoid repeated scanning. Second, if there is a hash table for an indexed argument but it has poor characteristics, the system scans other instantiated arguments to see whether it can create a better hash table. The system maintains a bit vector on each table in which is marks arguments that are less suitable than the argument to which the table belongs.

  Clauses that have a variable at an otherwise indexable argument must be linked into all hash buckets. Currently, predicates that have more than 10% such clauses for a specific argument are not considered for indexing on that argument.

  Disregarding variables, the suitability of an argument for hashing is expressed as the number of unique indexable values devided by the standard deviation of the number of duplicate values for each value plus one.^{21Earlier versions simply used the number of unique values, but poor distribution of values makes a table less suitable. This was analysed by Fabien Noth and Günter Kniesel.}

  The indexes of dynamic predicates are deleted if the number of clauses is doubled since its creation or reduced below 1/4th. The JIT approach will recreate a suitable index on the next call. Indexes of running predicates cannot be deleted. They are added to a `removed index list' associated to the predicate. Dynamic predicates maintain a counter for the number of goals running the predicate (a predicate can `run' multiple times due to recursion, open choice-points and it can run in multiple threads) and destroy removed indexes if this count drops to zero. Outdated indexes of static predicates (e.g., due to reconsult or enlarging multifile predicates) are reclaimed by garbage_collect_clauses/0.

2.17.1 Future directions

• The current indexing system is largely prepared for secondary indexes. This implies that if there are many clauses that match a given key, the system could (JIT) create a secondary index. This secondary index could exploit another argument or, if the key denotes a functor, an argument inside the compound term.

• The `special cases' can be extended. This is notably attractive for static predicates with a relatively small number of clauses where a hash lookup is too costly.

2.17.2 Indexing and portability

The base-line functionality of Prolog implementations provide indexing on constants and functor (name/arity) on the first argument. This must be your assumption if wide portability of your program is important. This can typically be achieved by exploiting term_hash/2 or term_hash/4 and/or maintaining multiple copies of a predicate with reordered arguments and wrappers that update all implementations (assert/retract) and selects the appropriate implementation (query).

YAP provides full JIT indexing, including indexing arguments of compound terms. YAP's indexing has been the inspiration for enhancing SWI-Prolog's indexing capabilities.