《深入理解Android》一3.4 内存管理与容器

本文涉及的产品
容器镜像服务 ACR,镜像仓库100个 不限时长
简介:

本节书摘来自华章出版社《深入理解Android》一书中的第3章,第3.4节,作者孟德国 王耀龙 周金利 黎欢,更多章节内容可以访问云栖社区“华章计算机”公众号查看

3.4 内存管理与容器

WTF作为一个基础库存在,它提供的内存管理手段与STL类似,主要是为容器和应用类提供了便捷高效的内存分配接口(当然一些内部使用的内存对齐接口也是必不可少的)。其中,OSAllocator和PageAllocation类只应用于JavaScriptCore(Safari使用的JS引擎)中,这里不做分析。本节重点分析FastAllocator,这里的FastAllocator是指封装FastMalloc得到的WTF_MAKE_FAST_ALLOCATED、FastNew/FastDelete以及FastNewArray/FastDeleteArray。

3.4.1 FastAllocator的实现及使用

众所周知,STL中的Allocator在libc提供的malloc之上实现了一个memory pool,以此来实现高效的内存分配和回收(可参考《STL源码剖析》第2章,当然最新STL的allocator的实现跟书中的描述已有较大差别),而WTF则走了另一条路——实现一个高效的malloc。
【→Wtf/FastMalloc.cpp : 3823行】

template<bool crashOnFailure>
ALWAYS_INLINE void *malloc(size_t size);

WTF中使用条件编译宏FORCE_SYSTEM_MALLOC来控制是否使用libc提供的malloc。在FORCE_SYSTEM_MALLOC为0时,上述自定义的malloc在fastMalloc/tryFastmalloc中被调用。该malloc本质上就是TCMalloc的再封装。TCMalloc性能远优于libc malloc,它为每个线程分配thread-local cache。对于尺寸≤32KB的内存分配请求直接从thread-local cache中分配,并且按8的整数倍尺寸分配。而对于>32KB的内存分配请求则从堆中分配,并按照4KB的整数倍分配。此外,TCMalloc还提供了垃圾回收策略。
 关于TCMalloc的实现可以参考:http://goog-perftools.sourceforge.net/doc/tcmalloc.html
但Android 4.2版的WebKit没有使用TCMalloc实现的malloc,也就是说fastMalloc/tryFastmalloc最终使用的还是bionic提供的malloc函数。fastMalloc在Android平台没有实现全功能porting。
【→FastAllocBase.h】

#define WTF_MAKE_FAST_ALLOCATED \
public: \            
   void* operator new(size_t, void* p) { return p; } \
   void* operator new[](size_t, void* p) { return p; } \
   \
   void* operator new(size_t size) \
   { \              
       void* p = ::WTF::fastMalloc(size); \
        ::WTF::fastMallocMatchValidateMalloc(p, ::WTF::Internal::AllocTypeClassNew); \
       return p; \
   } \
   \
   void operator delete(void* p) \
   { \
       ::WTF::fastMallocMatchValidateFree(p, ::WTF::Internal::AllocTypeClassNew); \
       ::WTF::fastFree(p); \
   } \              
   \
   void* operator new[](size_t size) \                                                                                                                  
   { \
       void* p = ::WTF::fastMalloc(size); \
       ::WTF::fastMallocMatchValidateMalloc(p, ::WTF::Internal::AllocTypeClassNewArray); \
       return p; \  
   } \
   \
   void operator delete[](void* p) \
   { \
        ::WTF::fastMallocMatchValidateFree(p, ::WTF::Internal::AllocTypeClassNewArray); \
        ::WTF::fastFree(p); \
   } \
 private: \
 typedef int ThisIsHereToForceASemicolonAfterThisMacro

在WebKit代码类的声明中,经常看到上述宏。该宏为类定义了标准的operator new和operator delete以及placement new。
::WTF::fastMallocMatchValidateFree(p, ::WTF::Internal::AllocTypeClassNewArray);
在Android 4.2平台上是一个空函数,也就是这里的operator new 直接调用fastMalloc来完成内存的分配,前面分析过fastMalloc内部其实就是直接调用malloc。由此我们也可以得出一个结论,malloc返回的内存指针在对齐性等方面满足operator new的要求。其实STL提供的部分Allocator内部也直接使用malloc分配内存。由于这里定制了类的operator new 和operator delete,因此如果在这个宏中添加log或者统计算法,可以分析声明了WTF_MAKE_FAST_ALLOCATED的类的对象的创建和销毁情况,进而辅助分析内存泄露或其他问题。

