Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
MAKAPOH
30 / 20 / 1
Регистрация: 08.09.2012
Сообщений: 77
#1

Неожиданный результат при сравнении производительности вектора и обычного массива - C++

16.08.2014, 15:54. Просмотров 895. Ответов 8
Метки нет (Все метки)

Добрый день.
Ради интереса сравнил проиводительность вектора с обычным массивом и получил неожиданный результат.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <chrono>
#include <vector>
 
int main()
{
  const std::size_t N = 40000000;
  std::vector<std::size_t> vector(N);
  std::size_t *raw_array = new std::size_t[N];
 
 
  auto start_time = std::chrono::high_resolution_clock::now();
  for (std::size_t i=0; i<N; ++i)
    vector[i] = i;
    //vector.at(i) = i;
  auto end_time = std::chrono::high_resolution_clock::now();
  std::cout << "vector: "
            << std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time).count()
            << " ms\n";
 
 
  start_time = std::chrono::high_resolution_clock::now();
  for (std::size_t i=0; i<N; ++i)
    raw_array[i] = i;
  end_time = std::chrono::high_resolution_clock::now();
  std::cout << "raw array: "
            << std::chrono::duration_cast<std::chrono::milliseconds>(end_time - start_time).count()
            << " ms\n";
 
 
  delete [] raw_array;
  return 0;
}
DEBUG: Vector(254ms) Raw array(105ms) - в 2,4 раза быстрее простой массив.
RELEASE: Vector(43ms) Raw array(81ms) - в 1,8 раза быстрее вектор.
Компилятор - Microsoft VisualC++ 12.0 (amd64)
ОС - Windows 7 64 bit

Мой вопрос в том как так получается что шаблонный класс обгоняет простой массив по скорости?
И ещё, если вместо operator[] использовать функцию at() для доступа к элементам вектора, то это никак не влияет на результат (в пределах погрешности измерения) хотя функция at() должна делать проверку на выход за границу размера вектора.
Заранее спаибо за ответы.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.08.2014, 15:54     Неожиданный результат при сравнении производительности вектора и обычного массива
Посмотрите здесь:

C++ Ошибка при сравнении символов
неожиданный результат C++
Не верный результат при обработке одномерного массива C++
Ошибка при сравнении элемента динамического массива с числом C++
Зацикливание при сравнении строк C++
Ошибка при сравнении типа char C++
Некоректный инкремент переменной цикла for при сравнении элементов массива C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
StailGot
27 / 22 / 6
Регистрация: 25.08.2013
Сообщений: 41
16.08.2014, 18:28     Неожиданный результат при сравнении производительности вектора и обычного массива #2
Цитата Сообщение от MAKAPOH Посмотреть сообщение
Мой вопрос в том как так получается что шаблонный класс обгоняет простой массив по скорости?
Скорее всего из-за кеширования.
При создании вектора происходит заполнение массива умолчательным значением. Если тоже самое проделать для сырого массива, то скорость сравняется.

C++
1
  std::size_t * raw_array = new std::size_t[N] (); // пустые скобки - так называемый "zero-initialization"
Убежденный
Системный программист
Эксперт С++
15102 / 6797 / 1073
Регистрация: 02.05.2013
Сообщений: 11,111
Завершенные тесты: 1
16.08.2014, 18:32     Неожиданный результат при сравнении производительности вектора и обычного массива #3
Цитата Сообщение от MAKAPOH Посмотреть сообщение
Мой вопрос в том как так получается что шаблонный класс обгоняет простой массив по скорости?
Причин может быть тьма.
Истину найдете в ассемблерном листинге.

Цитата Сообщение от MAKAPOH Посмотреть сообщение
если вместо operator[] использовать функцию at() для доступа к элементам вектора, то это никак не влияет на результат (в пределах погрешности измерения) хотя функция at() должна делать проверку на выход за границу размера вектора.
Я думаю, компилятор - не дурак.
Размер вектора и значение итератора цикла известны на этапе компиляции, в
результате оптимизации все проверки могут быть выброшены за ненадобностью.
Либо они занимают столь ничтожное время, что не влияют на результат.
DrOffset
6851 / 4062 / 927
Регистрация: 30.01.2014
Сообщений: 6,859
16.08.2014, 18:54     Неожиданный результат при сравнении производительности вектора и обычного массива #4
Цитата Сообщение от MAKAPOH Посмотреть сообщение
И ещё, если вместо operator[] использовать функцию at() для доступа к элементам вектора, то это никак не влияет на результат (в пределах погрешности измерения) хотя функция at() должна делать проверку на выход за границу размера вектора.
Оптимизация. Проверка уже проводится в цикле, вот он и выбросил ее из at.
Цитата Сообщение от MAKAPOH Посмотреть сообщение
Мой вопрос в том как так получается что шаблонный класс обгоняет простой массив по скорости?
Если ты посмотришь ассемблер,
Assembler
1
2
3
4
5
6
7
8
9
10
$LL3@test_vec:
    movd    xmm0, esi
    pshufd  xmm0, xmm0, 0
    paddd   xmm0, xmm1
    add esi, 4
