Garbage Collection project (GSOC 2013)

Hi,

My name is Gao, a CS sophomore from SUNY Buffalo. I am interested in the
Garbage Collection (GC) project offered by MLton. A copy of my proposal is
attached with this email. I would greatly appreciate your comments and
suggestions.

Sincerely,
Gao

**  proposal begins  **

1.      Title of Project:

Generational Collector with Thresholds (This corresponds to Garbage
Collector Improvements project for MLton Google Summer of Code 2013.)



2.      Statement of Purpose:

A number of fundamental decisions must be made when implementing a memory
allocation and garbage collection subsystem [1]:



(1) When allocating memory, what algorithm should be used?

(2) If garbage collection is performed, which algorithm should be used?

(3) When should garbage collection be performed?

(4) When should the heap be expanded, and by how much should it expand?

(5) If the heap is being compacted, when should it be compacted?



In this proposal, we focus on the topic (3) and (4) and propose a way to
improve the performance of MLton garbage collector (GC), more specifically
the total execution time of the program, by introducing various levels of
thresholds, which could control the point at which the collection and the
expansion of heap are performed. There are other important factors related
to the performance of GC, such as the total GC time, the number of page
faults and the amount of memory consumed during the run of the program.
However, in this proposal, we are going to focus on optimizing the overall
time performance of the program.



3.      Background:

1)      GC Scheme for MLton:

The most recent implementation of MLton uses copying, mark-compact, and
generational collection GC schemes and is capable of switching
automatically between them at run time based on the amount of live data
relative to the amount of RAM (See Fig.1 for the variables that help to
decide which scheme to use).

float copy; /* Minimum live ratio to use copying GC. */

float copyGenerational; /* Only use generational GC with copying collection
if the ratio

                  * of heap size to live data size is below
copyGenerational.*/

float live; /* Desired ratio of heap size to live data. */

float markCompact; /* Minimum live ratio to use mark-compact GC. */

float markCompactGenerational; /* Only use generational GC with mark-compact

* collection if the ratio of heap size to live data size is

* below markCompactGenerational. */

*Fig.1: Important variables for making the decisions which GC scheme to use*

2)       Generational Collection in MLton:

The generational collection algorithm in MLton adopts the idea from [Sansom
1991], which utilizes the generational collection scheme proposed by Appel
(Appel [1989]). Appel’s scheme divides the heap into two generations, the
old-space and the new-space. The old-space is placed in the lower end of
the heap memory and the remaining memory is split into two semi-spaces. The
higher space is allocated to the new-space and the lower is used when
collecting the new-space during a minor collection. When the new-space is
filled up, a minor GC will be performed. Whenever the new-space is
collected, all the objects are promoted onto the end of the old-space and
the old-space is extended. When the old-space grows to half of the heap
space, a major GC will be performed. This collects the entire old-space by
copying it into the other half of the heap memory and using a move
operation to move the old-space back to the lower end of the heap [2] [3] (
See Fig.2 for details). The paper [Sansom 1991] adds compaction and other
features into the original Appel collector, which makes it more efficient
than before.

* Fig.2 Appel’s Generational Collector [3]*



3)      Research has been done to introduce thresholds into
Boehm-Demers-Weiser (BDW) conservative mark-and-sweep garbage collector
deployed in IBM’s High Performance Java (HPJ) environment [1]. With the
help of the thresholds, the new algorithm performed equally or better than
the traditional BDW collector for most of the applications.



4.      The Problem:

Current generational GC scheme adopted by MLton will perform collection
when a certain limit is reached. For minor GC, it will be triggered when
the new-space is filled up by data. For major GC, it will be performed when
old-space is larger than a certain ratio compared to the available physical
memory. Note that both of the GCs are done according to a single variable
limit. Such variable limit has its disadvantages, because it may not be
able to perform collection at the time when GC is most needed and expand
heap to better utilize available physical memory. The limit could introduce
infrequent GC. For instance, there is a large number of garbage in the
new-space. However, it’s not reaching the limit yet. If any operations
require memory allocation on the heap, then the GC will be triggered. The
cost for this scenario will be less, if we perform the GC before the limit
is reached and in a more dynamic way. For the case of heap expansion, the
current scheme will not be able to expand the heap in a flexible way to
fully make use of physical memory. The above two cases showed the necessity
to introduce a dynamic control of the point, at which the GC is performed
and a way to resize the heap. So I propose the following scheme to improve
the efficiency of both minor and major collections for generational GC.



5.      Methodology:

I propose to modify the idea from [T. Brecht ACM 2006] for both new-space
and old-space GCs and apply it to MLton. The general procedure is as
follows:

1)      Compute the first threshold T1 according to the formula 1 – 3.6 /
(log2(Avail. Mem.)). Then increase each subsequent threshold by (1 – T1) x
0.2, until the last threshold T6 is computed to be 1.

2)      Adopt the heap resizing and GC execution point scheme from [T.
Brecht ACM 2006] to assist garbage collection for MLton. The rules are as
follows:

1>    Exponentially increase the heap by a factor of 2 until the first
threshold is met, which is T1 in this case. After this, heap will only be
expanded to the next threshold. For example, after the heap size reached T3,
the next expansion will only increase the heap size to T4, not increasing
it to 2 x T3.