3.4.2 容器类概述

WTF提供了为数众多的容器类,比如BlockStack、 ByteArray、 FixedArray、 Deque、 Vector、 HashTable等。本节重点分析Vector和HashTable的实现及使用,以此为基础,其余几种容器的实现及使用,读者可自行分析。

  1. Vector的实现及使用
    WTF中的Vector与STL中的Vector的行为基本一致,对外呈现的也是动态数组的行为。

【→Vector.h】

template<typename T, size_t inlineCapacity = 0>
class Vector {
    WTF_MAKE_FAST_ALLOCATED;
private:
    typedef VectorBuffer<T, inlineCapacity> Buffer;
    typedef VectorTypeOperations<T> TypeOperations;
public:
    typedef T ValueType;
    //关键点(1)
    typedef T* iterator; 
    //关键点(2)
    typedef const T* const_iterator; 
   
    explicit Vector(size_t size)  : m_size(size) ,  m_buffer(size)
    {
        if (begin())
           TypeOperations::initialize(begin(), end());
    }
    ~Vector()  {  if (m_size) shrink(0); }
    //关键点(3)
    size_t size() const { return m_size; }
    //关键点(4)
    size_t capacity() const { return m_buffer.capacity();}
    //关键点(5)
    T& at(size_t i) ;
    //关键点(6) 
    T& operator[](size_t i) { return at(i); }
    //关键点(7)
    iterator begin() { return data(); }
    //关键点(8)
    iterator end() { return begin() + m_size; }
    ////关键点(9)
    template<typename U> size_t find(const U&) const; 

void shrink(size_t size);
    void grow(size_t size);
    void resize(size_t size);
    void reserveCapacity(size_t newCapacity);
    void reserveInitialCapacity(size_t initialCapacity);
    void shrinkCapacity(size_t newCapacity);
    void remove(size_t position);
private:
    void expandCapacity(size_t newMinCapacity);
    const T* expandCapacity(size_t newMinCapacity, const T*);
    bool tryExpandCapacity(size_t newMinCapacity);
    const T* tryExpandCapacity(size_t newMinCapacity, const T*);
    template<typename U> U* expandCapacity(size_t newMinCapacity, U*); 
    size_t m_size;
    Buffer m_buffer;
};

上面代码截取的是Vector中重要的实现函数,下面分析Vector的几个重要成员。
关键点(1)(2):由于Vector采用连续存储结构,因此这里的iterator直接使用了原生指针。
关键点(3)(4):函数size()返回的是Vector中已存储的元素数目,而capacity()返回的是Vector所使用的Buffer的容量,这个capacity随元素增删的变化,也就是 Vector内存管理的核心内容。
关键点(5)(6):为Vector提供了数组访问的行为,这也是Vector动态数组行为的关键点。
关键点(7)(8):提供了获取iterator的接口,与使用STL容器的iterator一样,Vector的iterator的begin与end是会随着对Vector的修改而变化的,比如通过iterator完成的一次遍历操作中,若伴随对Vector元素的插入或删除操作,那么每一次操作完毕都要重新获取begin或end。
关键点(9):提供的find操作是一个O(N)的顺序遍历查找操作,如果用Vector来存储大量数据,而用它提供的find操作来查找元素,并不高效。
介绍Vector的主要行为后,再来看一下Vector的存储结构,本节不再仔细列举VectorBuffer和VectorTypesOperations的实现,只在宏观上说明这两个类的原理。
Vector用VectorBuffer作为内部存储数据的容器,而VectorBuffer的实现是通过fastMalloc来分配内存,用placement new来初始化对象(前面讲过malloc分配的内存满足operator new分配内存的要求),这样将Vector中对象的存储空间分配与对象初始化分开。
Vector中元素的初始化、复制、移动等操作由VectorTypesOperations来封装,其中成员函数的行为因数据类型的不同而不同,具体行为由VectorTraits封装的编译时类型计算信息控制。
当Vector因append函数或insert函数调用而引起内存空间不足时,间接调用reserveCapacity()来重新分配内存,并释放原来使用的内存空间。当Vector通过remove函数移除掉一些元素时,只是简单析构原来的对象。整个内存原理的示意图为图3-1。
图3-1中,begin指针代表begin()返回的iterator,end指针代表end()返回的iteraror。size()表示的范围为Vector中含有元素的部分,capacity表示已经分配的空间。扩展空间部分表示在insert函数或append函数等操作引起额外空间分配时,要重新分配的空间。

