C++ 2D 矩阵迭代器与嵌套 for 循环的效率比较

标签 c++ arrays iterator 2d

我有一个二维数组的行主迭代器，其取消引用运算符如下:

int& Iterator::operator*(){ return matrix_[y_][x_]; }  //matrix_ has type int**

(前缀)增量运算符如下:

Iterator& Iterator::operator++()
{
    if((++x_ == xs_) && (++y_ != ys_)) //ys_, xs_ are the dimensions of the matrix
        x_ = 0;
    return *this;   
}

我可以将此迭代器与 std::transform 的优化版本一起使用(不会返回不需要的结果，以节省一些指令)

template < class InputIterator, class OutputIterator, class UnaryOperator >
inline void MyTransform( InputIterator first1, InputIterator last1,
                         OutputIterator result, UnaryOperator op )
{
    for (; first1 != last1; ++first1, ++result)
        *result = op(*first1);
}

这样调用它:

MyTransform(matrix1.begin(),matrix1.end(),matrix2.begin(), MyFunctor());

但是，当我将性能与经典的嵌套 for 循环进行比较时:

MyFunctor() f;
for (int y=0; y<ySize; y++)
    for (int x=0; x<xSize; x++)
        matrix2.[y][x] = f(matrix1.[y][x]);

基于迭代器的解决方案大约是。比嵌套 for 循环解决方案慢 25%。 MSVC 和 Intel C++ 编译器都是这种情况(两者似乎都会根据需要自动内联)。

现在问题似乎不在于迭代器增量运算符，就好像我执行以下(丑陋的)混合解决方案结合了迭代器遍历和原始数组访问(后者使用迭代器的内部计数进行索引):

MyFunctor f;
for (; mat1Begin != mat1End; ++mat1Begin, ++mat2Begin)
{ 
    //mat1 and mat2 are type int**
    mat2[mat2Begin.y_][mat2Begin.x_] = f(mat1[mat1Begin.y_][mat1Begin.x_]);
}

它实际上比嵌套 for 循环解决方案快一点。对我来说，这表明性能受到影响的是迭代器在执行分配时的取消引用。

我的问题是，为什么在赋值中取消引用迭代器

*result = op(*first1);

相对于原始数组访问，会造成如此巨大的性能损失吗？有什么技术可以用于这个简单的设计，以获得(几乎)相当于原始数组版本的性能吗？

为了响应此社区的有用反馈，我修改了代码，以便缓存循环的外部计数器，因此代码现在如下所示:

int& Iterator::operator*()
{
    return column_[x_]; 
} 

Iterator& Iterator::operator++()
{
    if(++x_ == xs_)      //ys_, xs_ are the dimensions of the matrix
    {
        if(++y_ != ys_)
        { 
            x_ = 0;
            column_ = matrix_[y_];
        }
    }
    return *this;
}

这将英特尔 C++ 编译器的性能提高到原始 2D 数组性能的约 85%，对于 MSVC 编译器也类似(实际上 MSVC 上对 MyTransform 的调用速度较慢 - 生成了更多汇编指令 - 但让我们忽略这一点现在我对循环/取消引用行为更感兴趣)。

当我将代码转换为使用指针算术(再次缓存列)时，性能明显低于英特尔编译器上的原始 2D 数组 (~70%)，但同样是原始 2D 数组的~85% MSVC编译器下

int& Image32Iterator::operator*()
{
    return *ptr_;
} 

//prefix
Image32Iterator& Image32Iterator::operator++()
{
    if(++ptr_ == ptrEnd_)
    {
        if(++row_ != rowEnd_)
        { 
            ptrEnd_ = (ptr_ = *row_) + xs_;
        }
    }
    return *this;
}

所以我试图了解 ~85% 的性能是否是使用基于迭代器的解决方案可以获得的最大值。令我惊讶的是，指针算术解决方案的性能如此之差(令人烦恼，因为我试图使用指针算术来看看我是否可以获得 > 85%!)。

我将继续调查并更新发现，但欢迎任何见解......

...因此，重点关注为什么迭代器的指针算术版本在 Intel 上执行得如此糟糕，而在 MSVC 编译器上执行得还不错，我查看了程序集，问题似乎是在为循环生成的代码中。对于所有其他函数(即构造函数、迭代器和解引用运算符、不等运算符等，生成的代码对于 Intel 和 MSVC 几乎是相同的，如果有的话，它对于 Intel 来说稍微更简洁)。

