优化交换机的模板替换 [英] Optimize template replacement of a switch

问题描述

我的一个项目中有很多自定义数据类型，它们都共享一个公共基类.

I have a lot of custom datatypes in one of my projects which all share a common base class.

我的数据(来自数据库)有一个数据类型，它通过基类的枚举来区分.我的架构允许特定数据类型专门用于派生类，或者可以由基类处理.

My data (coming from a database) has a datatype which is distinguished by an enum of the base class. My architecture allows a specific datatype to be specialized with a derived class or it can be handled by the base class.

当我构造一个我的特定数据类型时，我通常直接调用构造函数:

When I construct one my specific datatypes I normally call the constructor directly:

Special_Type_X a = Special_Type_X("34.34:fdfh-78");
a.getFoo();

有一些模板魔术也允许像这样构造它:

There is some template magic which also allows constructing it like this:

Type_Helper<Base_Type::special_type_x>::Type a =  Base_Type::construct<Base_Type::special_type_x>("34.34:fdfh-78");
a.getFoo();

对于 enum 类型的某些值可能没有专门化，所以

For some values of the type enum there might be no specialization so

Type_Helper<Base_Type::non_specialized_type_1>::Type == Base_Type

当我从数据库中获取数据时，编译时不知道数据类型，因此有第三种方法来构造数据类型(来自 QVariant):

When I'm fetching data from the database the datatype isn't known at compile time so there's a third way to construct the datatypes (from a QVariant):

Base_Type a = Base_Type::construct(Base_type::whatever,"12.23@34io{3,3}");

但当然我希望调用正确的构造函数，因此该方法的实现看起来像:

But of course I want the correct constructor to be called, so the implementation of that method used to look like:

switch(t) {
     case Base_Type::special_type_x:  
        return Base_Type::construct<Base_Type::special_type_x>(var);

     case Base_Type::non_specialized_type_1:  
        return Base_Type::construct<Base_Type::non_specialized_type_1>(var);              

     case Base_Type::whatever:  
        return Base_Type::construct<Base_Type::whatever>(var);     

     //.....
}

这段代码是重复的，因为基类也可以处理新类型(添加到枚举中)，我想出了以下解决方案:

This code is repetitive and since the base class can handle new types (added to the enum) as well, I came up with the following solution:

// Helper Template Method
template <Base_Type::type_enum bt_itr>
Base_Type construct_switch(const Base_Type::type_enum& bt, const QVariant& v)
{
  if(bt_itr==bt)
    return Base_Type::construct<bt_itr>(v);
  return construct_switch<(Base_Type::type_enum)(bt_itr+1)>(bt,v);
}

// Specialization for the last available (dummy type): num_types
template <>
Base_Type construct_switch<Base_Type::num_types>(const Base_Type::type_enum& bt, const QVariant&)
{
  qWarning() << "Type" << bt << "could not be constructed";
  return Base_Type(); // Creates an invalid Custom Type
}

我原来的switch语句被替换为:

And my original switch statement is replaced with:

return construct_switch<(Base_Type::type_enum)0>(t,var);

此解决方案按预期工作.

This solution works as expected.

然而编译后的代码是不同的.虽然原始 switch 语句的复杂度为 O(1)，但新方法的复杂度为 O(n).生成的代码递归调用我的辅助方法，直到找到正确的条目.

The compiled code is however different. While the original switch statement had a complexity of O(1) the new approach results in a O(n) complexity. The generated code recursively calls my helper method until it finds the correct entry.

为什么编译器不能正确优化它?有没有更好的方法来解决这个问题?

Why can't the compiler optimize this properly? Are there any better ways to solve this?

类似问题:在模板化和非模板化之间进行交互时替换 switch 语句-模板代码

我应该提到我想避免 C++11 和C++14 并坚持C++03.

I should mention that I would like to avoid C++11 and C++14 and stick to C++03.

推荐答案

这就是我所说的魔术开关问题——如何获取(范围的)运行时值并将其转换为编译时常量.

This is what I call the magic switch problem -- how to take a (range of) run time values and turn it into a compile time constant.

>

抽象地说，您要生成此 switch 语句:

Abstractly, you want to generate this switch statement:

switch(n) {
  (case I from 0 to n-1: /* use I as a constant */)...
}

您可以使用参数包在 C++ 中生成与此类似的代码.

You can use parameter packs to generate code that is similar to this in C++.

我将从 开始c++14-替换样板:

template<unsigned...> struct indexes {typedef indexes type;};
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<unsigned max> using make_indexes_t = typename make_indexes<max>::type;

现在我们可以轻松创建从 0 到 n-1 的无符号整数的编译时序列.make_indexes_t<50> 扩展为 indexes<0,1,2,3, ... ,48, 49>.c++14 version 在 O(1) 步骤中这样做，因为大多数(所有?)编译器使用内在函数实现 std::make_index_sequence .上面是线性的(在编译时——在运行时什么都不做)递归深度和二次编译时内存.这很糟糕，您可以在工作中做得更好(对数深度，线性记忆)，但是您有超过 100 种类型吗?如果没有，这就足够了.

Now we can create a compile-time sequence of unsigned integers from 0 to n-1 easily. make_indexes_t<50> expands to indexes<0,1,2,3, ... ,48, 49>. The c++14 version does so in O(1) steps, as most (all?) compilers implement std::make_index_sequence with an intrinsic. The above does it in linear (at compile time -- nothing is done at run time) recursive depth, and quadratic compile time memory. This sucks, and you can do better with work (logarithmic depth, linear memory), but do you have more than a few 100 types? If not, this is good enough.

接下来，我们构建一个回调数组.由于我讨厌 C 遗留的函数指针语法，我会加入一些毫无意义的样板来隐藏它:

Next, we build an array of callbacks. As I hate C legacy function pointer syntax, I'll throw in some pointless boilerplate to hide it:

template<typename T> using type = T; // pointless boilerplate that hides C style function syntax

template<unsigned... Is>
Base_Type construct_runtime_helper( indexes<Is...>, Base_Type::type_enum e, QVariant const& v ) {
  // array of pointers to functions:  (note static, so created once)
  static type< Base_Type(const QVariant&) >* const constructor_array[] = {
    (&Base_Type::construct<Is>)...
  };
  // find the eth entry, and call it:
  return constructor_array[ unsigned(e) ](v);
}
Base_Type construct_runtime_helper( Base_Type::type_enum e, QVariant const& v ) {
  return construct_runtime_helper( make_indexes_t< Base_Type::num_types >(), e, v );
}

而鲍勃是你的叔叔^{1.用于分派的 O(1) 数组查找(使用 O(n) 设置，理论上可以在您的可执行文件启动之前完成).}

and Bob is your Uncle^{1. An O(1) array lookup (with an O(n) setup, which in theory could be done prior to your executable launching) for dispatch.}

1鲍勃是你的叔叔"；是英联邦的一句谚语，它说一切都已完成并开始工作".大致.

1 "Bob's your Uncle" is a British Commonwealth saying that says "and everything is finished and working" roughly.

这篇关于优化交换机的模板替换的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！