使模板化优化更易于维护

Question

有时候编译器可以通过使用模板化的内部实现来更好地优化代码不变量。例如，如果您知道图像中有固定数量的通道，那么可以使用以下方式进行优化：

Image::doOperation() {
    for (unsigned int i = 0; i < numPixels; i++) {
        for (unsigned int j = 0; i j mChannels; j++) {
            // ...
        }
    }
}

你可以这样做：

template<unsigned int c> Image::doOperationInternal() {
    for (unsigned int i = 0; i < numPixels; i++) {
        for (unsigned int j = 0; j < c; j++) {
            // ...
        }
    }
}

Image::doOperation() {
    switch (mChannels) {
        case 1: doOperation<1>(); break;
        case 2: doOperation<2>(); break;
        case 3: doOperation<3>(); break;
        case 4: doOperation<4>(); break;
    }
}

这使得编译器能够为不同的通道数生成不同的展开循环（从而大大提高运行时效率，并且还可以打开不同的优化，如SIMD指令等）。

然而，这通常会扩展到一些相当大的情况语句中，任何以这种方式进行了优化的方法都必须有展开的情况语句。假设我们有一个已知图像格式的enum Format（其中枚举的值恰好映射到通道数）。由于枚举只具有某个范围内的已知值，因此有一种诱惑去尝试这样做：

template<Image::Format f> Image::doOperationInternal() {
    for (unsigned int i = 0; i < numPixels; i++) {
        for (unsigned int j = 0; j < static_cast<unsigned int>(f); j++) {
            // ...
        }
    }
}

Image::doOperation() {
    const Format f = mFormat;
    doOperationInternal<f>();
}

然而，在这种情况下，编译器（理所当然地）抱怨f不是常量表达式，即使它只有有限的范围，在理论上，编译器也可以生成switch逻辑以覆盖所有枚举值。

那么，我的问题是：是否有一种替代方法，可以让编译器在不需要每个函数调用的switch-case爆炸的情况下生成恒定值优化的代码？

- fluffy

---

我认为你可以使用类似于boost::variant（即类型安全联合）的东西来接近解决问题。您仍然需要枚举所有要支持的“c”值，但该枚举更紧凑。我认为一般的解决方案是代码生成器。 - Adam

@Adam 我不确定 boost::variant 在这种情况下如何帮助... 你能否尝试构思一种方法并发布一个答案？ :) - fluffy

一个通道应该包含数百万个图像像素，因此我认为遍历所有通道的开销与处理每个通道的工作量相比微不足道。在你的“优化”之前和之后，你真的观察到了运行时性能上的实质性差异吗？ - nodakai

@nodakai 是的，这非常重要。这也是一种常见的优化方式。如果A很大，A*B对B很敏感，而A+B则不会。在每个像素操作中最内层的代码是乘法情况。 - Yakk - Adam Nevraumont

@BenVoigt 我将示例保持简单，因为我不想优化本身的实质成为我试图改进的障碍。 - fluffy

Answer 1

创建跳转表数组，然后调用。目标是创建一个包含各种函数的数组，然后进行数组查找并调用所需函数。

首先，我会用C++11来做。C++1y 包含自己的整数序列类型，并且有易于编写的auto返回类型：C++11版本将返回void。

我们的函数类大致如下：

struct example_functor {
  template<unsigned N>
  static void action(double d) const {
    std::cout << N << ":" << d << "\n"; // or whatever, N is a compile time constant
  }
};

在C++11中，我们需要一些样板代码：

template<unsigned...> struct indexes {};
template<unsigned Max, unsigned... Is> struct make_indexes:make_indexes< Max-1, Max-1, Is... > {};
template<unsigned... Is> struct make_indexes<0, Is...>:indexes<Is...> {};

创建并匹配索引包的模式。

接口如下所示：

template<typename Functor, unsigned Max, typename... Ts>
void invoke_jump( unsigned index, Ts&&... ts );

并且被称为：

invoke_jump<example_functor, 10>( 7, 3.14 );

我们首先创建一个助手：

template<typename Functor, unsigned... Is, typename... Ts>
void do_invoke_jump( unsigned index, indexes<Is...>, Ts&&... ts ) {
  static auto table[]={ &(Functor::template action<Is>)... };
  table[index]( std::forward<Ts>(ts)... )
}
template<typename Functor, unsigned Max, typename... Ts>
void invoke_jump( unsigned index, Ts&&... ts ) {
  do_invoke_jump( index, make_indexes<Max>(), std::forward<Ts>(ts)... );
}

这段代码创建了一个静态的Functor::action表，然后通过查找并调用它。

在C++03中，我们没有...语法，所以我们必须手动完成更多的事情，也没有完美的转发。因此，我将创建一个std::vector表代替。

首先，有一个可爱的小程序按顺序运行Functor.action<I>()其中I在[Begin, End)之间：

template<unsigned Begin, unsigned End, typename Functor>
struct ForEach:ForEach<Begin, End-1, Functor> {
  ForEach(Functor& functor):
    ForEach<Begin, End-1, Functor>(functor)
  {
    functor->template action<End-1>();
  }
};
template<unsigned Begin, typename Functor>
struct ForEach<Begin,Begin,Functor> {};

