Prolog的按需索引与动态编译框架：原理、实现与性能评估

# Prolog的按需索引与动态编译框架：原理、实现与性能评估 ## 1. Prolog子句的按需索引 ### 1.1 索引表回收步骤 在处理索引表时，需要进行以下操作来回收空间： 1. 等待表未被使用，即没有任何地方指向该表。 2. 遍历表并释放其持有的所有引用。 3. 物理回收空间。 ### 1.2 XXX和YAP中的实现 #### XXX的实现 - 编译器使用启发式方法确定最佳索引参数（不一定是第一个参数），并使用`switch on *`指令完成此任务。 - 为其他适合按需索引的参数静态生成`dindex on constant`指令。目前，如果一个参数在所有子句中仅包含常量或仅包含结构符号，则认为它是合适的候选参数。 - XXX仅使用`dindex on constant`和`dindex on structure`指令，从不使用`dindex on term`。并且，XXX不在结构符号内部执行按需索引。 - 对于动态谓词，仅当它们由Datalog事实组成时才使用按需索引。如果断言了一个非Datalog事实的子句，则会删除该谓词的所有动态创建的索引表，并且`dindex on constant`指令将变为空操作。用户可以使用选项禁用编译代码中的按需索引。 #### YAP的实现 - YAP从版本5开始实现按需索引，当前实现支持静态代码、动态代码和内部数据库。 - 与之前介绍的算法不同，YAP的所有索引代码都是按需生成的。因此，YAP不能假设`dindex on *`指令后面跟着`try-retry-trust`链。默认情况下，YAP必须在整个谓词中搜索与索引代码当前位置匹配的子句。对于较大的关系，每次索引扩展都这样做效率非常低，在这种情况下，YAP会在每个`dindex on *`节点维护一个匹配子句列表。 - YAP对动态谓词的索引与静态索引遵循非常相似的算法，关键思想是索引树中的大多数节点必须单独分配，以便它们可以独立增长或收缩。YAP可以对某些子句包含无约束变量的参数进行索引，但仅适用于静态谓词，因为在动态代码中这样做会使LU语义的支持变得复杂。YAP使用术语JITI（Just-In-Time Indexing）来指代按需索引。 ### 1.3 性能评估 #### 1.3.1 按需索引无效时的性能 在某些程序中，按需索引可能不会触发，或者即使触发也可能除了运行时索引构建的开销外没有其他效果。为了测量这种开销，使用了一些表处理基准测试，因为它们规模小且易于理解，并且对于JITI来说是不利情况。表1(a)展示了一些基准测试在第一种参数索引和按需索引下的性能（时间以毫秒为单位）。 | 基准测试 | YAP - 1st | YAP - JITI | XXX - 1st | XXX - JITI | | --- | --- | --- | --- | --- | | tc l io (8000) | 13 | 14 | 4 | 4 | | tc r io (2000) | 1445 | 1469 | 614 | 615 | | tc d io (400) | 3208 | 3260 | 2338 | 2300 | | tc l oo (2000) | 3935 | 3987 | 2026 | 2105 | | tc r oo (2000) | 2841 | 2952 | 1502 | 1512 | | tc d oo (400) | 3735 | 3805 | 4976 | 4978 | | compress | 3614 | 3595 | 2875 | 2848 | 从表中可以看出，即使按需索引无效，运行时开销也处于噪声水平，大多不易察觉。 #### 1.3.2 按需索引有效时的性能 当按需索引有效时，它可以显著提高运行时性能。使用了以下程序和应用进行测试： - sg cyl：在24 × 24 × 2圆柱体上的相同生成数据库基准测试，发出开放查询。 - muta：一个计算密集型应用，大多数谓词是有意定义的。 - pta：一个实现Andersen指向分析的表逻辑程序，将一个中等规模的命令式程序编码为一组事实（约16,000个），并使用规则编码感兴趣的属性，通过这些规则的闭包确定程序属性。 - tea：Andersen指向分析的另一种实现，分析的程序是javac基准测试，编码在一个包含411,696个事实（总共62,759,581字节）的文件中，其编译超出了XXX编译器（无JITI）的限制，因此仅在YAP中运行此基准测试。 表1(b)展示了这些应用在第一种参数索引和按需索引下的性能（时间以毫秒为单位）以及加速比。 | 基准测试 | YAP - 1st | YAP - JITI | YAP - 比率 | XXX - 1st | XXX - JITI | XXX - 比率 | | --- | --- | --- | --- | --- | --- | --- | | sg cyl | 2,864 | 24 | 119× | 2,390 | 28 | 85× | | muta | 30,057 | 16,782 | 1.79× | 26,314 | 21,574 | 1.22× | | pta | 5,131 | 188 | 27× | 4,442 | 279 | 16× | | tea | 1,478,813 | 54,616 | 27× | — | — | — | 可以看出，按需索引显著提高了这些应用的性能。在muta中，由于大部分时间花在递归谓词上，YAP的加速比仅为79%，XXX的加速比为22%。其余基准测试的执行速度提高了数倍（从