Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > И снова про производительность std::vector

Автор: xTr1m 8.5.2013, 16:01

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

Код


unsigned int BynarySearch(vector<int> &vec, int value)
{
    unsigned int start = 0, end = vec.size() - 1;
    while(true)
    {
        int tmpIndex = start + (end - start) / 2;
        if(vec[tmpIndex] == value)
            return tmpIndex;        

        if(value < vec[tmpIndex]) end = tmpIndex;
        else  start = tmpIndex;            

        if(end - start == 1)
        {
            if(vec[start] == value) return start;
            if(vec[end] == value) return end;
        }
    }

    return -1;
}

unsigned int BynarySearch(int *arr, const int size, int value)
{
    unsigned int start = 0, end = size - 1;
    while(true)
    {
        int tmpIndex = start + (end - start) / 2;
        if(arr[tmpIndex] == value)        
            return tmpIndex;        

        if(value < arr[tmpIndex]) end = tmpIndex;
        else  start = tmpIndex;            

        if(end - start == 1)
        {
            if(arr[start] == value) return start;
            if(arr[end] == value) return end;
        }
    }

    return -1;
}

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

Автор: Static 8.5.2013, 16:18

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

Автор: bsa 8.5.2013, 16:24

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

Автор: xTr1m 8.5.2013, 16:26

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

Код


#ifdef __debug

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

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

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

Автор: kamre 9.5.2013, 05:53

Цитата(bsa @ 8.5.2013, 16:24

)

Думаю, в релизе скорость работы сравняется.

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

Код


#include <vector>
#include <iostream>
#include <chrono>

using namespace std;
using namespace chrono;

unsigned int BinarySearch(vector<int> &vec, int value)
{
    unsigned int start = 0, end = vec.size() - 1;
    while(true)
    {
        int tmpIndex = start + (end - start) / 2;
        if(vec[tmpIndex] == value)
            return tmpIndex;

        if(value < vec[tmpIndex]) end = tmpIndex;
        else  start = tmpIndex;

        if(end - start == 1)
        {
            if(vec[start] == value) return start;
            if(vec[end] == value) return end;
        }
    }

    return -1;
}

unsigned int BinarySearch(int *arr, const int size, int value)
{
    unsigned int start = 0, end = size - 1;
    while(true)
    {
        int tmpIndex = start + (end - start) / 2;
        if(arr[tmpIndex] == value)
            return tmpIndex;

        if(value < arr[tmpIndex]) end = tmpIndex;
        else  start = tmpIndex;

        if(end - start == 1)
        {
            if(arr[start] == value) return start;
            if(arr[end] == value) return end;
        }
    }

    return -1;
}

template <typename F>
void test(const char* desc, F f)
{
    cout << desc << ": ";
    const size_t n = 10;
    typedef high_resolution_clock::time_point tp;
    tp t0 = high_resolution_clock::now();
    for (size_t i = 0; i < n; ++i) {
        f();
    }
    tp t1 = high_resolution_clock::now();
    duration<double> time_span = duration_cast<duration<double>>(t1 - t0);
    cout << time_span.count()/n << " sec" << endl;
}

int main()
{
    const size_t sz = 2000000;
    vector<int> v;
    for (size_t i = 0; i < sz; ++i) {
        v.push_back(i);
    }
    auto vect = [&] () -> int {
        unsigned int res;
        for (size_t i = 0; i < sz; ++i) {
            res = BinarySearch(v, i);
        }
        return res;
    };
    auto array = [&] () -> int {
        unsigned int res;
        for (size_t i = 0; i < sz; ++i) {
            res = BinarySearch(v.data(), sz, i);
        }
        return res;
    };
    test("vector", vect);
    test("array", array);
}

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

Автор: Static 9.5.2013, 10:19

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

Автор: kamre 9.5.2013, 10:34

Цитата(Static @ 9.5.2013, 10:19

)

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

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

Код


const_reference
operator[](size_type __n) const
{ return *(this->_M_impl._M_start + __n); }

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

Автор: Static 9.5.2013, 11:37

Цитата(kamre @ 9.5.2013, 09:34

)

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

Не знаю

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

Автор: volatile 9.5.2013, 13:24

Цитата(xTr1m @ 8.5.2013, 16:01

)

Все это для дебага, но разница в 16 раз

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

Цитата(kamre @ 9.5.2013, 05:53

)

vector: 0.462927 sec
array: 0.401723 sec

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

Автор: kamre 9.5.2013, 14:10

Цитата(volatile @ 9.5.2013, 13:24

)

Массив быстрей будет, по любому, но не значительно.

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

Автор: volatile 9.5.2013, 14:56

Цитата(kamre @ 9.5.2013, 14:10

)

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

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

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

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

Автор: VSB 19.5.2013, 10:29

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