文档章节

支配树(Dominator Tree)

akane_oimo
 akane_oimo
发布于 09/20 09:52
字数 663
阅读 11
收藏 0

MAT中的支配树

在使用MAT分析项目的内存泄漏问题时,其中有一个支配树(Dominator)视图。如果我们把Java对象之间的引用关系看做一张有向图(可以存在环)的话,对象的支配树体现了对象之间的支配关系。如果所有指向对象B的路径都要经过对象A,则认为对象A支配对象B。如果对象A是离对象B最近的支配对象,则认为对象A是对象B的直接支配者。

支配树定理

除起始节点外都有每个点都有唯一的idom(直接支配者),且不成环,故所有的 (idom(w),w) 边形成一棵树,v支配w当且仅当v是树中w的祖先,这棵树叫做支配树。

对象的支配树有以下性质:

  1. 对象A的子树(所有被对象A支配的对象集合)表示对象A的保留集(retained set),即深堆
  2. 如果对象A支配对象B,那么对象A的直接支配者也支配对象B
  3. 支配树的边与对象引用图的边不直接对应

对象支配树的作用

可以用来求深堆的大小。这里解释一下浅堆和深堆:

  • 浅堆表示一个对象结构所占用的内存大小
  • 深堆表示一个对象被GC回收后,可真实释放的内存大小

从支配树的性质可以看出,如果释放对象A,则对象A对应的支配树上的子树都将被释放,因为子树上的对象都不可达了,应该被GC回收。所以支配树上某个对象节点的子树上所有对象的大小就是该对象的深堆大小。

支配树的求解方法

简单求解方法

使用 “迭代+DFS”方法实现。时间复杂度是O(mn)。

  1. 每次删掉一个点,判断哪些点无法从起始节点r到达
  2. 删掉点u后发现点v无法到达,那么点u就是r->v的必经点(点u就是v的支配点)

Lengauer-Tarjan算法

 Lengauer-Tarjan算法可以在更优的时间复杂度下求解有向图的支配树。

© 著作权归作者所有

共有 人打赏支持
akane_oimo
粉丝 21
博文 131
码字总数 161640
作品 0
南京
其他
私信 提问
关于android应用内存占用查看及优化

第一步: 查看内存使用情况 我常用的查看内存使用情况的两种方式: 1、使用命令:adb shell dumpsys meminfo $package_name or $pid 2、 通过ddms查看 如果通过监控发现内存居高不下,一直增...

roc2013
2012/11/05
0
2
Eclipse Memory Analyzer tool 工具的使用

1、前言 在使用阿里云的OSS服务时,服务器内存高居不下,导致服务异常,最终通过Jmap+MAT找到了内存溢出的方法,定位到了问题所在。 整体思路是先用Jmap从生产上dump下来内存快照,然后用Mat...

freeli
2017/10/31
0
0
ANDROID 探究oom内幕

从早期G1的192MB RAM开始,到现在动辄1G -2G RAM的设备,为单个App分配的内存从16MB到48MB甚至更多,但OOM从不曾离我们远去。这是因为大部分App中图片内容占据了50%甚至75%以上,而App内容的...

gavin_jin
2014/03/13
0
0
Mozilla Firefox 46 Beta 5 发布

Mozilla Firefox 46 Beta 5今日已经被上传到FTP服务器,包 含全平台全语种 32/64位版本,46版为GNU/Linux平台整合了GTK3,改善了JIT编译器的安全性,并将无加密传输的密码文本框标记为不安全...

oschina
2016/03/26
1K
2
Android中如何查找内存泄露

1、首先确定是否有内存泄露及哪个程序造成。 1.1、内存泄露已弹出out of memory对话框的情况。 这种情况很简单,直接看对话框就知道是哪个应用的问题了。然后再分析该应用是否是因为内存泄露...

chengche
2013/11/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

撬动世界的支点——《引爆点》读书笔记2900字优秀范文

撬动世界的支点——《引爆点》读书笔记2900字优秀范文: 作者:挽弓如月。因为加入火种协会的读书活动,最近我连续阅读了两本论述流行的大作,格拉德威尔的《引爆点》和乔纳伯杰的《疯传》。...

原创小博客
9分钟前
0
0
《配电网自动化技术》第一章

写了配电网的组成、历程、难点、存在问题、解决方案,还是蛮好的。尤其是各地建设的系统后续又无法实用化,以及多种终端反而增加了运维工作量等,都是目前切实存在的让大家不停吐槽的内容。

max佩恩
14分钟前
0
0

中国龙-扬科
32分钟前
2
0
使用vuex的state状态对象的5种方式

vuex是一个专门为vue.js设计的状态管理模式,并且也可以使用devtools进行调试。 下面给大家来贴一下我的vuex的结构 下面是store文件夹下的state.js和index.js内容 //state.jsconst state =...

peakedness丶
35分钟前
2
0
NetCore MVC Demo

地址:http://114.116.9.72:5411

whltian
43分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部