《深入理解Android》一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函数等操作引起额外空间分配时,要重新分配的空间。

  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为存储空间的大小。在存储空间不足时,存储空间尺寸扩展为原来的两倍。

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

时间: 2024-10-28 10:05:50

《深入理解Android》一3.4 内存管理与容器的相关文章

《深入理解Android》一3.7 本章小结

3.7 本章小结 本章主要介绍了WTF库的实现与使用,包括其中的OwnPtr.RefPtr.断言.内存管理.容器.原子操作等内容,为读者继续阅读及实际开发提供支持.同时,还介绍了Android 的crash dump以及WebKit的运行时线程结构等,希望为读者勾勒出WebKit运行的动态画面.有这些内容作为基础,读者就可以展开WebKit的神奇画卷.

OC内存管理-OC笔记

内存管理细节:http://blog.sina.com.cn/s/blog_814ecfa90102vus2.html 学习目标 1.[理解]内存管理 2.[掌握]第一个MRC程序 3.[掌握]内存管理的原则 4.[理解]野指针与僵尸对象 5.[理解]单个对象的内存管理 6.[理解]多个对象的内存管理 7.[掌握]set方法的内存管理 8.[掌握]@property参数 9.[掌握]@class关键字 10.[理解]循环retain 一.内存管理 程序在运行过程中会在堆空间创建大量的对象,当对象

C++内存管理变革

引言 C/C++语言的内存管理经历了几次变革,但至今仍未能趋于成熟.这几次变革主要包括: 1. 从malloc/free到new/delete.这场变革是OOP技术兴起的产物.C++是强类型语言,new/delete的主要成果也就是加强了类型观念,减少了强制类型转换的需求.但是从内存管理角度看,这个变革并没有多少的突破性. 2. 从new/delete到内存配置器(allocator).自从STL被纳入C++标准库后,C++世界产生了巨大的变化.而从内存管理角度来看,allocator的引入也是

Android内存管理简述

相信一步步走过来的Android从业者,每个人都会遇到OOM的情况.如何避免和防范OOM的出现,对于每一个程序员来说确实是一门必不可少的能力.今天我们就谈谈在Android平台下内存的管理之道,开始今天的主题之前,先再次回顾两个概念. 内存泄漏:对象在内存heap堆中中分配的空间,当不再使用或没有引用指向的情况下,仍不能被GC正常回收的情况.多数出现在不合理的编码情况下,比如在Activity中注册了一个广播接收器,但是在页面关闭的时候进行unRegister,就会出现内存溢出的现象.通常情况下

Android内存管理之道

相信一步步走过来的Android从业者,每个人都会遇到OOM的情况.如何避免和防范OOM的出现,对于每一个程序员来说确实是一门必不可少的能力.今天我们就谈谈在Android平台下内存的管理之道,开始今天的主题之前,先再次回顾两个概念. 相信一步步走过来的Android从业者,每个人都会遇到OOM的情况.如何避免和防范OOM的出现,对于每一个程序员来说确实是一门必不可少的能力.今天我们就谈谈在Android平台下内存的管理之道,开始今天的主题之前,先再次回顾两个概念. 内存泄漏:对象在内存heap

Android开发之内存管理

学习了下android的SDK里对内存管理部分的描述,结合搜集的一些资料汇分享总如下: 在任何软件开发环境中,RAM都是非常宝贵资源.在移动操作系统里,由于物理内存的限制,它会变得更加的宝贵.虽然Android的Dalvik虚拟机会常规的执行垃圾回收,但是开发人员仍然不能忽略什么时候.在哪里申请和释放内存资源.为了能够使垃圾回收器从应用里正常的回收内存资源,开发人员需要避免产生内存泄露,注意在合适的时候释放引用Reference(内存泄露常常由于保持着全局变量的引用).对于大多数应用,Dalvi

android内存管理

在任何软件开发环境中,RAM都是非常宝贵资源.在移动操作系统里,由于物理内存的限制,它会变得更加的宝贵.虽然Android的Dalvik虚拟机会常规的执行垃圾回收,但是开发人员仍然不能忽略什么时候.在哪里申请和释放内存资源. 为了能够使垃圾回收器从应用里正常的回收内存资源,开发人员需要避免产生内存泄露,注意在合适的时候释放引用Reference(内存泄露常常由于保持着全局变量的引用).对于大多数应用,Dalvik垃圾收集器会处理大部分的回收工作:系统会在对应脱离活动线程的作用域后回收你申请的内存

深入理解Linux内存管理机制(一)

深入理解Linux内存管理机制(一)通过本文,您即可以: 1. 存储器硬件结构: 2.分段以及对应的组织方式: 3.分页以及对应的组织方式. 注1:本文以Linux内核2.6.32.59本版为例,其对应的代码可以在http://www.kernel.org/pub/linux/kernel/v2.6/longterm/v2.6.32/linux-2.6.32.59.tar.bz2找到. 注2:本文所有的英文专有名词都是我随便翻译的,请对照英文原文进行理解. 注3:推荐使用Source Insig

[jjzhu学java]深入理解JVM笔记之内存管理机制

深入理解JVM笔记之内存管理机制 运行时数据区域 程序计数器 JVM栈 本地方法栈 Java堆 方法区 运行时常量池 直接内存 对象访问 OutOfMemoryError异常 Java堆溢出示例 JVM栈和本地方法栈溢出 运行时常量池溢出 本机直接内存溢出 深入理解JVM笔记之内存管理机制 运行时数据区域 程序计数器 每个线程都有一个程序计数器(PC),是当前线程所执行的字节码的行号指示器,通过改变程序计数器的值来选取下一条指令.各线程之间的计数器互不影响,是线程私有的内存. 如果线程执行的是一