65.9K
CodeProject 正在变化。 阅读更多。
Home

西部最快的智能指针

Itay Maman
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.56/5 (17投票s)

2001年12月6日

13分钟阅读

viewsIcon

118641

downloadIcon

1598

需要一个超级快速的引用计数智能指针实现吗？AUTO_REF 就能提供，其源码非常“轻巧”，只有 3,886 字节（< 4KB）。

引言

几周前，我不得不编写一些代码，其中几个线程需要操作同一个类的实例。同步问题基本都解决了，所以我面临的主要问题是：何时可以安全地删除这个共享实例？

解决这个问题的明显方法是使用某种引用计数机制。该机制可以确保我的对象仅在对该对象的引用数量达到零时才会被删除。作为一名热衷的 C/C++ 程序员，我一直（传统上）不愿使用这类解决方案，因为我总是担心底层算法的性能开销。尽管 Boost::shared_ptr 是一个很好的实现，但我无法使用它，因为我的项目要求在不添加额外库的情况下进行编译。

于是，我坐下来写我自己的智能指针，它将“专门解决性能问题”。调试完成后，我将生成的类（命名为：AUTO_REF）带到测试赛道，与其他类似类进行正面较量。本文附带的演示项目实际上就是我用来为这些类计时进行基准测试的应用程序。结果将在本文的基准测试部分介绍。

接口

“饶了我吧，”我听到你说，“我只想知道如何将 AUTO_REF 集成到我的代码中。” 好的，这里是详细信息。假设您刚刚编写了一个名为 MY_CLASS 的类，它有一个名为 run(int x) 的成员函数。下面是如何通过 AUTO_REF 指针访问 MY_CLASS 对象。

  1. 设置您的项目
    1. 将 auto_ref.cpp 添加到您的项目中。
    2. 确保 auto_ref.h 和 quick_mem_manager.h 位于项目的包含文件搜索路径中。
  2. 设置 AUTO_REF 指针
    3. MY_CLASS* raw1 = new MY_CLASS();         // First object (obj1)
MY_CLASS* raw2 = new MY_CLASS();         // Second object (obj2)

AUTO_REF<MY_CLASS> p1 = raw1;                
AUTO_REF<MY_CLASS> p2 = p1;              // p1,p2 both point at obj1
  3. 更改引用的对象
    4. AUTO_REF<MY_CLASS> p3 = raw2;            // p3 points at obj2
p2 = p3;                                 // p2,p3 both point at obj2
  4. 解引用
    5. p1->run(5);                              //Invokes run(5) on obj1. 
(*p1).run(5);                            //   same thing

p2->run(3);                              //invokes run(3) on obj2
  5. 检查有效性（通过自动 bool 转换实现）
    6. if(p1)                               
      cout << "p1 is valid";       // p1 is dereferenceable 


if(!p2)
      cout << "p2 is invalid";     // p2 is empty. Dereferencing 
                                   // is not allowed
  6. 不要做的事情
    AUTO_REF<MY_CLASS> pt1(raw1);       // First pointer - no problem!

AUTO_REF<MY_CLASS> pt2(pt1);        // Declaring an additional
                                    // pointer thru an
                                    // existing AUTO_REF pointer - ok!

AUTO_REF<MY_CLASS> pt3(raw1);       // Declaring an additional pointer
                                    // WITHOUT using the existing 
                                    // AUTO_REF pointer
                                    //            - Wrong !!!!

设计理念

那么，智能指针到底是什么？智能指针是一种指针，它使程序员无需调用 delete() 来释放指向的对象。在典型的实现中，智能指针的构造函数会增加对象的引用计数，而其析构函数会减少计数。当计数达到零时，析构函数还会销毁对象，从而允许程序员完全忘记释放对象。听起来很棒？好吧，有一个陷阱：如果您的数据结构存在循环引用（A -> B -> C -> A），智能指针将无法按预期工作，但我们稍后会讨论到这个问题（稍后）。目前，让我们假设您 的数据结构没有循环引用。

在深入探讨 AUTO_REF 类的设计之前，让我们回顾一些实现智能指针的典型方法。

