小黑屋

0%

性能优化-：（01）2021.1.13-性能优化第一次课（数据结构篇）

发表于 更新于 分类于

一、概述

如果想自己写公司的apm，可以参考koom和matrix这2个来源框架

做完a任务和b任务，就可以做c任务，这时候可以用countdownLatch来实现​

做性能优化，很重要的一点就是线上的APM​

二、Java层的实现

简历中一定要有指标

  • cpu指标，如负载，线程数等

  • 内存指标

  • FPS

  • ANR

  • 卡顿

  • GC/oom还是和内存相关，gc日志

  • 网络，hook到okhttp

  • 远程下发，日志回捞，下发shell，执行动态代码

  • crash怎么监测？其实就是监视线程，java层有uncatchexception

  • anr怎么监测？就是监测文件，file obsever，监测anr文件

  • 用户行为链路，其实就是监测activity和fragment。在application中通过lifecyclecallback即可

可以说我们公司有做了类似头条的 APM，有几个人做，参考了xx，xx框架实现了

三、APM

首先讲设计思路。

1、配置

做 APM 肯定是有配置的，类似于:

1
2
3
4
5
6
7
8
String[] params default {}


[{
    "clazz": "",
    "name": "Test",
    "params": ["a", "b"]
}]

配置都是使用 注解 + Json 实现 （课程里面还没说怎么用到的注解）

2、cpu与gc

使用linux命令​如prco/stat等

3、anr

面试官问一个问题，首先要回答有哪些知识点，看过哪些框架​，比如做性能监测，面试官问你是启动优化吗？可能不那么好回答，但是可以说做了类似抖音，类似快手的APM，别人就明白了。然后就是几个人做，大概做什么我负责哪些部分，我看了哪些框架源码，我自己是怎么想的。

anr监测主要就是文件监听，监听data/anr/trace.txt​

4、fps帧率

使用 Geographer（单词可能写错，翻译为:编舞者​）

四、如何看项目源码

  1. 首先看构造函数

  2. 其次浏览属性，不一定能全部看懂，粗略知道含义

  3. 看其重要的 api 中的具体实现

看代码的时候，需要思考别人为什么这么设计。比如别人使用数据结构是基于什么考虑，空间换时间，还是时间换空间。 老师以 ArrayList 为例分析了这个过程。

这里有个知识点，ArrayList 扩容的时候，变成以前的1.5倍

HashMap 的 getNode() ，这个方法很精华：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

由于在一定时候会将链表转为红黑树，所以在 get 的时候需要判断是树还是链表：

1
if (first instanceof HashMap.TreeNode)

这个判断是否是树，是树就从红黑树中获取，是链表就do-while 遍历链表，直至找到或者遍历到最后一个结点为止。

这里面有个值得注意的点，用 & 符做求余的操作，根据 hash 值求 index ：

1
2
if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null)

通过 (n - 1) & (hash = hash(key)) 确定当前 key 应该在 HashMap 中数组的位置。注意一下，只有当 n 是 2 的 多少次方的情形才适用，采用 & 操作进行求余的原理可以参考：

java取余位运算_使用位运算&取余_陈安研究员的博客-CSDN博客

五、代码性能评测

在公司证明自己做的事情需要做测试数据，比如说 SparseArray 、ArrayMap 来替换 HashMap ，怎么证明性能更高？那就适用 几个，几千，几万个数据，然后通过 Android Studio 的 Profiler 去可视化查看Memory 指标中 Java 方面占用的空间。

老师解析 SparseArray 源码的时候，put 操作值得关注：

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
public void put(int key, E value) {
    int i = ContainerHelpers.binarySearch(mKeys, mSize, key);

    if (i >= 0) {
        mValues[i] = value;
    } else {
        i = ~i;

        if (i < mSize && mValues[i] == DELETED) {
            mKeys[i] = key;
            mValues[i] = value;
            return;
        }

        if (mGarbage && mSize >= mKeys.length) {
            gc();

            // Search again because indices may have changed.
            i = ~ContainerHelpers.binarySearch(mKeys, mSize, key);
        }

        mKeys = GrowingArrayUtils.insert(mKeys, mSize, i, key);
        mValues = GrowingArrayUtils.insert(mValues, mSize, i, value);
        mSize++;
    }
}

如果已经存在key-value了，那就直接覆盖，否则，看起来通过

1
i = ~i;

即对 i 取反操作就能获取到要存入的位置，这是什么原理？其实这是个技巧，避免了再次计算一次 index ，总而言之就是取反操作(~) 的性质：

  • 当 n 为正数时， ~(n) = -(n + 1)

  • 当 n 为负数时， ~n = (-n) - 1

所以，上述判断 i 的逻辑就比较通顺了：

1
2
3
4
5
6
if (i >= 0) {
    mValues[i] = value;
} else {
    i = ~i;
    //。。。。
}

如果找到位置当前有值了，直接覆盖；否则，取反得到真正的 index ，然后根据判断将 key 和 value 存入。附 binarySearch （二分查找）的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static int binarySearch(int[] array, int size, int value) {
    int lo = 0;
    int hi = size - 1;

    while (lo <= hi) {
        final int mid = (lo + hi) >>> 1;
        final int midVal = array[mid];

        if (midVal < value) {
            lo = mid + 1;
        } else if (midVal > value) {
            hi = mid - 1;
        } else {
            return mid;  // value found
        }
    }
    return ~lo;  // value not present
}

1、SparseArray 和 HashMap 比较：

  • 2个数组key数组和value数组

  • 默认是10的大小，hashmap为16

  • 不需要包装

  • 二分查找，稍微低了点点，HashMap 的hash算法效率高

所以，SparseArray 的主要优势是节省内存。

堆

本质：二叉树来维护一维数组

堆它和树有什么区别？堆不用指针（Node），树会有指针，所以堆更省内存。

二叉树最后一个非叶子节点：(length - 1) /2，排序首先动这个结点。

《算法导论》太难就看《算法4》

opencv 和 ffmpeg 不建议去做，深入太难了

flutter 也不要去写 API ，要去架构，引擎的东西

路哥活得很通透：

大起大落，讲课的时候失去了所有，名言：

  • 人总要失去些什么才能成长

  • 除了生与死，其他的都是小事

算法不用怕，早晚半个小事，坚持3年，大厂没问题

总要去做架构，假如以后的部门黄了

vulcan 是 openGL 的升级版

录音分析，自己面试为什么会失败，一句话一句话听

谢谢你的鼓励