我必须承认这过于可爱了(链是由构造函数依赖项隐式创建的)。

然后我们使用它来构建一个vector。

template<typename Signature, typename Functor>
struct PopulateVector {
  std::vector< Signature* >* target; // change the signature here to whatever you want
  PopulateVector(std::vector< Signature* >* t):target(t) {}
  template<unsigned I>
  void action() {
    target->push_back( &(Functor::template action<I>) );
  }
};

我们可以将这两者连接起来：

template<typename Signature, typename Functor, unsigned Max>
std::vector< Signature* > make_table() {
  std::vector< Signature* > retval;
  retval.reserve(Max);
  PopulateVector<Signature, Functor> worker(&retval);
  ForEach<0, Max>( worker ); // runtime work basically done on this line
  return retval;
}

我们可以将跳转表构建为std::vector。

然后，我们可以轻松地调用跳转表的第I个元素。

struct example_functor {
  template<unsigned I>
  static void action() {
    std::cout << I << "\n";
  }
};
void test( unsigned i ) {
  static std::vector< void(*)() > table = make_table< void(), example_functor, 100 >();
  if (i < 100)
    table[i]();
}

当传递整数 i 时，它会打印该整数并换行。

表格中函数的签名可以是任何你想要的，因此你可以传递指向类型的指针并调用方法，其中I是编译时常量。 action方法必须是static的，但它可以调用其参数的非static方法。

C++03的主要区别在于您需要为跳转表的不同签名编写不同的代码，并且需要很多机制（以及一个std :: vector代替静态数组）来构建跳转表。

在进行严肃的图像处理时，您将希望以这种方式生成扫描线函数，并且可能嵌入了每像素操作在生成的扫描线函数的某个地方。 除非您的图像只有1像素宽并且高达10亿像素，否则每个扫描线执行一次跳转分发通常足够快。

上述代码仍需审核确保正确性：它是未经编译的。

- Yakk - Adam Nevraumont

---

我也对此感兴趣，但我没有完全理解你在做什么。你能否进一步扩展一下 @fluffy 的示例？ - Adam

我赞同@Adam的观点——看起来像是一个很好的答案，但是我真的不理解这个答案（我以为我在这方面相当有知识！）。另外，我更喜欢不需要C++11的东西（boost可以，但是我只能支持g++ 4.1）。 - fluffy

没有11是很困难的：细节更容易。我在出租车上写的，所以简要说明了一下。我可以用03来完成，但我们最终会得到一串if语句（可能是二叉树），只有当分支与工作相距较远且工作重复时才能良好运行。另一方面，初始低效的设置在运行时是否可接受？（因此慢速设置，快速分支？） - Yakk - Adam Nevraumont

@Adam 添加了更多的解释。包括C++03版本。C++03版本相当糟糕，但你能做什么呢？ - Yakk - Adam Nevraumont

C++11版本非常好，当我可以使用C++11时。不过，我认为@mattnewport的版本更好，因为易于理解、可移植性等方面（每次调用多出来的一点点开销并不需要担心——当它能够将内部循环的速度提高数倍时，谁会在意几个额外的分支呢？），但这仍然得到了我的+1，因为它教给了我很多我不知道的东西。 - fluffy

@fluffy 很好的观点 -- 我花了太多精力使其支持N种不同情况，而你只需要4种。 - Yakk - Adam Nevraumont

Answer 2

Yakk的C++11/1y技术很棒，但如果C++03版本对于您来说有点太过于模板技巧，那么有一个更简单/不太优雅的版本，至少避免了复制和粘贴开关语句，并且只需要维护一个开关语句。

#include<iostream>

using namespace std;

struct Foo {
    template<unsigned int c>
    static void Action() {
        std::cout << "c: " << c << endl;
    }
};

template<typename F>
void Dispatch(unsigned int c) {
    switch (c) {
    case 1: F::Action<1>(); break;
    case 2: F::Action<2>(); break;
    case 3: F::Action<3>(); break;
    }
}

int main() {
    for (int i = 0; i < 4; ++i)
        Dispatch<Foo>(i);
}

- mattnewport

---

这很可爱，我认为即使每个操作具有不同的参数计数（因为参数可以在操作构造函数中绑定），它也是可用的。无论如何，比我的当前#define hack要好得多。我可能最终会使用它。谢谢！ :) - fluffy

虽然在对象的方法中实际使用这个技巧有点棘手。你要么将对象作为self引用传递（并在外部操作），要么每个方法都有一个结构体，然后委托给方法本身。不过，这仍然是一种值得记住的好技巧。 - fluffy

Answer 3

仅为完整起见，这是我（暂时）采用的解决方案：

#define DISPATCH_TEMPLATE_CALL(func, args) do { \
    switch (mChannels) { \
    case 1: func<1> args; break; \
    case 2: func<2> args; break; \
    case 3: func<3> args; break; \
    case 4: func<4> args; break; \
    default: throw std::range_error("Unhandled format"); \
    } \
} while (0)

template<unsigned int n> void Image::doSomethingInternal(a, b, c) {
    // ...
}

void Image::doSomething(a, b, c) {
    DISPATCH_TEMPLATE_CALL(doSomethingInternal, (a, b, c));
}

显然这不是一个理想的方法。但它确实可以工作。

- fluffy