即时子句索引

SWI-Prolog 对多个参数提供“即时”（just-in-time）索引。“即时”表示子句索引不是由编译器（或动态谓词的 asserta/1）预先构建的，而是在第一次调用某个可能受益于索引的谓词时构建，也就是至少有一个参数已经实例化的调用。本节描述索引逻辑使用的规则。注意，这套逻辑并不是一成不变的。系统的索引能力会继续变化。虽然这不可避免地会让某些特定用例发生回退，我们仍会尽力避免显著变慢。

下面的列表描述不同谓词和调用的子句选择过程。各个备选方案按列出的顺序考虑。

  • 专用代码

    编译器当前识别两种特殊情况：只有一个子句的静态代码；以及有两个子句的静态代码，其中一个子句的某个参数是空列表（[]），另一个子句的同一参数是非空列表（[_|_]）。注意，如果这个参数是输出参数，语义会保持不变，但效率会稍微下降。可以用 mode/1 把该参数声明为 - 来避免这种变慢。9.3.18 及以前版本只考虑第一个参数。

  • 在主索引参数上线性扫描

    主子句列表维护一个键（key），通常针对第一个参数。索引键要么是常量，要么是函子（name/arity 引用）。如果调用的主索引参数已实例化，并且子句少于 10 个，系统会使用该索引键做线性扫描，寻找可能匹配的子句。如果结果是确定性的，就使用该结果；否则系统会寻找更好的索引。7.7.2 及以前版本即使结果非确定也会使用。主索引参数是第一个满足如下条件的参数：至少有一个子句在该参数上具有可索引（非变量）值。9.3.18 及以前版本中，主索引固定为第一个参数。

  • 哈希查找

    如果上述方案都不适用，系统会考虑已有哈希表中那些对应参数已经实例化的表。如果找到特征可接受的表，就使用它。否则，系统会评估所有已实例化参数上的子句，并选择最好的候选参数来创建新的哈希表。如果没有任何单个参数能提供可接受的哈希质量，系统会搜索参数组合。最后一步是在 SWI-Prolog 7.5.8 中加入的。索引候选搜索只会在前 254 个参数上进行。

    如果单参数索引包含多个具有相同 name/arity 且至少有一个非变量参数的复合项，就会创建列表索引（list index）。后续查询中，如果这个参数绑定为复合项，JITI 索引会递归地应用到该项的参数上。这称为深层索引（deep indexing）。深层索引是在 7.7.4 版中加入的。另见“深层索引”。

    如果某个子句在本可索引的参数位置上是变量，它必须链接到所有哈希桶中。目前，如果某个谓词在特定参数上有超过 10% 的这类子句，该参数就不会被考虑用于索引。

    忽略变量后，一个参数是否适合哈希，用“唯一可索引值的数量”除以“每个值的重复数量的标准差加一”来表示。早期版本只使用唯一值数量；但值分布不佳会让表不那么适合索引。这个问题由 Fabien Noth 和 Günter Kniesel 分析过。

    对动态谓词而言，如果子句数量相对索引创建时翻倍，或减少到低于原来的四分之一，索引会被删除。JIT 方法会在下一次调用时重新创建合适的索引。正在运行的谓词索引不能被删除。它们会被加入该谓词关联的“已移除索引列表”。谓词中过期的索引由 garbage_collect_clauses/0 回收。子句垃圾收集器会基于时间和空间启发式规则自动调度。详情见 garbage_collect_clauses/0。

库 library(prolog_jiti) 提供 jiti_list/0 和 jiti_list/1，用于列出所有或部分已创建哈希表的特征。

动态谓词使用与静态谓词相同的规则建立索引，但从不应用专用代码方案。此外，如果子句数量相对该谓词上次评估时翻倍，或缩小到低于四分之一，JITI 索引会被丢弃。后续调用会重新评估动态谓词的统计信息，并在适用时创建新索引。

JIT 索引由一组名称以 ci_ 开头的 Prolog 标志控制，例如 ci_min_speedup。见 current_prolog_flag/2。

深层索引

