5

我试图达到/想出的目标

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

  • 3给出一个包含 3 个元素的向量
  • 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它只是dimIterators的包装器

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循环一样快的东西。我有一个未初始化的双精度和可重复获取的空乘法测试

  • 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 维索引。此外，我希望能够在给定维度的方向上访问相邻元素。删除这些功能可能是个坏主意，例如 (inside dimIterator)

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

我之前的想法是

  1. 对于所有一般操作都有一个基类，其中不需要知道相应的索引，然后
  2. 为每个维度提供专门的类（通过 CRTP 滥用来重用通用代码？）。

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

4

1 回答 1

2

boxQuantity'svirtual 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)
于 2013-07-24T16:56:36.440 回答