вектор <bool>доступ

Question

Я профилировал свой код, используя gprof и из отчета, большинство, если не все из первых двадцати или около того вещей относятся к вектору

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  ms/call  ms/call  name    
 14.71      0.05     0.05  3870399     0.00     0.00  std::vector<bool, std::allocator<bool> >::size() const
 11.76      0.09     0.04 10552897     0.00     0.00  std::_Bit_reference::_Bit_reference(unsigned long*, unsigned long)
 11.76      0.13     0.04  7890323     0.00     0.00  std::_Bit_const_iterator::_Bit_const_iterator(std::_Bit_iterator const&)
  5.88      0.15     0.02 10089215     0.00     0.00  std::_Bit_iterator::operator*() const
  5.88      0.17     0.02  6083600     0.00     0.00  std::vector<bool, std::allocator<bool> >::operator[](unsigned int)
  5.88      0.19     0.02  3912611     0.00     0.00  std::vector<bool, std::allocator<bool> >::end() const
  5.88      0.21     0.02                             std::istreambuf_iterator<char, std::char_traits<char> > std::num_get<char, std::istreambuf_iterator<char, std::char_traits<char> > >::_M_extract_int<unsigned long long>(std::istreambuf_iterator<char, std::char_traits<char> >, std::istreambuf_iterator<char, std::char_traits<char> >, std::ios_base&, std::_Ios_Iostate&, unsigned long long&) const
  2.94      0.22     0.01  6523499     0.00     0.00  std::_Bit_reference::operator bool() const
  2.94      0.23     0.01  3940406     0.00     0.00  std::vector<bool, std::allocator<bool> >::begin() const
  2.94      0.24     0.01  2807828     0.00     0.00  std::_Bit_iterator::operator++()
  2.94      0.25     0.01   146917     0.00     0.00  std::_Bit_iterator_base::_M_incr(int)
  2.94      0.26     0.01   121706     0.00     0.00  std::__miter_base<unsigned long*, false>::__b(unsigned long*)
  2.94      0.27     0.01    46008     0.00     0.00  std::_Bvector_base<std::allocator<bool> >::~_Bvector_base()
  2.94      0.28     0.01    22596     0.00     0.00  std::_Bit_iterator std::__copy_move<false, false, std::random_access_iterator_tag>::__copy_m<std::_Bit_iterator, std::_Bit_iterator>(std::_Bit_iterator, std::_Bit_iterator, std::_Bit_iterator)
  2.94      0.29     0.01     4525     0.00     0.05  integer::operator+(integer)
  2.94      0.30     0.01     1382     0.01     0.01  void std::_Destroy<unsigned int*, unsigned int>(unsigned int*, unsigned int*, std::allocator<unsigned int>&)
  2.94      0.31     0.01                             std::string::size() const
  2.94      0.32     0.01                             std::basic_string<char, std::char_traits<char>, std::allocator<char> >::~basic_string()
  2.94      0.33     0.01                             std::locale::locale()
  2.94      0.34     0.01                             __dynamic_cast

- это хороший знак, так как это означает, что остальныемои функции довольно эффективны, или что доступ к значениям из вектора действительно медленный?

im компилируется с помощью gcc -std = c ++ 0x

Answer 1

vector<bool> не хранит bool с. Это в основном битовое поле. Вы платите за все, что нужно, чтобы изменить одно значение.

Если производительность во время выполнения является проблемой, рассмотрите vector<char> или deque<bool>.

Answer 2

, поскольку это означает, что остальные мои функции довольно эффективны, или что доступ к значениям из вектора действительно медленный?

Поскольку «медленный» и «эффективный» являются относительными значениямиЭто бессмысленное различие.Наиболее объективный способ интерпретации отчета:

Поскольку операция std :: vector 'потребляет наибольшее количество времени, с этого следует начать, чтобы сделать код еще быстрее .

Обратите внимание, что std::vector<bool> обычно немного медленнее, чем std::vector<int>, потому что он не хранит реальные bool с, а скорее набор битовых масок (то есть в идеале требуется только один бит на запись).Это экономит место, но медленнее.Если вам нужно, чтобы это было быстрее, попробуйте вместо этого использовать std::vector<int> (или char, .., в зависимости от ваших потребностей).

Я подозреваю, что std::vector<bool> может сильно пострадать от отладочных сборок, поэтомупопробуйте несколько флагов оптимизации, если вы этого еще не сделали (вы всегда должны это делать для профилирования).

Answer 3

Многое говорит о вашей программе?За исключением бизнеса vector<bool>, он практически ничего не говорит.

Вы видите из первых рук проблемы с gprof .

Предположим,Вы знаете, что у некоторой функции "высокое время", что означает, что счетчик программы отбирал много раз, но это не та функция, которую вы написали или можете изменить.

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

gprof пытается помочь вам, также угадывая, что такое время включительно для подпрограммы, сколько раз она вызывается и график вызовов.Если нет рекурсии, и у вас есть только дюжина или около того функций, и вы не выполняете никаких операций ввода-вывода, это может быть полезно.

Существует немного другой подход, воплощенный в профилировщиках, таких как Увеличить .Вместо выборки только счетчика программы, выборка всего стека вызовов.Зачем?Поскольку строки кода, ответственные за потраченное время, находятся в стеке в течение этого времени , просто просят, чтобы их заметили.

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

Answer 4

Я бы сказал, что воняет, потому что 14,71% вашего времени тратится на vector<bool>::size()!?! Размер, вероятно, дано.

Попробуйте уменьшить количество вызовов до размера () или используйте вектор фиксированного размера, если вы знаете размер заранее: bitset

Редактировать после прочтения обновления на вопрос:

Обязательное изменение: g++ --std=c++0x -g -O3 (это две опечатки и флаг оптимизации, перепрофилировать!); Шаблонные классы интенсивно используют встраивание, и это, в свою очередь, позволяет использовать еще несколько оптимизаций. Порядок ускорения легко 10-кратный

Answer 5

vector<bool> на самом деле является специализацией шаблона, где каждое значение bool хранится как один битОднако невозможно напрямую работать с отдельными битами так же, как с int или только с «обычным» bool.Таким образом, алгоритмы, используемые в vector<bool>, сильно отличаются от «нормальных» vector<>, и для максимально возможного сохранения интерфейса vector он может возвращать прокси-объекты, которые манипулируют битами при вызове функций, подобных * 1008.*.Это может повлиять на результаты в вашем отчете gprof, в зависимости от конфигурации вашего компилятора и рассматриваемого кода.