标记压缩算法
思路
标记压缩算法也是移动对象进行垃圾回收的算法。不过和 gc 复制不同的是，它自始至终只使用一个空间。每次复制的时候，都是向堆的低地址端进行复制，就像把所有活动对象一口气挤到了最左端，把垃圾挤没了一样。
算法实际上是不可能一遍就直接把对象给挪到合适的位置的。因为如果直接挪动的话，会无法修正其指向子对象的指针。
所以需要两次扫描，一次先设定好这个对象要去的位置，把指针也修正好。第二次真正的开始进行挪移。
最开始的方案可以理解为要保证对象在内存中的相对顺序，所以采用了三遍的方式。在遍历之前先进行标记，然后第一遍是设定位置，第二遍是修正指针，第三遍是挪动对象。这种算法我们称为 Lisp2 算法。
代码
$scan 表示正在下一个要扫描的对象的首地址
$free 表示如果挪动的话空闲位置的首地址
$startStart 堆的首地址
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
// 在标记后调用
compactionPhase(){
setForwardPtr();
adjustPtr();
moveObj();
}
// 设置每个对象的新位置
setForwardPtr(){
scan = $free = $heapStart;
while(scan < $heapStart + $heapSize){
// 引用
obj = *scan;
if(obj.mark == True){
obj.forward = $free;
$free += obj.size;
}
scan += obj.size;
}
}
// 修正指针
adjustPtr(){
for(r : $roots){
r = r.forward;
}
scan = $heapStart;
while(scan < $heapStart + $heapSize){
// 引用
obj = *scan;
if(obj.mark == True){
for(child : children(obj)){
child = child.forward;
}
}
scan += obj.size;
}
}
moveObj(){
for(r : $roots){
r = r.forward;
}
// 这里顺带把 free 也给维护了，方便之后使用
scan = $free = $heapStart;
while(scan < $heapStart + $heapSize){
obj = *scan;
if(obj.mark == True){
// 同理此处还是当做引用
newObj = *obj.forward;
copyData(obj,newObj);
newObj.forward= NULL;
newObj.mark = False;
$free += obj.size;
}
scan+=obj.size;
}
}
优点
显然标记压缩算法获得了接近两倍于 gc 复制算法的堆的利用效率。只需要额外记录 forward 和 mark 即可。
相比于标记清扫算法，能够更有效的利用堆。
缺点
- STW 时间长，正比于堆中所有对象的数量。
- 搜索三次，导致每次搜索时间都会很长。
优化
Two-Finger 算法
TF 算法的思想是指经历两次扫描来进行优化。但是它有个严重的制约条件： 所有对象大小必须一致。
第一次扫描，使用双指针，将所有右侧的对象都填到左边的空位中。左侧的指针叫 $free , 右侧的叫 $live 。
第二次扫描，修正所有子对象的指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// 移动对象
moveObj(){
$free = $heapStart;
$live = $heapStart+$heapSize;
while($free<$live){
while($free<$live && $live.mark == False){
// 事实上，所有对象的 size 都是一样的
$live-=$live.size;
}
while($free<$live && $free.mark == True){
$free+=$free.size;
}
if($free<$live){
copyData($live,$free);
$live.mark=False;
$live.forward = $free;
$free.mark=True;
}
}
}
adjustPtr(){
for(r : $roots){
// 这里算是个优化，只需要动 $free 后面的对象即可，前面的原有的对象不会动的
if(r >=$free){
r = r.forward;
}
}
scan = $heapStart
while(scan < $free){
scan.mark = False;
for(child : children(scan)){
// 同上文
if(child >= $free){
child = child.forward;
}
}
scan += scan.size;
}
}
这里的 forward 指针不必放在头中，可以放在第一个域里面。只需要两次扫描。
但是缺点也很明显，对象大小一致这个太过苛刻。可以尝试与前文的 BiBop 方法结合。另外此算法也对缓存不友好。
表格算法
表格算法也是两次扫描，不过保证了先后顺序。这个算法是一群一群的挪动，而且采用表格而不是 forward 来操控。
首先算法通过扫描，每当扫出一个连续的对象群，就会获得以下信息：
- 这个对象群之前的空闲位置的首地址
- 这个对象群的长度
我们就这样一个一个地将对象群挪放到其前面的空闲位置，也就是向左挤压，然后在他们后面放置一个表格用来记录这对象群的信息，以用来稍后修复指针。
表格可以理解成 vector<pair<int,int>> ，每个元素记录一个对象群的原起始位置以及滑动的距离（也就是新旧首地址之差）
先将对象群移动到左端，然后在原来它存在的区间最后一个位置的后一个位置（也就是存放区间的超尾）放一个表格
然后移动下一个对象群的时候，是很有可能覆盖掉前一个表对象群的表格的，先在超尾存放自己的表格额，然后把之前的表格都放到这个表格后面。所以表格的顺序并不一定是按照对象群首地址的位置排列的。
所以在之后的更新指针就需要做额外的工作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
adjustPtr(){
for(r : $roots){
r = newAddress(r);
}
scan = $heapStart;
while(scan < $heapStart + $heapSize){
if(scan.mark == True){
for(child : children(scan)){
child = newAddress(child);
}
}
}
}
// 寻找 obj 的新地址
newAddress(obj){
// table 中是一个 pair
bestSize,bestAddress = table[bestPos];
// 寻找首地址小于等于 obj 的元素的最大值
for(address,size : table){
if(address <= obj && address > bestAddress){
bestSize = size
bestAddress = address;
}
}
return obj-size;
}
优点
优点是不需要多余的空间，还保持了所有对象的顺序，并且还不需要规定每个对象的大小
缺点
缺点也很明显，引入了维护表格的开销，虽然可以通过对表格排序来将查找过程变为二分查找，但是排序本身也有损耗。
