计数体技术
Kevlin Henney
(kevlin@curbralan.com)
引用计数技术?你可能会认为没什么新鲜的。每一本优秀的 C++ 教材,只要带你达到中级或高级水平,都会介绍这个概念。过去已经对其进行了如此彻底的探索,你可能会原谅自己认为所有能说的都已经说过了。好吧,让我们从第一原理开始,看看我们是否能挖掘出一些新的东西....
然后就没有了...
引用计数背后的原理是保持对象的运行使用计数,这样当计数降至零时,我们就知道该对象未被使用。这通常用于简化动态分配对象的内存管理:保持对该对象持有的引用计数,当计数为零时,删除该对象。
如何跟踪对象的用户数量?嗯,普通指针非常“笨”,因此需要额外的间接层来管理计数。这本质上是设计模式 [Gamma, Helm, Johnson & Vlissides, Addison-Wesley, ISBN 0-201-63361-2] 中描述的 PROXY 模式。其意图是
为另一个对象提供一个替身或占位符,以控制对它的访问。
Coplien [高级 C++ 编程风格和习惯用法, Addison-Wesley, ISBN 0-201-56365-7] 定义了一组与句柄和主体部分的基本分离相关的习惯用法。《Taligent 程序设计指南》[Addison-Wesley, ISBN 0-201-40888-0] 确定了代理(又名替身)的许多特定类别。广义上讲,它们分为两大类
- 隐藏:句柄是感兴趣的对象,隐藏了主体本身。句柄的功能通过委托给主体获得,句柄的用户不知道主体。引用计数字符串提供了一种透明的优化。主体在字符串的副本之间共享,直到需要更改时才创建副本。这种写时复制模式(延迟求值的特例)需要使用隐藏的引用计数主体。
- 显式:这里,主体是感兴趣的对象,而句柄仅为其访问和内务处理提供智能。在 C++ 中,这通常作为智能指针习惯用法实现。其中一个应用是引用计数智能指针,它们协同工作以保持对象的计数,并在计数降至零时删除它。
附加 vs 分离
对于引用计数智能指针,计数可以存在于两个位置,从而产生两种不同的模式,这两种模式都在软件模式 [Coplien, SIGS, ISBN 0-884842-50-X] 中概述。
- 计数体或附加计数句柄/体将计数放置在被计数的对象内。好处是可计数性是被计数对象的一部分,并且引用计数不需要额外的对象。缺点显然是这是侵入性的,并且当对象不是基于堆时,引用计数的空间会被浪费。因此,引用计数将您绑定到特定的实现和使用风格。
- 分离计数句柄/体将计数放置在被计数对象之外,以便它们一起处理。这样做的明显好处是,这项技术是完全非侵入性的,所有智能和支持设备都在智能指针中,因此可以用于独立于引用计数指针创建的类。主要的缺点是频繁使用这种方法可能会导致大量小对象(即计数器)在堆上创建。
即使进行这种简单的分析,似乎分离计数句柄/体方法也更胜一筹。实际上,随着模板的日益普及,这通常是首选方法,并且是常见的(但非标准的)counted_ptr
背后的原则。[Boost 名称是 shared_ptr
而不是 counted_ptr
。]
计数体的常见实现是在计数类型派生自的基类中提供计数机制。或者,为每个需要它的类全新提供引用计数机制。这两种方法都不能令人满意,因为它们非常封闭,将类耦合到特定的框架中。再加上计数在未计数对象中处于休眠状态的非内聚性,您会感觉到,除了在诸如 COM 和 CORBA 等广泛的对象模型中使用外,计数体方法可能仅在特殊情况下有用。
基于需求的方法
正是开放性的问题说服我重新审视计数体习惯用法的问题。是的,当使用这种习惯用法时,会期望存在一定程度的侵入性,但是有没有办法最大限度地减少这种侵入性,并将计数机制的选择与所使用的智能指针类型解耦?
近年来,构建开放式通用组件的最具指导意义的代码和规范主体是 Stepanov 和 Lee 的 STL(标准模板库),现在是 C++ 标准库的一部分。STL 方法广泛使用基于类型良好定义的操作要求的编译时多态性。例如,每个容器、包含和迭代器类型都由应在该类型的对象上执行的操作定义,通常带有描述附加约束的注释。编译时多态性,顾名思义,根据函数名称和参数用法(即重载)在编译时解析函数。与基于类型、名称和函数签名的运行时多态性相比,这种侵入性较小,但如果出现错误,则不太容易诊断。
这种基于需求的方法可以应用于引用计数。对于类型成为可计数,我们需要的操作大致是
- 一个
acquire
操作,用于注册对可计数对象的兴趣。 - 一个
release
操作,用于取消注册对可计数对象的兴趣。 - 一个
acquired
查询,用于返回可计数对象当前是否已被获取。 - 一个
dispose
操作,负责处置不再被获取的对象。
请注意,计数被推导为这种类型的抽象状态的一部分,并且没有以任何其他方式提及或定义。这种方法的开放性部分源于全局函数的使用,这意味着没有暗示任何特定的成员函数;这是一种无需修改类本身即可包装现有计数体类的完美方法。开放性的另一方面来自对操作的更精确规范。
对于类型成为可计数,它必须满足以下要求,其中 ptr
是指向该类型的单个对象(即不是数组)的非空指针,并且#function
表示对 function(ptr)
的调用次数
表达式 | 返回类型 | 语义和注释 |
acquire(ptr) |
无要求 | 后置条件:acquired(ptr) |
release(ptr) |
无要求 | 前置条件:acquired(ptr) 后置条件:acquired(ptr) == #acquire - #release |
acquired(ptr) |
可转换为 bool |
返回:#acquire > #release |
dispose(ptr, ptr) |
无要求 | 前置条件:!acquired(ptr) 后置条件:*ptr 不再可用 |
请注意,dispose
的两个参数是为了支持选择要调用的函数的适当类型安全版本。在一般情况下,意图是第一个参数确定要删除的类型,并且通常是模板化的,而第二个参数选择要使用的模板,例如,通过符合特定的基类。
此外,还必须满足以下要求,其中 null
是指向可计数类型的空指针
表达式 | 返回类型 | 语义和注释 |
acquire(null) |
无要求 | 操作:无 |
release(null) |
无要求 | 操作:无 |
acquired(null) |
可转换为 bool |
返回:false |
dispose(null, null) |
无要求 | 操作:无 |
请注意,这些函数在抛出或不抛出异常方面没有要求,除非如果抛出异常,则函数本身应该是异常安全的。
变得智能
给定类型的可计数要求,可以定义一个通用智能指针类型,该类型使用它们进行引用计数
template<typename countable_type> class countable_ptr { public: // construction and destruction explicit countable_ptr(countable_type *); countable_ptr(const countable_ptr &); ~countable_ptr(); public: // access countable_type *operator->() const; countable_type &operator*() const; countable_type *get() const; public: // modification countable_ptr &clear(); countable_ptr &assign(countable_type *); countable_ptr &assign(const countable_ptr &); countable_ptr &operator=(const countable_ptr &); private: // representation countable_type *body; };
为了阐述,这个类的接口被有意保持简单,例如,省略了成员模板和 throw
规范。大多数函数在实现上非常简单,很大程度上依赖于 assign
成员作为关键函数
template<typename countable_type> countable_ptr<countable_type>::countable_ptr(countable_type *initial) : body(initial) { acquire(body); } template<typename countable_type> countable_ptr<countable_type>::countable_ptr(const countable_ptr &other) : body(other.body) { acquire(body); } template<typename countable_type> countable_ptr<countable_type>::~countable_ptr() { clear(); } template<typename countable_type> countable_type *countable_ptr<countable_type>::operator->() const { return body; } template<typename countable_type> countable_type &countable_ptr<countable_type>::operator*() const { return *body; } template<typename countable_type> countable_type *countable_ptr<countable_type>::get() const { return body; } template<typename countable_type> countable_ptr<countable_type> &countable_ptr<countable_type>::clear() { return assign(0); } template<typename countable_type> countable_ptr<countable_type> &countable_ptr<countable_type>::assign(countable_type *rhs) { // set to rhs (uses Copy Before Release idiom which is self assignment safe) acquire(rhs); countable_type *old_body = body; body = rhs; // tidy up release(old_body); if(!acquired(old_body)) { dispose(old_body, old_body); } return *this; } template<typename countable_type> countable_ptr<countable_type> &countable_ptr<countable_type>::assign(const countable_ptr &rhs) { return assign(rhs.body); } template<typename countable_type> countable_ptr<countable_type> &countable_ptr<countable_type>::operator=(const countable_ptr &rhs) { return assign(rhs); }
公共责任
符合要求意味着类型可以与 countable_ptr
一起使用。这是一个实现混合类(mix-imp),它通过成员函数将其可计数性赋予其派生类。此类可以用作类适配器
class countability { public: // manipulation void acquire() const; void release() const; size_t acquired() const; protected: // construction and destruction countability(); ~countability(); private: // representation mutable size_t count; private: // prevention countability(const countability &); countability &operator=(const countability &); };
请注意,操作函数是 const
,而 count
成员本身是 mutable
。这是因为可计数性不是对象抽象状态的一部分:内存管理不依赖于对象的 const
性或其他方面。我不会在此处包含成员函数的定义,因为您可能可以猜到它们:分别为操作函数递增、递减并返回当前计数。在多线程环境中,您应确保此类读取和写入操作是原子的。
那么我们如何使这个类可计数呢?一组简单的转发函数就可以完成这项工作
void acquire(const countability *ptr) { if(ptr) { ptr->acquire(); } } void release(const countability *ptr) { if(ptr) { ptr->release(); } } size_t acquired(const countability *ptr) { return ptr ? ptr->acquired() : 0; } template<class countability_derived> void dispose(const countability_derived *ptr, const countability *) { delete ptr; }
现在任何从 countability
派生的类型都可以与 countable_ptr
一起使用
class example : public countability { ... }; void simple() { countable_ptr<example> ptr(new example); countable_ptr<example> qtr(ptr); ptr.clear(); // set ptr to point to null } // allocated object deleted when qtr destructs
运行时混合
挑战是以非侵入方式应用计数体,这样当对象未计数时,就不会产生开销。我们想要做的是在每个对象而不是每个类的基础上赋予这种能力。实际上,我们追求的是任何对象的可计数性,即 void *
指向的任何东西!毋庸置疑,void
可能是任何类型中最不确定的。
解决这个问题的力量至少可以说非常有趣。有趣,但并非不可克服。鉴于运行时对象的类不能以任何明确定义的方式动态更改,并且对象的布局必须是固定的,因此我们必须找到一个新的位置和时间来添加计数状态。必须仅在堆创建时添加这一事实表明以下解决方案
struct countable_new; extern const countable_new countable; void *operator new(size_t, const countable_new &); void operator delete(void *, const countable_new &);
我们重载了带有虚拟参数的 operator new
,以将其与常规全局 operator new
区分开来。这与标准库中 std::nothrow_t
类型和 std::nothrow
对象的使用相当。placement operator delete
用于在构造失败时执行任何清理。请注意,并非所有编译器都支持这一点。
使用 countable
的 new
表达式的结果是在堆上分配的对象,该对象具有保存计数的标头块,即,我们通过在其前面添加标头来扩展了对象。我们可以在实现文件中的匿名命名空间(未显示)中提供一些功能,以支持从原始指针进行的计数及其访问
struct count { size_t value; }; count *header(const void *ptr) { return const_cast<count *>(static_cast<const count *>(ptr) - 1); }
这里要遵守的一个重要约束是 count
的对齐方式应使其适合任何类型。对于显示的定义,在几乎所有平台上都是这种情况。但是,您可能需要为那些不满足要求的平台添加填充成员,例如使用匿名 union
来共同对齐 count
和对齐方式最严格的类型。不幸的是,没有可移植的方法来指定这一点,以便也观察到最小对齐方式 - 这是指定不直接使用 new
或 malloc
结果的自定义分配器时遇到的常见问题。
同样,请注意,计数不被认为是对象逻辑状态的一部分,因此从 const
到非 const
的转换 - count
实际上是 mutable
类型。
分配器函数本身非常简单
void *operator new(size_t size, const countable_new &) { count *allocated = static_cast<count *>(::operator new(sizeof(count) + size)); *allocated = count(); // initialise the header return allocated + 1; // adjust result to point to the body } void operator delete(void *ptr, const countable_new &) { ::operator delete(header(ptr)); }
给定正确分配的标头,我们现在需要 可计数 函数在 const void *
上运行以完成整个过程
void acquire(const void *ptr) { if(ptr) { ++header(ptr)->value; } } void release(const void *ptr) { if(ptr) { --header(ptr)->value; } } size_t acquired(const void *ptr) { return ptr ? header(ptr)->value : 0; } template<typename countable_type> void dispose(const countable_type *ptr, const void *) { ptr->~countable_type(); operator delete(const_cast<countable_type *>(ptr), countable); }
其中最复杂的是 dispose
函数,它必须确保正确类型的析构,并且还必须从正确的偏移量收集内存。它使用第一个参数的值和类型来正确执行此操作,第二个参数仅充当策略选择器,即使用 const void *
将其与先前为 const countability *
显示的 dispose 区分开来。
变得更智能
既然我们有一种在创建时为任何类型的对象添加可计数性的方法,那么要使它与我们之前定义的 countable_ptr
一起工作还需要什么?好消息:什么都不需要!
class example { ... }; void simple() { countable_ptr<example> ptr(new(countable) example); countable_ptr<example> qtr(ptr); ptr.clear(); // set ptr to point to null } // allocated object deleted when qtr destructs
new(countable)
表达式为分配和释放定义了不同的策略,并且与其他分配器一样,任何尝试混合您的分配策略(例如,在用 new(countable)
分配的对象上调用 delete
)都会导致未定义的行为。这类似于您将 new[]
与 delete
或 malloc
与 delete
混合使用时发生的情况。可计数一致性的全部意义在于可计数对象与 countable_ptr
一起使用,这确保了正确的使用。
但是,事故总会发生,并且您不可避免地可能会忘记使用 new(countable)
进行分配,而是使用 new
。在大多数情况下,可以通过扩展此处显示的代码以向 count
添加检查成员来检测到此错误和其他错误,从而验证每次访问时的检查。确保标头和实现源文件之间清晰分离的好处意味着您可以引入此分配器的检查版本,而无需重新编译代码。
结论
本文介绍了两个关键概念
- 使用通用的基于需求的方法来简化和调整计数体模式的使用。
- 通过控制分配,使用运行时混合模式动态且非侵入性地向固定类型添加功能的能力。
两者结合应用产生了基本计数体模式的新变体,非侵入式计数体。您可以进一步扩展这个主题,并为 C++ 设计一个简单的垃圾回收系统。
countable_ptr
、countability
和 countable new
的完整代码也可用。