вектор‹логический› доступ

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

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

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

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

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

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

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

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

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

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

Изменить после прочтения обновления вопроса:

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

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

Вы сами видите проблемы с gprof.

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

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

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

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

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