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

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

Восстановить пароль Регистрация
 
MAKAPOH
30 / 20 / 1
Регистрация: 08.09.2012
Сообщений: 77
16.08.2014, 15:54     Неожиданный результат при сравнении производительности вектора и обычного массива #1
Добрый день.
Ради интереса сравнил проиводительность вектора с обычным массивом и получил неожиданный результат.
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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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"
Убежденный
Системный программист
 Аватар для Убежденный
14200 / 6215 / 986
Регистрация: 02.05.2013
Сообщений: 10,356
Завершенные тесты: 1
16.08.2014, 18:32     Неожиданный результат при сравнении производительности вектора и обычного массива #3
Цитата Сообщение от MAKAPOH Посмотреть сообщение
Мой вопрос в том как так получается что шаблонный класс обгоняет простой массив по скорости?
Причин может быть тьма.
Истину найдете в ассемблерном листинге.

Цитата Сообщение от MAKAPOH Посмотреть сообщение
если вместо operator[] использовать функцию at() для доступа к элементам вектора, то это никак не влияет на результат (в пределах погрешности измерения) хотя функция at() должна делать проверку на выход за границу размера вектора.
Я думаю, компилятор - не дурак.
Размер вектора и значение итератора цикла известны на этапе компиляции, в
результате оптимизации все проверки могут быть выброшены за ненадобностью.
Либо они занимают столь ничтожное время, что не влияют на результат.
DrOffset
6450 / 3824 / 885
Регистрация: 30.01.2014
Сообщений: 6,618
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
Почетный модератор
6468 / 2243 / 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
6450 / 3824 / 885
Регистрация: 30.01.2014
Сообщений: 6,618
16.08.2014, 22:49     Неожиданный результат при сравнении производительности вектора и обычного массива #7
Цитата Сообщение от MAKAPOH Посмотреть сообщение
Я правильно понимаю что заполнение умолчательным значением помещает массив (или часть массива) в кеш процессора и это приводит к увеличению скорости доступа?
Не само по себе умолчательное значение, а уже произведенные действия над этими данными. Если, скажем, ты позовешь свою функцию подсчета и заполнения для сырого (массива не заполненного нулями) два раза, то получишь на втором вызове тот же результат.
Vourhey
Почетный модератор
6468 / 2243 / 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     Неожиданный результат при сравнении производительности вектора и обычного массива
Еще ссылки по теме:

Ошибка при сравнении типа char C++
Некоректный инкремент переменной цикла for при сравнении элементов массива C++
C++ Зацикливание при сравнении двоичных чисел

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

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

Текущее время: 04:28. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru