理论计算机科学电子笔记148（2006）127-154www.elsevier.com/locate/entcs自调整计算Umut Acar1 Guy Blelloch2 Matthias Blume1Robert Harper2 Kanat Tangwongsan2摘要我们提出了一个标准ML库，用于编写自动调整其数据变化的程序。图书馆结合了可修改的参考和备忘录，以实现有效的更新。我们描述了一个实现的库，并将其应用到维护一组动态变化的点的凸包的问题。 我们的实验表明，库的容量很小，自我调整程序可以调整到比从头开始重新计算快三个数量级的小变化。实现依赖于可以由模态类型系统强制执行的不变量。我们使用现有的语言，抽象接口的可修改的引用和memoization，确保相同的安全属性，而不使用模态类型。然而，用于备忘录化的接口并不能很好地扩展，这表明基于语言的方法毕竟是更可取的。关键词：增量计算，选择记忆，变化传播，计算几何，凸壳，快壳在许多应用领域中，如仿真系统、机器人、语言环境，计算必须适应外部数据的变化。这种能力可以实现一种全新的计算类别，这在以前是不可能的[7，8]，并通过利用大多数变化都很小的事实来实时执行复杂的计算。有效地处理程序输入的微小变化的问题在程序设计语言界得到了广泛的研究。这被称为增量计算。其目标是设计通用的技术来编写可以适应变化的程序。其中两个关键技术是动态依赖图和动态依赖图。1{umut，blume}@t t i-c。奥尔湾我是说，我是说，我是说。2{blelloch，rwh，ktangwo n}@cs. cmu。ed u。 Ca rnegieMellonUiverity.1571-0661 © 2006 Elsevier B. V.在CC BY-NC-ND许可下开放访问。doi：10.1016/j.entcs.2005.11.043128联合Acar等人/理论计算机科学电子笔记148（2006）127臭氧化。动态依赖图（DDG）[2，3]通过启用更改传播来更新依赖关系，从而推广了静态依赖图[10记忆化[20，14，13，3]依赖于记住函数调用的结果，并在可能的情况下重用它们。虽然这两种技术都是通用的，但它们只对某些类型的输入变化和某些类型的计算产生在以前的工作[2，3]中，我们指出了每种技术的局限性，并声称它们可以结合起来，以大大提高性能。在本文中，我们提出了一个SML库，结合DDG和备忘录。使用该库，程序员可以通过对代码进行微小的更改，将普通的纯函数程序转换为自调整程序自我调整程序会调整以适应任何对其数据的外部变化。当自调整程序执行时，运行时系统构建表示计算和数据之间的关系的动态依赖图（或DDG）。节点表示数据，边表示它们之间的关系。每个边都标记有一个闭包，该闭包确定如何从其源计算其目的地。在自调整程序完成其执行之后，用户可以改变任何计算数据（例如，输入）并通过执行变化传播来更新输出。可以重复该改变和传播步骤。变化传播算法通过重新执行其源已经改变的边的闭包来模仿从头开始执行来更新计算。当重新执行一个闭包时，算法可以通过备忘录化来重用该闭包的先前执行所创建的边和节点。当重新执行边时，算法丢弃属于先前执行的未使用的边和节点，因为这些元素不再属于计算。为了证明我们的方法的有效性，我们考虑了计算几何的应用[9]。我们实现了快速壳算法计算凸壳，并进行了实验评估。我们的实验表明，库的开销很小，并且自我调整程序可以比从头开始重新计算更快地适应变化。对于快速外壳算法，我们的实验表明，一个近线性的时间间隔之间的变化传播和从头开始重新计算。对于我们考虑的输入大小，更改传播可以是三个数量级。比从头开始重新计算更快。联合Acar等人/理论计算机科学电子笔记148（2006）1271291图书馆我们提出了一个结合了可修改引用和记忆的库。该库确保可修改引用的安全使用，但它不能确保记忆化原语的安全使用。在第4节中，我们介绍了确保记忆化安全使用的组合子。原则上，用于记忆化的组合子可以与本节中考虑的库合并。但是，由于第4节中讨论的可伸缩性问题，我们没有这样做。首先，我们对底层模型进行了高层次的描述（完整的描述超出了本文的范围）。然后，我们描述了库的接口，并提出了完整的实现的核心代码1.1底层模型更改传播必须检测数据的更改，以便可以重新执行处理这些数据的计算。跟踪变化的参照系称为可修改参照。我们经常将可修改的引用称为可修改的引用。一个可修改的可以被认为是一个具有固定地址但内容可变的内存位置。我们把保证产生固定结果的计算称为稳定的，而把可能产生可变数据的其他计算称为可变的。每个可变计算的结果都记录在一个modifiable中，只有可变计算可以读取modifiable的内容在传播过程中，当有挂起的更改时，实现会根据r的原始值，可能会记录（对r中包含的值）的更改。注意r本身，即，包含可能更改的值的位置的地址保持固定。从一个已修改的读取开始重新执行可变计算的整个剩余部分可能非常低效，因为它的重要部分可能并不真正依赖于已修改的值。我们使用计算的记忆来动态地检测这种情况：当一个函数被调用时，与前一次执行过程中完全相同的参数，那么对应于这个函数调用的计算部分可以被重用。然而，由于备忘录化的计算可能包含由挂起的更改所影响的读操作，因此必须将这些更改传播到成功的备忘录查找的结果中。因此，在变更传播和备忘录化之间存在一种对偶形式：变更传播需要跳过一部分计算，130联合Acar等人/理论计算机科学电子笔记148（2006）127Fig. 1. 交替重复使用和重复执行“划分”出需要重新执行的子间隔。记忆化需要重新执行计算的一部分，并“划分”出要跳过的间隔。一个简单的例子如图1所示：更改传播尝试尽可能多地重用整个计算（间隔A），但必须重新执行其中的两个部分（间隔B和C），因为这些部分是由一个不确定的读操作控制的。在B的重新执行期间，通过记忆化发现可重用部分（间隔D）。类似地，E可以在C的重新执行期间被重新使用。然而，有一个改变，即a在D内执行读操作，这迫使嵌套在D内的子间隔F重新执行。通过将记忆化和更改传播协同组合到自适应记忆化中，我们还可以放宽记忆化的重用规则。这种松弛使得即使当计算所依赖的值不同时也能够重用计算。考虑一个函数调用f（X，y），其中X表示除y之外的所有参数。如果我们安排y从可修改的rX（其中rX本身只依赖于X）中读取，而不是作为参数传递，那么y的值就不会出现在memo-lookup中。相反，函数调用的先前执行-即使是不同的y值-可以通过更改传播重用并调整为新的y值。请注意，这与部分求值不同，因为更改传播将利用y的新旧值之间的相似性。联合Acar等人/理论计算机科学电子笔记148（2006）127131签名框值=签名型指数αtvalinit： unit→ unitval new：α→αtval eq：αt *αt → boolvalvalueOf：valindexOf：valfromInt：端结构箱：αt→ααt→ indexint→ int tBOXED VALUE = struct.端signature COMBINATORS =签名eqtypeα modreftypeα ccval modref：αcc→α modrefval write：（α*α→ bool）→α→αcc valread：βmodref *（β→αcc）→αccval mkLift：（α*α→ bool）→（框索引列表 *α）→（αmodref→β）→βval mkLiftCC：（（α*α→ bool）*（β*β→ bool））→（框索引列表 *α）→（αmodref→β cc）→βcc（** Meta Operations**）val init：unit→unitval change：（α*α→ bool）→αmodref→α→ unit valderef：αmodref →αval propagate：unit→ unitend结构C：COMBINATORS =结构.端图二. 装箱值和组合子的签名。1.2图书馆界面图2显示了库的接口BOXED VALUE模块提供对装箱值进行操作的功能。我们使用盒子（或标记值）来支持恒定时间的相等性测试，这是高效记忆所必需的[3]。新函数通过将唯一整数索引与给定值关联来创建装箱值。eq函数通过比较两个装箱值的索引来比较它们。valueOf和indexOf函数分别返回装箱值的值和索引。装箱值模块可以用用于为类型创建装箱值的函数来扩展。这种类型特定的函数必须与底层类型的相等性相一致。例如，函数fromInt可以将索引i分配给integeri。132联合Acar等人/理论计算机科学电子笔记148（2006）127COMBINATORS模块定义了可修改的引用和可变的计算。每次执行αcc类型的可变计算都从创建一个新的αmodref类型的可修改对象开始。可修改项写在计算结束时。 在执行期间，引用永远不会显式。相反，它是以一种强烈地让人想起一元计算的方式“在幕后”进行的任何非平凡的可变计算都会读取一个或多个其他可变项，并根据读取的值执行计算。表示可变计算的αcc类型的值使用write、read和mkLiftCC构造。modref 函 数 在 将 新 生 成 的 modifiable 作 为 结 果 返 回 之 前 ， 对 该modifiable执行给定的write函数创建了一个简单的计算，它只是将给定的值写入底层的modifiable。为了避免不必要的传播，在写入时使用 提 供 的 相 等 函 数 比 较 读 组 合 子 ， 我 们 将 在 fix 表示 法将 其 称 为Q→，它与读取值的接收器一起使用一个不可读组合子的结果是一个包含从可修改对象读取的过程的计算，一个基于结果值的计算，以及一个由另一个可修改计算表示的延续。计算和延拓由接收器的主体和结果给出。函数mkLift和mkLiftCC处理自适应记忆，即基于部分匹配函数参数的使用普通的参数化，只要整个参数列表没有精确匹配，则对函数调用的备忘录表查找将失败。如上所述，自适应记忆化背后的想法是区分严格和非严格参数，并仅基于严格参数进行记忆化。通过在memo表中存储计算（而不仅仅是返回值），然后可以使用更改传播机制将成功的查找调整为非严格参数中的任何更改。由于更改传播依赖于对可修改对象的读取操作，因此记忆化函数必须通过此类可修改对象访问其非严格参数。memo表仅由原始参数列表的严格部分索引，记住为非严格参数预留的可修改参数以及memoized计算。给定参数列表的严格部分，提升操作将αmodref→β类型的函数映射到α→β类型的函数，其中α是非严格参数的类型。 3我们的mkLift和mkLiftCC组合子从适当的选择中为普通和可变的计算创建提升操作。3在实际库中，参数以不同的顺序出现，以使实际代码更方便地习惯使用接口。联合Acar等人/理论计算机科学电子笔记148（2006）127133为所涉及的类型设置相等谓词。参数列表的严格部分由索引列表表示，假设值和索引之间是1 - 1映射，例如：，即由BOXED VALUE接口提供的值。这里没有显示，我们的库还包含mkLift2，mkLiftCC2，mkLift3，mkLiftCC3等，以支持多个非严格参数。当它的memo表查找失败时，提升的函数创建包含其非严格参数的新modi- ables，执行其主体，并将计算和modi-ables存储到memo表中。计算通过记录它们的返回值和使用时间戳的动态依赖图（DDG）的表示来存储[2]。一个成功的备忘录查找发现修改和计算。然后，提升的函数将其当前的非严格参数写入其各自的modifiable中，并让更改传播调整计算以产生更改。程序员有责任确保所有的提升函数应用程序都能准确地指定严格和非严格变量。为了正确性，需要将记忆化表达式的所有自由变量指定为严格或非严格。将变量分类为严格或非严格并不影响正确性，而只是影响性能。在以前的工作[3]中，我们提出了选择性记忆技术，以基于分支的安全方式记忆表达式。COMBINATORS 模 块 还 提 供 Meta 操 作 ， 用 于 检 查 和 更 改 存 储 在modifiables中的值，并执行更改传播。修改功能类似于写功能。它将modifiable的底层值更改为一个新值-这是作为一个副作用实现的。propagate函数运行变化传播算法。更改传播根据自上次执行或上次更改传播以来发出的更改更新计算。Meta操作应该只在顶层使用--只有在程序内部不使用元操作的情况下，库才能保证正确的行为。1.3执行附录A给出了实现该库的代码。该实现由以下模块组成：框、组合子、备忘表、可修改项、订单维护数据结构和优先级队列。我们给出了由modifiables和combinators组成的库的核心部分的完整代码。134联合Acar等人/理论计算机科学电子笔记148（2006）1272自调整编程本节描述如何使用第1节中介绍的库编写自调整程序。作为例子，我们考虑一个从列表中过滤元素的函数和一个用二元运算符组合列表中的值的函数。第3节描述了如何使用这些函数实现快速外壳算法的自调整版本。2.1可调列表图3显示了实现可修改列表的模块的签名和代码Modifiable列表与普通列表类似，不同之处在于可修改列表单元格存储在可修改对象内部。可修改列表允许用户通过更改Meta操作更改存储在尾部元素中的值来更改其内容。可修改列表库提供了函数write、lengthLessThan、eq、filter和combine。eq函数测试两个列表的浅相等性。写函数专门用于可修改列表的COMBINATOR模块的写 lengthLessThan函数测试列表是否短于给定值。这个函数很容易实现，因此我们省略了代码。滤波器和组合函数将在以下部分中讨论。2.2转型程序员可以分两步把一个普通程序变成一个自调整程序。第一步通过将值放入可修改的变量中使程序自适应;这在以前的工作中有详细描述[2]。第二步添加记忆。为了最大限度地重用结果，应该尽可能细粒度地应用备忘录化。但是，如果许多记忆化计算共享同一个密钥，则性能会有所提高。程序员可以通过确保每个memoized函数调用都由其严格参数的值唯一例如，考虑过滤器功能。图4显示了普通滤波器的代码（左）和它的自调整版本（右）。该函数接受一个测试函数f和一个列表l，并返回f为真的元素的列表。转换的第一步涉及将输入列表更改为可修改列表，并适当地放置modref，read，write函数[2]。在第二步中，我们通过考虑滤波器的两个分支来记忆滤波器。由于NIL分支执行的是琐碎的工作，因此不需要记录。对于CONS分支，我们使用mkLift和memoize创建一个提升操作符联合Acar等人/理论计算机科学电子笔记148（2006）127135过滤器：（αBox.t→bool）→（αBox.t ML.t）→（αBox.t列表）funfilter f l =letvallift= C. mk LiftML.eqfun filter M c=案例CML.NIL ML.write ML.NIL|ML.CONS（h，t）tQ<$→（fnct）提升（[Box.indexOfh]，ct）（fnt如果（fh），则ML.write（ML.CONS（h，C.modref（tQ<$→filterM）elsetQ<$→filterM））在C.modref（lQ<$→filterM）结束filter：（αBox.t→bool）→（αBox.tlist）→（αBox.tlist）funfilter f l=让fun filter M c =case c ofnil|h：：tif（fh）then（CONS（h，filterM t））else filterMtin filterMl endsignature MOD LIST =签名数据类型α modcell = NIL|（α * α modcell C.modref）型α t = αmodcell C.modref的CONSval eq：αBox.t modcell *α Box.t modcell→ boolval write：αBox.t modcell→α Box.t modcell C.ccval lengthLessThan：int→（αt）→bool C.modrefval过滤器：（αBox.t→ bool）→αBox.t t→（αBox.t t）val combine：（αBox.t*αBox.t→αBox.t）→（αBox.t t→α Box.tC.modref end结构ML：MOD LIST = struct数据类型α modcell = NIL|（α * α modcell C.modref）型α t = αmodcell C.modref的CONSinfixQ<$→val op Q<$→=C.readfun eq（a，b）=（a，b）为（NIL，NIL）的情况为真|（ CONS（ha，ta），CONS（hb，tb））× Box.eq（ha，hb）和（ta=tb）|假的fun write c = C.write eq cfunlengthLessThan n l =.fun filter f l =.（* 参见图4*）有趣的组合binOp 1 =. （* 见图5 *）端图三. 可修改列表的签名和实现。见图4。 自动调节过滤器功能。分支，将h视为严格的，将t的内容（绑定到ct）视为非严格的。由于升降机操作员将ct放入另一个可调单元，因此需要额外读取136联合Acar等人/理论计算机科学电子笔记148（2006）1272.3程序稳定性即使任何纯函数程序都可以有条不紊地转换成一个自我调整的程序，但并不是所有的程序都能在变化下有效地执行。性能取决于程序在这种变化下的稳定性在其他工作[1，4]中，我们形式化了稳定性，并证明了一些算法的稳定性界稳定性的精确处理超出了本文的范围，但我们想给出一些直观的解释。一个程序的稳定性可以通过比较程序在变化发生之前和之后对输入的执行来确定。一个简单的稳定性标准是查看两次执行计算的所有数据之间的差异-大的差异意味着程序不稳定。更精确的分析是基于计算（执行）跟踪之间的距离，而不仅仅是数据。跟踪被定义为用严格参数标记的已执行提升函数的集合两个跟踪之间的距离是在两个跟踪的对称集合差中的函数调用的总执行时间-我们将这样的函数调用称为一个不确定的。如果在其他跟踪中没有具有相同严格参数的调用，则该调用是被拒绝的在某些条件下，可以证明跟踪距离和调整时间相等[1]。例如，可以通过示出在该变化下的跟踪距离是恒定的来示出过滤器例如，考虑对列表中的值求和。在遍历列表的同时保持所有访问过的元素的部分和的直接技术是不稳定的，因为删除/插入一个键将改变包括该键的所有部分和。我们现在提供一个稳定的解决方案，这个问题在一个更一般的设置。使用列表进行计算的一个基本原语是组合（combine，也称为组合）。fold或reduce）原语，该原语采用二元运算和列表，并通过应用二元运算来组合列表中的值。通过选择要应用的二进制运算，combine可以对列表执行各种为了给这个问题提供一个稳定的解决方案，我们采用了一种随机化的方法。这个想法是将输入列表分成越来越小的列表，直到列表是一个单例。要将列表减半，请选择列表中随机选择的子集，然后从列表中删除所选元素删除一个元素会将其值合并到左边最接近的幸存元素中。请注意，确定性方法（例如，删除每隔一个元素）是不稳定的，因为删除/插入元素可能会通过移动联合Acar等人/理论计算机科学电子笔记148（2006）127137fun combine binOp l=letfun halfListl=let val hash = Hash.new（）fun pairEqual（（b1，c1），（b2，c2））= Box.eq（b1，b2）andalso ML.eq（c1，c2）val writePair = C.writevallift = C.mkLiftCC（ML.eq，ML.eq）有趣的一半c =let fun sumRun（v，ML.NIL）= writePair（v，c）| sumRun（v，ML.CONS（h，t））= tQ<$→（fn ct t）if hash（Box.indexOf h）= 0 then writePair（binOp（v，h），ct）else sumRun（binOp（v，h），ct）如果CML.NIL ML.write ML.NIL| ML.CONS(h,t) ⇒ t Q ›→ (fn ct ⇒升力（[Box.indexOf h]，ct）（fnttQ<$<$→（fnctlet val p = C.modref（sumRun（h，ct））in pQ<$→（fn（v，端in C.modref（lQ<$→（fn c <$half c））endfun combl= ML.长度LessThan 2lQ›→（fnb如果b则lQ<$→（fn c<$ML.NIL的case c重新提升EmptyList|ML.CONS（h，）C.writeh）elsecomb（halfList l））在C.modref（comb l）末端图五.自调整列表组合。多个元素的位置由一个。图5显示了该方法的代码。我们假设给定的二元算子是结合的-交换性不是必需的。对于随机化，我们使用一个随机哈希函数[22]，它以一半的概率返回0或1作为示例，图6示出了计算列表[（a，0）、（b，8）、（c，5）、（d，3）、（e，2）、（g，9）、（h，6）、（i，4）、（j，1）]和[（a，0）、（b，8）、（c，5）、（d，3）、（e，2）、（f，7）、（g，9）、（h，6）、（i，4）、（j，1）]中的值的和的combine其通过值为7的键f来区分 钥匙是… ，k. 第二可以通过插入f并执行改变传播来从第一个开始获得执行。在更改传播过程中，只有阴影单元格将被重新计算。基于这种直觉，并通过建立与Skip List [19]的同构，可以证明删除/插入需要列表大小的对数时间[1]。138联合Acar等人/理论计算机科学电子笔记148（2006）127一F 7F 71J4我e 2D 3C 5B 8a0级1J4我15Ge 2D 313Ba0级一名38G20a 0 b 18G15I 5a 0 b 13D 3e 2G15I 4J 1a 0 b 8c 5 d 3e 2九国集团H 6I 4J 1一25G 20a0级B 25G 15我 5九国集团H 6见图6。 在插入值为7的键f之前和之后的每一轮列表。3自调整快速船体一组点的凸包是包围这些点的最小多边形。我们描述了一个自调整版本的快速船体算法计算凸包，并提出了一个实验评估。凸壳已经在普通和动态（增量）设置中进行了研究[12，18，17，16，9，5]。图8显示了快速外壳算法的代码，如第2.2节所述的转换技术所示。按照文献中的标准，我们只计算上壳-相同的算法可以通过使用稍微不同的距离函数来计算完整的壳。代码依赖于modifiable列表，一个提供由POINT签名指定的几何图元的模块-很容易给出此签名的实现。图7说明了算法是如何工作的。该算法首先计算输入中最左边（min）和最右边（max）的点，然后调用split（min，max）。split函数取直线（p1，p2）并过滤掉该直线下方的点。然后，该函数找到离直线最远的点max，并分别对直线（p1，max）和（max，p2）执行两次递归调用该算法使用combine函数来查找最左边和最右边的点，以及联合Acar等人/理论计算机科学电子笔记148（2006）127139(i)输入Maxp1−滤波器输出−p2(ii)找到极端，然后过滤MaxMax递归调用上船体最后上大厅见图7。 快速外壳算法离直线最远的点。为了评估我们的方法的有效性，我们对给定的输入I测量以下数量。• 运行非自调整快速船体的时间，表示为T检验器（I）。• 运行自调整快速船体的时间，TinitialRun（I）。• 删除/插入的平均时间，表示为TavgDelIns（I）：该量通过为每个元素运行删除-传播-插入-传播步骤并计算平均时间来测量。每一步都删除一个元素，运行更改传播，将元素插回，然后运行更改传播。图9显示了输入大小高达200 K（即，200000）。输入是随机生成的。大小为n的输入是通过从10n× 10n的正方形中随机选择n个点产生的。实验在2.7GHz Power Mac G5上运行，内存为4GB;机器运行Mac OS X。我们使用带有选项ram-slop 1的MLton [21]编译器。此选项指示编译器使用系统上的所有可用内存（但是，MLton最多只能分配两个100字节）。实验表明，该算法的开销TinitialRun（I）/Tverifier（I）不超过6，包括垃圾收集时间。当不包括垃圾收集的时间时，开销大约是两倍。在初始运行期间，垃圾收集时间与总执行时间的比率140联合Acar等人/理论计算机科学电子笔记148（2006）127签名POINT =sig类型tval toLeft：t *t→ boolval toRight：t *t→ boolval left Turn：t*t*t→ bool valdistToLine：t*t→t→realval fromCoordinates： real*real→tval toCoordinates：t→ real*real端结构P：POINT =结构.端结构QuickHull =结构结构C =梳状infixQ<$→valop Q<$→=C.readfunsplit（rp1，rp2，ps，hull） =letval lift= C.mkLiftCC2（ML.eq，ML.eq，ML.eq）fun splitM（p1，p2，ps，hull）=让fun选择p =P.distToLine（Box.valueOf p1，Box.valueOf p2）（Box.valueOfp）>0.0 vall= ML.filter select psinlQ<$→（fncl案例clML.NIL ML.write（ML.CONS（p1，hull））| ML.CONS(h,t) ⇒ hull Q ›→ (fn chull ⇒lift（[Box.indexOf p1，Box.indexOfp2]，cl，chull）（fn（l，hull））letval（v1，v2）=（Box.valueOf p1，Box.valueofp2）fun select（a，b）=if（P.distToLine（v1，v2）（Box.valueOfa）> P.distToLine（v1，v2）（Box.valueOf b））然后aelse bvalrmax = ML.combine selectlval rest= C.modref（rmaxQ <$→（fnmaxsplitM（max，p2，l，hull）inrmaxQ<$→（fnmaxsplitM（p1，max，l，rest））end）端in rp1Q<$$> →（fn p1<$rp2 Q<$$> →（fn p2<$splitM（p1，p2，ps，hull）endfun qhulll=C.modref（（ML.lengthLessThan 2l）Q›→（fn b）ifb then ML.write ML.NIL elseletfun select f（a，b）=if f（Box.valueOf a，Box.valueOf b）then a else bvalmin = ML.combine（select P.toLeft）lvalmax = ML.combine（selectP.toRight）lvalh =C.modref（maxQ<$→（fnmML.write（ML.CONS（m，C.modref（ML.writeML.NIL））in split（min，max，l，h）end））端见图8。 自调整快速船体。联合Acar等人/理论计算机科学电子笔记148（2006）127141应用+ G.C.时间申请时间时间正常（非自调整）运行4 30初始运行3.5253202.52 151.510150.501K20K40K60K80K100K120K140K160K180K 200K输入大小01K20K40K60K80K100K120K140K160K180K 200K输入大小0.002插入/删除的平均时间3500加速比=自擦除/变化传播0.00160.00123000250020000.000815000.0004100050001K20K40K60K80K 100K 120K 140K 160K 180K 200K输入大小01K20K40K60K80K100K120K140K160K180K 200K输入大小图9.第九条。为快速船体计时时间随着输入大小的增加而增加。在高峰期，垃圾收集时间占总执行时间的67%。其中一个原因可能是自调整程序在初始执行期间构建并存储动态依赖图和备忘录表。虽然垃圾收集的比率可能相对较高，但这对于初始运行来说问题不大，因为初始运行仅发生一次，计算通过更改传播来调整更改。左下角的图显示了通过更改传播进行删除/插入的平均时间。这个量随着输入大小的增加而缓慢增加。垃圾收集的时间不超过总执行时间的40%，即使是大的输入。它在输入大小约为64K时达到峰值。为了了解更改传播的速度，我们将更改传播的时间与从头开始重新计算的时间进行比较（通过运行快速外壳算法的普通非自适应实现）。我们将更改传播获得的加速定义为从头开始重新计算的时间除以插入或删除后执行更改传播的时间。图9显示了计算的平均加速比，即Tverifier（I）/TavgDelIns（I），有和没有垃圾收集时间的应用+ G.C. 时间应用时间非自调整运行时间应用+ G.C. 时间应用时间时间加速（应用+ G.C.）加速（应用程序）时间加速比142联合Acar等人/理论计算机科学电子笔记148（2006）127mfun f（x，y，z）= mif x<0然后让！yv=y返回g（yv）end否则让！zv= z in return h（zv）end实验表明，随着输入大小的增加，加速比增加到超过两千倍。4使用库到目前为止，我们已经考虑了一种设置，其中用于备忘录查找的键是完全显式的，让程序员完全控制并承担全部负担。当想要利用给定输入的仅部分对计算结果有贡献的事实时，该负担可能变得麻烦。因此，一种不同的（和互补的）技术是使用自动跟踪输入的相关部分的实现的选择性记忆。像自调整计算一样，选择性记忆对程序施加了限制。在以前的工作中，我们讨论了一种语言的设计，它具有可以在编译时强制执行这些约束的模态类型[3]。在这样的语言中，一个小程序片段可能是如下所示关键字mfun引入了一个memoizing函数。最初，它的所有参数（这里是x、y和z）都被认为是资源。在执行过程中，函数跟踪它如何使用其资源，并将此信息记录在称为分支的跟踪中。记忆是基于这个分支的。在这个例子中，f的调用不会同时依赖于y和z此外，y和z之间的决定仅仅基于x的符号;x因此，在计算f（-1，2，3）一次之后，调用f（-2，2，4）将导致成功的备忘录表查找。实际上被记忆化的计算部分由return下的表达式表示。为了便于记忆，每个记忆函数实例都有自己的memo表。该表的索引方式为返回时分支的值。分支描述了函数的执行路径，并记录了每个决策点的方向。此外，它还记录了通过读取资源（使用let！）.要做到这一点，代码必须具有这样的属性，即在expertation到达return时，函数必须为了实现这一点，return下的表达式不能提及（因此不能依赖于）任何资源。有了专门为此设计的语言，编译器可以很容易地相比之下，联合Acar等人/理论计算机科学电子笔记148（2006）127143α型资源val bang：α资源→αval mless：int resource * int→ bool resourceval mif：布尔资源 *（单位→β）*（单位→β）→β···val return：(unit→α）→αmif（mless（x，0），fn（）返回（fn（）返回 g（bang y））fn（）返回（fn（）返回 h（bang z））库必须依赖于其宿主语言的现有类型系统，在我们的例子中是SML。尝试对资源类型使用抽象构造函数是很有吸引力的，它只为其实例提供有限的一组操作下面是这样一个设计的尝试：上面的例子的主体可以呈现为：mif（mless（x，0），fn（）） let yv = bang y in return（fn（）） g（yv）end）fn（）让zv = bang z返回（fn（）让h（zv）end）不幸的是，这是一个错误的开始。 ML类型系统可以限制可应用的操作集，但它无法阻止仅仅提到变量。因此，它不会阻止任何人通过在return下对资源应用bang来错误地尽管如此，仍然有可能构建一个强制执行所需不变量的库。诀窍是避免命名资源，再次使用类似于一元编程的技术[6]。就像状态monad操作从位置到值的映射而不命名这个映射一样，我们将操作资源而不命名它们。选择性记忆可以很容易地与前面描述的思想结合起来：可修改的引用和更改传播。然而，为了在前面的工作中描述的模态类型系统的形式）。4.1记忆计算该库由用于构造备忘录计算的组合子组成（参见图10）。一个memo-computation 是一个类型为（α，ν，ρ）mc的抽象值c。它表示一个memoizing函数中的程序点，可以将其视为一个分隔的延续，直到相应的返回。的144联合Acar等人/理论计算机科学电子笔记148（2006）127类型e（α，ν，ρ）mc返回值： （α，ν，ν）mcvalDo： （ν→μ）*（α，μ，ρ）mc→（α，ν，ρ）mc对值： （（α*β）*γ，ν，ρ）mc→（α*（β*γ），ν，ρ）mcvalunpair： （α*（β*γ），ν，ρ）mc→（（α*β）*γ，ν，ρ）mc结果： （α*（α*β），ν，ρ）mc→（α*β，ν，ρ）mc值交换： （α*（β*γ），ν，ρ）mc→（β*（α*γ），ν，ρ）mc交换2： （α*（β*（γ*δ）），ν，ρ）mc→（α*（γ*（β*δ）），ν，ρ）mc值下降： （β，ν，ρ）mc→（α*β，ν，ρ）mcvalBang： （β，int*ν，ρ）mc->（int*β，ν，ρ）mc如果： （β，ν，ρ）mc*（β，ν，ρ）mc->（b 〇l*β，ν，ρ）mcval案例： （β，ν，ρ）mc*（（α*αlist）*β，ν，ρ）mc->（αlistt*β，ν，ρ）mcvalmemo：（α* unit，unit，ρ）mc ->α->ρ见图10。 一种用于记忆计算的延续可以访问类型α的资源和类型ν的非资源它最终产生一个ρ型结果。当需要返回一个值时，memoizing函数只是丢弃剩余的资源，并生成当前的累加器作为答案。累加器以某个常量（这里是单位）开始。资源对其价值的任何影响都作为分支的一部分进行监控和记录。如果我们忽略边效应的可能性，那么所有其他可能影响累加器状态的值对于记忆函数的任何给定实例都是不变的。因此，在执行备忘录查找时不需要考虑此值。根据所执行的计算，v可以实例化为任意类型。程序员使用Do组合子将计算指定为SML函数，将累加器转换为新累加器。使用Do指定的子计算需要记忆化。我们不能使用普通的SML函数对资源进行操作，因为这样做会“泄漏”资源，从而可能违反所需的不变量。另一种方法是让库提供对资源进行操作的组合子。由于我们希望能够同时处理多个资源，因此我们将多个资源组织成一个资源堆栈，并施加相应的约束，即α将被实例化为资源堆栈类型。资源栈类型是单位（表示没有资源）或τ*σ，其中τ是资源类型，σ是资源栈类型。可能的资源类型是装箱类型、资源类型对、类型bool和τ列表，其中τ是另一种资源类型。为了说明的简单性，我们假设int是唯一的装箱类型。第一组与资源相关的组合子用于操纵资源，联合Acar等人/理论计算机科学电子笔记148（2006
我的内容管理
展开
