PLDI 2014 Artifact Evaluation for Adapton: Composable, Demand-Driven Incremental Computation

Table of contents

Instructions to run Adapton micro-benchmarks

  1. Download (412MB) and unzip it.
  2. Open adapton.vmwarevm in VMWare.
  3. Either follow the instructions below or at the login screen:
    1. Log in with username "ubuntu" and password "ubuntu"
      • It may be more convenient to SSH into the virtual machine as explained at the login screen.
    2. Run the Adapton benchmarks:
      • cd ~/adapton
      • make small-pldi2014-benchmarks
      This will take a couple of hours to run, and will generate several tables of results similar to Table 1 in the paper (or Table 2 in the supplemental report). Alternatively:
      • make tiny-pldi2014-benchmarks will take a few minutes to run
      • make pldi2014-benchmarks will take about a day to run (the VM configuration will need to be modified to provide 8 cores and 16GB of memory for this to run successfully)
      The absolute magnitude of the results (running time, memory usage, overhead/speed-up) between the above commands will differ, of course. However, the relative results, i.e., whether Adapton is faster or not compared to other implementations, should be mostly consistent between the above commands.
    3. The results are generated as nested subdirectories in Results/BenchmarkAdapton, e.g.:
      • adapton/Results/BenchmarkAdapton
        • small-pldi2014-2014-02-09-05-03-29
          • batch
            • 2014-02-09-05-15-12 monotonic
            • ...
            • summary
              • index.html
              • summary.txt
          • lazy
            • ...
          • swap
            • ...
          • switch
            • ...
        • small-pldi2014-2014-02-09-06-12-55
        • ...
      In particular, each of batch, lazy, swap, and switch contains a subdirectory named summary with two files:
      A HTML file containing a table summarizing the running time, memory usage, as well as overhead and speed-up of Adapton and EagerTotalOrder over EagerNonInc and LazyNonInc. To view this, copy the directory to your host machine and open in your favorite browser (tested in Firefox and Safari), e.g.:
      • yourhostmachine% scp -r ubuntu@vmipaddress:adapton/Results .
      • yourhostmachine% firefox Results/BenchmarkAdapton/small-pldi2014-2014-02-09-05-03-29/lazy/summary/index.html
      A text-only version of the above (view using less -S summary.txt).
      An example of these tables is shown below:
      task input # take # EagerNonInc LazyNonInc Adapton EagerTotalOrder
      time max-heap time max-heap from-scratch incremental from-scratch incremental
      overhead max-heap speed-up max-heap overhead max-heap speed-up max-heap
      seconds bytes seconds bytes EagerNonInc LazyNonInc bytes EagerNonInc LazyNonInc bytes EagerNonInc LazyNonInc bytes EagerNonInc LazyNonInc bytes
      exptree 100000 1 12.9e-3 15.2e+6 24.1e-3 16.3e+6 131e+0 69.9e+0 173e+6 63.9e+0 120e+0 175e+6 76.9e+0 41.1e+0 169e+6 161e+0 301e+0 169e+6
      filter 100000 100001 52e-3 15.7e+6 41.9e-3 15.7e+6 11.4e+0 14.1e+0 92.9e+6 3.19e+0 2.57e+0 162e+6 10.7e+0 13.3e+0 102e+6 8.5e+0 6.85e+0 135e+6
      map 100000 100001 82.5e-3 22.8e+6 73.2e-3 23.8e+6 7.46e+0 8.41e+0 96.9e+6 3.21e+0 2.85e+0 166e+6 6.75e+0 7.6e+0 102e+6 8.3e+0 7.37e+0 169e+6
      tfold(min) 100000 1 97.3e-3 23.7e+6 90.1e-3 20.7e+6 14.3e+0 15.4e+0 161e+6 1.4e+3 1.29e+3 163e+6 11.8e+0 12.8e+0 169e+6 881e+0 816e+0 169e+6
      tfold(sum) 100000 1 104e-3 24.8e+6 97.5e-3 20.7e+6 13.4e+0 14.3e+0 163e+6 674e+0 630e+0 163e+6 11e+0 11.7e+0 169e+6 493e+0 461e+0 169e+6
      • input # refers to the size of the input (number of elements in a list or leaf nodes in tree).
      • take # refers to the (maximum) size of the output that is demanded (number of elements in the output list; note that some tasks produce only 1 output element).
      • max-heap refers to the maximum heap size as reported by OCaml's garbage collector.
      • from-scratch refers to the initial computation, before any updates are made.
      • incremental refers to (the average over all) subsequent incremental computations.
      • overhead is computed as X from-scratch time/*NonInc time, where X is Adapton or EagerTotalOrder.
      • speedup is computed as *NonInc time/X incremental time, where X is Adapton or EagerTotalOrder.
      • Cells highlighted in gray (marked with * in the text version) indicate the implementation that has a highest speed-up or uses the least memory for a particular task.
      Table 1 of the paper is based the incremental speed-up columns.

Instructions to run Adapton Spread Sheet (AS2) demo

  1. Compile and run the native binary for the application interactively as follows:
    % cd ~/adapton
    % make as2
    % ./_product/runas2.native
    The interactive command help. (with terminating period) will cause the system to display a summary of its other commands, and its formula syntax.
  2. The application can be configured and controlled from the command line. To see a summary of command-line options:
    % ./_product/runas2.native --help
  3. The application offers different implementations of the Adapton primitives for comparison purposes. The command line switch --adapton-module controls which implementation is used:
    % ./_product/runas2.native --adapton-module impl
    Where impl is one of: In Section 6.2 of the paper, the two implementations Adapton and EagerTotalOrder are compared with the non-incremental baseline EagerNonInc:
    % ./_product/runas2.native --adapton-module Adapton
    % ./_product/runas2.native --adapton-module EagerTotalOrder
    % ./_product/runas2.native --adapton-module EagerNonInc
  4. The following test script works for all versions, and can be entered interactively:
    scrambled; goto 10!a1 ; print ; repeat 5 do scramble1 ; print done .
  5. Alternatively, this script can be invoked at the command-line as follows:
    % ./_product/runas2.native --num-changes 5 --stats-test 10
    In this mode, the program prints statistics and appends this information to the file as2-stats.out, then exits. The numbers 5 and 10 control the number of changes and total number of sheets, respectively. Of course, they can be changed to other integers.