Transcript Introduction Implementation Data structure Garbage collection for

Garbage collection for data structure reorganisation
Introduction
Complex data structures can be optimized to reduce their access times as
well as removing unneeded data from within them. To make this possible
the garbage collector needs to provide help to the data structure. This
project examines the functionality that needs to be provided by the data
structure and the garbage collector to make this possible.
Implementation
Data structure
The complex data structure used for the
optimization is the trailer array. Trailer
arrays provide us a way of storing multiple
sets data at an index. Trailer arrays hold
this information indefinitely even when the
information is no longer used. We examine
how to determine if sets of data was
needed or not within the structure and then
clean it up.
Garbage Collection
To find unneeded data in within the data
structure, the structure needs to be informed
which versions are visible to others in the
heap. The structure then removes links to the
data within the structure, the garbage
collector can then remove unneeded objects
during a normal garbage collection. The
JikesRVM platform was used to handle
calling of the cleanup as well as identifying
the data structure objects.
PersistentArray
PersistentArrayMaster
0
1
2
3
AAA BBB CCC DDD
PersistentArrayDelta
PersistentArrayDelta
0
2
AAP
CCD
PersistentArrayDelta
1
BBG
Data Structure object interactions.
Persistent Space
PersistentMasterArray
Rerooting
n
Exter
r e n ce
a l re f
te
Ex
rn a
l
re n
re f
ce
A view of the Data Structure in the heap.
by George Kurian
[email protected]