GC plan_phase二叉树挂接的一个算法

乎语百科 300 0

楔子

在看GC垃圾回收plan_phase的时候,发现了一段特殊的代码,仔细研究下得知,获取当前数字bit位里面为1的个数。

通过这个bit位为1的个数(count),来确定挂接当前二叉树子节点的一个地方。

算法

size_t logcount (size_t word)
{
    //counts the number of high bits in a 16 bit word.
    assert (word < 0x10000);
    size_t count;
    count = (word & 0x5555) + ( (word >> 1 ) & 0x5555);
    count = (count & 0x3333) + ( (count >> 2) & 0x3333);
    count = (count & 0x0F0F) + ( (count >> 4) & 0x0F0F);
    count = (count & 0x00FF) + ( (count >> 8) & 0x00FF);
    return count;
}

counts the number of high bits in a 16 bit word.这一段英文注释很有误导性,它的意思翻一下大致是:获取当前16位字里面的高位bit数。 如果按照这个理解,基本上不知道这个logcount函数是干嘛的。

但实际上它做的事情非常简单。

举个例子: 5的二进制:0101,那么经过logcount函数计算之后,返回值为2。因为5的二进制里面有两个1。 以此类推,6返回2,7返回3,8返回1。

背景

GC垃圾回收的计划阶段,当plan_phase构建二叉树的时候,需要区分根节点,左子节点,和右子节点。新加入的新节点作为根节点,新节点的左子节点(G)就是上一个根节点(C)的右子节点。新节点本身又作为上一个根节点(C)的右子节点。

图:

上面这个算法的作用就是,把新加入的新节点挂接到二叉树深度N(logcount返回值)的地方。 图两个二叉树,分别深度为2和3。logcount返回其参数bit位里面为1的个数,作为二叉树的深度。然后进行一个挂接。其行为逻辑是二叉树构建的核心。

整体

GC计划阶段(plan_phase)的二叉树构建主要是为后面的重定位,压缩和清扫做准备。 二叉树是其关键一步。 大致为:

1.区分固定对象和非固定对象,如果非固定对象后面跟着非固定对象就会形成一个堆段,如果后面继续有非固定对象,则继续加入这个小堆段。如果后面跟着固定对象则到小堆段到此为止。然后判断固定对象后面是否跟着固定对象,如果是则把这两个固定对象形成一个小堆段。后面继续判断,如果还是固定对象则加入到小堆段。如没有,则此小堆段到此为止。其逻辑跟非固定对象一样。如此一直遍历完这个堆,这样的话堆里面形成了一个个小堆段。

2.这些小堆段,会被plan_phase当成一个个的节点,然后把这些节点通过相关的逻辑构建成一颗二叉树。

3.如果二叉树过于庞大,则无论是在时间还是在空间上的复杂度都很高。为了避免性能问题,于是引入了brick_table来分割这颗庞大的二叉树

结尾

理解其行为,则需联系上下文,查看其整体构建,然后逐步推导。

标签: # plan_phase # 算法

留言评论

  • 这篇文章还没有收到评论,赶紧来抢沙发吧~