c++ - 等效于嵌套 for 循环的迭代器显示 50% 的性能故障 - 为什么？

Question

我试图实现/弄清楚什么

我试图找出为任意维数编写通用容器( vector 、矩阵、高维对象)的最佳方法。应在编译时指定维数以及每个维的元素数，如下所示:

3给出一个包含 3 个元素的 vector

10, 10给出一个包含 100 个元素的矩阵

7, 5, 3给出一个具有 105 个元素的二阶张量

...

人们应该能够以一种简单的方式循环遍历所有元素以进行简单的操作:将所有 ( double ) 元素乘以标量 double ，按元素添加两个兼容的容器等。此外，应该能够循环遍历所有元素，知道它们每个维度的相应索引，例如来自 (0, 0, 0)至 (6, 4, 2)对于张量。

我的尝试:递归迭代器嵌套可变参数模板

我认为可变参数模板参数是一个很好的工具，可以递归地连接每个维度的迭代器。

template<
  int N, // the number of elements to iterate for this dimension
  int... otherN // the other dimension's lengths
> class dimIterator;

为了存储指向第一个元素的指针，我有一个 boxIterator请记住这只是 dimIterator 的包装器秒

template<
  typename dataType,
  int... allN
> class boxIterator : public dimIterator<allN...> { // tried as member or inheritance
  protected:
    dataType* data;

  public:
    boxIterator(dataType* data) :
      dimIterator<allN...>(),
      data(data)
    {
      //cout << "constructing box iterator." << endl;
    }

    int getIndex() const {
      int result = dimIterator<allN...>::getIndex();
      return result;
    }

    dataType* getPtr() {
      dataType* result = data + this->getIndex();
      return result;
    }
    const dataType* getPtr() const {
      dataType* result = data + this->getIndex();
      return result;
    }

    bool isDone() const {return dimIterator<allN...>::isDone();}

    boxIterator<dataType, allN...>& operator ++() {
      dimIterator<allN...>::operator++();
      return *this;
    }

    dataType& operator *() {return *(this->getPtr());}
    const dataType& operator *() const {return *(this->getPtr());}
};

template<
  int N, // the number of elements to iterate for this dimension
  int... otherN // the other dimension's lengths
> class dimIterator : public dimIterator<otherN...> { // tried as member or inheritance
  protected:
    int i;

  public:
    dimIterator() :
      dimIterator<otherN...>(),
      i(0)
    {
      //cout << "constructing level with " << N << " gridpoints." << endl;
    }

    int getIndex() const {
      int result = i + N*dimIterator<otherN...>::getIndex();
      return result;
    }

    bool isDone() const {return dimIterator<otherN...>::isDone();}

    dimIterator<N, otherN...>& operator ++() {
      if(i<N-1) {
        ++i;
      }
      else {
        i = 0;
        dimIterator<otherN...>::operator++();
      }
      return *this;
    }
};

template<int N> // stop recursion if only one dimension left
class dimIterator<N> {
  protected:
    int i;

  public:
    dimIterator() :
      i(0)
    {
      //cout << "constructing last level with " << N << " gridpoints." << endl;
    }

    int getIndex() const {
      int result = i;
      return result;
    }

    bool isDone() const {return ( i>= N );}

    dimIterator<N>& operator ++() {
      ++i;
      return *this;
    }
};

最初，我对这种方法非常满意，因为它允许为任意数量的维度编写相同的高级迭代器循环。可以很容易地获得每个维度的索引和类似的东西，比如某个维度中给定框的间距。

这种方法的问题

然而，即使我尝试为迭代器逻辑使用模板和内联函数，编译器也不会将这些东西优化为与执行嵌套 for 一样快的东西。循环。我有一个未初始化的 double 和可重复的空乘法测试

2.5 秒，嵌套原生 for循环

具有高级迭代器访问权限的 5 秒

我的问题

是什么阻止编译器将方法视为嵌套的等价物 for循环？

解决此类问题的通用高性能方法是什么？我猜一定有一个轻量级的库。

完整代码和编译信息

编译 g++ -O3 -std=c++11 .版本是 g++ (GCC) 4.8.1 .

完整代码(从上面部分重复):

#include <iostream>

using namespace std;

template<int first, int... other>
class integerPack {
  public:
    constexpr static int length = 1 + integerPack<other...>::length;
    constexpr static int product = first*integerPack<other...>::product;
};

template<int only>
class integerPack<only> {
  public:
    constexpr static int length = 1;
    constexpr static int product = only;
};

template<
  int N, // the number of elements to iterate for this dimension
  int... otherN // the other dimension's lengths
> class dimIterator;

template<
  typename dataType,
  int... allN
> class boxIterator : public dimIterator<allN...> { // tried as member or inheritance
  protected:
    dataType* data;

  public:
    boxIterator(dataType* data) :
      dimIterator<allN...>(),
      data(data)
    {
      //cout << "constructing box iterator." << endl;
    }

    int getIndex() const {
      int result = dimIterator<allN...>::getIndex();
      return result;
    }

    dataType* getPtr() {
      dataType* result = data + this->getIndex();
      return result;
    }
    const dataType* getPtr() const {
      dataType* result = data + this->getIndex();
      return result;
    }

    bool isDone() const {return dimIterator<allN...>::isDone();}

    boxIterator<dataType, allN...>& operator ++() {
      dimIterator<allN...>::operator++();
      return *this;
    }

    dataType& operator *() {return *(this->getPtr());}
    const dataType& operator *() const {return *(this->getPtr());}
};

