楔子在看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)的右子节点 。
图:
![GC plan_phase二叉树挂接的一个算法](http://img.zhejianglong.com/231018/0530544537-0.png)
文章插图
上面这个算法的作用就是,把新加入的新节点挂接到二叉树深度N(logcount返回值)的地方 。图两个二叉树 , 分别深度为2和3 。logcount返回其参数bit位里面为1的个数 , 作为二叉树的深度 。然后进行一个挂接 。其行为逻辑是二叉树构建的核心 。
整体GC计划阶段(plan_phase)的二叉树构建主要是为后面的重定位,压缩和清扫做准备 。二叉树是其关键一步 。大致为:
1.区分固定对象和非固定对象,如果非固定对象后面跟着非固定对象就会形成一个堆段,如果后面继续有非固定对象,则继续加入这个小堆段 。如果后面跟着固定对象则到小堆段到此为止 。然后判断固定对象后面是否跟着固定对象 , 如果是则把这两个固定对象形成一个小堆段 。后面继续判断,如果还是固定对象则加入到小堆段 。如没有,则此小堆段到此为止 。其逻辑跟非固定对象一样 。如此一直遍历完这个堆 , 这样的话堆里面形成了一个个小堆段 。
2.这些小堆段,会被plan_phase当成一个个的节点,然后把这些节点通过相关的逻辑构建成一颗二叉树 。
3.如果二叉树过于庞大,则无论是在时间还是在空间上的复杂度都很高 。为了避免性能问题,于是引入了brick_table来分割这颗庞大的二叉树
结尾理解其行为,则需联系上下文,查看其整体构建,然后逐步推导 。
【GC plan_phase二叉树挂接的一个算法】
推荐阅读
- vulnhub靶场之THE PLANETS: EARTH
- PLAN 谣言检测——《Interpretable Rumor Detection in Microblogs by Attending to User Interactions》
- .Net CLR GC plan_phase二叉树和Brick_table
- 将 N 叉树编码为二叉树
- 飞机用英语怎么读 飞机用英语怎么读发音airplane
- cause、reason、excuse、explanation,这些英语高频近义词需掌握
- 什么是二叉树的遍历 什么是二叉树
- 飞机的资料 关于飞机的资料
- planning怎么读英语 planning怎么读
- eplan如何导出pdf图纸在哪里找 EPLAN如何导出PDF图纸