Lib.rs

› 算法 › Adapton
#增量 #记忆化 #增量计算 #按需驱动 #性能测试 #依赖图 #自适应

nightly bin+lib adapton-lab

Adapton 的测试和性能评估套件

作者：Matthew Hammer

1 个不稳定版本

使用旧的 Rust 2015

0.1.0 2017年5月2日

#1140 在 算法

MPL-2.0 许可证

120KB
2.5K SLoC

Adapton Lab：通用测试和评估

快速入门

Adapton 使用 Rust 语言的最新版本和运行时。要使用它，请安装 rust nightly（编译器和运行时的最新版本）。更好的是，安装 rustup.rs 并按照其说明切换到 nightly 频道。

git clone https://github.com/cuplv/adapton-lab.rust
cd adapton-lab.rust
cargo run

此脚本将调用 Adapton Lab 的默认行为，该行为包括运行测试套件以测试 Adapton 的 dev 分支。下面，我们将介绍更多内容、背景信息、有关命令行参数的详细信息以及如何扩展测试套件的指南。

简介

本文件描述了 Adapton Laboratory，或简称 Adapton Lab。Adapton Lab 为测试和评估测试套件提供了一个通用（可重用）的 harness，该测试套件针对各种 Adapton 应用层进行测试

  • Adapton 引擎:
    • DCG：基于需求计算图（Demanded-Computation Graph）的缓存，具有通用变更传播。
    • Naive：无缓存。
  • Adapton 集合库：序列、有限映射、集合、图等。
  • 集合库上的有趣算法，包括
    • 标准图算法
    • 计算几何算法
    • 程序静态分析

作为 Rust 库，Adapton 提供了数据结构集合和运行时库，用于编写通用增量计算。在最高级别，这种方法由程序员编写函数式程序，这些程序在归纳、持久结构上运行，具体为

  • 列表,
  • 表示 序列 的平衡树
  • 表示 有限映射、有限集合 和 图 的哈希试
  • 上述结构的归纳（按需驱动）版本。

对增量算法的Adapton方法进行第一次近似，包括在不变的输入上编写一个函数式（贪婪或惰性）程序，生成一个不变的输出。进一步细化这个近似，程序员还使用显式抽象来对（显式）名义化缓存进行操作，这会将一个一等、动态作用域的名称与每个动态分配关联起来。

背景：名义化缓存

未来，我们希望将名义化缓存隐式化；目前，只有显式技术存在。（旁白：过去对隐式自适应计算的研究仅关注使所谓的可修改引用的使用隐式化；这是一个互补且正交的问题，与隐式选择名义化缓存的名字策略无关）。

名义化Adapton给出了名义化缓存的第一个操作语义，并包括了初步的编码列表、序列、映射和集合并（OOPSLA 2015）。这些集合受到了Pugh和Teitelbaum关于通过函数缓存进行增量计算的研究（POPL 1989）的强烈启发。名义化Adapton用显式方法替换了结构命名策略（即hash-consing），允许命令式缓存效果。它为使用这些集合的计算提出了几种命名策略。一个中心问题是编写算法，以避免无意中覆盖其缓存，导致意外的振荡或反馈；这种影响偏离了纯函数行为，这影响了程序员对动态增量行为的推理。

类型化（名义化）Adapton为名义化缓存的存储命名效应提供了一个有用的静态近似，使得可以编写通用库代码，同时避免无意中的振荡和反馈。与用于强制名义结构的其他类型系统不同，类型化Adapton使用类型和效果系统来强制名义化缓存的动态作用域是一次写入，即函数式，而不是命令式或关系式的。其他名义类型系统侧重于强制一等绑定器的词法作用域；这个问题及其解决方案与强制名义化缓存的名义结构是正交的。

Rust尚未实现类型化Adapton，只实现名义化Adapton。换句话说，可能会滥用Rust接口并偏离类型化Adapton允许的内容。这个测试框架的一个目的就是确保当程序员期望它们这样做时，算法遵循从头开始的致性。

参考文献

Adapton论文:

其他论文:

  • 通过函数缓存进行增量计算
    Bill Pugh和Tim Teitelbaum。 POPL 1989。
    • 结构化缓存，针对hash-consed，纯函数数据结构
    • 结构化缓存函数调用，针对纯计算

