特殊工具与技术

--优化内存分配

引言：

C++的内存分配是一种类型化操作:new为特定类型分配内存,并在新分配的内存中构造该类型的一个对象。new表达式自动运行合适的构造函数来初始化每个动态分配的类类型对象。

new基于每个对象分配内存的事实可能会对某些类强加不可接受的运行时开销,这样的类可能需要使用用户级的类类型对象分配能够更快一些。这样的类使用的通用策略是,预先分配用于创建新对象的内存,需要时在预先分配的内存中构造每个新对象。

另外一些类希望按最小尺寸为自己的数据成员分配需要的内存。例如,标准库中的 vector类预先分配额外内存以保存加入的附加元素,将新元素加入到这个保留容量中。将元素保持在连续内存中的时候,预先分配的元素使vector能够高效地加入元素。

在每种情况下(预先分配内存以保存用户级对象或者保存类的内部数据)都需要将内存分配与对象构造分离开。将内存分配与对象构造分离开的明显的理由是,在预先分配的内存中构造对象很浪费,可能会创建从不使用的对象。当实际使用预先分配的对象的时候,被使用的对象必须重新赋以新值。更微妙的是,如果预先分配的内存必须被构造,某些类就不能使用它。例如,考虑vector,它使用了预先分配策略。如果必须构造预先分配的内存中的对象,就不能有基类型为没有默认构造函数的vector——vector没有办法知道怎样构造这些对象。

【小心地雷】

本节提出的技术不保证使所有程序更快。即使它们确实能改善性能,也可能带来其他开销,如空间的使用或调试困难。最好将优化推迟到已知程序能够工作,并且运行时测试指出改进内存分配将解决已知的性能问题的时候。

一、C++中的内存分配

C++中,内存分配和对象构造紧密纠缠,就像对象和内存回收一样。使用new　表达式的时候,分配内存,并在该内存中构造一个对象:使用delete表达式的时候,调用析构函数撤销对象,并将对象所用内存返还给系统。

接管内存分配时,必须处理这两个任务。分配原始内存时,必须在该内存中构造对象;在释放该内存之前,必须保证适当地撤销这些对象。

【小心地雷】

对未构造的内存中的对象进行赋值而不是初始化,其行为是未定义的。对许多类而言,这样做引起运行时崩溃。赋值涉及删除现存对象,如果没有现存对象,赋值操作符中的动作就会有灾难性效果。

C++提供以下两种方法分配和释放未构造的原始内存：

1）allocator类,它提供可感知类型的内存分配。这个类支持一个抽象接口,以分配内存并随后使用该内存保存对象。

2）标准库中的operatornew 和 operatordelete,它们分配和释放需要大小的原始的、未类型化的内存。

C++还提供不同的方法在原始内存中构造和撤销对象。

1）allocator类定义了名为construct和 destroy的成员,其操作正如它们的名字所指出的那样：construct成员在未构造内存中初始化对象,destroy 成员在对象上运行适当的析构函数。

2）定位new表达式接受指向未构造内存的指针,并在该空间中初始化一个对象或一个数组。

3）可以直接调用对象的析构函数来撤销对象。运行析构函数并不释放对象所在的内存。

4）算法uninitialized_fill和uninitialized_copy像 fill和 copy　算法一样执行,除了它们的在目的地构造对象而不是给对象赋值之外。

二、allocator类

allocator类是一个模板,它提供类型化的内存分配以及对象构造与撤销。

allocator类将内存分配和对象构造分开。当allocator对象分配内存的时候,它分配适当大小并排列成保存给定类型对象的空间。但是,它分配的内存是未构造的,allocator的用户必须分别construct和 destroy放置在该内存中的对象。

１、使用allocator管理类成员数据

回忆：vector类将元素保存在连续的存储中。为了获得可接受的性能,vector 预先分配比所需元素更多的元素。每次将元素加到容器中时， vector成员检查是否有可用空间以容纳另一元素。如果有,该成员在预分配内存中下一可用位置初始化一个对象;如果没有自由元素,就重新分配vector:　vector获取新的空间,将现在元素复制到空间,增加新元素,并释放旧空间。

vector所用存储开始是未构造内存,它还没有保存任何对象。将元素复制或增加到这个预分配空间的时候,必须使用allocator类的construct成员构造元素。

简易实现Vector类：

template <class T> class Vector
{
public:
    Vector():elements(0),first_free(0),end(0) {}
    void push_back(const T &);
    //...

private:
    static std::allocator<T> alloc;
    void reallocate();

    T *elements;
    T *first_free;
    T *end;
    //...
};

每个Vector<T>类型定义一个allocator<T>类型的 static数据成员,以便在给定类型的Vector中分配和构造元素。每个Vector对象在指定类型的内置数组中保存其元素,并维持该数组的下列三个指针，如图:

１）elements,指向数组的第一个元素。

２）first_free,指向最后一个实际元素之后的那个元素。

３）end,指向数组本身之后的那个元素。

可以使用这些指针来确定Vector的大小和容量：

?Vector的size(实际使用的元素的数目)等于first_free- elements。

?Vector的capacity(在必须重新分配Vector之前,可以定义的元素的总数)等于end- elements。

?自由空间(在需要重新分配之前,可以增加的元素的数目)是end– first_free。

２、使用construct

push_back成员使用这些指针将新元素加到Vector末尾：

template <typename T>
void Vector<T>::push_back(const T &item)
{
    if (first_free == end)
    {
        reallocate();   //分配新空间并复制现存元素，将指针重置为指向新分配的空间
    }

    alloc.construct(first_free,item);
    ++ first_free;
}

