День добрый. Случайно играясь с производительностью, получил очень странный для меня результат. Функция двоичного поиска для вектора и "сырого" массива

То есть все одинаковое, кроме способа обращения к элементу (хотя и он по большому счету схож). Прогнав данные функции 1000000 раз по отсортированному массиву от 1 до 1000000 я получил, что вектор осилил это за 2,5 сек против 0,15 для "сырого" массива. Все это для дебага, но разница в 16 раз (обычный std::find вообще свыше 120 сек). Я конечно понимаю, что вектор функциональнее и уже готовое решение (с большей возможностью для расширения / изменения) и в конце концов стандарт, но какова цена? Может я не так меряю?

Попробуйте все-таки в релизе.

xTr1m, вообще-то, в STL есть уже двоичный поиск - upper_bound и lower_bound. Может стоит не изобретать велосипед?
Думаю, в релизе скорость работы сравняется.

То, что поиск есть я знаю, это я уже так, для себя. Попробовал в релизе, действительно стало сравнимо. Но, что он там делает то? Вроде, строк типа 

я там не видел.

хотя все равно разница есть. Вектор = 0.18, Массив = 0. Но это уже для 2000000 прогонов.

Добавлено через 14 минут и 31 секунду
Все равно возникает ощущение, что те, кто придумывает свой велосипед иногда правы.

Это сообщение отредактировал(а) xTr1m - 8.5.2013, 16:40

У меня тоже в релизе вектор чуть отстает:

сборка так: g++ -std=c++11 -O3 binary_search_perfo.cpp
выводит:
vector: 0.462927 sec
array: 0.401723 sec
причем чиселки стабильные, пара цифр после запятой не меняется вообще

Вектор может еще отставать из-за проверки на выход за пределы массива.

А где здесь проверка на выход за границы:


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

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

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


да, вот это похоже на реальные цифры

А чем это "по любому" объясняется?

ну например, псевдокод
vector [2] = 3;
это будет скомпилировано как-то так ==>

int * p = vector.pointer; 
p[2] = 3;

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

В студии есть дополнительные проверки, по умолчанию включенные в дебаге, чтобы проще отлаживать было. Подробнее - http://msdn.microsoft.com/en-us/library/aa985872.aspx