Resources for “Control Theory for Principled Heap Sizing”

Authors: David R. White, Jeremy Singer, Jonathan M. Aitken, Richard E. Jones

Jonathan M. Aitken is at the University of Sheffield.

Richard E. Jones is at the University of Kent.


This paper proposed and demonstrated the use of a PID Controller to manage heap size within the Jikes RVM. We used a subset of the DaCapo 2006 MR2 and DaCapo 2009 Benchmarks as example workloads, excluding those that did not run reliably on the RVM. First, we ran tests to examine the normal behaviour of the Jikes heap resizing mechanism when executing these benchmarks. Then we enabled the PID controller and followed the Ziegler-Nichols method of tuning to determine suitable coefficients to be used for each benchmark (for deployment, we would choose a summary statistic of these coefficients).

To evaluate the PID Controller’s effectiveness, we compared it to the existing Jikes resizing mechanism, and a reimplementation of the HotSpot VM’s mechanism that we adapted to Jikes.

This webpage contains online resources designed to enable other researchers to recreate and build upon our work.

We actively encourage feedback, debate, suggestions and constructive criticism: please feel free to contact us.

Overview

The patch for the Jikes RVM is not very clean. It evolved through many stages, as with most research, and we have not cleaned it up a great deal. The vital changes to the code could be implemented in a very small patch.

We ran these experiments on a lightly loaded 2011 MacBook Pro, a quadcore machine. To a large extent, the load on the machine should not have a great impact on our results, as we rely only on process CPU time when decided how to change the heap size.

Download the Archive

This archive contains the directory structure and files required to repeat our work.

If you’re interested in our work, please contact us so we can keep track of who is working in this area, and whether it is worthwhile spending some time cleaning up and documenting the source code properly.

File System Structure

We checked out Jikes, applied the patch, and created directories as follows:

  • <jikes_root>/experiments
  • <jikes_root>/results
  • <jikes_root>/dacapo
  • <jikes_root>/patch

The “experiments” directory contains bash scripts to run our experiments, R scripts to analyse our results, and an Excel spreadsheet containing figures measured during the tuning process.

The “results” directory holds raw stdout files for the RVM, and cleaned CSV files suitable for processing in the R statistical package (generated by running the relevant “process” scripts for each experiment).

The “dacapo” directory contains the source code for our phased benchmark used in the final expeirment below.

The “patch” directory contains our patch.

Preparation

Clone Jikes:

hg clone http://hg.code.sourceforge.net/p/jikesrvm/code

Switch to the revision we forked from:

hg update -r 65aaf607fd8d

Uncompress our archive into the resulting directory.

Download DaCapo

Download the DaCapo benchmark jar files for 2006 and 2009 from http://www.dacapobench.org. Place these in the “dacapo” directory.

Apply our patch:

patch -p1 < patch/control_theory_heap_sizing.patch

Patch is also available here.

Build Jikes (for OS X):

ant -Dhost.name=x86_64-osx -Dtarget.name=x86_64-osx -Dconfig.name=FastAdaptiveMarkSweep

Experimentation

The experiments were run in numerical order. Note that not all the work we performed here is detailed. For example, we considered alternative methods of tuning include the “impulse” method, that were discarded for pragmatic reasons.

Experiment 1 – Checking Benchmarks Complete Successfully

Experiments 1a and 1b execute the Da Capo benchmarks on the RVM with a small problem size. By examining their output files, we were able to identify which benchmarks would not execute on the RVM. This can be manually checked with `grep “PASSED” 200?.txt` within the results directory.

Experiment 2 – Obtain Reasonable Target Values for g (Experiment A in the Paper)

In experiment two, we ran those benchmarks that completed successfully in Experiment 1, with a 250MB heap size limit using the standard Jikes resizing mechanism. We logged the value of g (GC overhead, passed through a median sliding window filter), and executed continuously until 100 GCs had been completed.

The script “2_process.sh” creates an R-friendly results file from the output that was subsequently run through “2_averages.r” to measure the median g values over each run. This gave us a sensible target to aim for in our evaluation, i.e. a value of g that we knew was achievable.

Experiment 3 – Tune PID (Experiment B in the Paper)

In experiment 3, we enabled the PID (proportional component only) and ran for 100 GCs with a gain level in the range 7 … 15. The aim was to find the gain at which clear oscillations could be observed for each benchmark.

The “3_process.sh” script cleans up the output files. The “3_plot.r” script produces graphs for each benchmark and every gain. These graphs were used to identify gain values at which clear oscillations began, known as the critical gain level in Ziegler-Nichols tuning.

Once we had done this, “3_median_time_period_measurement.r” was used to plot only those graphs corresponding to the critical gain levels. Then we were able to use R to estimate the time period of the oscillations using:

coords <- locator(type="l")

We recorded these measurements in the “3_tuning_results.xlsx” file within the experiments directory, which also includes the calculations specified by the Ziegler-Nichols method. This file contains the resulting tuned constants for the PID controller.

Experiment 4 – Evaluation (Experiment C in the paper)

In the evaluation, we ran each benchmark with the tuned controller fully enabled and log the resulting measures of g and the heap size over time. These were used to produce the graphs in the paper. The script “4_process.sh” cleans up the data; “4_plot.r” then produces the graphs for each benchmark.

Experiment 5 – Evaluate Phased Benchmark (Experiment D in the paper)

For this experiment, we created a phased benchmark that alternates between the xalan and sunflow benchmarks for the DaCapo 2009 benchmarks. The additional source code is within the dacapo/phased directory, and is overlayed on the DaCapo jar. The class that initiates the benchmark is org.dacapo.harness.PhasedHarness.

Scripts “5a, b and c run the phased benchmark using the PID controller, the default Jikes heap resizing method, and the HotSpot heap resizing method respectively. “5_process.sh” cleans up the output, and the “5_retrieve_phases.sh” script is a quick hack to produce a file describing phase change locations, to assist in plotting the graph.

Finally, the large graph is plotted with “5_plot.r”. There are a few aspects of this script that must be adjusted for specific output (to ensure graph items appear in the right place, there is no overlap of labels and data plot, etc.).