STL 源码简析 – std::function (上)

感觉挺久没写 C++ 相关的东西了,反正最近写个玩具读了一遍源码手动实现了一遍 function 不如来总结一波 STL 的实现方法。

在讨论具体的实现之前,首先要明白 function 能干什么?实现的难点在哪儿?

function 类简介

function 能从所有可以直接在后面加对括号就执行一个子过程的对象构造,具体来讲它可以从函数指针、闭包类型(即 lambda 表达式)或者是其它有函数调用运算符 operator() 的对象构造(比如 random 库中的一系列类)。

闭包类型实际上也可以视作是编译器自动生成的带有一种函数调用运算符的匿名结构体。事实上,对于代码中的每个 lambda 定义,编译器都会默默地帮你生成一个新的“结构体”定义,也就是所谓的闭包类型。对于捕获的变量,事实上成为了闭包类型中的成员变量。而 lambda 函数体定义,则用于生成该闭包类型的函数调用运算符。

回到 function 本身, function 最主要的作用是保存和管理其它可调用 (Callable) 对象、调用保存的可调用对象。

function 的模板参数, R(Args...) ,是一个 C 风格的函数类型。一个更熟悉的形式可能是函数指针类型 R(*)(Args...) ,当然其函数引用类型也是存在的 R(&)(Args...) ,不过对于模板参数来说当然是越简单越好。

function 的模板参数就是它目前所保存的可调用对象的 operator() 函数原型,或者至少对于每个函数参数或返回值类型可以转换或者隐式构造成模板中的类型。同时,可以被同类型的 function 接纳的可调用类也可能有无数个, function 本身并不知道它所保存的对象的类型,那它该如何调用这个对象的某个成员函数,比如构造、析构呢?

事实上这就是 function 类(也是很多带有类型擦除性质的类,比如 std::any )在实现时面对的第一个挑战,也是必须要解决的问题,它需要管理对象的生命,它还要想办法调用它所保存的对象的函数调用、构造、析构等等成员函数。这点上, libc++(LLVM) 和 libstdc++(GNU) 采取了两种迥异的做法,分别是虚函数和……函数指针。

在看以下内容前,可以参考一下互联网上用虚表的简单 function 实现 Naive std::function implementation

困难 —— libc++ 实现

好啦,“困难”只是开玩笑的,不要被吓到了。因为后面还有地狱(笑)。

本文的 libc++ 是 7.0.1 版本的,大部分发行版只要从包管理器装个 libc++ 就送头文件了。 Arch Linux 下从 AUR 安装 libc++ 就送,头文件在 /usr/include/c++/v1/functional ,该头文件中定义了不少类,我们只需要关心和 function 相关的几个。

functional 头文件中有许多其它类的定义。首先我们看到 function 本身,它在 1412 行被声明,在 1587-1685 行被定义。在 function 类内部有两个成员, __function::__base<_Rp(_ArgTypes...)> 类指针 __f_ 和一个 aligned_storage<3*sizeof(void*)>::type __buf

具体的代码分析在后面进行,这里解释一下成员变量的作用, __base<_Rp(_ArgTypes...)> 就是上文提到的虚表实现中的多态基类。该指针指向由可调用对象类型、分配器类型、函数类型组成的三元组决定的多态派生类 __func<_Fp, _Alloc, _Rp(_ArgTypes...)> 的实例。而 aligned_storage 则是当需要保存的可调用对象足够小 (<=3*sizeof(void*))的时候,在 function 对象内部保存用的缓存区。

虚基类和派生类

我们把目光跳转到多态基类 __function::__base 上,在 1461 行声明,在 1463-1480 行定义。

template<class _Fp> class __base;

template<class _Rp, class ..._ArgTypes>
class __base<_Rp(_ArgTypes...)>
{
    __base(const __base&);
    __base& operator=(const __base&);
public:
    _LIBCPP_INLINE_VISIBILITY __base() {}
    _LIBCPP_INLINE_VISIBILITY virtual ~__base() {}
    virtual __base* __clone() const = 0;
    virtual void __clone(__base*) const = 0;
    virtual void destroy() _NOEXCEPT = 0;
    virtual void destroy_deallocate() _NOEXCEPT = 0;
    virtual _Rp operator()(_ArgTypes&& ...) = 0;
#ifndef _LIBCPP_NO_RTTI
    virtual const void* target(const type_info&) const _NOEXCEPT = 0;
    virtual const std::type_info& target_type() const _NOEXCEPT = 0;
#endif  // _LIBCPP_NO_RTTI
};

