понедельник, 13 февраля 2012 г.

std vector iterator

Стало интересно, насколько много мы теряем, когда с дуру и не к месту перебираем элементы вектора не по индексу, а используя итератор.

Вариант 1 - доступ к значениям элементов вектора по индексу.
#include <iostream>
#include <vector>

using namespace std;

int main() {

    size_t vsize = 200000000;

    vector<double> v;
    v.resize(vsize, 0);

    for ( size_t i=0; i<vsize; i++ ) {

        v[i] = i/0.23;
    }

    double x = 0;

    for ( size_t i=0; i<vsize; i++ ) {

        x = v[i] / 283746.40596837 * 0.92386936827364;
    }

    return 0;
}
Среднее по 5-ти замерам время работы программы составило 4.7136 сек.

Вариант 2 - доступ к значениям элементов вектора с использованием итератора.
#include <iostream>
#include <vector>

using namespace std;

int main() {

    size_t vsize = 200000000;

    vector<double> v;
    v.resize(vsize, 0);

    for ( size_t i=0; i<vsize; i++ ) {

        v[i] = i/0.23;
    }

    double x = 0;

    for ( vector<double>::iterator it=v.begin(); it!=v.end(); ++it ) {

        x = *it / 283746.40596837 * 0.92386936827364;
    }

    return 0;
}
Среднее по 5-ти замерам время работы программы составило 7.196 сек.

Итак, производительность во втором случае упала почти на 34.5%... Честно говоря, я не думал, что итераторы настолько круто снижают производительность.
Для справки: компиляция осуществлялась с флагом -O0.

UPD: 09.01.2013

А теперь вариант 3 (с использованием возможностей C++11).
#include <iostream>
#include <vector>

using namespace std;

int main() {

    size_t vsize = 200000000;

    vector<double> v;
    v.resize(vsize, 0);

    for ( size_t i=0; i<vsize; i++ ) {

        v[i] = i/0.23;
    }

    double x = 0;

    for ( size_t z : v ) {

        x = z / 283746.40596837 * 0.92386936827364;
    }

    return 0;
}
Производительность практически та же, что и в варианте 2.

3 комментария:

  1. Давайте прикинем. Имеет место 200 миллионов итераций, общий проигрыш по времени составляет 2.48 секунды. Значит, на каждой итерации мы проигрываем около 12 нс. Ну, Артём, мы же не ассемблерщики, чтобы считать подобный проигрыш сколь-нибудь существенным.

    ОтветитьУдалить
    Ответы
    1. Да, с количеством итераций я махнул конечно ) В моей работе, более реальным размером векторов будет что-нибудь порядка 35000 элементов. И в этом случае мы потеряем в абсолюте порядка 0.001 сек на тестовом примере, т.е. ничто )

      Удалить
    2. Но ведь это только в моей работе. С моими наборами данных. И на моем достаточно мощном компьютере. При ином раскладе все может сложиться иначе.

      Удалить