/usr/lib/swi-prolog/doc/Manual/jitindex.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">

<html>
<head>
<title>SWI-Prolog 7.1.16 Reference Manual: Section 2.17</title><link rel="home" href="index.html">
<link rel="contents" href="Contents.html">
<link rel="index" href="DocIndex.html">
<link rel="summary" href="summary.html">
<link rel="previous" href="cyclic.html">
<link rel="next" href="widechars.html">

<style type="text/css">

/* Style sheet for SWI-Prolog latex2html
*/

dd.defbody
{ margin-bottom: 1em;
}

dt.pubdef, dt.multidef
{ color: #fff;
padding: 2px 10px 0px 10px;
margin-bottom: 5px;
font-size: 18px;
vertical-align: middle;
overflow: hidden;
}

dt.pubdef { background-color: #0c3d6e; }
dt.multidef { background-color: #ef9439; }

.bib dd
{ margin-bottom: 1em;
}

.bib dt
{ float: left;
margin-right: 1.3ex;
}

pre.code
{ margin-left: 1.5em;
margin-right: 1.5em;
border: 1px dotted;
padding-top: 5px;
padding-left: 5px;
padding-bottom: 5px;
background-color: #f8f8f8;
}

div.navigate
{ text-align: center;
background-color: #f0f0f0;
border: 1px dotted;
padding: 5px;
}

div.title
{ text-align: center;
padding-bottom: 1em;
font-size: 200%;
font-weight: bold;
}

div.author
{ text-align: center;
font-style: italic;
}

div.abstract
{ margin-top: 2em;
background-color: #f0f0f0;
border: 1px dotted;
padding: 5px;
margin-left: 10%; margin-right:10%;
}

div.abstract-title
{ text-align: center;
padding: 5px;
font-size: 120%;
font-weight: bold;
}

div.toc-h1
{ font-size: 200%;
font-weight: bold;
}

div.toc-h2
{ font-size: 120%;
font-weight: bold;
margin-left: 2em;
}

div.toc-h3
{ font-size: 100%;
font-weight: bold;
margin-left: 4em;
}

div.toc-h4
{ font-size: 100%;
margin-left: 6em;
}

span.sec-nr
{
}

span.sec-title
{
}

span.pred-ext
{ font-weight: bold;
}

span.pred-tag
{ float: right;
padding-top: 0.2em;
font-size: 80%;
font-style: italic;
color: #fff;
}

div.caption
{ width: 80%;
margin: auto;
text-align:center;
}

/* Footnotes */
.fn {
color: red;
font-size: 70%;
}

.fn-text, .fnp {
position: absolute;
top: auto;
left: 10%;
border: 1px solid #000;
box-shadow: 5px 5px 5px #888;
display: none;
background: #fff;
color: #000;
margin-top: 25px;
padding: 8px 12px;
font-size: larger;
}

sup:hover span.fn-text
{ display: block;
}

/* Lists */

dl.latex
{ margin-top: 1ex;
margin-bottom: 0.5ex;
}

dl.latex dl.latex dd.defbody
{ margin-bottom: 0.5ex;
}

/* PlDoc Tags */

dl.tags
{ font-size: 90%;
margin-left: 5ex;
margin-top: 1ex;
margin-bottom: 0.5ex;
}

dl.tags dt
{ margin-left: 0pt;
font-weight: bold;
}

dl.tags dd
{ margin-left: 3ex;
}

td.param
{ font-style: italic;
font-weight: bold;
}

/* Index */

dt.index-sep
{ font-weight: bold;
font-size: +1;
margin-top: 1ex;
}

/* Tables */

table.center
{ margin: auto;
}

table.latex
{ border-collapse:collapse;
}

table.latex tr
{ vertical-align: text-top;
}

table.latex td,th
{ padding: 2px 1em;
}

table.latex tr.hline td,th
{ border-top: 1px solid black;
}

table.frame-box
{ border: 2px solid black;
}

</style>
</head>
<body style="background:white">
<div class="navigate"><a class="nav" href="index.html"><img src="home.gif" alt="Home"></a>
<a class="nav" href="Contents.html"><img src="index.gif" alt="Contents"></a>
<a class="nav" href="DocIndex.html"><img src="yellow_pages.gif" alt="Index"></a>
<a class="nav" href="summary.html"><img src="info.gif" alt="Summary"></a>
<a class="nav" href="cyclic.html"><img src="prev.gif" alt="Previous"></a>
<a class="nav" href="widechars.html"><img src="next.gif" alt="Next"></a>
</div>
<h2 id="sec:jitindex"><a id="sec:2.17"><span class="sec-nr">2.17</span> <span class="sec-title">Just-in-time 
clause indexing</span></a></h2>

<a id="sec:jitindex"></a>

<p><a id="idx:jitindex:221"></a>SWI-Prolog provides `just-in-time' 
indexing over multiple arguments.<sup class="fn">23<span class="fn-text">JIT 
indexing was added in version 5.11.29 (Oct. 2011).</span></sup> 
`Just-in-time' means that clause indexes are not built by the compiler 
(or <a id="idx:asserta1:222"></a><a class="pred" href="db.html#asserta/1">asserta/1</a> 
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.

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

<p>
<ul class="latex">
<li><i>Special purpose code</i><br>
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 (<code>[]</code>) and one where the 
first argument is a non-empty list (<code>[_|_]</code>).

<p>
<li><i>Linear scan on first argument</i><br>
The principal clause list maintains a <em>key</em> 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.

<p>
<li><i>Hash lookup</i><br>
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 it marks arguments that are less suitable 
than the argument to which the table belongs.

<p>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.

<p>Disregarding variables, the suitability of an argument for hashing is 
expressed as the number of unique indexable values divided by the 
standard deviation of the number of duplicate values for each value plus 
one.<sup class="fn">24<span class="fn-text">Earlier 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&uuml;nter 
Kniesel.</span></sup>

<p>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 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
<a id="idx:garbagecollectclauses0:223"></a><a class="pred" href="consulting.html#garbage_collect_clauses/0">garbage_collect_clauses/0</a>.
</ul>

<p><h3 id="sec:indexfut"><a id="sec:2.17.1"><span class="sec-nr">2.17.1</span> <span class="sec-title">Future 
directions</span></a></h3>

<a id="sec:indexfut"></a>

<p>
<ul class="latex">
<li>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.

<p>
<li>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.
</ul>

<p><h3 id="sec:indexport"><a id="sec:2.17.2"><span class="sec-nr">2.17.2</span> <span class="sec-title">Indexing 
and portability</span></a></h3>

<a id="sec:indexport"></a>

<p>The base-line functionality of Prolog implementations provides 
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 <a id="idx:termhash2:224"></a><a class="pred" href="db.html#term_hash/2">term_hash/2</a> 
or <a id="idx:termhash4:225"></a><a class="pred" href="db.html#term_hash/4">term_hash/4</a> 
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).

<p>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.

<p></body></html>
swi-prolog-nox 6.6.6-5 / usr / lib / swi-prolog / doc / Manual / jitindex.html
