泛型<编程>：类型化缓存(III)
Andrei Alexandrescu
这是类型化缓存——轻量级和灵活的连续任意类型对象数组——的最后部分。它定位于基本内建数组和复杂的std::vector之间，当效率很重要时。类型化缓存是非常有用的结构，更重要的是，它可作为方便的基础部件来建立更复杂的结构——比如string,vector,queue及其他。
前一部分[1]集中讨论基本的有关buffer操作的高效率实现，比如填充和拷贝内存。本篇你要读到的文章有一个更广的视角——我们要讨论拷贝和移动对象，而不是原始数据。
低能的分配器(Allocator)
当我在聚会中想要用讨论基于策略的设计[2]来让人们大吃一惊时，我经常嘲笑STL分配器是个有名的关于策略的实验，却是一个悲惨的失败实验。
正如弗洛伊德指出中年焦虑与儿童时期的小事情有关，C++的内存分配的有趣故事需要追溯到C。
从一开始，C就提供三个内存管理的功能函数：malloc,free和realloc
void* malloc(size_t size);
void free(void* p);
void* realloc(void* p, size_t newSize);
三也许是个神奇的数字，但三个内存管理函数却远远不够。如果你考虑到恼人的重复——realloc能一个顶三个——情况就更是如此：
* 如果你传入空指针，realloc做malloc的工作
* 如果你传入一个零大小，realloc做free的工作
所以说realloc是个全能函数，能处理你所有内存管理的需要。（顺及，这是个坏迹象）
我们来看一个典型的realloc实现是这样的：
void* realloc(void* p, size_t newSize)
{
//排除极端情况
if (p ==0) return malloc (newSize);
if (newSize == 0) return free(p), 0;
//尝试就地扩充
if (p == _expand(p, newSize) && _msize(p) >= newSize)
{
return p;
}
//需要移动内存——获取新内存块
void* pNew = malloc(newSize);
if (!pNew) return 0;
//移动数据至新位置
memcpy(pNew, p, std::min(_msize(p), newSize));
free(p);
return pNew;
}
我想上面的realloc实现很易读，尤其因为它不遵照SESE(单个入口，单个出口Single Entry,Single Exit)规则[3]。但一些细节还不是很清楚——_expand和_msize是做什么的？
这两个函数是realloc的工具：
void* Expand(void* p, sizet newSize);
size_t _mSize(void* p);
_expand尝试就地扩充被它第一个参数指向的内存块。有可能当你要重分配一块内存时，它紧邻的内存块恰巧可用。在这个情况下，内存分配器可以只要快速调整它的记录内存使用的结构来反映出重分配了那块新内存。这比拷贝整个块到一个更大的位置要快许多。成功时，_expand返回指向它的指针。
_msize只返回它参数指向的内存块的大小。（所有内存管理器都必须知道每个内存块的大小）
_expand和_msize是非标准的，所以你只能通过realloc来间接使用它们。
回到realloc，如果就地扩充失败，realloc就分配一整块新内存块。用memcpy拷贝旧内存块到新内存块，free掉旧内存块。非常简单。也许过于简单了。
当C++诞生时，它非常依赖C的库和基本功能函数。尤其是，如果C++从头开发出它自己的，单独的内存分配器是非常困难的——在标准C分配器上建立一个新的，强类型的分配机制显得更有意义。
而这就是问题所在。
尽管memcpy对C是那么忠心耿耿，但它却是C++好心但笨拙的仆人。对C，用memcpy移动东西工作得很好，但C++需要更多。带构造函数和析构函数的对象不能象这样在内存中移动。它们可能包装了指向它们自身内部或编译器控制的数据（比如虚继承时指向基类的指针）。这意味着一个C++对象如果从一处memcpy到另一处就可能不再有效——公平地说，C++标准明确禁止memcpy不是POD（简单旧类型）的对象。
如果memcpy不够好，那么realloc就不够好——所以从第一天开始C++就没有给予重分配的机会。C++有new和delete，但没有“renew”或其他类似于realloc的任何东西。
这样std::allocator（它分配出来另一个东西就是带给所有人的烦恼）也没有提供任何的重分配的接口也就不让人奇怪了。所以在第二个千年的暮色中，大多数现代C++库没有一个手段来支持优化的内存分配。
因为C++缺乏高效的重分配，C++程序就注定要使用更多的内存并且/或者达不到应该达到的速度。C和C++不对外支持_msize，所以实际应用中一块动态分配内存的尺寸通常被存储两次——在分配器内部和在程序本身处，这就更在伤口上撒了一把盐。
现在请暂时闭上眼睛。闭上眼睛想象你周围各种C++应用程序在那运行（或崩溃）——所有的这些桌面应用，商业应用，服务器，多层、嵌入式系统，及其他你能想出来的。现在张开眼睛面对现实。它们不够优化：它们在不需要拷贝内存时拷贝内存，它们管理不需要它们管理的信息。所有这些都因为C的原始分配器的设计不对客户提供对两个基本函数的访问[4]。
我们现在看看我们怎样优化buffer的内存分配。因为类型化缓存使用分配器，我们需要一个和std::allocator接口协作良好的解决方案。
The Mallocator
不，这不是好来坞的电影名（译注：作者认为它很象Gladiator吗？还是其他什么？）——他只是个基于malloc 的类似于std的分配器。
我们从一个事实开始，realloc在C++中不是完全无用的，它只是无法用在C++的一部分类型上。所以即使在缺乏足够的标准C API的情况下，你也能够安全地对任何POD使用realloc，包括所有基本类型。这样在我们的buffer类中，为了达到快速的重分配，我们需要下列前提：
A） 知道一个任意类型T是否是一个POD。
B） 定义一个基于malloc的分配器，它和std::allocator有相同接口，并增加重分配函数。对POD来说，这个新的分配器直接使用realloc，对于非POD，它返回“否”，这种情况下调用者必须执行典型的分配—拷贝—释放系列动作。
C） 提供一个方法来询问一个分配器：“你可以重分配吗？”对这个问题std::allocator必须回答“不。”要点是，你不能std::allocator。
D） 如果可能，在buffer中尽量使用reallocate。就是说，如果你实例化buffer<char,std::allocator<char> >，就用一般做法。但如果是buffer<char, mallocator<char> >，那么buffer就尽可能使用高效率的重分配。
上面每个事项在现代C++中都有一个唯一最佳解决方法，在继续往下读前想一想，把这
作为个练习怎么样？
好，公布答案。
A） 如果你读过[5]，你就知道TypeTraits是解决方法。在[5]的代码基础上增加一些东西，你现在可以这样写
namespace TypeTraits
{
template <typename T> struct IsPOD
{
enum { value = IsPrimitive<T>::value };
};
}
默认情况只有基本类型是POD，正如[5]中所展示的，你可以对你知道是POD的类型建立特化的TypeTraits::IsPOD
B） Herb和Jim可能会写到：“先知Austern已经详细介绍过怎样写一个兼容于标准的分配器了。”事实上，Matt Austern在[6]中这样做了，这你能够在万能的互连网上找得到。
template <typename T>
struct Mallocator
{
...使用malloc/free的分配器实现，参见[6]...
T* reallocate(T* p, size_type newSize)
{
return TypeTraits::IsPOD<T>::value
? static_cast<T*>(realloc(p, newSize))
: static_cast<T*>(0);
}
}:
C） 如何在不改变其内部代码的情况下查询一个类型的功能呢？当然是——traits[7]!这不需要花什么力气：
template<typename A>
struct AllocatorSupportsReallocation
{
enum {value = false };
};
template <typename T>
struct AllocatorSupportsReallocation< Mallocator<T> >
{
enum {value = true };
};
D） 写一个函数靠一个布尔值作为条件来区分两个重载版本可以通过使用Int2Type[2，8]来很容易地完成。通过重载来处理是否重分配是最好的手段
template <typename A>
typename A::pointer Reallocate(
A& alloc,
typename A::pointer p;
typename A::size_type oldObjectCount,
tyoename A::size_type newObjectCount,
Int2Type<false>)
{
....用不支持重分配的分配器实现重分配...
}
template <typename A<
typename A::pointer Reallocate(
A& alloc,
typename A::pointer p,
typename A::size_type oldObjectCount,
typename A::size_type newObjectCount,
Int2Type<true>)
{
....用支持重分配的分配器实现重分配....
}
为什么你需要oldObjectCount参数？很简单：当A::realloc返回零，然后你需要分配一个新内存块并拷贝对象时，你需要知道你有多少对象。这就是为什么两个Reallocate函数实现都操作对象数，而不是字节数。Reallocate比较标准分配器的成员函数来说是个层次稍微高一点的函数。
现在当调用Reallocate时，所有buffer<T,A>需要做的是传递Int2Type<TypeTraits::IsPOD<T>::value>作为最后一个参数，然后，瞧吧！快速重分配起作用了！
有时候，你确实能够访问类似于_wxpand和_msize库扩展函数。Microsoft的C库就是这样的一个例子。这意味着，你可以高效地对所有类型进行重分配，而不只是POD。当然，如果你这样做而且你要让你的代码有跨平台的能力，你就必须使用#ifdef。
移动对象
我们现在转到另一个主题。即使你可以借助于任何就地扩展的手段来快速重分配内存，这离优化还是很远。考虑下面：
buffer<std::string buf(100000);
for (size_t i = 0; i != buf.size(); ++i)
{
buf[i] = GetSomeString(i);
}
....
Buf.reserve(buf.size() + 1000);
现在无论你是否使用Mallocator，有时候你不得不需要经历分配——拷贝——摧毁的循环。假定上例发生这个动作，对reserve调用就包括了移动1,000,000个字符串对象。在C++中，移动对象的做法类似于那些基本的转移方法：在另一处克隆对象然后摧毁源对象。
克隆所有这些字符串可能开销庞大——如果字符串不是引用记数的话。这比只拷贝它们所在的内存要大许多——这是非常可能的[9]——这样reserve就带来了许多不必要的工作，reserve分配一个新内存块，拷贝每个字符串到新块，然后最终，摧毁老块中的字符串。
但为什么当我们实际上只需要轻松地重新放置对象时却做了所有这些拷贝动作呢？我们只需要告诉一个字符串：“嗨，在内存里有你一个新位置，请自己重新就位。”因为字符串的老位置已经没用了（不管怎样都会被丢弃），字符串可以只要快速拷贝其内部指针到目标内存块。
我们不需要想很久就能明白象这样做需要把移动作为一个基本操作，而不同于拷贝，拷贝是复制对象。移动没有复制，对象总数保持不变。在缺乏移动这个概念的情况下，我们在C++中通过克隆然后摧毁原对象来实现它。我们需要做得更聪明些。
有许多方法可以实现移动。最简单的一个可以用函数
template <class T> void Move(T* src, void* dest);
但这样做不是那么简单。假设你正在实现一个字符串类：
class UltimateString
{
char* start_;
char* end_;
char* endOfStorage_; //因为不能用_msize，叹息中....
public:
....其他函数....
};
现在假设你为UltimateString来特化Move，如下
template <>
void Move(UltimateString* src, void* dest)
{
UltimateString* typedDest = static_cast<UltimateString*>(dest);
typedDest->start_ = src->start_;
typedDest->end_ = src->end_;
typedDest->endOfStorage_ = src->endOfStorage_;
}
如果你认为这样可以了，那你就错了。这样不可以，因为标准给编译器增加它们自己的数据到你的类里的自由（除非它们是POD）。这就是说：编译器可能在你的字符串类中增加一个int __coolnessFactor_成员变量，一个你不知道的成员变量让你从src到dest拷贝所有东西成为不可能。Move的结果是不可预料的。
C++强调每个有构造函数对象必须通过调用这些构造函数中的一个来创建。其他创建对象的途径都是被禁止的。所以移动对象必须通过某些构造函数来实现。
teplate <typename T>
struct Takeover
{
explicit Takeover(T& obj) : obj_(obj) {}
T& Get() { return obj_; }
private:
T& obj_;
};
TakeOver在一个对象中包装了一个引用并提供对它的访问。
然后，你实现一个UltimateString的构造函数，它接受一个Takeover<UltimateString>对象：
class UltimateString
{
char* start_;
char* end_;
char* endOfStorage_; //因为不能用_msize，再次叹息中....
public:
UltimateString(Takeover<UltimateString> wrap)
{
UltimateString& src = wrap,Get();
start_ = src.start_;
end_ = src.end_;
endOfStorage_ = src.endOfStorage_;
//清空源指针
src.start_ = src.end_ = src.endOfStorage_ = 0;
}
....
};
为了方便，我们把上面的构造函数叫做“接管构造函数”。接管构造函数与其他构造函数共存。它把三个指针拷贝到被构造的字符串对象中，然后清空源指针。我们需要最后一步是因为接管构造函数必须使源对象处于一个可摧毁状态。
目前为止一切都很好。但是，你怎么知道在一段泛型代码中一个类型T实现了一个接受Takeover<T>参数的构造函数呢？基于此，你需要有在编译时分派调用不同的移动对象的策略。
这是本文中最有趣的部分，因为我能够有机会让你看[2]和[8]。记得Conversion模板吗？如果不记得，相信我，它值得一看，所以打印[8]并读一下，或者更好（至少对我），买本[2]。Conversion提供一个编译时检测是否U能够转换为某种类型T的手段。如果你把U换为Takeover<T>把T换成，恩，还是T，你会发现这就是我们问题的解决方案。任何代码可以从外部知道任意一个类型是否实现一个接管构造函数。
关于意外安全的方面。一般移动一个对象不应该抛出意外，因为移动不涉及到分配新资源。但这不总是真的。考虑下面代码：
class Widget
{
....不实现一个接管构造函数....
....拷贝构造函数可能抛出意外....
};
class Midget
{
Widget w_;
public:
Midget(Takeover<Widget> wrap)
{
...啊呀呀，你怎么实现它而不抛出意外？....
}
};
这个问题可以用两个方法避免。一个是，很简单，把Widget成员替换为Widget*（或者，你有足够的魄力，替换为std::auto_ptr<Widget>），并使用动态分配。指针可以被干净利落地拷贝而不用拷贝Widget本身，所以构造函数很容易写。
第二个在Midget中实现一个接管构造函数的方法需要Widget的两个不同功能。
1、 Widget必须实现一个不抛出的swap，就象所有标准库中的容器那样。它也为其他类型建立了一个（非常不健全的）框架来定义swap。最为重要的，标准库示范了不抛出的对象交换是个基本的功能操作。Swap在各种情况下都非常有用，并且不能在类实现的外部高效地（且不抛出）地实现。如果你熟知标准，你可能在你所有的一级类（非多态）对象中实现swap。（如果幸运，本文可能说服你同样实现一个接管构造函数）
2、 Widget的默认构造函数不抛出一个意外。这通常很容易做到。
如果满足上面两个条件，你可以这样实现接管构造函数：
Midget(Takeover<Widget> wrap)
: w_() //很明显w调用默认构造函数
{
w_.swap(wrap.Get().w_);
}
这样就是先创建一个目标对象的空值，用空值和被接管的对象的值交换。
接管构造函数和交换是两个有关的并且稍微重复的操作，它们间的关系如下所示：
* 你可以用不抛出的swap实现一个接管构造函数，但只有你有一个不抛出的构造函数才能做到。如果所有你的构造函数都可能抛出，swap是无法用做实现接管构造函数的。
* 如果不存在那个@#!%^&（本处屏蔽若干文字）对齐问题，你本可以用一个接管构造函数实现swap。
void SwapViaMove (Midget& lhs, Midget& rhs)
{
char buffer[sizeof(Midget)] //必须对齐才能存放一个Midget
//拷贝lhs到buffer
Midget* lhsMoved = new (buffer) Midget(Takeover<Midget>(lhs));
//移动rhs到lhs
lhs.~Midget();
new (&lhs) Midget(Takeover<Midget>(rhs));
//移动lhs（现在在buffer中）到rhs
rhs.~Midget();
new (&rhs( Midget(Takeover<Midget>(*lhsMoved));
lhsMoved->~Midget();
}
这个函数不正确（而且看上去非常诡异），因为没有百分百通用的方法来保证buffer正确对齐以放置一个Widget。
如果你能够访问不抛出的构造函数，你可以象这样除掉对齐问题：
void SwapViaMove(Midget& lhs, Midget& rhs)
{
Midget temp; //不抛出
//移动lhs到temp
temp.~Midget();
new (&temp) Midget(Takeover<Midget>(lhs));
//移动rhs到lhs
lhs.~Midget();
new (&lhs) Midget(Takeover<Midget>(rhs));
//移动temp到rhs
rhs.~Midget();
new (&rhs) Midget(Takeover<Midget>(temp));
//temp.~Midget(); 不需要，因为编译器会做
}
（如果你想把temp声明为static来节约某些步骤，你会失去这个函数的可重入性（reentrancy）
结论：任何不抛出的swap和接管构造函数可以自由地用另一个来实现，当且仅当你可以访问一个不抛出构造函数。
现在考虑移动对象序列，最有效的算法是这样：
* 如果类型是POD，你就用memcpy,memmove，或[1]中介绍的最快拷贝方式中的一种。Duff也许会说：我没听错吧。:)
* 否则，如果类型支持接管构造函数，就用它
* 否则在循环中使用蛮干的克隆——摧毁方式。
概要和结论
在C和C++中通用的内存分配方式是不够优化的。C库不能够就地扩展一个内存快，结果C++也同样不支持这些。此外，C和C++不提供一个内存块的大小信息，但这个信息分配器却可以得到。这两个缺陷影响到了应用程序的速度和足印（footprint）。我不知道这个影响严重到什么程度，我怀疑对大多数应用程序影响是小或者忽略不计，对某些程序则很麻烦。
为了克服所提到的缺陷，你可以设计一个分配器（Mallocator），它对POD使用realloc。这样至少你对象中的部分可以从快速重分配中受益。如果你的C库实现提供类似于_msize和_expand的扩展功能，你可以在你Mallocator实现中使用这些，这样就对所有对象执行快速重分配。
对C++对象，不抛出的移动是个象拷贝一样的基本操作。交换对象从概念上说某种程度等于移动（在特定环境下）。一个可靠的移动对象方法是用接管构造函数。
无论你怎样去实现它，有一个移动对象（快速和不抛出意外）的手段是使类似于vector<vector<double> >的复合容器成为可行的唯一途径。
[1] Andrei Alexandrescu. "Generic<Programming>: Typed Buffers (II)," C/C++ Users Journal C++ Experts Forum, October 2001, <www.cuj.com/experts/1910/alexandr.htm>.
[2] Andrei Alexandrescu. Modern C++ Design (Addison-Wesley Longman, 2001). 这不是第一本提出基于策略的设计的书，但这本书系统地记载并使用这样的设计。
[3] SESE是结构化编程时代的一个广为传播的咒语。在SESE至高无上的国度中，每个函数必须只有一个入口（不管怎样，大多数语言这样设计的） 和一个出口。“单出口”限制在今天，这个意外的时代，已经的是陈腐不堪了。尽管已经得到反复证明，SESE代码相对于同等多出口代码更长，更难维护的，更复杂和更低效。仍旧有许多可怜的灵魂坚信SESE是伟大的事物。（毕竟亚里士多德本人相信太阳被飞翔的天使拖过天空）SESE的狂热分子们在Pascal和C时代形成规模。不幸的是随着年龄的推进，这些人正是今天的开发经理们。
[4] Microsoft's C 库实现的确提供对_expand和_msize的访问. 你可以说出你要的，但Redmond（微软所在地）那的人出了名的实际。
[5] Andrei Alexandrescu. "Generic<Programming>: Typed Buffers (I)," C/C++ Users Journal C++ Experts Forum, August 2001, <www.cuj.com/experts/1908/alexandr.htm>.
[6] Austern, Matt. "The Standard Librarian: What Are Allocators Good For?" C/C++ Users Journal C++ Experts Forum, December 2000, <www.cuj.com/experts/1812/austern.htm>.
[7] Andrei Alexandrescu. "Traits: The else-if-then of Types," C++ Report, April 2000.
[8] Andrei Alexandrescu. "Generic<Programming>: Mappings between Types and Values," C/C++ Users Journal C++ Experts Forum, October 2000, <www.cuj.com/experts/1810/alexandr.htm>.
[9] Andrei Alexandrescu. "Generic<Programming>: A Policy-based basic_string implementation", C/C++ Users Journal C++ Experts Forum, June 2001, <www.cuj.com/experts/1906/alexandr.htm>.
Andrei Alexandrescu 是位于西雅图的华盛顿大学的博士，也是受到好评的《Modern C++ Design》一书的作者。可以通过www.moderncppdesign.com. 来联系他。Andrei同时也是C++研讨会 (<www.gotw.ca/cpp_seminar>).的一名有号召力的讲师。
你可以从CUJ网站或http://merced.go.nease.net/code/buffer.zip获得本文源代码。
[返回] 中文XML论坛 - 专业的XML技术讨论区 →
休息区 → 『 灌水天堂 』 → 泛型<编程>：类型化缓存(III)
(订阅本版)
2004/9/28 9:53:00
顶端 
泛型<编程>：类型化缓存(III)(16740字) － 卷积内核，2004年9月28日
新浪微博
