Jul*_*ius 5 c++ optimization performance iterator c++11
我试图找出为任意数量的维度编写通用容器(向量,矩阵,高维对象)的最佳方法.维度的数量以及每个维度的元素数量应在编译时指定,如下所示:
3 给出一个带有3个元素的向量10, 10 给出一个包含100个元素的矩阵7, 5, 3 给出具有105个元素的二阶张量一个人应该能够以简单的方式遍历所有元素进行简单的操作:double用标量乘以all()元素,在元素方面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循环一样快的东西.我进行了一次测试,其中未初始化的双打和可重复的获得空乘
for循环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;
}
virtual关键字的@cdmh感谢您的回答.代码是通过获取一个更大的程序来组装的,其中virtual并不像我的例子那样明显无用.我预计virtual主要影响调用函数/运算符的时间,而不是执行它.据我所知,执行时间的主要部分是在循环内部,我忘了删除virtual.但是,在我的情况下删除virtual不会带来显着的性能优势？(我在你的建议后测试过.)
我可能错过了指出的是,我想迭代连续内存块中的所有元素,并能够获得每个元素的n维索引.此外,我希望能够在给定维度的方向上访问邻居元素.也许删除那些功能是个坏主意,例如(内部dimIterator)
template<int dindex>
int getCoord() const {
if(1 == dindex) {
return i;
}
return otherDims.template getCoord<dindex-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)