所有权：这些智能指针不使用引用计数，而是跟踪哪个指针实例“拥有”指向的对象。当指针被复制构造或复制赋值时，它会从另一个指针那里“获取”所有权，而该指针实际上变得无效。如果一个指针在拥有对象时被销毁，则对象也会被销毁。作为这种方法的代表性示例，请查看 STL 的 auto_ptr 类。这是一种简单而健壮的方法，具有最小（零）的内存开销，但它不是真正的智能指针，因为您不能同时让两个指针指向同一个对象。这个缺点使得无法将 auto_ptr 存储在 STL 容器中。（阅读更多）。

继承：这种智能指针只能指向从专用基类（例如：SP_BASE）派生的类。从智能指针的角度来看，它指向 SP_BASE 的一个实例。虽然这保持了实现的简单性，但由于使用了继承和虚函数（SP_BASE 的析构函数 必须是虚的，作为开始），它会带来显著的性能开销。

模板：智能指针类将指向对象的类型作为模板参数。因此，指针实际上“知道”它指向的对象类型。这种设计提供了更好的性能（与继承设计相比），但另一方面，它可能导致可执行文件大小增加。一个典型的例子：Boost::shared_ptr

AUTO_REF 的实现试图满足以下指南/要求：

  • [GL-1] 与原始指针相比，性能下降最小。
  • [GL-2] 性能优先于内存开销。
  • [GL-3] 完全的异常安全。
  • [GL-4] AUTO_REF 的源代码文件大小必须很小。（这个要求应该能让大多数开发者满意）
  • [GL-5] AUTO_REF 可以存储在 STL 容器中。
  • [GL-6] 代码应该可以在标准的 Visual C++ 编译器上编译，无需额外库。

对于不熟悉“异常安全”这个术语的读者，这里有一个简短、直观（完全非正式）的定义：如果抛出异常，您的对象将保持稳定状态，不会发生任何意外的副作用（例如：内存泄漏）。

在开发过程中，[GL-1] 是六个要求中最重要的。它几乎立即暗示了使用模板方法，并且-此外-我决定在每个 AUTO_REF 对象中保留原始指针值。我本可以将该指针放在共享结构中，与计数器一起，但这将导致每次解引用指针时额外的内存访问操作。将指针移出共享结构，使解引用更快，并将该共享结构简化为（仅仅）一个 LONG。

下一个重要决定是采用自定义内存分配器。分配计数器（类型：LONG）是 AUTO_REF 算法中最频繁、最耗时的步骤。由于所有分配的大小都相同，因此使用为分配固定大小缓冲区定制的内存管理器似乎是完美的。同样，我不允许使用 boost，所以重用 boost::pool 是不可能的。因此，我提供了我自己的类似分配器。

其他要求，[GL-3] 到 [GL-5]，基本上都是顺带实现的，只需付出很少的努力。使代码异常安全需要更多的思考，但幸运的是，我刚刚读完了 Herb Sutter 的优秀著作 “Exceptional C++”。通过遵循书中的建议，使 AUTO_REF 满足这一要求并不困难。至于代码大小，它仅为 3,886 字节。

实现

那么 auto_ref.cpp/.h 中的代码是如何实现这一切的呢？

关键在于 auto_ref.h。该文件定义了 AUTO_REF 类，它完成了大部分工作。当创建一个新的 AUTO_REF 指针时，它会接收一个指向现有类/结构（“原始”指针）的指针，并将其存储在 m_inst_p 数据成员中。然后，构造函数分配一个小的 LONG 大小的缓冲区来保存引用计数器。计数器的初始值为 1，因为有一个 AUTO_REF 对象指向该对象。

当一个新的 AUTO_REF 对象使用现有的 AUTO_REF 对象进行初始化（即复制构造）时，新对象会从现有对象中获取原始指针和计数器指针。此外，计数器会增加 1，因为新创建的对象实际上是另一个指向被指向对象的引用。请注意，代码使用了 InterlockedIncrement 来使此操作即使在两个线程同时创建两个新的 AUTO_REF 实例时也是安全的。

析构函数同样简单：它会减少计数器（再次使用 InterlockedDecrement），并且-如果计数器已达到零-它会删除被指向的对象和引用计数器。

复制赋值：我本可以使用一个结合了析构函数和复制构造函数的代码。这会导致类似以下内容：

    //Destruction starts here
    if(!InterlockedDecrement(m_ref_p)) {
        delete m_inst_p;
        g_the_auto_ref_pool.free(m_ref_p);
    }

    //Copy construction starts here
    m_ref_p = other.m_ref_p;
    m_inst_p = other.m_inst_p;
    InterlockedIncrement(m_ref_p);

    return *this;

