代码之家 › 专栏 › 技术社区 › erjiang

优化位数组访问

bitarray vector stl optimization c++

erjiang · 技术社区 · 15 年前

我使用Dipperstein的bitarray.cpp类处理两级(黑白)图像,图像数据以一个像素一位的形式存储。

我需要按每幅图像4-9百万像素的顺序,在数百幅图像上迭代每一位,使用for循环,如下所示:

for( int i = 0; i < imgLength; i++) {
    if( myBitArray[i] == 1 ) {
         //  ... do stuff ...
    }
}

性能是可用的,但并不惊人。我通过gprof运行程序,发现有大量的时间和数以百万计的呼叫 std::vector 像迭代器和Begin这样的方法。下面是顶部采样函数:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 37.91      0.80     0.80        2     0.40     1.01  findPattern(bit_array_c*, bool*, int, int, int)
 12.32      1.06     0.26 98375762     0.00     0.00  __gnu_cxx::__normal_iterator<unsigned char const*, std::vector<unsigned char, std::allocator<unsigned char> > >::__normal_iterator(unsigned char const* const&)
 11.85      1.31     0.25 48183659     0.00     0.00  __gnu_cxx::__normal_iterator<unsigned char const*, std::vector<unsigned char, std::allocator<unsigned char> > >::operator+(int const&) const
 11.37      1.55     0.24 49187881     0.00     0.00  std::vector<unsigned char, std::allocator<unsigned char> >::begin() const
  9.24      1.75     0.20 48183659     0.00     0.00  bit_array_c::operator[](unsigned int) const
  8.06      1.92     0.17 48183659     0.00     0.00  std::vector<unsigned char, std::allocator<unsigned char> >::operator[](unsigned int) const
  5.21      2.02     0.11 48183659     0.00     0.00  __gnu_cxx::__normal_iterator<unsigned char const*, std::vector<unsigned char, std::allocator<unsigned char> > >::operator*() const
  0.95      2.04     0.02                             bit_array_c::operator()(unsigned int)
  0.47      2.06     0.01  6025316     0.00     0.00  __gnu_cxx::__normal_iterator<unsigned char*, std::vector<unsigned char, std::allocator<unsigned char> > >::__normal_iterator(unsigned char* const&)
  0.47      2.06     0.01  3012657     0.00     0.00  __gnu_cxx::__normal_iterator<unsigned char*, std::vector<unsigned char, std::allocator<unsigned char> > >::operator*() const
  0.47      2.08     0.01  1004222     0.00     0.00  std::vector<unsigned char, std::allocator<unsigned char> >::end() const
... remainder omitted ...

我不太熟悉C++的STL,但是有谁能解释为什么,例如,STD::vector::(开始)被称为几百万次?当然,我是否可以做点什么来加快速度?

编辑: 我只是放弃并优化了搜索函数(循环)。

5 回复 | 直到 15 年前

Mark 15 年前

BitArray.cpp代码的快速峰值显示:

bool bit_array_c::operator[](const unsigned int bit) const
{
    return((m_Array[BIT_CHAR(bit)] & BIT_IN_CHAR(bit)) != 0);
}

m_数组的类型为std::vector

stl vectors上的[]运算符具有恒定的复杂性,但它很可能实现为对vectors::begin的调用,以获取数组的基地址,然后计算偏移量以获得所需的值。因为bitarray.cpp在每次位访问时都调用[]运算符,所以您会收到很多调用。

考虑到您的用例,我将创建bitaray.cpp中包含的功能的自定义实现,并根据您的顺序逐位访问模式对其进行调优。

不要使用无符号字符,使用32或64位值来减少所需的内存访问次数。
我会使用一个普通数组,而不是向量来避免查找开销
创建一个顺序访问函数nextbit(),它不执行所有查找。存储一个指向当前“值”的指针。您只需在32/64位边界上增加它,边界之间的所有访问都是一个简单的掩码/移位操作,应该非常快。

Chris Dodd 15 年前

您在概要文件输出中看到许多内联函数的事实意味着它们没有被内联——也就是说,您没有在启用优化的情况下进行编译。所以优化代码最简单的方法就是使用-o2或-o3。

分析未优化的代码很少有价值,因为优化和未优化的代码的执行概要可能完全不同。33

DaveR 15 年前

如果看不到您的代码,就很难对如何加速您正在做的事情做出具体的评论。然而, vector::begin() 用于将迭代器返回到向量中的第一个元素-它是跨向量迭代时的标准例程。

实际上,我建议使用更现代的探查器,例如 OProfile 这将给您提供更多细粒度的信息,根据您是如何运行的,您的程序花费时间到实际的C++行,或者甚至单个ASM指令。

作为旁白-你为什么选择使用 bitarray.cpp 而不是香草 std::vector<bool> ?我自己没有用过,但快速浏览上面的链接就可以发现 bitarray.cpp 支持其他功能 std::vector<bool> 如果你不好好利用这一点,与stl向量类相比,可能会增加开销…

jkeys 15 年前

您可以通过使用指针/迭代器(我不确定bitaray.cpp究竟为您做了什么)来提高性能,如下所示:

for (bool *ptr = myBitArray, int i = 0; i != imgLength; ++i, ++ptr)
{
   if (*myBitArray == 1)
   {
       //handle
   }
}

我在这里只使用int i,因为我不确定您的位数组是否将以空终止,在这种情况下,您的条件可能只是

*myBitArray != '\0';

或者你可以设计一个更好的最终条件。使用std::迭代器最好,但我怀疑您的位数组是否支持它。

编辑:

通常这是一个微优化,但是如果循环处理足够多的事情,它可能会稍微提高性能。

user57368 15 年前

如果性能足够重要,您必须担心访问单个位,那么您可能应该将代码并行化。由于您将其描述为图像处理,很可能位的状态i不会影响您处理位i+1到i+6的方式,因此您可能可以重写代码以一次对字节和字进行操作。只要能够将计数器的增量减少8到64倍,就可以显著地提高性能,而且还可以使编译器更容易地优化代码。