2>    When Ti is reached the first time, a GC is performed. For rest of the
execution time, the rules of performing GC are changed. When Ti is reached
not the first time, perform GC if and only if the number of reclaimed
memory from the most recent GC Rj is greater than Ti+1 – Ti. The purpose of
this rule is to avoid unnecessary, too frequent GC when the memory is
populated by mostly live data.

6.      Implementation Details:

Timeline for the summer: The program starts on June 17th and ends on
September 16th, covering a total of 14 weeks. I made the tentative timeline
for the program as follows:

Prior-to-Start:    Start to port the testing programs into MLton and set up
automated testing units. I also plan to collect more benchmarking programs
for testing my proposed idea (Appel’s collection is a good reference [6]).

Week 1 – Week 2: Further familiarize myself with current MLton architecture
and learn about Garbage Collection in depth. Specifically I will focus more
on generational garbage collection. I plan to use the book *Garbage
Collection: Algorithms for Automatic Memory Management by Richard Jones* as
my primary reference.

Week 2 – Week 3: Test existing benchmarks and try to understand how big is
the impact of the time at which the GC is performed on the overall time
performance, so that I could have a better knowledge of what kind of
benchmarking programs would benefit from the new algorithm.

Week 3 – Week 4: Implement the first version of generational collection
with thresholds for minor GC.

Week 4 – Week 6 (Mid-term): Integrate the implementation with MLton,
continue to work on porting the testing programs into MLton, and create
more unit tests for the new algorithm (The list of benchmarks I plan to use
is listed below. Please see Table 1).

Week 6 – Week 7: Continue the testing for my implementation of minor GC and
further clean up the code. Moreover, I plan to finish performance tuning by
the end of the week to have a better view of how well my algorithm could do
compared to standard MLton generational GC scheme.

Week 7 – Week 8: Implement the first version of generational collection
with thresholds for major GC.

Week 8 – Week 10: Perform testing specifically for major GC and compare the
results with standard MLton approach.

Week 10 – Week 13 (Suggested “pencils down” date): Integrate my
implementation with MLton and create unit testing for the new algorithm.
(The list of benchmarks I plan to use is listed below. Please see Table 1).
I also plan to work on the performance tuning when my algorithm is applied
to both minor and major GCs, so that I could have an overall idea of how
well my implementation could do.

Week 13 – Week 14 (Firm “pencils down” date): Complete the summaries of my
entire implementation, clean up the code for major GC and finish the
documentation.



The above timeline is tentative. If I have extra time during the summer, I
plan to apply the idea of introducing thresholds into GC to other
collection schemes, such as copying and mark-compact collection schemes.



Program

Description

CW

The Concurrency Workbench is a tool for analyzing networks of finite state
processes expressed in Milner’s Calculus of Communicating Systems,
processing a sample session input.

Leroy

An implementation of the Knuth-Bendix completion algorithm, implemented by
G´erard Huet, processing some axioms of geometry.

Lexgen

A lexical-analyzer generator, implemented by James S. Mattson and David R.
Tarditi, processing the lexical description of Standard ML.

MLton

The MLton compiler.

Modula

A compiler translating a Modula-like language into GNUC. The input is a
1400-line source program.

PIA

The Perspective Inversion Algorithm decides the location of an object in a
perspective video image.

Simple

A spherical fluid-dynamics program, developed as a “realistic” FORTRAN
benchmark, translated into ID, and then translated into Standard ML by Lal
George. Its imperative style may be expected of time-critical pieces of
systems software, or of pieces translated from existing code.

VLIW

A Very-Long-Instruction-Word instruction scheduler written by John Danskin.

Yacc

A LALR(1) parser generator, implemented by David R. Tarditi, processing the
grammar of Standard ML.

*Table 1: Benchmark programs used for automated testing suites [4].*



7.      Conclusion:

The new GC algorithm for MLton would collect garbage more smartly,
collecting if the last collection harvested a large number of unreachable
data, otherwise doing nothing. Moreover, the new algorithm separates the
heap expansion into two phases: exponential growth phase and
grow-to-threshold phase, which all together could better utilize the
available physical memory.



8.      Reference:

[1] Brecht, T., Arjomandi, E., Li, C. and Pham, H., “Controlling garbage
collection and heap growth to reduce the execution time of Java
applications,” ACM Transactions on Programming Languages and Systems, Vol.
28, No. 5, September 2006.



[2] AW Appel [1989], “Simple generation garbage collection and fast
allocation,” Software Practice and Experience 19(2), Feb 1989, 171-183.



[3] P. M. Sansom. Dual-Mode Garbage Collection. In Proceedings of the
Workshop on the Parallel Implementation of Functional Languages, pages
283--310, 1991.



[4] Darko Stefanovic, “Generational copying garbage collection for Standard
ML: a quantitative study.”



[5] White, D., Singer, J., Aitken, J., Matthews, D.: Automated Heap Sizing
in the Poly/ML Runtime (Position Paper)



[6] Andrew W. Appel. Compiling with Continuations. Cambridge University
Press, first edition, 1992.


** proposal ends**

------------------------------------------------------------------------------
Get 100% visibility into Java/.NET code with AppDynamics Lite
It's a free troubleshooting tool designed for production
Get down to code-level detail for bottlenecks, with <2% overhead.
Download for free and get started troubleshooting in minutes.
http://p.sf.net/sfu/appdyn_d2d_ap2

_______________________________________________
MLton-devel mailing list
[email protected]; [email protected]
https://lists.sourceforge.net/lists/listinfo/mlton-devel