template<
  int N, // the number of elements to iterate for this dimension
  int... otherN // the other dimension's lengths
> class dimIterator : public dimIterator<otherN...> { // tried as member or inheritance
  protected:
    int i;

  public:
    dimIterator() :
      dimIterator<otherN...>(),
      i(0)
    {
      //cout << "constructing level with " << N << " gridpoints." << endl;
    }

    int getIndex() const {
      int result = i + N*dimIterator<otherN...>::getIndex();
      return result;
    }

    bool isDone() const {return dimIterator<otherN...>::isDone();}

    dimIterator<N, otherN...>& operator ++() {
      if(i<N-1) {
        ++i;
      }
      else {
        i = 0;
        dimIterator<otherN...>::operator++();
      }
      return *this;
    }
};

template<int N> // stop recursion if only one dimension left
class dimIterator<N> {
  protected:
    int i;

  public:
    dimIterator() :
      i(0)
    {
      //cout << "constructing last level with " << N << " gridpoints." << endl;
    }

    int getIndex() const {
      int result = i;
      return result;
    }

    bool isDone() const {return ( i>= N );}

    dimIterator<N>& operator ++() {
      ++i;
      return *this;
    }
};

template<
  int... allN
> class box {
  public:
    constexpr static int dimension = integerPack<allN...>::length;
    constexpr static int NN = integerPack<allN...>::product;

    template<typename dataType>
    using iterator = boxIterator<dataType, allN...>;
};

template<typename dataType, typename boxType>
class boxQuantity {
  public:
    typedef typename boxType::template iterator<dataType> iterator;
    constexpr static int dimension = boxType::dimension;
    constexpr static int NN = boxType::NN;

    typedef boxQuantity<dataType, boxType> thisClass;

  protected:
    boxType mybox;
    dataType* data;
    iterator myit;

  public:
    boxQuantity(
      const boxType& mybox
    ) :
      mybox(mybox),
      data(new dataType[NN]),
      myit(data)
    {
      cout << "I am a quantity of dimension " << dimension
        << " with " << NN << " gridpoints." << endl;
    }

    virtual ~boxQuantity() {
      delete[] data;
    }

    iterator begin() const {
      iterator it(data);
      return it;
    }

    dataType& operator [] (int i) {return data[i];}
    const dataType& operator [] (int i) const {return data[i];}

    // iterator syntax with recursive for-like logic: 5 s
    virtual thisClass& operator *= (const thisClass& rhs) {
      thisClass& lhs = *this;
      for(iterator it=lhs.begin(); !it.isDone(); ++it) {
        lhs[myit.getIndex()] *= rhs[myit.getIndex()];
      }
      return *this;
    }

    // plain nested native for loops: 2.5 s
    /*virtual thisClass& operator *= (const thisClass& rhs) {
      thisClass& lhs = *this;
      for(int yindex=0; yindex<1000; ++yindex) {
        for(int xindex=0; xindex<1000; ++xindex) {
          lhs[yindex*1000 + xindex] *= rhs[yindex*1000 + xindex];
        }
      }
      return *this;
    }*/
};

typedef box<1000, 1000> boxType;
typedef boxQuantity<double, boxType> qType;

int main() {
  boxType qBox;

  qType q1(qBox);
  qType q2(qBox);

  for(int i=0; i<2000; ++i) {
    q1 *= q2;
  }

  return 0;
}

阅读评论/答案后的改进尝试

@cdmh 关于 virtual关键词

感谢您的回答。该代码是通过获取一个更大的程序片段来组装的，其中 virtual不像我的例子那样明显没用。我预计 virtual主要影响 的时间调用 函数/运算符，但不适用于 正在执行 它。据我所知，执行时间的主要部分花在循环内，我忘记删除 virtual .但是，删除 virtual在我的情况下不会带来显着的性能优势？ (我根据您的建议进行了测试。)

@Yakk 关于线性迭代连续的内存块

我可能错过指出的是，我想遍历连续内存块中的所有元素 和 能够获得每个元素的 n 维索引。此外，我希望能够在给定维度的方向上访问相邻元素。也许删除这些功能是一个坏主意，例如(内 dimIterator)

    template<int dindex>
    int getCoord() const {
      if(1 == dindex) {
        return i;
      }
      return otherDims.template getCoord<dindex-1>();
    }

我之前的想法是

有一个用于所有一般操作的基类，其中不需要知道各自的索引，然后

为每个维度提供专门的类(通过 CRTP 滥用来重用通用代码？)。

但是，我更喜欢像上面这样的通用解决方案。我无法想象它必须慢得多，因为与嵌套循环相比，我没有看到有效的差异。

Answer 1

boxQuantity的 virtual operator*=()不会被内联，这会阻止很多优化。在您的示例中，您不是从此类派生的。删除此 virtual运算符允许内联代码和使用 SIMD 指令:

00861330  movsd       xmm0,mmword ptr [edx+eax*8]  
00861335  mulsd       xmm0,mmword ptr [edi+eax*8]  
0086133A  movsd       mmword ptr [edi+eax*8],xmm0  
0086133F  dec         ecx  
00861340  jne         main+90h (0861330h)