高性能异构容器

• 下载源代码 - 21.37 KB

目录

• 引言
• 现有解决方案
  • 经典多态
  • 类似联合的元素
  • 元组
  • 结论
• tek::record 实现
  • 所需技术背景
    • 类型列表
  • tek::record 静态部分
  • tek::record 动态部分
    • 引言
    • 实现
  • 深入的优化讨论
    • 边界检查消除
    • 伪可变参数行为的影响
      • 第一种方法
      • 第二种方法
    • 分支消除
• 用法
  • 构造函数
  • 成员函数
  • I/O 操作
  • 类型信息
  • tek::record 的配置
  • 非成员等价物
  • 仿函数定义
• 基准测试
  • 测试的解决方案
  • 性能测量方法
    • 类定义
    • 索引属性
    • 配置
    • 系统规格
  • 基准测试
    • 稳定配置
      • 平台 Visual C++
      • 平台 GCC
    • 不稳定配置
      • 平台 Visual C++
      • 平台 GCC
  • 结论
• 总体结论
• 参考文献
• 注释
• 历史

引言

异构容器是一种可以存储不同类型元素的容器。对于 C++ 这样的强类型语言，这种容器不是自然存在或内置的功能。尽管存在许多模拟这种异构特性的解决方案，但它们通常涉及内存空间或运行时速度的权衡。

本文介绍了一个固定大小的异构容器 tek::record，它试图在大小和速度方面都达到最佳性能。本文的目标不仅仅是列出 tek::record 的功能，而是解释此类解决方案的实现方式，从基本的模板元编程概念到高级优化技术。

现有解决方案

本章列出了实现异构容器最知名和最受欢迎的解决方案及其主要缺点。

经典多态

在经典的解决方案中，容器存储指向基类的指针，而多个类则继承自该基类。然后通过集合中每个元素的动态类型来实现异构特性。

限制

• 在这种情况下，虚函数无法内联
• 无法直接使用内置类型
• 丢失派生类的类型标识和特定特征

类似联合的元素

一个 union 容器可以模拟异构行为，因为联合的值可以通过多种类型来解释。然而，纯粹的联合存在严重限制

• 它们只接受受限类型
• 它们不是类型安全的
• 它们必须预留至少等于联合中最大类型大小的空间，导致异构容器中内存空间的浪费

类似联合的实现，例如带鉴别符的联合，已经出现以克服其中一些限制。这类实现的一个例子是 boost::variant。这类类似联合的实现也存在一些限制

• 仍然存在空间浪费
• 轻微的运行时开销，具体取决于具体实现。

元组

元组是有限元素的集合。在 C++ 中，元组的实现是一个固定大小的容器，可以容纳任何类型的元素。在这种实现中，元素访问是静态解析的，因此没有运行时开销。

限制

• 固定大小
• 无法动态访问元素

结论

我们回顾了一些流行的异构容器实现。此列表并非详尽无遗，还有其他解决方案（boost::any、void* 等），它们也存在上述一些限制。在检查每种解决方案的缺点时，我们可以注意到元组与其他解决方案之间存在某种差距

• 元组在速度和内存方面都是最佳的，但功能非常少，且不提供动态访问。因此，它的用途非常有限，例如模拟多个返回值。
• 其他解决方案较慢，但允许标准和动态容器操作。

tek::record 容器试图通过提供良好的性能和动态访问其元素来部分弥补这一差距。

tek::record 实现

所需技术背景

在解释异构容器的实现之前，必须简要回顾一下 typelist 的概念。如果您已经知道 typelist 是什么，您可以直接跳到 下一节。

类型列表

typelist 是一种包含一定数量类型的类型。它的实现基于以下模板结构

template < typename T, typename U >
struct typelist {
  typedef T element_type;
  typedef U next_type;
};

为了定义可变数量的不同类型，typelist 结构递归声明如下

typedef
typelist< int,
          typelist < char,
                 typelist < MyClass,
                        end_of_list > > > MyTypelist;

上面的声明定义了一个包含三种类型的列表：int、char、MyClass。列表以一个特殊的结构 end_of_list 终止，该结构充当结束标记。乍一看，对类型的简单访问如下所示

MyTypelist::element_type // int
MyTypelist::next_type::element_type // char
MyTypelist::next_type::next_type::element_type // MyClass

然而，为了使其有用且方便，必须以通用方式（使用索引）访问类型。这种访问的实现是递归的：通过 next_type 类型遍历给定索引次数。

