Basically Immix organizes the heap into "regions":
- Coarse grained blocks, usually 32k in size (GHC also uses 32k for block size currently)
- blocks are divided into lines, 128b in size
Objects may span lines but no blocks. The idea is to reclaim memory on line and block level instead of per object.
- A line is considered free if it does not contain any live object.
- A block is considered free if it does not contain any live line.
In marking phase Immix walks the objects and marks
- the object itself to terminate the transitive closure
- the line the object is allocated in
The structure to mark a line is called a "line map" in the paper. Basically it is an array
uint8_t line_map[BLOCK_SIZE / LINE_SIZE]
(A bitmap would be much more space efficient but wouldn't work in a parallel GC as setting a bit might race with other threads)
Now the interesting part: How does allocation work? Immix keeps
-
Hp and HpLim pointers
Memory is allocated by increasing Hp. If Hp exceeds HpLim...
-
a list of recycable blocks (blocks which are partially full)
... free lines are searched in the list of recycable blocks. Since we have the line_map structure for each block this can be done in linear time. Hp and HpLim are adjusted to the fresh line group.
-
a list of empty blocks
... if no free line is found Immix takes fresh lines from the next empty block.
This way Immix supports bump allocation in line groups.
Immix does marking and evacuation in one pass. If a block is considered fragmented (e.g. by inspecting its line map) Immix can choose to evacuate objects. Allocation of the target memory is done using the regular line allocator. Evacuation is opportunistic. If Immix has no memory left to evacuate to it holds evacuation but continious to mark the object graph.
I propose a two generational Immix Garbage collector:
- every thread keeps its nursery to bump allocate into
- on GC nursery is evacuated into Immix space