看起来还可以？错了！如果执行自赋值，此代码将减少计数器，删除被指向的对象（假设我们从引用计数为一的状态开始），然后将计数器增加回一。因此，m_inst_p 会失效，因为它现在指向一个已删除的对象。这绝对不是一个理想的结果。

解决此问题的常见方法是将这段代码封装在 if 语句中：if(this != &other) {...} return *this; 。然而，还有另一种方法。

创造性的方法需要使用 Herb Sutter 所说的“强异常安全复制赋值的规范形式”。这本书（《Exceptional C++》）认为，如果您提供一个非抛出的 swap() 函数，您就可以始终使用以下几行来编写复制赋值：

    T &operator=(const  T &rhs) {
        T temp(rhs);
        swap(temp);
        return *this;
    }

这很巧妙，完全异常安全，并且-作为额外的奖励-您还可以获得 swap 功能。所以-Herb-这个赋值运算符是献给您的。

我的代码定义了另一个类：QUICK_MEM_MANAGER。该类实现了自定义分配器功能，以加速 AUTO_REF 所需的内存操作。算法如下：QUICK_MEM_MANAGER 使用 C 的标准 malloc() 来分配几 KB 大小的内存块。它还维护一个空闲缓冲区列表（LIFO）。

当调用 QUICK_MEM_MANAGER::malloc() 时，它会检查空闲缓冲区列表是否为空。如果不为空，它会从列表中移除第一个缓冲区并将其返回给调用者。否则，它会在最近分配的块中找到一个新的缓冲区（如果需要，会分配一个新块）。由于所有缓冲区的大小都相同，我们可以绝对确定从空闲列表中移除的缓冲区将满足调用者请求的大小。

当调用 QUICK_MEM_MANAGER::free() 函数时，指定的缓冲区会被放置在空闲列表中，这是一个 O(1) 时间的操作。该列表实现为单向链表，指针本身就存储在空闲缓冲区 **内部**，因此无需额外的内存。

限制

循环指针

我答应过要回到这个问题。为了说明问题，让我们看一个例子：您定义了一个类 MY_CLASS，它有一个名为 next 的 AUTO_REF<MY_CLASS> 指针作为数据成员。
struct MY_CLASS {
   AUTO_REF<MY_CLASS> next;
};

void demo_func() {
    AUTO_REF<MY_CLASS> pa(new MY_CLASS);  // object A
    AUTO_REF<MY_CLASS> pb(new MY_CLASS);  // object B
    AUTO_REF<MY_CLASS> pb(new MY_CLASS);  // object C
    pa->next = pb;
    pb->next = pc;
    pc->next = pa;
}

执行此代码后，我们创建了一个指针循环：A -> B -> C -> A。现在，让我们看看每个对象的引用计数：A 有 pa 指向它，还有 pc->next，所以 A 的总计数是 2。B（pb 和 pa->next）和 C 也是如此。

当 demo_func() 返回时，pa, pb 和 pc 超出作用域。因此，引用计数器会减少，但没有对象被删除，因为所有计数器都从 2 变为 1。所以，就 AUTO_REF 机制而言，这些对象仍在被使用。另一方面，此时，没有局部/全局/静态指针引用 A、B 或 C 中的任何一个。这意味着代码无法访问/删除其中任何一个对象。底线是 - 我们存在内存泄漏，因为这 3 个对象将永远不会被释放。

您应该注意到，如果我们没有进行最后一次赋值 pc->next = pa;（即，我们没有闭合链），那么当 pa 超出作用域时，A 的引用计数器将变为零。因此，A 将被销毁，这将导致 B 的计数器减少到 0（因为 A 的析构函数已调用 pa->next 的析构函数）。因此，B 也将被销毁，最终 C（由于与 B 相同的原因）。

解决此问题（循环数据结构的引用计数）需要采用更复杂的“垃圾回收”算法，但这会牺牲简洁性和速度。这当然不是我想要的，所以我决定将这个问题留白。开发人员必须意识到这个限制，因为它对 AUTO_REF 指针在某些数据结构中的使用施加了限制。

