我试图实现/弄清楚什么
我试图找出为任意维数编写通用容器( 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 和可重复的空乘法测试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;
}
阅读评论/答案后的改进尝试
@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>();
}
我之前的想法是
但是,我更喜欢像上面这样的通用解决方案。我无法想象它必须慢得多,因为与嵌套循环相比,我没有看到有效的差异。
最佳答案
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)
关于c++ - 等效于嵌套 for 循环的迭代器显示 50% 的性能故障 - 为什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17839260/