文档章节

支配树(Dominator Tree)

akane_oimo
 akane_oimo
发布于 09/20 09:52
字数 663
阅读 6
收藏 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
粉丝 20
博文 129
码字总数 156483
作品 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
Android中如何查找内存泄露

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

chengche
2013/11/27
0
0
请教各位大神,有谁了解g++的编译选项

g++ 4.9.2版本,有一个选项-aggressive-loop-optimizations,这个选项会自动优化代码 例如 #include class test_data { public: ~test_data(); static testdata* newtest_data(unsigned shor......

maoqianwanwenguo
09/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

帧动画(wifi信号动态动画)

准备六张wifi不同信号强度的素材图片,复制到drawable目录中 在drawable目录中新建frame文件,并编写代码 <animation-list xmlns:android="http://schemas.android.com/apk/res/android"> ...

lanyu96
32分钟前
2
0
快速get到学习Linux操作系统的点

Linux是一套免费使用和自由传播的类Unix操作系统,是一个基于POSIX和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。Linux能够运行主要的UNIX工具软件、网络协议和应用程序。它支持32位...

问题终结者
40分钟前
1
0
Django2 model操作数据库

1.将应用(如learn)添加到安装应用配置中 将我们新建的应用(learn)添加到 settings.py 中的 INSTALLED_APPS中,告诉Django有这么一个应用。 INSTALLED_APPS = [ 'django.contrib.ad...

MichaelShu
43分钟前
2
0
SpringBoot基础篇Bean之条件注入之注解使用

更多Spring文章,欢迎点击 一灰灰Blog-Spring专题 bean的条件注入,除了前面一篇博文中介绍的通过@Conditional注解配合Condition接口的实现之外,还提供了更多简化的注解使用方式,省略了自己...

小灰灰Blog
54分钟前
2
0
git clone 报错 Clone failed: Authentication failed for

新装了系统,git和phpstorm的配置全都没有了,重新安装了git和phpstorm 系统:windows10 代码托管平台:阿里云code 软件的安装不作赘述。 报错1 Could not read from remote repository 解决...

Marhal
55分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部