一旦push_back函数知道还有空间容纳新元素,它就请求allocator对象构造一个新的最后元素。construct函数使用类型T的复制构造函数将item值复制到由first_free指出的元素，然后,将first_free加 1以指出又有一个元素在用。

３、重新分配元素与复制元素

template <typename T>
void Vector<T>::reallocate()
{
    std::ptrdiff_t size = first_free - elements;
    std::ptrdiff_t newcapacity = 2 * max(static_cast<int>(size),1);

    T *newelements = alloc.allocate(newcapacity);
    uninitialized_copy(elements,first_free,newelements);

    for (T *p = first_free; p != elements; )
    {
        alloc.destroy(--p);
    }

    if (elements)
    {
        alloc.deallocate(elements,end - elements);
    }

    elements = newelements;
    first_free = newelements + size;
    end = elements + newcapacity;
}

我们使用一个简单但效果惊人的策略:每次重新分配时分配两倍内存。函数首先计算当前在用的元素数目,将该数目翻倍,并请求allocator对象来获得所需数量的空间。如果Vector为空,就分配两个元素。

uninitialized_copy调用使用标准copy算法的特殊版本。这个版本希望目的地是原始的未构造内存,它在目的地复制构造每个元素,而不是将输入范围的元素赋值给目的地,使用T的复制构造函数从输入范围将每个元素复制到目的地。

for循环对旧数组中每个对象调用allocator的 destroy成员它按逆序撤销元素,从数组中最后一个元素开始,以第一个元素结束。destroy函数运行　T类型的析构函数来释放旧元素所用的任何资源。

一旦复制和撤销了元素,就释放原来数组所用的空间。在调用deallocate　之前,必须检查elements是否实际指向一个数组。

【注解】

deallocate期待指向由allocate分配的空间的指针,传给　deallocate一个零指针是不合法的。

最后,必须重置指针以指向新分配并初始化的数组。将first_free和 end　指针分别置为指向最后构造的元素之后的单元以及所分配空间末尾的下一单元。

//P636 习题18.1/2
//in Vector.h
#ifndef VECTOR_H_INCLUDED
#define VECTOR_H_INCLUDED

#include <algorithm>
#include <memory>

template <class T> class Vector
{
public:
    typedef T* iterator;

public:
    Vector():elements(0),first_free(0),end(0) {}
    void push_back(const T &);
    void reserve(const size_t );

    void resize(const size_t );
    void resize(const size_t ,const T &);

    T &operator[](const size_t);
    const T &operator[](const size_t) const;

    size_t size()
    {
        return first_free - elements;
    }
    size_t capacity()
    {
        return end - elements;
    }

    iterator begin()
    {
        return elements;
    }
    iterator last()
    {
        return first_free;
    }

private:
    static std::allocator<T> alloc;
    void reallocate();

    T *elements;
    T *first_free;
    T *end;
};

template <typename T> std::allocator<T> Vector<T>::alloc;

template <typename T>
void Vector<T>::reallocate()
{
    std::ptrdiff_t size = first_free - elements;
    std::ptrdiff_t newcapacity = 2 * std::max(static_cast<int>(size),1);

    T *newelements = alloc.allocate(newcapacity);
    std::uninitialized_copy(elements,first_free,newelements);

    for (T *p = first_free; p != elements; )
    {
        alloc.destroy(--p);
    }

    if (elements)
    {
        alloc.deallocate(elements,end - elements);
    }

    elements = newelements;
    first_free = newelements + size;
    end = elements + newcapacity;
}

#endif // VECTOR_H_INCLUDED

//in Vector.cpp
#include "Vector.h"

template <typename T>
void Vector<T>::push_back(const T &item)
{
    if (first_free == end)
    {
        reallocate();
    }

    alloc.construct(first_free,item);
    ++ first_free;
}

template <typename T>
void Vector<T>::reserve(const size_t capa)
{
    size_t size = first_free - elements;
    T *newelements = alloc.allocate(capa);

    if (size <= capa)
    {
        uninitialized_copy(elements,first_free,newelements);
    }
    else
    {
        uninitialized_copy(elements,elements + capa,newelements);
    }

    for (T *p = first_free; p != elements;)
    {
        alloc.destroy(--p);
    }
    if (elements)
    {
        alloc.deallocate(elements,end - elements);
    }

    elements = newelements;
    first_free = elements + std::min(size,capa);
    end = elements + capa;
}

template<class T>
void Vector<T>::resize(const size_t n)
{
    size_t size = first_free - elements;

    if (n > capacity())
    {
        reallocate();
        std::uninitialized_copy(elements + size,elements + n,T());
    }
    else if (n > size)
    {
        std::uninitialized_copy(elements + size,elements + n,T());
    }
    else
    {
        for (T *p = first_free; p != elements + n;)
        {
            alloc.destroy(--p);
        }
    }

    first_free = elements + n;
}

template<class T>
void Vector<T>::resize(const size_t n,const T &t)
{
    size_t size = first_free - elements;

    if (n > capacity())
    {
        reallocate();
        std::uninitialized_copy(elements + size,elements + n,t);
    }
    else if (n > size)
    {
        std::uninitialized_copy(elements + size,elements + n,t);
    }
    else
    {
        for (T *p = first_free; p != elements + n;)
        {
            alloc.destroy(--p);
        }
    }

    first_free = elements + n;
}

template<class T>
T &Vector<T>::operator[](const size_t index)
{
    return elements[index];
}
template<class T>
const T &Vector<T>::operator[](const size_t index) const
{
    return elements[index];
}