Before Implementing Garbage Collector Algorithms for MMTk

Jikes RVM comes bundled with multiple plans, allowing us to build it with a preferred garbage collection algorithm, either concurrent such as concurrent mark and sweep (CMS), or the stop the world implementations that are not concurrent. When implementing a concurrent garbage collector, it is recommended to benchmark it against CMS collector, as it is the complete concurrent collector in production, where all the other collectors operate in the stop-the-world manner, where the program threads are halted.

Testing whether a new collector will work with the current build is a good starting point before actually starting with the coding.

[1]. First build Jikes RVM, with MarkSweep garbage collector

bin/buildit -j $JAVA_HOME localhost BaseBase MarkSweep

[2]. Test the GC

bin/buildit -j $JAVA_HOME localhost -t gctest BaseBase MarkSweep

[3]. Dummy Compressor GC.

Before testing the real implementation of the new GC algorithm Compressor, we will test that it will work.

Copy the package org.mmtk.plan.marksweep in MMTk/src as org.mmtk.plan.compressor and rename the package names accordingly. 

In build/configs, copy BaseBaseMarkSweep.properties as BaseBaseCompressor.properties

[4]. Test the dummy compressor GC
bin/buildit -j $JAVA_HOME localhost -t gctest BaseBase Compressor

You should be able to see the [echo] ... SUCCESS as seen above in [2], upon a successful build. Now this is time to check the implementation of the new algorithm.

Jikes RVM comes bundled with multiple test cases for benchmark suites and test benches, which can be found at testing/tests.
For example, SPECjbb2000, SPECjbb2005, SPECjvm98, SPECjvm2008, and mmtk-harness.

[5]. To run the dacapo (free and open source; download) (Dacapo is specifically used for the client side testing of the rvm), SPECjvm2008 (free download), and SPECjbb2005 tests against a production build or a BaseBase Compressor build,
bin/buildit -j $JAVA_HOME localhost  -t dacapo -t SPECjvm2008 -t SPECjbb2005 production
or
bin/buildit -j $JAVA_HOME localhost -t dacapo BaseBase Compressor

[6] Benchmarking with DaCapo. 
pradeeban@llovizna:~/jikesrvm/dist/BaseBaseMarkSweep_x86_64-linux$ ./rvm -jar dacapo.jar jython
*sys-package-mgr*: processing new jar, '/home/pradeeban/jikesrvm/dist/BaseBaseMarkSweep_x86_64-linux/dacapo.jar'
*sys-package-mgr*: processing new jar, '/home/pradeeban/jikesrvm/dist/BaseBaseMarkSweep_x86_64-linux/jksvm.jar'
*sys-package-mgr*: processing new jar, '/home/pradeeban/jikesrvm/dist/BaseBaseMarkSweep_x86_64-linux/rvmrt.jar'
===== DaCapo jython starting =====
-------------------------------------------------------------------------------
PYBENCH 2.0
-------------------------------------------------------------------------------
* using Python 2.2a1
* Python version doesn't support garbage collection
* system check interval set to maximum: 2147483647
* using timer: time.time

Calibrating tests. Please wait...

Running 1 round(s) of the suite at warp factor 20:

* Round 1 done in 61.664 seconds.

-------------------------------------------------------------------------------
Benchmark: 2013-04-06 12:13:24
-------------------------------------------------------------------------------

    Rounds: 1
    Warp:   20
    Timer:  time.time

Test                             minimum  average  operation  overhead
-------------------------------------------------------------------------------
          BuiltinFunctionCalls:    479ms    479ms    1.88us    0.000ms
           BuiltinMethodLookup:    941ms    941ms    1.79us    0.000ms
                 CompareFloats:    256ms    256ms    0.43us    0.000ms
         CompareFloatsIntegers:    199ms    199ms    0.44us    0.000ms
               CompareIntegers:    371ms    371ms    0.41us    0.000ms
        CompareInternedStrings:    510ms    510ms    0.68us    0.000ms
                  CompareLongs:    256ms    256ms    0.49us    0.000ms
                CompareStrings:    371ms    371ms    0.74us    0.000ms
                CompareUnicode:    278ms    278ms    0.74us    0.000ms
                 ConcatStrings:   6144ms   6144ms   24.58us    0.000ms
                 ConcatUnicode:   4123ms   4123ms   27.49us    0.000ms
               CreateInstances:   1094ms   1094ms   19.54us    0.000ms
            CreateNewInstances:   2056ms   2056ms   48.95us    0.000ms
       CreateStringsWithConcat:   4112ms   4112ms    8.22us    0.000ms
       CreateUnicodeWithConcat:   1884ms   1884ms    9.42us    0.000ms
                  DictCreation:   1532ms   1532ms    7.66us    0.000ms
             DictWithFloatKeys:    475ms    475ms    1.06us    0.000ms
           DictWithIntegerKeys:    468ms    468ms    0.78us    0.000ms
            DictWithStringKeys:    266ms    266ms    0.44us    0.000ms
                      ForLoops:    945ms    945ms   75.60us    0.000ms
                    IfThenElse:    397ms    397ms    0.59us    0.000ms
                   ListSlicing:    956ms    956ms  136.57us    0.000ms
                NestedForLoops:   1024ms   1024ms    1.37us    0.000ms
          NormalClassAttribute:    911ms    911ms    1.52us    0.000ms
       NormalInstanceAttribute:    453ms    453ms    0.76us    0.000ms
           PythonFunctionCalls:   1343ms   1343ms    8.14us    0.000ms
             PythonMethodCalls:   2451ms   2451ms   21.79us    0.000ms
                     Recursion:   1091ms   1091ms   43.64us    0.000ms
                  SecondImport:   1009ms   1009ms   20.18us    0.000ms
           SecondPackageImport:   1030ms   1030ms   20.60us    0.000ms
         SecondSubmoduleImport:   1509ms   1509ms   30.18us    0.000ms
       SimpleComplexArithmetic:   1651ms   1651ms    3.75us    0.000ms
        SimpleDictManipulation:    612ms    612ms    1.02us    0.000ms
         SimpleFloatArithmetic:    991ms    991ms    1.50us    0.000ms
      SimpleIntFloatArithmetic:    351ms    351ms    0.53us    0.000ms
       SimpleIntegerArithmetic:    350ms    350ms    0.53us    0.000ms
        SimpleListManipulation:    440ms    440ms    0.75us    0.000ms
          SimpleLongArithmetic:    931ms    931ms    2.82us    0.000ms
                    SmallLists:   1263ms   1263ms    3.71us    0.000ms
                   SmallTuples:   3198ms   3198ms   11.84us    0.000ms
         SpecialClassAttribute:    908ms    908ms    1.51us    0.000ms
      SpecialInstanceAttribute:    456ms    456ms    0.76us    0.000ms
                StringMappings:   2341ms   2341ms   18.58us    0.000ms
              StringPredicates:    825ms    825ms    2.36us    0.000ms
                 StringSlicing:   1803ms   1803ms    6.44us    0.000ms
                     TryExcept:     40ms     40ms    0.04us    0.000ms
                TryRaiseExcept:   2113ms   2113ms   66.03us    0.000ms
                  TupleSlicing:   1951ms   1951ms   14.86us    0.000ms
               UnicodeMappings:    942ms    942ms   52.33us    0.000ms
             UnicodePredicates:    705ms    705ms    2.61us    0.000ms
                UnicodeSlicing:    859ms    859ms    3.51us    0.000ms
-------------------------------------------------------------------------------
Totals:                          61664ms  61664ms

===== DaCapo jython PASSED in 66736 msec =====

MMTk mechanisms, policies, and plans

Class Diagram: MMTk Policies

MMTk is a flexible memory management utility written using java, for Jikes RVM. It is also ported to Rotor - the Microsoft's open C# runtime. Key Compositional Elements in MMTk are utilities, policies, and plans.

Bootstrapping
Jikes is meta-circular, as it is written in Java, the language it interprets as a JVM. Here, the functionality of the parent interpreter is applied directly to the source code being interpreted, without any additional implementation. Hence it requires a bootstrap VM to run upon, to create a boot image. However, it doesn't run on an external JVM. Rather, a small boot image runner written using C is responsible for loading the image files at run time, and it transfers the control to the native VM code that runs on the host [1].

Interruptibility

Compiler pragmas are used by MMTk to control the inlining and interruptibility, and scoped across methods and classes, where more specific pragma scopes such as method pragmas override the broader ones such as class pragmas. Classes annotated @Uninterruptible make the class uninterruptible. If most of the methods in a class are uninterruptible, annotating the class as uninterruptible is reasonable and preferred. All the policies and plans have the unintteruptible classes.

1) Mechanisms (utility)
MMTk comes with the utility classes that provides mechanism for the memory management, across multiple policies and plans that use those policies. An ideal example showing the usage of the utility package is, the interface Constants. All the classes either implement the Constants interface, or are sub classes of the classes that implement the interface.

1. Bump pointer allocation
2. Free list allocation
3. Large object allocation
4. Finalization

2) Policies (policy)
Spaces are contiguous regions of virtual memory, that is managed by a single policy. MMTk maps policies to spaces. In an address space, any given policy can manage multiple spaces.

Policies are implemented following the local/global pattern, and named XXXSpace and XXXLocal.
1. Copying Collector - CopySpace extends Space | CopyLocal extends BumpPointer

Class Diagram: MMTk Plans

2. Explicitly Managed Collector - ExplicitFreeListSpace extends SegregatedFreeListSpace | ExplicitFreeListLocal extends SegregatedFreeListLocal
3. ExplicitLargeObjectSpace extends BaseLargeObjectSpace |
4. Immortal Collector - ImmortalSpace extends Space | ImmortalLocal extends BumpPointer
5. Treadmill Collector - LargeObjectSpace extends BaseLargeObjectSpace | LargeObjectLocal extends LargeObjectAllocator
6. Mark-Compact Collector (MarkCompactCollector) - MarkCompactSpace extends Space | MarkCompactLocal extends BumpPointer
7. Mark-Sweep Collector - MarkSweepSpace extends SegregatedFreeListSpace | MarkSweepLocal extends SegregatedFreeListLocal
8. RawPageSpace extends Space
9. SegregatedFreeListSpace extends Space

Each instance of a policy space maps to a single virtual memory space, with P instances of the local class attached, where the collector is P-way parallel.

3) Plans (plan)
It is the highest level of composition, as it composes policies to build a memory management algorithm.
1. CMS (concurrent.marksweep)
2. CopyMS (copyms)
3. GenCopy (generational.copying)
4. GenMS (generational.marksweep)
5. GenImmix (generational.immix)
6. MC (markcompact)
7. MS (marksweep)
8. RC (refcount.fullheap)
9. GenRC (refcount.generational)
10. SS (semispace)
11. GCTrace (semispace.gctrace)
12. UsePrimitiveWriteBarriers (semispace.usePrimitiveWriteBarriers)
13. StickyImmix (stickyimmix)
14. StickyMS (stickyms)