这就是之前所说的用虚表实现运行时判断调用哪个函数的方法,而这个 __base 就是一切包装可调用对象的类型的基类。其中的几个成员函数名很好理解,等说到派生类的实现再解释。

看到下几行的 __function::__func ,它继承了 __base 类,也就是上文所说的对于每个可调用类的包装类。看它的模板参数,第一项就是它负责包装的类,第二项是分配器,第三项则是原生函数类型。这样的话,派生类就知道了可调用对象的类型,而虚表则知道是该找哪个派生类,这就实现了对可调用对象的操作。

template<class _FD, class _Alloc, class _FB> class __func;

template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
class __func<_Fp, _Alloc, _Rp(_ArgTypes...)>
    : public  __base<_Rp(_ArgTypes...)>
{
    __compressed_pair<_Fp, _Alloc> __f_;
public:
    _LIBCPP_INLINE_VISIBILITY
    explicit __func(_Fp&& __f)
        : __f_(piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__f)),
                                    _VSTD::forward_as_tuple()) {}
    _LIBCPP_INLINE_VISIBILITY
    explicit __func(const _Fp& __f, const _Alloc& __a)
        : __f_(piecewise_construct, _VSTD::forward_as_tuple(__f),
                                    _VSTD::forward_as_tuple(__a)) {}

    _LIBCPP_INLINE_VISIBILITY
    explicit __func(const _Fp& __f, _Alloc&& __a)
        : __f_(piecewise_construct, _VSTD::forward_as_tuple(__f),
                                    _VSTD::forward_as_tuple(_VSTD::move(__a))) {}

    _LIBCPP_INLINE_VISIBILITY
    explicit __func(_Fp&& __f, _Alloc&& __a)
        : __f_(piecewise_construct, _VSTD::forward_as_tuple(_VSTD::move(__f)),
                                    _VSTD::forward_as_tuple(_VSTD::move(__a))) {}
    virtual __base<_Rp(_ArgTypes...)>* __clone() const;
    virtual void __clone(__base<_Rp(_ArgTypes...)>*) const;
    virtual void destroy() _NOEXCEPT;
    virtual void destroy_deallocate() _NOEXCEPT;
    virtual _Rp operator()(_ArgTypes&& ... __arg);
#ifndef _LIBCPP_NO_RTTI
    virtual const void* target(const type_info&) const _NOEXCEPT;
    virtual const std::type_info& target_type() const _NOEXCEPT;
#endif  // _LIBCPP_NO_RTTI
};

举个具体的例子,对于一个 hash<bitset<N>> 实例来说,用它构造出来的 __func 签名 __func<hash<bitset<N>>, allocator<bitset<N>>>, size_t()>

__compressed_pair 的空基类优化

__func 成员只有一个 __compressed_pair<_Fp, _Alloc> 。这个类在 LLVM 标准库 memory 头文件中 2193-2289 行被定义,它的两个基类 __compressed_pair_elem 在同文件下 2119-2187 行被定义和特化。

这个类利用了空基类优化来节省空间的,它的两个基类是对模板参数的一个包装,这在 LLVM 标准库中被广泛应用:由于大部分情况下我们的分配器都是标准分配器,而标准分配器无状态,一般实现中都是一个空类,而我们又不得不在对象中保存分配器。对于标准分配器来说,这就立刻浪费了大量的对齐空间。因此可以说这个 __compressed_pair 就是为了优化 std::allocator 而存在的。

几个构造函数都在类体内实现了,构造方式很简单,就是利用了 __compressed_pair 的 piecewiese construct 静态分派,来将参数传递到它的成员中构造。 piecewise 构造具体的定义在 memory 头文件的 2235-2242 行,而基类的构造定义在 2135-2139 和 2172-2176 行。

