Оптимизация доступа к битовым массивам - PullRequest
Новая
       13

Оптимизация доступа к битовым массивам

2 голосов
/ 09 августа 2009

Я использую класс Дипперштейна 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 ...

Я не очень знаком с STL в C ++, но кто-нибудь может пролить свет на то, почему, например, std :: vector :: begin () вызывается несколько миллионов раз? И, конечно, могу ли я что-то сделать, чтобы ускорить это?

Редактировать: Я просто сдался и оптимизировал функцию поиска (цикл) вместо этого.

Ответы [ 5 ]

6 голосов
/ 09 августа 2009

Тот факт, что вы видите много встроенных функций в выводе своего профиля, подразумевает, что они не являются встроенными, то есть вы не компилируете с включенной оптимизацией. Поэтому для оптимизации кода проще всего было бы использовать -O2 или -O3.

Профилирование неоптимизированного кода редко имеет смысл, поскольку профиль выполнения оптимизированного и неоптимизированного кода, скорее всего, будет совершенно разным. 33

2 голосов
/ 09 августа 2009

быстрый пик в коде для 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 имеет постоянную сложность, но, вероятно, он реализован как вызов вектора: :: begin, чтобы получить базовый адрес массива, а затем вычисляет смещение, чтобы получить желаемое значение. поскольку bitarray.cpp звонит оператору [] при КАЖДОМ БИТОВОМ ДОСТУПЕ, вы получаете много звонков.

учитывая ваш вариант использования, я бы создал пользовательскую реализацию функциональности, содержащейся в bitarray.cpp, и настроил ее для вашего последовательного, побитового шаблона доступа.

  • Не используйте беззнаковые символы, используйте 32- или 64-битные значения, чтобы уменьшить количество обращений к памяти.
  • Я бы использовал обычный массив, а не вектор, чтобы избежать затрат на поиск
  • Создать функцию последовательного доступа nextbit (), которая не выполняет все операции поиска. Сохраните указатель на текущее «значение», все что вам нужно сделать, чтобы увеличить его на 32-битной границе, все обращения между границами являются простыми операциями маски / сдвига и должны быть очень быстрыми.
1 голос
/ 09 августа 2009

Не видя ваш код, сложно сделать конкретные комментарии о том, как ускорить то, что вы делаете. Однако vector::begin() используется для возврата итератора к первому элементу в векторе - это стандартная процедура для итерации по вектору.

Я бы на самом деле рекомендовал использовать более современный профилировщик, такой как OProfile , это даст вам гораздо более детальную информацию о том, куда ваша программа тратит свое время - вплоть до самой строки C ++, или даже индивидуальная инструкция asm, в зависимости от того, как вы ее выполняете.

В качестве отступления - почему вы решили использовать bitarray.cpp вместо ванили std::vector<bool>? Я сам этим не пользовался, но быстрое сканирование по вышеуказанной ссылке показывает, что bitarray.cpp поддерживает дополнительную функциональность по сравнению с std::vector<bool>, которая, если вы не используете ее, может добавить дополнительные издержки по сравнению с векторным классом STL. .

0 голосов
/ 09 августа 2009

Если производительность настолько важна, что вам нужно беспокоиться о доступе к отдельным битам, то вам, вероятно, следует распараллелить свой код. Поскольку вы описываете это как обработку изображений, скорее всего, состояние бита i не повлияет на то, как вы обрабатываете биты с i + 1 по i + 6, поэтому вы, вероятно, можете переписать свой код для работы с байтами и словами за раз. Возможность увеличения счетчика в 8–64 раза реже должна обеспечить измеримое увеличение производительности, а также упростит компилятору оптимизацию вашего кода.

0 голосов
/ 09 августа 2009

Вы можете улучшить производительность, используя указатель / итератор (я не уверен, что именно bitarray.cpp делает для вас), например: 

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

Я использую только int i здесь, потому что я не уверен, что ваш битовый массив будет нулевым, в этом случае ваше условие может просто быть 

*myBitArray != '\0';

Или вы могли бы взломать лучшее конечное состояние. Лучше всего использовать std :: iterator, но я сомневаюсь, что ваш bitarray поддержит его.

Edit:

Обычно это будет микрооптимизация, но если вы зацикливаетесь на достаточном количестве вещей, это, вероятно, немного улучшит производительность.

...