这里是 Intel 生成代码的汇编器，后面是 MSVC 生成代码的汇编器。我已将 for 循环更改为 while 循环，以使生成的汇编程序更易于阅读:

英特尔生成的代码:

while(begin != end)
01392D31  push        eax  
01392D32  lea         eax,[begin]  
01392D35  lea         edx,[end]  
01392D38  mov         dword ptr [esp],edx  
01392D3B  mov         ecx,eax  
01392D3D  call        ImageExperiments::Image32Iterator::operator!= (139103Ch)  
01392D42  mov         byte ptr [ebp-74h],al  
01392D45  movzx       eax,byte ptr [ebp-74h]  
01392D49  movzx       eax,al  
01392D4C  test        eax,eax  
01392D4E  je          ImageExperiments::greyscale_iterator2+0BCh (1392DACh)  
{
    *it8 = gsf(*begin);
01392D50  lea         eax,[begin]  
01392D53  mov         ecx,eax  
01392D55  call        ImageExperiments::Image32Iterator::operator* (13910A5h)  
01392D5A  mov         dword ptr [ebp-10h],eax  
01392D5D  push        eax  
01392D5E  lea         eax,[gsf]  
01392D61  mov         edx,dword ptr [ebp-10h]  
01392D64  mov         edx,dword ptr [edx]  
01392D66  mov         dword ptr [esp],edx  
01392D69  mov         ecx,eax  
01392D6B  call        ImageExperiments::GreyScaleFunctor::operator() (139101Eh)  
01392D70  mov         byte ptr [ebp-72h],al  
01392D73  movzx       eax,byte ptr [ebp-72h]  
01392D77  mov         byte ptr [ebp-71h],al  
01392D7A  lea         eax,[it8]  
01392D7D  mov         ecx,eax  
01392D7F  call        ImageExperiments::Image8Iterator::operator* (1391050h)  
01392D84  mov         dword ptr [ebp-0Ch],eax  
01392D87  mov         eax,dword ptr [ebp-0Ch]  
01392D8A  movzx       edx,byte ptr [ebp-71h]  
01392D8E  mov         byte ptr [eax],dl  
    ++begin; 
01392D90  lea         eax,[begin]  
01392D93  mov         ecx,eax  
01392D95  call        ImageExperiments::Image32Iterator::operator++ (1391028h)  
01392D9A  mov         dword ptr [ebp-8],eax  
    ++it8;
01392D9D  lea         eax,[it8]  
01392DA0  mov         ecx,eax  
01392DA2  call        ImageExperiments::Image8Iterator::operator++ (1391014h)  
01392DA7  mov         dword ptr [ebp-4],eax  
01392DAA  jmp         ImageExperiments::greyscale_iterator2+41h (1392D31h)  
}
}
00CA2DAC  leave  
00CA2DAD  ret

MSVC 生成的代码:

while(begin != end)
010316E0  lea         eax,[end]  
010316E3  push        eax  
010316E4  lea         ecx,[begin]  
010316E7  call        ImageExperiments::Image32Iterator::operator!= (1031096h)  
010316EC  movzx       ecx,al  
010316EF  test        ecx,ecx  
010316F1  je          ImageExperiments::greyscale_iterator2+74h (1031724h)  
{
    *it8 = gsf(*begin);
010316F3  lea         ecx,[begin]  
010316F6  call        ImageExperiments::Image32Iterator::operator* (10311EAh)  
010316FB  mov         eax,dword ptr [eax]  
010316FD  push        eax  
010316FE  lea         ecx,[gsf]  
01031701  call        ImageExperiments::GreyScaleFunctor::operator() (1031032h)  
01031706  mov         bl,al  
01031708  lea         ecx,[it8]  
0103170B  call        ImageExperiments::Image8Iterator::operator* (1031118h)  
01031710  mov         byte ptr [eax],bl  
    ++begin; 
01031712  lea         ecx,[begin]  
01031715  call        ImageExperiments::Image32Iterator::operator++ (1031041h)  
    ++it8;
0103171A  lea         ecx,[it8]  
0103171D  call        ImageExperiments::Image8Iterator::operator++ (103101Eh)  
}
01031722  jmp         ImageExperiments::greyscale_iterator2+30h (10316E0h)  
}
01031724  pop         edi  
01031725  pop         esi  
01031726  pop         ebx  
01031727  mov         esp,ebp  
01031729  pop         ebp  
0103172A  ret