template < class T, int INDEX >
struct get_type {
    typedef typename get_type < typename T::next_type,
                                INDEX-1 >::type type;
};
template < class T >
struct get_type < T, 0 > {
    typedef typename T::element_type type;
};

有了递归的 get_type 结构，我们现在可以使用静态索引访问类型

get_type < MyTypelist, 0 >::type;
// generates: MyTypelist::element_type

get_type < MyTypelist, 2 >::type;
// generates: MyTypelist::next_type::next_type::element_type

现在我们对 typelist 有了足够的了解。请注意，我们省略了它们的一些功能。有关更多详细信息，请参阅 参考文献中的 [Alexandrescu]。

tek::record 静态部分

正如我们在 现有解决方案章节 中看到的，元组比其他异构容器具有一些性能优势。它们不浪费内存空间 ¹，并且访问元素速度非常快。为了达到这种性能，元组的经典实现依赖于遵循 typelist 思想的模板结构。

示例

template < typename T, typename U >
struct tuple {
    T element;
    U next;

    typedef T element_type;
    typedef U next_type;

};

可以为结构指定任意数量的类型

tuple< int,
       tuple < std::string,
               tuple < MyClass,
                       end_of_list > > > >

这样的声明大致会翻译成以下内容（不包括 typedefs）

struct tuple<...> {
    int element;  //first element
    struct tuple<...> {
        std::string element; // second element
        struct tuple<...> {
            MyClass element; // third element
            end_of_list next;
        } next;
    } next;
};

元组定义了两种索引访问方式，这两种方式都是静态执行的

• 元素类型的索引访问
• 元素值的索引访问

列表中元素类型的索引访问与我们之前看到的 typelist 实现中使用的 get_type 结构相同。元素值的索引访问是通过递归函数完成的

template< int INDEX, typename return_type >
struct get_element {
    template< class T >
    static return_type Do( T& tup )
    {
        return get_element< INDEX-1, return_type >::Do( tup.next );
    }
};

template< typename return_type >
struct get_element< 0, return_type > {
    template< class T >
    static return_type Do( T& tup )
    {
        return tup.element;
    }
};

现代编译器能够内联递归函数，就好像值被直接访问一样。return_type 模板参数是通过使用 get_type 结构计算的。实际上，计算 return 类型更为复杂，因为我们可能会添加或删除引用和常量限定符。例如，如果 tek::record 被声明为常量，我们应该 return 一个常量。

tek::record 动态部分

引言

元组的实现是一个高性能、固定大小异构容器的良好基础。但是，元组不提供对其元素的动态访问。这是很自然的：像 myTuple[x] 这样的表达式，其中 x 是运行时给定的索引，编译器应该生成什么代码，因为类型必须与 x 一起在运行时确定？如果它是 int、std::string 或用户定义的类，代码可能会有所不同。由于像 myTuple[x] 这样的简单表达式无法由编译器评估，因此动态访问将通过一个名为 apply 的函数完成，该函数接受两个参数

• 用户提供的仿函数，将应用于索引元素
• 一个索引

仿函数充当访问者 ²，应为每种元素类型重载函数。

示例

myTuple.apply( Print(),index );

仿函数定义

struct Print {
    void operator()( int element )
    {
        std::cout << "int : " << element << endl;
    }
    void operator()( double element )
    {
        std::cout << "double : " << element << endl;
    }
    void operator()( char element )
    {
        std::cout << "char : " << element << endl;
    }
};

element 参数将由 apply 函数提供。当然，如果源代码对于某些或所有类型都是相同的，则可以使用模板函数来分解源代码。

实现

这种动态访问的实现必须生成每种类型的每种可能的代码，并根据索引的运行时值选择正确的代码。选择可以通过简单的 if then else 链或 switch case 语句完成。

使用 switch 的示例（伪代码）

template < class T >
void apply ( int index, T functor )
{
  switch ( index ) {
    case 0 : functor ( tuple[0] ); break; // tuple[0] is an int
    case 1 : functor ( tuple[1] ); break; // tuple[1] is a std::string
    ...
  }
}

注意：tuple[x] 是伪代码。实际上，我们必须使用 get_element 结构。