template <class... _Args, size_t... _Indexes>
_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
__compressed_pair_elem(piecewise_construct_t, tuple<_Args...> __args,
                       __tuple_indices<_Indexes...>)
    : __value_type(_VSTD::forward<_Args>(_VSTD::get<_Indexes>(__args))...) {}

template <class... _Args1, class... _Args2>
  _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
  __compressed_pair(piecewise_construct_t __pc, tuple<_Args1...> __first_args,
                    tuple<_Args2...> __second_args)
      : _Base1(__pc, _VSTD::move(__first_args),
               typename __make_tuple_indices<sizeof...(_Args1)>::type()),
        _Base2(__pc, _VSTD::move(__second_args),
               typename __make_tuple_indices<sizeof...(_Args2)>::type()) {}

多态派生类的实现细节

回到 __func ,虽然代码很简单,不过有个技巧值得一提:在 1519-1530 是它的 __clone() 成员函数。单看名字就可以知道它是用来复制对象本身的。

template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
__base<_Rp(_ArgTypes...)>*
__func<_Fp, _Alloc, _Rp(_ArgTypes...)>::__clone() const
{
    typedef allocator_traits<_Alloc> __alloc_traits;
    typedef typename __rebind_alloc_helper<__alloc_traits, __func>::type _Ap;
    _Ap __a(__f_.second());
    typedef __allocator_destructor<_Ap> _Dp;
    unique_ptr<__func, _Dp> __hold(__a.allocate(1), _Dp(__a, 1));
    ::new (__hold.get()) __func(__f_.first(), _Alloc(__a));
    return __hold.release();
}

逻辑很简单,就是构造了一个 unique_ptr 之后直接往里原地构造对象。之所以用 unique_ptr 而最后直接 release ,主要目的是简化内存管理。就算在构造期间抛出异常,申请的内存也能被干净利落地 RAII 回收掉,不需要手动处理。

剩下的一些成员函数实现都很朴素,不再逐个介绍。包括复制、析构、析构并回收内存以及返回 RTTI 等操作。 我们的主角 operator() 可能需要解释一下。

template<class _Fp, class _Alloc, class _Rp, class ..._ArgTypes>
_Rp
__func<_Fp, _Alloc, _Rp(_ArgTypes...)>::operator()(_ArgTypes&& ... __arg)
{
    typedef __invoke_void_return_wrapper<_Rp> _Invoker;
    return _Invoker::__call(__f_.first(), _VSTD::forward<_ArgTypes>(__arg)...);
}

它套了一个 __invoke_void_return_wrapper 类,它被定义在 __function_base 头文件中 312-372 行。

function 有这么个约定,模板参数中的返回类型不是强制要求相等的,只要能为 void 就可以接受任何参数类型相匹配的对象。因此这个 __invoke_void_return_wrapper 的作用就是当 function 模板参数中返回类型为 void 时丢弃 _Fp 对象 operator() 产生的值。

关于那几个调用了转发函数的地方,看起来像极了完美转发(不是),在后面和 function::operator() 一起解释。

std::function

从 1587 开始的 100 行,都是 function 类的定义。上文提到过,它的两个成员变量, __f_function 非空的时候永远指向 __func 对象,而 __buf_ 则在 __func 实体够小的时候储存 __func ,此时 __f_ 指向 __buf_

先看到 1600 行开始的一个模板结构体定义和特化:

  template <class _Fp, bool = __lazy_and<
      integral_constant<bool, !is_same<__uncvref_t<_Fp>, function>::value>,
      __invokable<_Fp&, _ArgTypes...>
  >::value>
  struct __callable;
  template <class _Fp>
      struct __callable<_Fp, true>
      {
          static const bool value = is_same<void, _Rp>::value ||
              is_convertible<typename __invoke_of<_Fp&, _ArgTypes...>::type,
                             _Rp>::value;
      };
  template <class _Fp>
      struct __callable<_Fp, false>
      {
          static const bool value = false;
      };

template <class _Fp>
using _EnableIfCallable = typename enable_if<__callable<_Fp>::value>::type;