如“即时子句索引”中介绍，深层索引会创建哈希表，用于区分共享同一 name/arity 复合项的子句。深层索引可以高效查找任意项。如果没有它，通常建议把项拍平，也就是把 F(X) 转为事实中的两个参数：一个参数表示函子 F，另一个参数表示参数 X。只要每个项的元数相同，这种方式就很好用。另一种方式是使用 term_hash/2 或 term_hash/4 增加一列，保存该项的哈希值。这种方式可以处理任意元数，但要求我们知道该项是基项（term_hash/2），或者知道到多深的层级可以获得足够选择性（term_hash/4）。

深层索引不要求具备这些知识，并且无论查询和项的实例化情况如何，都能带来高效查找。当前版本仍有一些限制：

  • 在每个层级上，使用哪个索引的决策是独立做出的。未来版本可能会更智能。
  • 深层索引只适用于单参数索引（可以是任意一个参数）。
  • 目前，索引深度限制为 7 层。

注意，编译 DCG 时（见 DCG 相关章节），如果第一个体目标是字面量，它会被包含进子句头。下面给出一个语法及其普通 Prolog 表示形式。

det(det(a), sg)  --> "a".
det(det(an), pl) --> "an".
det(det(the), _) --> "the".

?- listing(det).
det(det(a), sg, [97|A], A).
det(det(an), pl, [97, 110|A], A).
det(det(the), _, [116, 104, 101|A], A).

深层参数索引会为第 3 个列表参数创建索引。如果所有规则都以字面量开头，并且所有字面量的前 6 个元素都唯一，这会提供加速，并让子句选择变为确定性。注意，一旦可以做出确定性选择，或不存在两个子句具有相同 name/arity 组合，深层索引创建就会停止。

未来方向

  • 可以扩展“特殊情况”。对于子句数量相对较少、哈希查找成本过高的静态谓词来说，这尤其有吸引力。
  • 为少量静态子句之间的选择创建高效的决策图。
  • 实现更好的判断机制，用于在深层索引和普通索引之间做选择。

体内代码索引

当前 SWI-Prolog 版本只考虑子句头来生成子句索引。这会导致无法检查头参数并在体内传递该参数，除非复制这个参数。考虑下面两个子句。二者在 Prolog 下语义相同。第一个版本会丢失子句索引，第二个版本会创建 f/1 参数的副本。二者都不理想。

p(X) :- X = f(I), integer(I), q(X).
p(f(I)) :- integer(I), q(f(X)).

从 SWI-Prolog 8.3.21 开始，凡是在体内任何其他目标之前发生、并针对头参数的合一，都会被特殊编译。实际效果是，被合一的项会移动到头部（从而提供索引），而使用该项的位置则直接使用相应参数。显式合一会被移除。反编译（clause/2）会反转这个过程，但不一定生成完全相同的项。重新插入的合一会按参数位置排序，而且变量总是位于 =/2 的左侧。因此：

p(X,Y) :- f(_) = Y, X = g(_), q(X,Y).

会被反编译为下面这个等价子句。

p(X,Y) :- X = g(_), Y = f(_), q(X,Y).

补充说明：

  • 该转换只对静态代码执行。
  • 合一必须在一个合取中紧跟在头部之后。
  • 唯一例外是会跳过对 true/0 的调用。这允许 goal_expansion/2 把目标转换为 true，同时保留这个优化。
  • 如果头参数没有被使用，体内合一仍会移动到头部。在这种情况下，反编译器不会反转该过程。因此，p(X) :- X = a. 与 p(a). 完全等价。
  • 目前，无论 Prolog 标志 optimise 如何设置，都会启用该优化。由于这个优化会妨碍源码级调试，这一点可能并不理想。另一方面，该优化会影响确定性，而我们并不希望确定性取决于是否启用优化。

索引与可移植性

Prolog 实现的基线功能是在第一个参数上按常量和函子（name/arity）建立索引。如果程序需要广泛可移植性，你必须以此为假设。通常可以通过使用 term_hash/2 或 term_hash/4，并且/或者维护同一谓词的多个副本来实现：这些副本使用重新排序的参数，并配合包装器更新所有实现（assert/retract），以及选择合适的实现（查询）。

YAP 提供完整的 JIT 索引，包括对复合项参数建立索引。YAP 的索引机制是增强 SWI-Prolog 索引能力的灵感来源。