image

  1. HashTable的实现及使用
    HashMap和HashSet的实现代码非常简单,几乎每一个函数都只有几行代码,原因就在于支撑它们的幕后高手是HashTable。HashTable作为HhashMap和HashSet的m_impl字段帮它们打理好了一切。

【→HashTable.h】

template<typename Key, typename Value, typename Extractor, typename
HashFunctions, typename Traits, typename KeyTraits>
    class HashTable {
    public:
        typedef HashTableIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> iterator;
        typedef HashTableConstIterator<Key, Value, Extractor, HashFunctions, Traits, KeyTraits> const_iterator;
        typedef Traits ValueTraits;
        typedef Key KeyType;
        typedef Value ValueType;

        iterator begin() { return makeIterator(m_table); }
        iterator end() { return makeKnownGoodIterator(m_table + m_tableSize); }
       
        int size() const { return m_keyCount; }
        int capacity() const { return m_tableSize; }
        pair<iterator, bool> add(const ValueType& value) { return add<KeyType,
        ValueType, IdentityTranslatorType>(Extractor::extract(value), value); }

        iterator find(const KeyType& key) { return find<KeyType,
        IdentityTranslatorType>(key); }
      bool contains(const KeyType& key) const { return contains<KeyType, IdentityTranslatorType>(key); }

        void remove(const KeyType&);
        void remove(iterator);
        void clear();
    private:
        static ValueType* allocateTable(int size);
        static void deallocateTable(ValueType* table, int size);

        void expand();
        void shrink() { rehash(m_tableSize / 2); }

        static const int m_minTableSize = 64;
        static const int m_maxLoad = 2;
        static const int m_minLoad = 6;

        ValueType* m_table;
        int m_tableSize;
        int m_tableSizeMask;
        int m_keyCount;
        int m_deletedCount;

#if CHECK_HASHTABLE_ITERATORS
    public:
        // All access to m_iterators should be guarded with m_mutex.
        mutable const_iterator* m_iterators;
        mutable Mutex m_mutex;
#endif
};

一切的故事都从HashTable的创建说起:
通过HashTable的构造函数可知,初创建时HashTable的内容是空的,多数字段都是简单地初始化为0。
调用HashTable的add函数添加元素时,add内部通过expand函数来扩张内存空间,expand会调用fastMalloc来分配空间,分配空间的大小为:m_minTableSize = 64(此后再次需要分配空间时,分配的空间为原来空间的大小乘2),然后调用rehash函数,会在其中设置m_tableSizeMask = newTableSize–1,此处的m_tableSizeMask用在了寻址过程中,也就是lookup函数的实现中。
HashTable内部有两个lookup函数,一个是有一个参数的普通成员函数:
ValueType * lookup(const Key& key) {return lookupIdentifyTranslatorType>(key); } //实现(1)
它内部调用了lookup的另一种模板实现:
template ValueType* lookup(const T&);//实现(2)
实现(1)更频繁地被类外使用,比如在HashMap的get函数就是用了实现(1)。在该应用场景下实现(2)的第二个模板参数为IdentifyTranslatorType,而HashTable的HashFunctions参数为DefaultHash::Hash,这里的KeyArg也就是HashMap的KeyArg参数。因此在lookup函数内部HashTranslator::hash(key)最终使用的是HashFunctions.h文件中定义的DefaultHash::Hash,也就是IntHash::Hash,其作用是将输入的各种宽度的key值折算成unsigned int 类型的散列值,参与寻址运算。
下面截取lookup函数的关键点:

unsigned h = HashTranslator::hash(key);
int i = h & sizeMask;

这里的i作为table的index来存放数据,这也就是真正的寻址算法。如果这一次没有在HashMap上找到合适的位置,那么接下来的动作是调用新的hash算法:

if (k == 0){
 k = 1 | doubleHash(h);
 i = (i + k) & sizeMask;
}

也就是说HashTable本质上用线性结构存储,而解决hash冲突的方法是二次hash。
图3-2中,begin和end表示HashTable使用线性存储空间的起始和结束地址,capacity为存储空间的大小。在存储空间不足时,存储空间尺寸扩展为原来的两倍。