所以在我看来，英特尔编译器生成了大约。指令数量增加 50%。我尝试用 __restrict 限定指针，看看这是否会对 Intel 一代产生任何影响，但事实并非如此。如果有人对为什么英特尔编译器的循环代码与 MSVC++ 编译器相比如此庞大/缓慢有任何建议，我会非常感兴趣!

最佳答案

我尝试重新创建您的代码，请参阅 here .

在 g++ (4.6.3, -O3) 下运行它，我发现:

1) 非迭代器版本确实更快，但在我的例子中大约是 4 倍。 2) 迭代器版本，无论您是否遵循迭代器或提取它们的计数器并使用它们直接访问数组，都会较慢(由于上述因素)。

我已经捕获了两个版本的汇编程序，发现它们与版本 2 中与迭代器递增逻辑相关的大量代码有很大不同。请注意，在这两种情况下，所有内容都是内联的。

情况 1 内循环，无迭代器:

.L18:
    xorl    %eax, %eax
    .p2align 4,,10
    .p2align 3
.L19:
    movq    24(%rsp), %rdx
    movq    40(%rsp), %rsi
    movq    (%rdx,%rcx), %rdx
    movq    (%rsi,%rcx), %rsi
    movl    (%rdx,%rax), %edx
    imull   %edx, %edx
    movl    %edx, (%rsi,%rax)
    addq    $4, %rax
    cmpq    $20000, %rax
    jne .L19
    addq    $8, %rcx
    cmpq    $40000, %rcx
    jne .L18
    movl    $.LC2, %esi
    movl    std::cout, %edi

情况2内循环，迭代器:

.L34:
    movl    %eax, 56(%rsp)
    movl    %ecx, 60(%rsp)
    movl    %edi, 72(%rsp)
    movl    %edi, 76(%rsp)
    movq    72(%rsp), %rdi
    cmpq    %rdi, 56(%rsp)
    je  .L36
    movq    24(%rsp), %rdi
    movslq  %eax, %r10
    movslq  %ecx, %r9
    movslq  %edx, %r11
    addl    $1, %eax
    movq    (%rdi,%r10,8), %rdi
    movslq  %esi, %r10
    movl    (%rdi,%r9,4), %edi
    movq    40(%rsp), %r9
    imull   %edi, %edi
    movq    (%r9,%r11,8), %r9
    movl    %edi, (%r9,%r10,4)
    movl    16(%rsp), %edi
    cmpl    %edi, %eax
    je  .L37
.L20:
    addl    $1, %edx
    cmpl    32(%rsp), %edx
    jne .L34
    addl    $1, %esi
    cmpl    %esi, %edx
    cmovne  %r8d, %edx
    jmp .L34
.L37:
    addl    $1, %ecx
    cmpl    %ecx, %eax
    cmovne  %r8d, %eax
    jmp .L20
.L36:

最终，如果您喜欢迭代器模式，我认为最好的建议是将矩阵内部数组重新定义为 int*，从而允许迭代器成为指针周围的简单包装器。这显然是以矩阵的随机访问索引为代价的，矩阵需要计算给定 x 的 int 数组中的一维偏移量， >y 和行宽(尽管这不是火箭科学!)。

关于C++ 2D 矩阵迭代器与嵌套 for 循环的效率比较，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11265477/

上一篇：c++ - 使用 pthread 解决 N 皇后难题

下一篇：c++ - Opengl ES 纹理绘制不正确

相关文章：

php - 我如何对多个 mysql foreach 数组进行排序并需要它们在 php 中保持一致？

java - 将 java 7 嵌套 for 循环转换为使用 java 8 流 API

c++ - 枚举特定于编译器的扩展的范围解析运算符？

c++ - 我可以在不创建结构实例的情况下获得结构字段的大小吗？

c++ - 试图获取从文件中读取的随机素数之和？

c++ - 为每种参数类型重新定义相同模式的函数

连接两个字符数组 C

javascript - JavaScript 中的按位运算符作为状态标志

java - ognl.OgnlException : source is null for getProperty(null, "0")错误

java - 如何在一个 hashmap 上设置 2 个迭代器

©2024 IT工具网  联系我们