线程安全

  • AUTO_REF 对象的构造、复制构造和析构是线程安全的。
  • 赋值（operator=）不是线程安全的：如果两个线程同时将一个值赋给现有的 AUTO_REF 实例，结果将是不可预测的。
  • 解引用未同步：当两个（或更多）线程通过 AUTO_REF 指针/指针调用对象 X 的请求（即成员函数）时，请求将以不可预测的顺序执行，可能以交错的方式执行。因此，如果希望您的程序以这种方式使用 X 的类，则 X 的类设计必须支持线程安全。

内存管理

QUICK_MEM_MANAGER 的分配方案已被证明相当快，但这种速度提升是以内存消耗为代价的：如果您分配大量内存（通过 QUICK_MEM_MANAGER::malloc()）然后释放大部分内存，则释放的部分不会返回给系统，只有 QUICK_MEM_MANAGER::malloc() 才能使用该内存部分。如果这是您应用程序的对象使用模式，您应该考虑使用其他智能指针，或者提供 QUICK_MEM_MANAGER 的自定义实现，该实现将在所需情况下表现更好。

数组指针

AUTO_REF 不知道它指向的是单个结构（或类）还是结构数组的第一个元素。因此，如果您使用 new[] 运算符创建数组，则不应使用接收到的指针来初始化 AUTO_REF。如果这样做，您将面临内存泄漏，因为当引用计数达到零时，只会销毁数组的第一个元素。这不是一个主要限制，因为您可以（a）将动态分配的数组“封装”在一个类中，或者（b）使用 std::vector，这可能是最简单、最安全的解决方案。

多个计数器

如代码示例 f - “不要做的事情”（本文界面部分）所示，您不能用一个对象（该对象已由另一个 AUTO_REF 对象指向）的原始指针来初始化一个 AUTO_REF 指针。这将导致未定义行为。规则是：如果您创建一个指向对象的 AUTO_REF 指针，请确保所有指向该对象的其他 AUTO_REF 都通过复制构造函数或复制赋值运算符进行赋值。

基准测试

开发 AUTO_REF 的主要动机是创建一个智能指针类，该类在速度开销方面比原始 C 指针的开销最小。AUTO_REF 的实现是否达到了预期效果？

为了回答这个有趣的问题，我编写了测试应用程序。该程序创建 N（设置为 320,000）个类的实例，并将这些对象的指针存储在 STL 向量中。然后，代码进入一个循环，该循环解引用（向量中存储的）指针，并调用指向对象的成员函数。此循环重复 N*60 次。

代码使用的指针类型由 PTR_SWITCH 预处理器符号确定，因此应用程序可以配置为使用以下任何指针类型：AUTO_REF 指针（AUTO）、原始 C 指针（RAW）、RefCountPtr（RCP）、idllib::smart_ptr（IDLLIB）和 boost::shared_ptr 指针（BOOST）。

我在 700MHz 的 Win2000 机器上测量了每种配置的平均运行时间。代码使用 MSVC6 和 STLport 4.5 编译。我将 RAW 配置的结果视为 100%，并计算了相对于该结果的百分比速度。当我修改主循环执行次数（当前设置为 N*60）时，RAW 和其他指针之间的差异发生了变化，但总体排名保持不变。您应该记住，尽管我的应用程序试图模拟典型的“真实生活”指针使用情况，但结果仅在此特定测试中有效。

Configuration        Run time (seconds)        %
==================================================
RAW                       10.3                100%
AUTO_REF                  11.7                113%
BOOST                     12.7                123%
RCP                       15.2                147%
IDLLIB                    16.6                161%

该表显示 AUTO_REF 指针表现非常好：AUTO_REF 仅带来 13% 的性能下降，这比其最近的竞争对手（BOOST）要好 10%。另外两个配置的性能下降超过 45%。

那么，什么时候应该使用 AUTO_REF？答案很简单：当您不想显式删除指针，但仍希望保持程序尽可能快时。

参考文献

  1. Herb Sutter，Exceptional C++
  2. Greg Colvin 和 Beman Dawes，Smart pointer library
  3. Steve Cleary，Boost Pool Library
  4. Herb Sutter，Effective memory management
  5. Stefan Chekanov，A Smart Pointer Capable of Object Level Thread Synchronization and Reference Counting Garbage Collection - 一篇CodeProject 文章。
  6. Sandu Turcan，A Simple Smart Pointer - 一篇CodeProject 文章。
© . All rights reserved.