定义从头开始一致性的交换图

考虑到测试和性能评估，Adapton实验室引入了几种可以通用实例化的数据结构和计算。这些元素可以通过以下图表联系起来。

  • Input_i：第i个输入（一个数据结构）。在通用方面，这包括输入生成和编辑的抽象概念。我们使用Rust中的Edit和Generate特质来抽象这些操作。
  • Output_i：第i个输出（一个数据结构）。为了验证增量输出与非增量输出的有效性（见下图），我们比较输出类型以确定它们的相等性。
  • Compute：将第i个输入与第i个输出相关的计算（一个计算）。我们使用Compute特质在Rust中捕获这个抽象。我们使用相同的计算来定义增量和非增量算法。
  • Edit_i：与第i个输入到第i+1个输入（一个计算）以及第i个输出到第i+1个输出（一个计算）相关的输入变化（也称为输入编辑或增量）。我们只需要保证每种输出类型的值可以进行比较。
  • Update_i：与第i+1个输入到第i+1个输出相关的输出变化，在过程中重用Output_i从Input_i的计算，使用其DCG和变化传播。

请注意，尽管输入和输出都是数据结构，但它们之间的关系都是计算：输入通过计算Edit_1进行修改，而为了计算Output_2，系统有两个选择

  • 朴素：在Input_2上运行Compute，（完全）从Input_2计算Output_2。 这种关系在图中显示为水平边。

  • DCG：重用Compute在Output_1上的跟踪计算，通过DCG的变化传播将Output_1转换为Output_2。这种关系在图中显示为图的右侧的垂直边。

从头开始一致性是一个元理论属性，它表明DCG方法在语义上与朴素方法等价。也就是说，这是下面图中交换的性质。

图例。假设我们考虑从1到4的i，以图示这些关系

        |
        |  Generate
       \|/ 
        `  
      Input_1 --> Compute --> Output_1
        |                       | 
        |  Edit_1               |   Update_1
       \|/                     \|/
        `                       ` 
      Input_2 --> Compute --> Output_2
        |                       | 
        |  Edit_2               |   Update_2
       \|/                     \|/
        `                       ` 
      Input_3 --> Compute --> Output_3
        |                       | 
        |  Edit_3               |   Update_3
       \|/                     \|/
        `                       ` 
      Input_4 --> Compute --> Output_4

生成和编辑参数

要获取Adapton Lab的命令行选项的快速列表，请使用-h

cargo run -- -h

Adapton Lab以通用方式生成和编辑输入（如图中左侧的垂直边）。

这些操作通过实验室用户通过几个生成参数（也控制编辑）进行调整。一个实现选择如何解释这些参数，以下是一些指导原则

   -a, --artfreq <artfreq>      for the Editor: the frequency of articulations, measured in non-nominal constructors.
   -b, --batch <batch>          for the Editor: the number of edits that the Editor performs at once.
   -d, --demand <demand>        for the Archivist: the number of output elements to demand; only relevant for lazy Archivists.
   -L, --lab <labname>          determines the Editor and the Archivist, from the lab catalog
   -l, --loopc <loopc>          for the Editor and Archivist: the loop count of edit-and-compute.
   -s, --size <size>            for the Editor: the initial input size generated by the Editor.
       --validate <validate>    a boolean indicating whether to validate the output; the default is true.

测试

Rust尚未实现类型化的Adapton，只实现了命名Adapton。换句话说，有可能误用Rust接口并偏离类型化Adapton允许的内容。这些偏差可能导致运行时类型错误、内存故障和堆栈溢出。

这个测试框架的一个目的是测试程序Compute在上述图中是否交换：即朴素的重计算始终与命名记忆化的行为匹配。

要可视化这种行为，尝试这个命令

cargo run -- --run-viz

（也：如果未向Adapton Lab提供选项，则默认为此行为。）

命令完成后，检查这个生成的HTML目录

open lab-results/index.html

评估

在测试Compute并验证足够的测试数据后，我们想要衡量在运行Compute和利用命名记忆化之间的性能差异。

要在较大的输入大小上运行计时测量，请尝试此命令

cargo run -- --run-bench

完成后，检查这个生成的HTML目录

open lab-results/index.html

依赖关系

~1.5MB
~26K SLoC