其结构体本身是在后面用来限制构造函数参数类型的,用到了一个 SFINAE 惯用法。它只有在满足模板参数不得为 function 本身(防止嵌套 function 的情况出现,尽管会优先匹配到拷贝构造,默认情况下不会发生),以及模板参数对象可以被参数列表的类型所调用,还有返回类型为 void 或是可以转换为 function 模板参数中的返回类型的类型时才有一个为 true 的静态成员变量 value ,就可以用于 enable_if

1596-1598 行的 __as_base 函数,它的功能就是一个 reinterpret_cast ,之所以写成函数可能是函数参数的指针可以隐式转换成 void * ,这样就可以少写一个 cast 了吧(我自己实现的时候就这么搞的)。

构造、复制和析构

接下来介绍重点逻辑。按代码的顺序,首先是拷贝构造函数:

template<class _Rp, class ..._ArgTypes>
function<_Rp(_ArgTypes...)>::function(const function& __f)
{
    if (__f.__f_ == 0)
        __f_ = 0;
    else if ((void *)__f.__f_ == &__f.__buf_)
    {
        __f_ = __as_base(&__buf_);
        __f.__f_->__clone(__f_);
    }
    else
        __f_ = __f.__f_->__clone();
}

这个很简单:首先判断是不是空对象,然后判断 __func 是不是在 __buf_ 中,再不然就是直接从堆上分配新地址。

template<class _Rp, class ..._ArgTypes>
function<_Rp(_ArgTypes...)>::function(function&& __f) _NOEXCEPT
{
    if (__f.__f_ == 0)
        __f_ = 0;
    else if ((void *)__f.__f_ == &__f.__buf_)
    {
        __f_ = __as_base(&__buf_);
        __f.__f_->__clone(__f_);
    }
    else
    {
        __f_ = __f.__f_;
        __f.__f_ = 0;
    }
}

移动构造的逻辑也很简单,因为只是移动所以就是指针换个指向。唯一的例外就是作为缓存的 aligned_storage 由于可能会在退出作用域的时候伴随主体 function 一起被析构,所以当存在缓存中的时候必须要拷贝一份。

template<class _Rp, class ..._ArgTypes>
template <class _Fp, class>
function<_Rp(_ArgTypes...)>::function(_Fp __f)
    : __f_(0)
{
    if (__function::__not_null(__f))
    {
        typedef __function::__func<_Fp, allocator<_Fp>, _Rp(_ArgTypes...)> _FF;
        if (sizeof(_FF) <= sizeof(__buf_) && is_nothrow_copy_constructible<_Fp>::value)
        {
            __f_ = ::new((void*)&__buf_) _FF(_VSTD::move(__f));
        }
        else
        {
            typedef allocator<_FF> _Ap;
            _Ap __a;
            typedef __allocator_destructor<_Ap> _Dp;
            unique_ptr<__base, _Dp> __hold(__a.allocate(1), _Dp(__a, 1));
            ::new (__hold.get()) _FF(_VSTD::move(__f), allocator<_Fp>(__a));
            __f_ = __hold.release();
        }
    }
}

__function::__not_null 是一个模板重载函数,对于可调用对象、成员函数指针、函数指针和 function 本身进行了重载,判断是不是空。

在参数非空的情况下,当 __func 足够小到可以装入缓存,且拷贝构造满足 noexcept 的情况下,会直接在缓存原地构造。不满足的时候——没错,又用 unique_ptr 偷懒了。

几个赋值函数 operator= 不是用 swap 实现就是和上面几乎一样,没什么好说的,所以不如直接来看 swap 的逻辑:

template<class _Rp, class ..._ArgTypes>
void
function<_Rp(_ArgTypes...)>::swap(function& __f) _NOEXCEPT
{
    if (_VSTD::addressof(__f) == this)
      return;
    if ((void *)__f_ == &__buf_ && (void *)__f.__f_ == &__f.__buf_)
    {
        typename aligned_storage<sizeof(__buf_)>::type __tempbuf;
        __base* __t = __as_base(&__tempbuf);
        __f_->__clone(__t);
        __f_->destroy();
        __f_ = 0;
        __f.__f_->__clone(__as_base(&__buf_));
        __f.__f_->destroy();
        __f.__f_ = 0;
        __f_ = __as_base(&__buf_);
        __t->__clone(__as_base(&__f.__buf_));
        __t->destroy();
        __f.__f_ = __as_base(&__f.__buf_);
    }
    else if ((void *)__f_ == &__buf_)
    {
        __f_->__clone(__as_base(&__f.__buf_));
        __f_->destroy();
        __f_ = __f.__f_;
        __f.__f_ = __as_base(&__f.__buf_);
    }
    else if ((void *)__f.__f_ == &__f.__buf_)
    {
        __f.__f_->__clone(__as_base(&__buf_));
        __f.__f_->destroy();
        __f.__f_ = __f_;
        __f_ = __as_base(&__buf_);
    }
    else
        _VSTD::swap(__f_, __f.__f_);
}

首先第一个 if自赋值保护,未经检查的自赋值常常会拖慢效率,有可能会导致内存泄漏甚至更严重的问题,所以在这种涉及到复制的函数中都需要考虑。

由于两个相同类型的 function 可能保存着不同的可调用对象 __func ,接下来 libc++ 的逻辑按 __func 实体保存的位置分成了四个部分解决——自己和对方都在缓存中、只有自己在缓存中、只有对方在缓存中、两者都在堆上。

都在缓存中的情况,其实就是如何交换两个变量的问题,方法不过就是tmp = lhs; lhs = rhs; rhs = tmp; 交换内存,当然自己的 __func 需要手动析构。

只有一者在缓存中的情况,就是 __f_ 指针换一下,然后拷贝一下缓存即可。而都在堆中就最简单了,只需要交换指针 __f_ 即可, 不需要对 __func 本身进行任何操作。

调用和参数传递

template<class _Rp, class ..._ArgTypes>
_Rp
function<_Rp(_ArgTypes...)>::operator()(_ArgTypes... __arg) const
{
    if (__f_ == 0)
        __throw_bad_function_call();
    return (*__f_)(_VSTD::forward<_ArgTypes>(__arg)...);
}

这就是 operator() 的真面目了。首先肯定是判断 function 是否为空啦。然后调用由 __base 声明的 operator(),走虚表到 __func 中。

函数调用成员函数的主要工作是参数传递,对于传递给 function 对象的参数,要做到如果传递给原来的可调用对象,效果是一样的,最主要的是,它不能有多余的拷贝,但多余的移动一般不成问题。

最引人注目的应该是这一句 std::forward<_ArgTypes>(__arg)... ,看着很像是完美转发,然而函数参数却不是通用引用, _ArgTypes 实际上是 function 的模板参数而非编译器推导的类型,所以这里的 std::forward 其实这是为了解决“所有的具名变量都是左值”这一问题而已。

那么,回忆一下多态派生类的实现细节,对一个 function 对象的调用,传参流程大概是这样的——

  1. 从用户手中传参调用 function::operator() ,这时候对于引用类型的参数该怎么传递就怎么传递;对于非引用类型的参数就会出现一次构造,构造方式由参数的类型决定,传入同类型右值则移动构造,其它情况也是调用和传入类型对应的构造函数。
  2. function::operator() 调用 __base::operator() ,这里用的引用不是通用引用,就是普通的右值。它将原先的非引用类型也变成了右值引用,如此便可减少一次构造。
  3. 最后从 __func::operator() 调用原来的可调用对象,这时候对于非引用类型还会出现一次构造,此时的构造也是视 function 模板参数和所保存的可调用对象调用参数而定(再次提醒, function 模板参数可以和函数原型不同,只要满足各类型 convertible 即可)。如果不同则调用相应的隐式构造、转换函数,如果相同,那么就是引用就不动,非引用就移动构造(进入 __func 后已经成了右值)。

看得出来,如果 function::operator() 的参数也用引用可以再减少一次构造,不过既然 C++ 标准要求和模板参数对齐,实现也只能妥协。不过还好,在程序员没写错的情况下不会出现多余的拷贝构造,顶多多出几次移动构造,再加上大部分编译器都支持复制消除,实际上并不会有太多的额外开销。

发表评论