A Control-Theory Approach to Heap Resizing

Table of Contents

• 1. Heap Sizing
  • 1.1. Control Theory for Principled Heap Sizing
    • 1.1.1. Intro
    • 1.1.2. Sweet spots
    • 1.1.3. Heap sizing in existing VMs.
    • 1.1.4. Heap sizing as a control problem
    • 1.1.5. Designing a Heap Size Controller
    • 1.1.6. Evauluation
    • 1.1.7. Related work

1 Heap Sizing

1.1 Control Theory for Principled Heap Sizing

http://www.dcs.gla.ac.uk/~jsinger/pdfs/ismm13.pdf

1.1.1 Intro

1. Programs frequently have seperate phases with very different memory behavior, no static heuristic acceptable
   
2. Control theory offers more formalism than trying to glue random, effective heuristics together.
   
3. Paper describes the idea of having a GC controller and increasing the heap size until the heap thrashing decreases and a throughput goal is hit.
   

1.1.2 Sweet spots

1. If heap too large, paging will impact performance. If too small, will thrash heap.
   
2. Can see a parabolic curve of running time and heap size. Ahead-of-time choice of heap size by benchmarking tends to not work though.
   

1.1.3 Heap sizing in existing VMs.

1. Existing VMs tend to increase heap size too optimistically, and decrease it more slowly than could be desired.
   
2. Jikes RVM
   
   1. After each GC, manager determines new "resize ratio" based on short term GC overhead (ratio of gc time and time since last GC) and ratio of heap that was live
      
      1. Is an index into a lookup table of hard-coded values found by trial-and-error
         
   2. Not explicitly goal-oriented in terms of throughput or heap size
      
   3. Doesn't take history into account, can flip-flop between states needlessly when live data size fluctuates back and forth quickly.
      
   4. There is no evidence that different GC algorithms will match these hard-coded heuristic thresholds
      
3. Hotspot
   
   1. Has a lot of tunable "ergonomics," and will resize heap to make best-effort to meet all priorities.
      
   2. Resizing rate much less flexible, ratio bounded between 0.95 and 1.2. Early on in execution, allows to grow at ratio 2.
      
   3. Venegrov has questioned whether the resize policies actually ensure progress towards goals.
      

1.1.4 Heap sizing as a control problem

1. Should use control theory
   
   1. Control theory mature in engineering
      
   2. Responds to both inputs and current deviation from goal.
      
   3. Software is very much like such a system, since software phase changes and sudden need to perform expensive, less frequent mode, can be seen as change to goal.
      
   4. Definitions:
      
      1. Steady-state error: The error that a system has after it's allowed to hit a steady state after trying to respond to a change.
         
      2. Transient response characteristics: How quickly a system responds to an input.
         
2. Formulating the Problem
   
   1. What's the input, what's the control variable, what's the feedback mechanism?
      
   2. Control variable = Heap resize ratio
      
   3. Measurement variable = Short-term GC overhead(ratio of GC pause time to time since last collection)
      
      1. Can use others as well, but not done in paper.
         
      2. Finds median overhead for past 5 collections. Dampens sensitivity and oscillation.
         

1.1.5 Designing a Heap Size Controller

1. Chose to treat entire GC system as black box, tune using Proportional Integral Derivative controller
   
2. Use a target GC overhead to resize heap
   
3. Only consider resizing after GC to avoid confounding variables in controller training.
   
4. PID Controller
   
   1. Why PID is appropriate
      
      1. Doesn't require a model of the system.
         
      2. Promises eventual zero steady-state error
         
      3. Takes history into account.
         
5. PID Controller Theory
   
   1. PID takes in responsiveness configuration, responds by outputting a change or "gain" in the controller
      
6. Implementation
   
   1. Built on Jikes/MMTK
      
   2. Uses bytes allocated as time proxy
      
   3. Heap growth manager was modified to use the PID controller
      
   4. Source: http://sourceforge.net/p/jikesrvm/research-archive/40/
      
7. Tuning:
   
   1. Can use the "empirical tuning method" which is effective, but dangerous in physical engineering.
      
   2. Ideal for software tuning
      

1.1.6 Evauluation

1. See paper for charts, results.
   
2. Generally positive
   
3. Might be worrying is that frequent, drastic changes in live data cause frequent, drastic changes in heap size.
   

1.1.7 Related work

1. Heuristic Approaches
   
   1. Brecht used Boehm GC. Grows heap by variably, finely-grained amount. Never shrinks heap.
      
   2. Most recent work has explicit goal to avoid paging
      
      1. Yang requires changes to OS
         
      2. Isla Vista system detects risk of paging by detecting allocation stalls
         
         1. Grows aggressively until allocation stall detected, and then shrinks aggressively
            
      3. Hertz has different VMs communicate relative stall/paging rates to optimize collection of multiple VMs.
         
2. Mathematical Models
   
   1. Sun varies size of heaps of multiple applications to hit performance goals
      
   2. Tay and Zong use number of page faults to direct resizing strategy to reduce number of faults.
      
      1. Threshold values determined by benchmarking, requires new derivation on a new system or new system behavior.
         
   3. Venegrov determines time not spent in GC for hotspot. Uses a study of the hotspot system to find custom tuning algorithm.
      
3. Control Theory Papers
   
   1. Storm deals with database configuration, uses control theory to handle ratio and size of sub-heaps for specific types of cached assets in database
      
   2. Gandhi uses control theory to optimize apache's CPU and memory utilization
      
   3. Growing research area
      

Created: 2014-10-22 Wed 16:56

Emacs 24.4.1 (Org mode 8.2.10)

Validate