Dart is a language that powers Flutter apps, and Dart virtual machine (VM) uses generational garbage collection by default. We implement Immix garbage collection that outperforms the original garbage collection in the Dart VM.

• Project Report, Presentation Slides, and Github Repo

Immix

Main three steps in canonical garbage collections are: (1) mark, (2) sweep, and (3) compact. These garbage collections all have limitations either having a poor locality, space inefficient, or high latency.

Immix is an efficient mark-region garbage collection solving the limitations by marking both lines and blocks. Here are characteristics of the lines and blocks:

• A block size is four times larger than the larget object size.
• Objects span lines, but not blocks.
• Lines with obejcts get marked.
• Implicit mark when small objects span from a previous line.

These characteristics minimize fragmentations, maximize sharing of freed blocks, and eventually enables fast garbage collection.

Please find details from the presentation slides shared on top.

Design Overview

We refer to Jikes RVM, which is an open Java VM for research, to understand how the Immix garbage collection is designed. In this section, we shows the original design of Immix in Jikes RVM how it stores objects and our design in Dart VM.

Jikes RVM

• A chunk is a container for all metadata for lines and blocks, tables for blocks, and 128 blocks.
• On top, there is a chunk map that contains addresses of all chunks created.

Dart VM

• Different from Immix in Jikes RVM, we simplify the block structure as above.
• The first line of each block keeps metadata (e.g., line mark tables and block state).
• Also in ImmixHeap, we keep addresses of all the blocks in an array, and it gets updated when creating a new block.

Structure Overview

We have spent time to understand actual structure implementation of Immix in Jikes RVM. By using a logging function in Jikes RVM, we could trace all function calls and relationships between while allocating objects and garbage collecting. Below are dependancy diagrams we have drawn and possible structure implementation in Dart VM to enable Immix.

Please read the project report shared on top for details.

Jikes RVM

Dart VM

Demo

To demonstrate our work, we have tested with a small number of blocks (3) and lines (11).

1. Allocation of 10 small objects

• It allocates 10 small object with a size less than 256 bytes (=line).
• Each mark means different status (#: Unavailable, *: Recyclable, .: Not used).
• We can see that 10 objects were allocated in first block, and not the block is unavailable.
• Currently even object is smaller than a line, it gets regular marking.

2. Allocation of a big object

• The allocation continues from the blocks in previous test.
• Third object is larger than half size of a block (max object size possible), and it gives an 0 because it cannot be allocated.
• It starts to allocate other 4 objects from a second block. After allocating 2 objects, 1000 bytes sized object is allocated on next line because there are no enough contiguous lines available.
• Last object can be allocated in second block and gets allocated there.

3. Request for a new block

• After allocating first two objects in 3rd block, it requests a new free block to allocate 1000 bytes sized object.

Future Work

Due to the limited time, we have implemented a simplified version of Immix garbage collection that can be manually called and used instead of being invoked automatically by the original object.cc file. To simulate our garbage collection, we manually called allocation functions.

In the future, we can advance the implementation by following two directions.

1. Implementing implicit marking for a single line
   • As mentioned, our garbage collection is a simplified version and does only a normal implicit marking instead of the single line implicit marking.
   • To implement, cursor and limit need to be implemented to track an exact address where to start allocating.
2. Completely replacing Dart garbage collection
   • To replace the original Dart garbage collection, our implementation requires to reliably intercept and bypass the original allocate call to our ImmixHeap allocate call.
   • It will not be simple and requires some effort to handle lots of original methods interacting with an original heap.