这种实现无非是一种类型切换，在面向对象的世界中，类型切换被认为是不好的，因为它会引入耦合：每次添加新类型时，都必须相应地修改 switch。然而，对于我们的实现来说，这并不是一个缺点，因为我们可以自动适应提供给记录的类型的类型切换。确实，如果使用级联 if then else 实现类型切换，这很容易做到。一个“递归”模板结构将遍历 typelist 并为每种类型添加一个 if 条件以及正确的代码。最后，编译器生成的代码将类似于

if (index == 0)
  //code for tuple[0]
else
  if (index == 1)
    //code for tuple[1]
  else
    if (index == 2)
      // code for tuple[2]
...

以这种方式找到正确的索引会产生 O(n) 的复杂度。可以生成搜索算法来降低复杂度，但性能仍然取决于异构容器处理的类型数量。备选解决方案是使用 switch case 语句。虽然这种语句的行为与我们使用的 if then else 相同，但编译器生成的实现可能因 case 值而异。

例如，假设我们要测试 0 到 3 的值范围。我们可以使用 switch 测试所有值

switch (x) {
 case 0 : ...
 case 1 : ...
 case 2 : ...
 case 3 : ...
}

上面的 switch 语句可以通过一个体面的 C++ 编译器进行优化，方法是构建一个 jump 表。该表包含每个 case 语句的指令地址。然后使用 x 值作为 jump 表的索引。因此，编译器生成的代码只是一个 jump，其操作数是 jump 表中由索引指向的值，这大致给出了以下代码指令

JUMP ADDR_TABLE[ x ];

jump 表的性能复杂度是恒定的，并且大多数时候优于 if then else 方法 ³。为了能够构建 jump 表，case 值必须是连续的 ⁴。测试我们异构容器的每个可能索引都满足此条件。因此，我们的容器中使用 switch case 方法来实现动态访问。但是，使 case 的数量适应给定的 record 类型列表更困难（参见 伪可变参数行为的影响 部分）。

深入的优化讨论

边界检查消除

由于我们处于固定大小容器的上下文中，因此越界检查有时可能是多余的，应该留给用户（参见使用章节中的 is_valid_index 函数）。但是，编译器始终进行边界检查以检查索引对于 jump 表是否有效。Visual C++ 提供了特定于编译器的关键字 __assume，因此程序员可以指定索引保证是 case 值之一。然后编译器可以决定不进行边界检查。

switch (x) {
 case 0 : ...
 case 1 : ...
 case 2 : ...
 default : __assume(0); // x = 0 , 1 or 2, nothing else
}

我不知道其他编译器是否支持此类关键字。在撰写本文时，GCC 不支持此类编译时假设。因此，__assume(0) 仅用于 Visual C++，其他编译器可能会检查边界。如您所见，本小节的标题是“边界检查消除”，它指的是某些语言（如 Java）中的编译器优化，可在访问数组元素时消除边界检查，而不以任何方式修改程序的完整性和行为。 ⁵ 因此，apply 函数应在索引有效性得到保证时使用。如果无法保证索引有效性，则应在调用 apply 函数之前调用 is_valid_index 函数。

伪可变参数行为的影响

C++ 语言的当前版本不支持可变参数模板，尽管在我们的情况下这是一个可取的特性。用户应该能够轻松地编写

record < int, char > a; // 2 elements
record < int, char, double, std::string > b; // 4 elements

而不是使用递归方式

record < int, < record char < record double , etc.

为了模拟可变参数模板，使用了默认模板参数。默认模板参数是 null_type，它是一个“虚拟类型”，不包含任何数据，并且充当 typelist 的结束标记。

template < class T0 = null_type,
       class T1 = null_type,
       class T2 = null_type,
       class T3 = null_type >
struct record {};

用户随后可以指定任意数量的参数，直到某个限制（示例中为 4）。此限制最终可以通过宏（参见使用章节）进行参数化。在内部，所有这些模板参数都转换为元组

tuple< T0, tuple < T1, tuple < T2,  T3 > > >

使用这种限制会导致我们的 apply 函数中的 switch 语句出现编译问题。与级联 if then else 不同，我们无法使用递归模板结构来生成正确数量的 case 语句。因此，我们必须实现 apply 函数，以便 case 的数量始终等于 record 可以处理的最大类型数。假设我们将此限制设置为 4，我们的 apply 函数将如下所示

template < class T >
void apply ( int index, T functor )
{
  switch ( index ) {
    case 0 : functor ( tuple[0] ); break;
    case 1 : functor ( tuple[1] ); break;
    case 2 : functor ( tuple[2] ); break;
    case 3 : functor ( tuple[3] );
  }
}