image

接下来分析HashTable的iterator的实现。HashTable的iterator是在调用begin或end时创建的,最本质的iterator对象是const_iterator, 而const_iterator内部也只是维持了一个指向value_type的指针而已,之所以如此是因为HashTable是线性存储的,进而iterator的自增或者自减操作也是简单的指针自增和自减操作,所以WTF的HashTable的iterator要比STL的HashMap的iterator实现简单(STL的HashMap使用数组加链表存储结构,用链表来解决hash冲突)。

相关文章
|
4月前
|
缓存 编解码 Android开发
Android内存优化之图片优化
本文主要探讨Android开发中的图片优化问题,包括图片优化的重要性、OOM错误的成因及解决方法、Android支持的图片格式及其特点。同时介绍了图片储存优化的三种方式:尺寸优化、质量压缩和内存重用,并详细讲解了相关的实现方法与属性。此外,还分析了图片加载优化策略,如异步加载、缓存机制、懒加载等,并结合多级缓存流程提升性能。最后对比了几大主流图片加载框架(Universal ImageLoader、Picasso、Glide、Fresco)的特点与适用场景,重点推荐Fresco在处理大图、动图时的优异表现。这些内容为开发者提供了全面的图片优化解决方案。
173 1
|
11月前
|
存储 前端开发 Java
Android MVVM架构模式下如何避免内存泄漏
Android采用MVVM架构开发项目,如何避免内存泄漏风险?怎样避免内存泄漏?
282 1
|
Kubernetes Cloud Native Java
云原生之旅:从容器到微服务的演进之路Java 内存管理:垃圾收集器与性能调优
【8月更文挑战第30天】在数字化时代的浪潮中,企业如何乘风破浪?云原生技术提供了一个强有力的桨。本文将带你从容器技术的基石出发,探索微服务架构的奥秘,最终实现在云端自由翱翔的梦想。我们将一起见证代码如何转化为业务的翅膀,让你的应用在云海中高飞。
|
10月前
|
监控 Java Android开发
深入探讨Android系统的内存管理机制
本文将深入分析Android系统的内存管理机制,包括其内存分配、回收策略以及常见的内存泄漏问题。通过对这些方面的详细讨论,读者可以更好地理解Android系统如何高效地管理内存资源,从而提高应用程序的性能和稳定性。
377 16
|
9月前
|
监控 Java Android开发
深入探索Android系统的内存管理机制
本文旨在全面解析Android系统的内存管理机制,包括其工作原理、常见问题及其解决方案。通过对Android内存模型的深入分析,本文将帮助开发者更好地理解内存分配、回收以及优化策略,从而提高应用性能和用户体验。
|
9月前
|
存储 缓存 监控
Docker容器性能调优的关键技巧,涵盖CPU、内存、网络及磁盘I/O的优化策略,结合实战案例,旨在帮助读者有效提升Docker容器的性能与稳定性。
本文介绍了Docker容器性能调优的关键技巧,涵盖CPU、内存、网络及磁盘I/O的优化策略,结合实战案例,旨在帮助读者有效提升Docker容器的性能与稳定性。
907 7
|
10月前
|
Android开发 开发者
Android性能优化——内存管理的艺术
Android性能优化——内存管理的艺术
|
Java 测试技术 Android开发
Android性能测试——发现和定位内存泄露和卡顿
本文详细介绍了Android应用性能测试中的内存泄漏与卡顿问题及其解决方案。首先,文章描述了使用MAT工具定位内存泄漏的具体步骤,并通过实例展示了如何分析Histogram图表和Dominator Tree。接着,针对卡顿问题,文章探讨了其产生原因,并提供了多种测试方法,包括GPU呈现模式分析、FPS Meter软件测试、绘制圆点计数法及Android Studio自带的GPU监控功能。最后,文章给出了排查卡顿问题的四个方向,帮助开发者优化应用性能。
808 4
Android性能测试——发现和定位内存泄露和卡顿
|
11月前
|
编解码 Android开发 UED
构建高效Android应用:从内存优化到用户体验
【10月更文挑战第11天】本文探讨了如何通过内存优化和用户体验改进来构建高效的Android应用。介绍了使用弱引用来减少内存占用、懒加载资源以降低启动时内存消耗、利用Kotlin协程进行异步处理以保持UI流畅,以及采用响应式设计适配不同屏幕尺寸等具体技术手段。
163 2