提问者:小点点

在循环内检查 std::vector 大小的正确方法


我有一个 std::vector,我需要经常循环。我看到两种方法可以做到这一点

第一种方式:

const size_t SIZE = myVec.size();
for (size_t i = 0; i < SIZE; i++)
{
    myVec[i] = 0;
}

第二种方式:

for (size_t i = 0; i < myVec.size(); i++)
{
    myVec[i] = 0;
}

是第一个比第二个更有效率,还是现代编译器知道优化第二个实现以使其与第一个实现一样高效?

FWIW,我在Visual Studio 2013上。


共3个答案

匿名用户

即使使用现代编译器,第一个版本通常也会更快。优化器很难证明大小不会由于与循环体中写入的位置混叠而改变,因此在许多情况下,第二个版本必须在每次循环迭代时重新计算大小。

我在Visual Studio 2013版本中对此进行了测量,发现32位和64位代码的性能差异。这两个版本都被 std::fill() 轻松击败。这些测量值是超过 1000 次运行和 1000 万个元素向量的平均值(将元素数量增加到 10 亿会在一定程度上降低性能差异,因为内存访问变得更加瓶颈)。

Method                   Time relative to uncached for loop
                         x86      x64

uncached for loop        1.00     1.00
cached for loop          0.70     0.98
std::fill()              0.42     0.57

循环代码的基线缓存大小:

const auto size = vec.size();
for (vector<int>::size_type i = 0; i < size; ++i) {
    vec[i] = val;
}

编译到此循环体(x86 版本):

00B612C0  mov         ecx,dword ptr [esi]  
00B612C2  mov         dword ptr [ecx+eax*4],edi  
00B612C5  inc         eax  
00B612C6  cmp         eax,edx  
00B612C8  jb          forCachedSize+20h (0B612C0h)  

而不缓存矢量大小的版本:

for (vector<int>::size_type i = 0; i < vec.size(); ++i) {
    vec[i] = val;
}

编译到这个,每次通过循环重新计算 vec.size():

00B612F0  mov         dword ptr [edx+eax*4],edi  
00B612F3  inc         eax  
00B612F4  mov         ecx,dword ptr [esi+4]            <-- Load vec.end()
00B612F7  mov         edx,dword ptr [esi]              <-- Load vec.begin()
00B612F9  sub         ecx,edx                          <-- ecx = vec.end() - vec.begin()
00B612FB  sar         ecx,2                            <-- exc = (vec.end() - vec.begin()) / sizeof(int)
00B612FE  cmp         eax,ecx  
00B61300  jb          forComputedSize+20h (0B612F0h)  

匿名用户

我更喜欢像第一种情况一样编写我的循环。对于第二种情况和 std::vector::size(),您可能会在编译器优化版本中为一些额外的加载付费,但是当您开始使用更复杂的数据结构时,这些简单的加载可能会变成昂贵的树查找。

即使有偏好,上下文有时也要求您以第二种形式编写循环。第一种情况暗示容器的大小没有发生突变,因为容器大小被检查过一次。当您阅读第二种情况时,每次迭代都会检查容器大小,这向用户暗示正文可能会改变容器的大小。

如果要更改循环体中的容器,请使用第二种形式并注释您正在更改容器并想要检查其大小。否则,首选第一个。

匿名用户

正如这里提到的,向量的复杂性