如果用户声明了一个 record< int , char >，则最后的 2 个 cases 会导致编译错误。有两种方法可以解决此问题。

第一种方法

我们可以使用一个封装每个 case 的结构，并在 x 小于 record 处理的类型数时生成 functor( tuple[x] )，否则生成空。

示例

case 0 : SilentCase< 0 > ( tuple, functor ); // generates functor( tuple[0] );
case 3 : SilentCase< 3 > ( tuple, functor ); // generates nothing

但仍然存在两个性能问题

• 编译器生成的 jump 表始终包含 4 个成员（在我们的示例中），而根据指定给 record 的类型数量，它可以包含更少。这是一个次要但确实存在的空间浪费。
• 因为 case 的数量可能较低，所以编译器可能会错过一些优化，因为当 case 非常少时，可以使用比 jump 表更好的优化。整个 apply 函数也可能更容易内联。

第二种方法

为了克服最后两个问题，我们必须将 switch 语句中的 case 数量调整为 record 处理的类型数量。但是，如前所述，我们无法使用递归结构来添加正确数量的 case 语句，正如使用 if then else 链一样。技巧是生成所有可能的 apply 函数，每个函数都有不同的 case 数量。为了在编译时选择正确的函数，我们将所有这些函数包装在一个结构中。后者接受一个 int 模板参数，该参数将用于指示 case 的正确数量。

示例（伪代码）

template < int I >
struct apply_select;