; Line 9
    movdqu  XMMWORD PTR [edi], xmm0
    lea edi, DWORD PTR [edi+16]
    cmp esi, 40000000               ; 02625a00H
    jb  SHORT $LL3@test_vec
то увидишь, что код копирования там абсолютно одинаковый, для того и другого случая. Разница во времени может обеспечиваться погрешностью измерения, а не реальным расхождением. А в современных системах так мерить вообще гиблое дело.

А вообще, тест у тебя некорректно написан. Много очень факторов могли бы испортить результат, этого не произошло в данном случае, но не факт, что не произошло бы в другом, при аналогичном подходе.
Vourhey
Почетный модератор
6474 / 2249 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
16.08.2014, 20:23     Неожиданный результат при сравнении производительности вектора и обычного массива #5
Цитата Сообщение от MAKAPOH Посмотреть сообщение
Мой вопрос в том как так получается что шаблонный класс обгоняет простой массив по скорости?
Не обгоняет. Засунь создание vector под проверку времени. И new с сырым массивом туда же.
MAKAPOH
30 / 20 / 1
Регистрация: 08.09.2012
Сообщений: 77
16.08.2014, 21:47  [ТС]     Неожиданный результат при сравнении производительности вектора и обычного массива #6
Не обгоняет. Засунь создание vector под проверку времени. И new с сырым массивом туда же.
Так а если я хочу измерять именно разницу в скорости доступа зачем мне засовывать создание массивов под проверку времени?
StailGot
Добавил скобочки к соданию сырого массива, скорость выровнялась. Я правильно понимаю что заполнение умолчательным значением помещает массив (или часть массива) в кеш процессора и это приводит к увеличению скорости доступа?
DrOffset
6851 / 4062 / 927
Регистрация: 30.01.2014
Сообщений: 6,859
16.08.2014, 22:49     Неожиданный результат при сравнении производительности вектора и обычного массива #7
Цитата Сообщение от MAKAPOH Посмотреть сообщение
Я правильно понимаю что заполнение умолчательным значением помещает массив (или часть массива) в кеш процессора и это приводит к увеличению скорости доступа?
Не само по себе умолчательное значение, а уже произведенные действия над этими данными. Если, скажем, ты позовешь свою функцию подсчета и заполнения для сырого (массива не заполненного нулями) два раза, то получишь на втором вызове тот же результат.
Vourhey
Почетный модератор
6474 / 2249 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
17.08.2014, 01:00     Неожиданный результат при сравнении производительности вектора и обычного массива #8
Цитата Сообщение от MAKAPOH Посмотреть сообщение
Так а если я хочу измерять именно разницу в скорости доступа зачем мне засовывать создание массивов под проверку времени?
Затем, чтобы это не приводило к таким заключениям, как в твоем первом сообщении. Что к вектору доступ быстрее.
Цитата Сообщение от MAKAPOH Посмотреть сообщение
Я правильно понимаю что заполнение умолчательным значением помещает массив (или часть массива) в кеш процессора и это приводит к увеличению скорости доступа?
Цикл по массиву выполняется в конструкторе вектора. Умолчательное там значение, или не умолчательное - пофигу.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.08.2014, 02:24     Неожиданный результат при сравнении производительности вектора и обычного массива
Еще ссылки по теме:

C++ Зацикливание при сравнении двоичных чисел
C++ Ошибка при сравнении введённых данных
C++ Почему функция atoi возвращает неожиданный результат?
Неожиданный результат при выводе значения переменной, несмотря на инкремент C++
C++ C++5 числами из массива при выборе операции показывает результат. (сумма, произведение . элементов массива)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
MAKAPOH
30 / 20 / 1
Регистрация: 08.09.2012
Сообщений: 77
17.08.2014, 02:24  [ТС]     Неожиданный результат при сравнении производительности вектора и обычного массива #9
Всем ещё раз спасибо, кое что я для себя прояснил.
Yandex
Объявления
17.08.2014, 02:24     Неожиданный результат при сравнении производительности вектора и обычного массива
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru