优化位数组访问

Question

我使用Dipperstein的bitarray.cpp类来处理图像数据原生存储为一个像素一位的双级（黑白）图像。

我需要通过每个位迭代，每个图像4--9百万像素的顺序，在数百张照片，使用for循环，是这样的：

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

性能是可用的，但不是很棒。我通过gprof运行该程序，并发现有大量时间和数百万次调用std::vector方法（如迭代器和开始）。这里的顶级采样功能：

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，但任何人都可以摆脱为什么，例如，标准::矢量::开始（光）被称为几百万次？当然，我能做些什么来加速它？

编辑：我只是放弃和优化搜索功能（循环），而不是。

Answer 1

快速峰值成bitarray.cpp的代码所示：

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

m_Array类型为std :: vector

STL向量上的[]运算符具有恒定的复杂性，但它可能实现为vector :: begin的调用以获取数组的基地址，然后计算偏移量t o达到你想要的价值。由于bitarray.cpp在每个位访问上对[]运算符进行调用，因此您会收到很多调用。

给出您的用例我将创建一个包含在bitarray.cpp中的功能的自定义实现，并调整它为您的顺序，一点一点访问模式。

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

Answer 2

没有看到你的代码，很难就如何加快你正在做的事情发表具体的评论。但是，vector::begin()用于将迭代器返回到向量中的第一个元素 - 在遍历向量时这是一个标准例程。

我实际上推荐使用更现代的分析器，例如OProfile，这会给你更多更细粒度的信息，说明你的程序在哪里花费了实际的C++时间，甚至是个别的asm指令，取决于你如何运行它。

另一方面 - 为什么你选择使用bitarray.cpp而不是香草std::vector<bool>？我没有使用它自己，但快速扫描上述链接暗示bitarray.cpp支持std::vector<bool>附加功能，如果您不使用可能会增加与STL向量类相比的开销...

Answer 3

你可以通过使用指针/迭代器提高性能（我不知道究竟bitarray.cpp为您做的），像这样：

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

，因为我不知道如果我只使用int我在这里您的位阵列将被空终止，在这种情况下，您的条件可能仅仅是

*myBitArray != '\0'; 

或者你可以破解一个更好的结束条件。使用std :: iterator会是最好的，但我怀疑你的bitarray会支持它。

编辑：

通常这会是一个微型的优化，但如果你遍历足够的东西，它可能会略微提高性能。

Answer 4

如果性能足够让您不必担心访问个别位，那么您应该可以并行化您的代码。既然你将它描述为图像处理，可能性是位i的状态不会影响你处理位i + 1到i + 6的方式，所以你可以重写你的代码来一次操作字节和单词。只需将计数器增加8到64倍就可以提供可测量的性能提升，并且还可以使编译器更容易优化代码。

Answer 5

事实上，您在配置文件输出中看到大量内联函数意味着它们没有被内联 - 也就是说，您没有在开启优化的情况下进行编译。所以你可以做的最简单的事情就是使用-O2或-O3。

剖析未优化的代码很少值得的，因为优化和未优化代码的执行配置文件将可能完全different.33