template <>
struct apply_select < 2 >
{
  static void apply ( int index, T functor )
    {
      switch ( index ) {
        case 0 : functor ( tuple[0] ); break;
        case 1 : functor ( tuple[1] ); break;
      }
};

template <>
struct apply_select < 3 >
{
  static void apply ( int index, T functor )
    {
      switch ( index ) {
        case 0 : functor ( tuple[0] ); break;
        case 1 : functor ( tuple[1] ); break;
        case 2 : functor ( tuple[2] ); break;
      }
};

...

在 record 实现中，以这种方式调用正确的 apply 函数

apply_select< record_size >::apply( index, functor );

这样，只有具有正确 case 数量的 apply 函数才会被编译器实例化和生成。

分支消除

我们之前看到，仿函数用作 apply 函数的参数。该仿函数可以为 record 处理的每种类型定义一个特定的 operator()，但有时，您可能希望进行通用处理并使用模板 operator()。例如，假设异构容器的每种类型都有一个名为 data 的数据成员。可以通过以下仿函数定义通用过程

struct MyFunctor {
  template < class T >
  void operator()( T& element )
  {
    process( element.data );
  }
};

通用过程很有趣，因为它们可能允许编译器进行额外的优化，关于 apply 函数中的 jump 表。此优化包括通过合并 case 来消除分支。

例如，考虑以下代码

switch (x) {
  case 0 : foo(); break;
  case 1 : foo(); break;
  case 2 : bar(); break;
  case 3 : bar(); break;
  case 4 : bar(); break;
}

我们看到这样的代码会导致编译器生成一个 jump 表

伪生成的代码

jump JUMP_TABLE[x]

label_case_0 : call foo ...
label_case_1 : call foo ...
label_case_2 : call bar ...
label_case_3 : call bar ...
label_case_4 : call bar ...

JUMP_TABLE 内容

index	标签地址
0	&label_case_0
1	&label_case_1
2	&label_case_2
3	&label_case_3
4	&label_case_4

应用分支消除的编译器将生成以下代码，而不是

伪生成的代码

jump JUMP_TABLE[x]

label_case_foo : call foo ... // 2 cases merged
label_case_bar : call bar ... // 3 cases merged

JUMP_TABLE 内容

index	标签地址
0	&label_case_foo
1	&label_case_foo
2	&label_case_bar
3	&label_case_bar
4	&label_case_bar

这有很多优点，因为

• 它减小了代码大小并有利于 apply 函数的内联。
• 它减少了分支目标的数量，这可能带来性能提升。
• 因为它减少了分支数量，所以它可能允许编译器使用比 jump 表更好的优化。

MyFunctor 的模板 operator() 似乎对 record 的每个元素应用相同的代码。然而，编译器生成的代码需要包含每个元素的地址，因此它可能实际上有所不同。

为了理解这个问题，让我们看看 apply 函数是如何工作的。后者在内部调用另一个函数，该函数将 record 数据作为附加参数。这是这个 internal 函数的声明

template < class T, class U >
apply_internal( T& record_data, int index, U& functor)
{
  switch( index ) {
    ...
  }
}

record_data 实际上包含所有元素，并且基本上具有与元组相同的结构。由于我们将元组的地址传递给 apply_internal 函数，因此生成的代码将通过应用不同的偏移量 **从** record_data 参数引用每个 case 对应的元素

template < class T, class U >
apply_internal( T& record_data, int index, U& functor)
{
  switch( index ) {
    case 0 : &record_data // generated address of the 1st element
    case 1 : &record_data + 12 // ... 2nd element
    case 2 : &record_data + 26 // ... 3rd element
...
  }
}

但是，如果我们直接传递已关注元素的地址而不是整个元组，编译器将不得不为每个 case 处理相同的引用

template < class T, class U >
apply_internal( T& element, int index, U& functor)
{
  switch( index ) {
    case 0 : &element
    case 1 : &element
    case 2 : &element
  }
}

为了在转到 apply_internal 函数之前知道索引指向的元素的地址，我们必须在构建 record 时将每个元素地址存储在 void* 数组中。然后 apply 函数加载元素的地址并将其用作 apply_internal 函数的参数

template < class U >
void apply (int index, U& functor )
{
  apply_internal< record_type >( addrTable[index], x, functor )
}

而 apply_internal 定义如下

template < class record_type, class U >
void apply_internal( void* element, int index, U& functor)
{
  switch( index ) {
    case 0 : functor ( * (typename get_type< record_type, 0 >::Type *>) // C-style cast
                                    element );
             break;
    case 1 : functor ( * (typename get_type< record_type, 1 >::Type *>)
                                    element );
             break;
  }
}

然而，这种方法有几个缺点

• 它会产生开销：在开始时构建地址表，并且每次访问时查找元素的地址
• 它只在少数上下文中触发，其中代码对于某些或所有元素是相同的
• 如果编写代码时不知道某些或所有类型，则可能无法确定代码是否对它们是相同的。即使它们是已知的，也可能出现一些误导性的情况。例如，在本章开头，我们定义了仿函数 MyFunctor，它对元素的数据成员执行通用处理：process(element.data)。即使 element.data 对于所有元素类型相同，但对于每个元素类型，该数据成员的偏移量可能不同，这会阻止 case 合并。

这就是为什么此优化默认禁用。可以通过定义 TEK_RECORD_MERGE_APPLY 宏（参见使用章节）来启用它，但它应保留用于实验或性能分析目的。

用法

本节列出了 tek::record 的功能。首先，这里有一个简单的例子来说明 tek::record 的基本用法

#include "tek/record.h"

#include <iostream>
using namespace std;

// we define a functor whose the job is to increment an element.
struct Inc {
  template < class T >
  void operator()( T& element ) const
  {
    element++;
  }
};

int main()
{
  tek::record< int, char, double > myRecord( 2, 'r', 5.25 );
  cout << myRecord;              // prints: (2 r 5.25)
  cout << myRecord.get<1>();     // prints: r
  myRecord.get<0>() = 10;        // 2 is replaced by 10
  myRecord.for_each( Inc() );    // Increment each element
  cout << "Enter the index of the element you want to increment :"
       << endl;

  int index ;
  cin >> index;

  if ( myRecord.is_valid_index( index ) )
    myRecord.apply( Inc(), index );
  else
    cout << "Invalid index entered";

  return 1;
}

以下是 tek::record 支持的操作的完整列表。请注意，没有操作会抛出异常。

构造函数

• template < class T0 ,..., class Ti >
tek::record()

  构造一个未初始化元素的 record。

• template < class T0 ,..., class Ti >
tek::record( const T0& a0 ,..., aj )

  构造一个已初始化前 j 个元素的 record。

  示例

  tek::record< char, int > myRecord( 'e', 3 ) // all elements initialized
  tek::record< char, int > myRecord( 'w' ) // the first element is initialized    

成员函数

• template< int I >
return_type& at< I >()

  返回位于索引 I 处的元素的引用。由于索引是通过模板参数给出的，因此无法在运行时确定。使用 apply 函数使用动态索引。

• template< class T >
void for_each( T& f )

  将仿函数 f 应用于 record 的每个元素。

• template< class T >
void apply( T& f, const unsigned int x )

  将仿函数 f 应用于位于索引 x 处的元素。注意：如果 x 是无效索引，则行为未定义。

• static bool is_valid_index( const unsigned int x )

  如果 x 是用于 apply 函数的有效索引，则返回 true，否则返回 false。

• template< class B, class T >
void for_interface( T& f )

  将仿函数 f 应用于类型为 B 或继承自基类 B 的元素。

I/O 操作

这些操作非常基础，不使用操纵器。它们主要提供用于测试其他 record 功能。I/O 操作将来可能会完全支持。

• template < class T0 ,..., class Ti >
std::ostream& operator<<( std::ostream& o, record < T0 ,..., Ti >& )

  以 (a0 a1 a2 ... ai) 的格式将 record 打印到输出流。

• template < class T0 ,..., class Ti >
std::istream& operator>>( std::istream& i, record < T0 ,..., Ti >& )

  以 (a0 a1 a2 ... ai) 的格式从输入流读取 record。

类型信息

• record< ... >::size

  返回 record 处理的类型数。

  示例

  typedef tek::record< int, char, double > MyRecordType;
  MyRecordType myRecord;
  myRecord.size // = 3
  MyRecordType::size // = 3

• record< ... >::element< I >::type

  返回由索引 I 指定的 record 的类型之一。

  示例

  typedef tek::record< int, char, double > MyRecordType;
  MyRecordType::element< 1 >::type // equivalent to char.

tek::record 的配置

record 的实现可以通过 tek/config/record_config.h 文件中的三个宏进行配置。

• #define TEK_RECORD_MAX_PARAMS

  定义 tek::record 可以处理的最大类型数
  -> 默认定义为 20

• #define TEK_RECORD_NO_IO

  禁用 iostream 运算符支持，阻止包含 <iostream> 头文件
  -> 默认未定义

• #define TEK_RECORD_MERGE_APPLY

  提供对 merge_apply 函数的访问。merge_apply 函数具有与 apply 函数相同的 interface，但实现不同，如果提供的仿函数对某些或所有元素执行相同的处理，则可能带来性能提升。它在其他方面会导致性能下降。定义宏还会降低 record 构造函数的性能并增加 record 大小。
  -> 默认未定义

非成员等价物

如果 record 类型是依赖名称，则需要显式模板参数的成员函数和结构必须以 template 关键字作为前缀。

示例

template < class T>
void f( T& myRecord )
{
  // myRecord.get<1>(); // error on some compilers
  myRecord.template get<1>(); // ok
}

只有支持双阶段名称查找的编译器，例如 GCC，在缺少 template 关键字时才会发出错误。这类编译器会解析模板函数 f，即使 f 没有被实例化。在解析过程中，编译器不知道 myRecord 的类型，因此也不知道 get 是一个模板函数，所以您必须添加 template 关键字，以便它可以正确地区分 < >（然后它将被识别为模板参数列表的分隔符，而不是小于/大于运算符）。一些编译器，例如 Visual C++ 8，只在模板函数实例化时才对其进行查看，此时它知道 get 是一个 template 成员函数，因此不需要 template 关键字。template 关键字很容易被遗忘，特别是如果使用 tek::record 的程序需要跨多个编译器移植。

因此，每个成员函数和结构都有一个非成员的等价物，以便更容易编写可移植代码。为了保持一致性，所有成员函数都有一个非成员的对应项，它们具有相同的名称和相同的参数列表，并在列表开头添加了一个 record 参数

myRecord.get< 0 >();
tek::get< 0 >( myRecord );

myRecord.for_each( myFunctor() );
tek::for_each( myRecord, myFunctor() );

myRecord.apply( myFunctor(), index );
tek::apply( myRecord, myFunctor(), index );

仿函数定义

在大多数情况下，用作 apply 函数参数的仿函数是一个临时对象

tek::apply( myRecord, myFunctor() );

如果是这样，operator() 函数的 const 限定符不得被忘记

struct MyFunctor {
  template < class T >
  void operator()( T& element ) const
  {
    ....
  }
}

为了模拟参数传递，您可以使用仿函数的构造函数

struct MyFunctor {
  MyFunctor(int arg) : arg_(arg) {}

  template < class T >
  void operator()( T& element ) const
  {
    // some computings with arg_
  }

  int arg_;
}

...

tek::apply( myRecord, myFunctor( 2 ) );

为了从 apply 函数返回值，仿函数必须继承自 tek::return_type 结构，该结构以所需的 return 类型作为模板参数。每个 operator() 都必须 return 相同的类型

struct Inc : public tek:return_type< int > {
  template < class T >
  int operator()( T& element ) const
  {
    ....
  }
}

基准测试

测试的解决方案

我测量了三种异构容器的动态分派性能

• tek::record
• boost::variant 数组
• 使用基类指针的经典多态数组

性能测量方法

每个基准测试在某种程度上都有欺骗性。在本节中，我尽量通过提供有关我如何操作的详细信息来限制这一点。

首先，由于容器处理的元素数量可能会影响性能，因此我用 2 到 20 个元素对每个容器进行了基准测试。每个元素类型都是一个继承自通用 abstract 基类的不同类，该基类声明了一个名为 foo 的纯虚函数。每个类都实现了 foo 虚函数。我测量了调用 foo 的性能，这为每种解决方案提供了不同的陈述

• 多态:
  container[index]->foo();

• boost:variant:
  boost::apply_visitor( Visitor(), container[index] );

• tek::record:
  container.apply( Functor(), index );

对于 variant 和 record 解决方案，我们需要使用一个仿函数，分别在我们的示例中称为 Visitor 和 Functor，它以完全相同的方式为两种解决方案实现 operator()

template 
void operator()(const T& element) const
{
    element.T::foo();
}

注意：因为在我们的例子中，按引用传递比按值传递更快，所以参数是 const T& element。但是，如果我们直接使用 element.foo()，编译器很可能会生成一个虚拟查找，element 是一个引用。然后我们使用 element.T::foo() 的形式，以便对 foo 的调用是静态绑定的。

类定义

对于每个类，foo 函数执行一些算术运算。因为 foo 的大小非常小，所以它会被系统地内联，前提是解决方案的调度机制允许它。

我测试了两种配置

• 每个类的 foo 实现都不同。
• foo 的实现对于一半的类是相同的。然后 merge_apply 函数可以应用其优化。

索引属性

索引在运行时确定。由于 foo 的调用是在循环中执行的，因此我决定测试两种索引

• 一个稳定的索引，在所有迭代中都保持不变。注意，这个稳定的索引不是一个常量，它在运行时一次性确定。
• 一个随机索引，在每次迭代中都会改变。随机索引被预取到一个数组中，因此循环只需要遍历该数组即可为每次循环获得一个随机索引。

我们不仅仅使用随机索引，因为使用这种索引的性能很大程度上取决于 CPU 及其分支预测单元，并且可能会出现重要变化。例如，我的机器是一台 Pentium 4 Prescott，具有 31 个阶段的流水线。错误的が分支预测会导致该流水线刷新，从而显著降低性能。稳定的索引消除了这些变化，因为采取的分支始终相同。此外，稳定的索引不会真正偏向一种解决方案而不是另一种，因为所有三种解决方案都使用无条件跳转，并且分支目标不是立即数，来实现其调度机制。

配置

最后，为了减少图的数量，我只使用了两种配置来测量性能

• 稳定配置：稳定索引 + 每个类的 foo 的唯一实现
• 不稳定配置：随机索引 + 一半类的 foo 的相同实现

系统规格

基准测试是在 Intel Pentium 4 3Ghz HT、1 Gb RAM 上进行的。测试了 2 个“平台”

• 平台 Visual C++
  操作系统：Windows XP sp2
  编译器：Visual C++ 8.0
  优化标志：/Ox /GL

• 平台 GCC
  操作系统：gentoo linux 2.6.19
  编译器：GCC 4.1.1
  优化标志：-O3

基准测试

稳定配置

平台 Visual C++

boost::variant 解决方案始终是最慢的，因为 Visual C++ 无法内联 boost::apply_visitor 函数。后者使用一个 switch 语句，该语句生成一个 jump 表，类似于 tek::record 解决方案，但它没有调整 case 的数量（参见 伪可变参数行为的影响 部分）。因此，它始终有 20 个 case，这对应于 boost:variant 可以处理的默认最大类型数。

tek::apply 解决方案在处理 9 个类型之前是最佳的。在 9 个类型时，Visual C++ 编译器认为 tek::apply 函数变得太大，选择不再内联它，导致性能下降。此时，虚调用是性能最佳的解决方案，仅略微领先。

平台 GCC

总的来说，GCC 比 Visual C++ 更积极地内联，使用给定的优化标志。boost::variant 解决方案在类型数量很少的情况下存在一些性能问题。事实上，正如我们所见，boost::variant 始终使用 20 个 case 的 switch 语句，但未使用的 case 会执行一些默认过程，其代码大小大于虚函数 foo。因此，使用的 case 越少，boost::apply_visitor 的代码大小就越大。因此，最多 5 个元素，GCC 不会内联 apply_visitor 函数。tek::apply 函数始终被内联。从 2 到 4 种类型，GCC 不使用 jump 表来实现 switch case 语句，而是更倾向于使用 if then else 方法。但是，我必须说，使用这种方法会导致额外的优化，这是稳定索引的一个副作用。事实上，tek::apply 函数在循环中执行，并且当使用 if then else 方法时，算法如下

for ( ... )
{
  if (stable_index == 0)
   apply_to_the_first_element
  else
   apply_to_the_second_element
  ...
}

然而，if 条件是不变的，因为 stable_index 本身也是一个不变量。因此，GCC 能够将代码转换为以下形式

if (stable_index == 0)
  for ( ... ) {
   apply_to_the_first_element
  }
else
  for ( ... ) {
   apply_to_the_second_element
  }
...

即使没有这种进一步提高四种类型处理性能的优化，tek::record 在这里也始终是最佳解决方案。

不稳定配置

平台 Visual C++

正如预期的那样，每种解决方案的性能在随机索引下是不稳定的。因为 merge_apply 函数合并了一些 case，所以它可以比 apply 函数更长地内联，从而在 8 到 12 种类型之间提供比后者更高的性能。

平台 GCC

GCC 为 tek::merge_apply 函数生成的代码包括 case 合并，但似乎对我的系统效率不高。它比 boost::variant 慢，后者也允许通过 case 合并进行分支消除（因为 boost::apply_visitor 接受索引元素作为参数）。总体而言，tek::apply 函数在这里是最好的。

结论

关于动态分派性能，tek::record 在几乎所有测试的上下文中都比 boost::variant 容器快。这主要是由于一些实现细节，因为两者都使用 switch case 语句，但从本质上讲，tek::record 也应该比带鉴别符的联合容器稍快，因为它直接访问其元素。与测试编译器实现的虚调用机制相比，tek::record 大多数时候更快，除了 Visual C++ 在大型多态 ⁶ 的情况下。然而，基准测试并没有测试所有可能有利于一种解决方案胜过另一种的情况。特别是，没有考虑大尺寸的虚函数，这有时可能有利于基本的虚调用，如果它阻止内联。虚函数的实现也可能根据编译器进行优化，但在当今的 C++ 编译器世界中，此类优化非常稀少。然而，尽管这些受到其静态性质的限制，但是基于配置文件的编译允许在这一领域进行新的优化，例如虚调用推测 ⁷。基准测试仅测量了基本虚函数实现的性能。

总体结论

tek::record 是一个固定大小的异构容器，它提供功能相对有限。然而，它同时具有以下特点

• 高性能动态分派
• 低内存空间消耗
• 类型身份保留

参考文献

[Alexandrescu]：“Modern C++ Design: Generic Programming and Design Patterns Applied”，Andrei Alexandrescu - Addison Wesley, 2001

注释

[1] ^ 不考虑数据结构填充

[2] ^ 访问者模式

[3] ^ 如果 switch 中的 case 非常少，则 jump 表不再是最快的实现：在这种情况下，编译器可能会使用另一种方法来实现 switch case。

[4] ^ 一些编译器对值必须连续的容忍程度不同。

[5] ^ 例如，如果用于访问数组中某个元素的索引在早期计算方式下，在任何情况下都将是一个有效的索引，那么编译器就可以应用边界检查消除并直接使用该索引：这不会影响程序的正确性。

[6] ^ Megamorphism = 具有大量类型的多态。

[7] ^ 虚拟调用推测是 Visual C++ 8 提供的 基于配置文件的引导优化 之一。

历史

• 24-02-2008:
  • 许可从 GPL 更改为 CPOL
  • [文章] 添加了关于 Visual C++ 内联策略的小解释（平台 Visual C++ 部分）
  • [文章] 修正了 get_type 代码（类型列表 部分）
  • [文章] 修正了仿函数代码以说明 return_type 功能（仿函数定义 部分）
• 2008-01-30：初始版本