Почему std :: pair быстрее, чем std :: tuple

Вот код для тестирования.

Кортежный тест:

using namespace std;

int main(){

    vector<tuple<int,int>> v;


    for (int var = 0; var < 100000000; ++var) {
        v.push_back(make_tuple(var, var));
    }
}

Парный тест:

#include <vector>

using namespace std;

int main(){

    vector<pair<int,int>> v;


    for (int var = 0; var < 100000000; ++var) {
        v.push_back(make_pair(var, var));
    }
}

Я измерил время с помощью команды времени Linux. Результат:

|       |   -O0   |    -O2   |
|:------|:-------:|:--------:|
| Pair  |   8.9 s |  1.60 s  |
| Tuple |  19.8 s |  1.96 s  |

Мне интересно, почему между этими двумя структурами данных в O0 такая большая разница, ведь они должны быть очень похожи. В 02 есть небольшая разница.

Почему разница в O0 такая большая и почему вообще есть разница?

РЕДАКТИРОВАТЬ:

Код с v.resize ()

Пара:

#include <vector>

using namespace std;

int main(){

    vector<pair<int,int>> v;

    v.resize(100000000);

    for (int var = 0; var < 100000000; ++var) {
        v[var] = make_pair(var, var);
    }
}

Кортеж:

#include<tuple>
#include<vector>

using namespace std;

int main(){

    vector<tuple<int,int>> v;

    v.resize(100000000);

    for (int var = 0; var < 100000000; ++var) {
        v[var] = make_tuple(var, var);
    }
}

Полученные результаты:

|       |   -O0   |    -O2   |
|:------|:-------:|:--------:|
| Pair  |  5.01 s |  0.77 s  |
| Tuple |  10.6 s |  0.87 s  |

РЕДАКТИРОВАТЬ:

Моя система

g++ (GCC) 4.8.3 20140911 (Red Hat 4.8.3-7)
GLIBCXX_3.4.19

performance c++11 stdtuple std-pair
person Aleksandar    schedule 11.11.2014    source источник
comment
Почему бы вам не взглянуть на стек вызовов и sizeof?   -  person Ajay    schedule 11.11.2014
comment
Я бы сказал, что вы должны сделать v.reserve(100000000); перед циклами в обоих случаях, чтобы сделать тест более точным.   -  person Jonathan Potter    schedule 11.11.2014
comment
@JonathanPotter, но если это устранит разницу, то будет видно, что строительство идет медленнее.   -  person gbjbaanb    schedule 11.11.2014
comment
Измерять производительность с -O0 бессмысленно - просто сравните оптимизированный код при тестировании.   -  person Paul R    schedule 11.11.2014
comment
Для измерения производительности вы должны запустить и измерить свою программу не только один раз, но и x раз, а затем взять среднее (или медианное) измеренное время выполнения. В противном случае у вас всегда может быть тот единственный системный вызов, который каким-то образом изменяет ваши измерения неопределенным образом.   -  person Sorin Totuarez    schedule 11.11.2014
comment
Сначала убедитесь, что вы правильно измеряете время: stackoverflow.com/a/9006802/412080   -  person Maxim Egorushkin    schedule 11.11.2014
comment
Мне интересно, будет ли -O3 иметь значение.   -  person BЈовић    schedule 11.11.2014
comment
Я использовал команду unix time. Я попробовал -O3 с perf stat, и оказалось, что пара и кортеж в моей системе работают одинаково.   -  person Aleksandar    schedule 11.11.2014
comment
@gbjbaanb: reserve не выполняет построение, а только выделяет память. Это удалит компонент выделения памяти из теста. Ваш обновленный код показывает resize, что не то, что я предлагал.   -  person Jonathan Potter    schedule 11.11.2014
comment
@JonathanPotter ах да, хороший момент. Не мое обновление, кстати.   -  person gbjbaanb    schedule 12.11.2014

Ответы (2)


arrow_upward
67
arrow_downward

Вам не хватает важной информации: какой компилятор вы используете? Что вы используете для измерения производительности микробенчмарка? Какую стандартную реализацию библиотеки вы используете?

Моя система:

g++ (GCC) 4.9.1 20140903 (prerelease)
GLIBCXX_3.4.20

Во всяком случае, я запустил ваши примеры, но сначала зарезервировал правильный размер векторов, чтобы избавиться от накладных расходов на выделение памяти. При этом я забавно наблюдаю нечто интересное противоположное - обратное тому, что вы видите:

g++ -std=c++11 -O2 pair.cpp -o pair
perf stat -r 10 -d ./pair
Performance counter stats for './pair' (10 runs):

      1647.045151      task-clock:HG (msec)      #    0.993 CPUs utilized            ( +-  1.94% )
              346      context-switches:HG       #    0.210 K/sec                    ( +- 40.13% )
                7      cpu-migrations:HG         #    0.004 K/sec                    ( +- 22.01% )
          182,978      page-faults:HG            #    0.111 M/sec                    ( +-  0.04% )
    3,394,685,602      cycles:HG                 #    2.061 GHz                      ( +-  2.24% ) [44.38%]
    2,478,474,676      stalled-cycles-frontend:HG #   73.01% frontend cycles idle     ( +-  1.24% ) [44.55%]
    1,550,747,174      stalled-cycles-backend:HG #   45.68% backend  cycles idle     ( +-  1.60% ) [44.66%]
    2,837,484,461      instructions:HG           #    0.84  insns per cycle        
                                                  #    0.87  stalled cycles per insn  ( +-  4.86% ) [55.78%]
      526,077,681      branches:HG               #  319.407 M/sec                    ( +-  4.52% ) [55.82%]
          829,623      branch-misses:HG          #    0.16% of all branches          ( +-  4.42% ) [55.74%]
      594,396,822      L1-dcache-loads:HG        #  360.887 M/sec                    ( +-  4.74% ) [55.59%]
        20,842,113      L1-dcache-load-misses:HG  #    3.51% of all L1-dcache hits    ( +-  0.68% ) [55.46%]
        5,474,166      LLC-loads:HG              #    3.324 M/sec                    ( +-  1.81% ) [44.23%]
  <not supported>      LLC-load-misses:HG       

      1.658671368 seconds time elapsed                                          ( +-  1.82% )

против:

g++ -std=c++11 -O2 tuple.cpp -o tuple
perf stat -r 10 -d ./tuple
Performance counter stats for './tuple' (10 runs):

        996.090514      task-clock:HG (msec)      #    0.996 CPUs utilized            ( +-  2.41% )
              102      context-switches:HG       #    0.102 K/sec                    ( +- 64.61% )
                4      cpu-migrations:HG         #    0.004 K/sec                    ( +- 32.24% )
          181,701      page-faults:HG            #    0.182 M/sec                    ( +-  0.06% )
    2,052,505,223      cycles:HG                 #    2.061 GHz                      ( +-  2.22% ) [44.45%]
    1,212,930,513      stalled-cycles-frontend:HG #   59.10% frontend cycles idle     ( +-  2.94% ) [44.56%]
      621,104,447      stalled-cycles-backend:HG #   30.26% backend  cycles idle     ( +-  3.48% ) [44.69%]
    2,700,410,991      instructions:HG           #    1.32  insns per cycle        
                                                  #    0.45  stalled cycles per insn  ( +-  1.66% ) [55.94%]
      486,476,408      branches:HG               #  488.386 M/sec                    ( +-  1.70% ) [55.96%]
          959,651      branch-misses:HG          #    0.20% of all branches          ( +-  4.78% ) [55.82%]
      547,000,119      L1-dcache-loads:HG        #  549.147 M/sec                    ( +-  2.19% ) [55.67%]
        21,540,926      L1-dcache-load-misses:HG  #    3.94% of all L1-dcache hits    ( +-  2.73% ) [55.43%]
        5,751,650      LLC-loads:HG              #    5.774 M/sec                    ( +-  3.60% ) [44.21%]
  <not supported>      LLC-load-misses:HG       

      1.000126894 seconds time elapsed                                          ( +-  2.47% )

как видите, в моем случае причина кроется в гораздо большем количестве зависших циклов как во фронтенде, так и в бэкэнде.

Откуда это взялось? Бьюсь об заклад, дело доходит до некоторой неудачной встраивания, аналогичной тому, что объясняется здесь: std :: векторная регрессия производительности при включении C ++ 11

Действительно, включение -flto уравнивает результаты для меня:

Performance counter stats for './pair' (10 runs):

      1021.922944      task-clock:HG (msec)      #    0.997 CPUs utilized            ( +-  1.15% )
                63      context-switches:HG       #    0.062 K/sec                    ( +- 77.23% )
                5      cpu-migrations:HG         #    0.005 K/sec                    ( +- 34.21% )
          195,396      page-faults:HG            #    0.191 M/sec                    ( +-  0.00% )
    2,109,877,147      cycles:HG                 #    2.065 GHz                      ( +-  0.92% ) [44.33%]
    1,098,031,078      stalled-cycles-frontend:HG #   52.04% frontend cycles idle     ( +-  0.93% ) [44.46%]
      701,553,535      stalled-cycles-backend:HG #   33.25% backend  cycles idle     ( +-  1.09% ) [44.68%]
    3,288,420,630      instructions:HG           #    1.56  insns per cycle        
                                                  #    0.33  stalled cycles per insn  ( +-  0.88% ) [55.89%]
      672,941,736      branches:HG               #  658.505 M/sec                    ( +-  0.80% ) [56.00%]
          660,278      branch-misses:HG          #    0.10% of all branches          ( +-  2.05% ) [55.93%]
      474,314,267      L1-dcache-loads:HG        #  464.139 M/sec                    ( +-  1.32% ) [55.73%]
        19,481,787      L1-dcache-load-misses:HG  #    4.11% of all L1-dcache hits    ( +-  0.80% ) [55.51%]
        5,155,678      LLC-loads:HG              #    5.045 M/sec                    ( +-  1.69% ) [44.21%]
  <not supported>      LLC-load-misses:HG       

      1.025083895 seconds time elapsed                                          ( +-  1.03% )

и для кортежа:

Performance counter stats for './tuple' (10 runs):

      1018.980969      task-clock:HG (msec)      #    0.999 CPUs utilized            ( +-  0.47% )
                8      context-switches:HG       #    0.008 K/sec                    ( +- 29.74% )
                3      cpu-migrations:HG         #    0.003 K/sec                    ( +- 42.64% )
          195,396      page-faults:HG            #    0.192 M/sec                    ( +-  0.00% )
    2,103,574,740      cycles:HG                 #    2.064 GHz                      ( +-  0.30% ) [44.28%]
    1,088,827,212      stalled-cycles-frontend:HG #   51.76% frontend cycles idle     ( +-  0.47% ) [44.56%]
      697,438,071      stalled-cycles-backend:HG #   33.15% backend  cycles idle     ( +-  0.41% ) [44.76%]
    3,305,631,646      instructions:HG           #    1.57  insns per cycle        
                                                  #    0.33  stalled cycles per insn  ( +-  0.21% ) [55.94%]
      675,175,757      branches:HG               #  662.599 M/sec                    ( +-  0.16% ) [56.02%]
          656,205      branch-misses:HG          #    0.10% of all branches          ( +-  0.98% ) [55.93%]
      475,532,976      L1-dcache-loads:HG        #  466.675 M/sec                    ( +-  0.13% ) [55.69%]
        19,430,992      L1-dcache-load-misses:HG  #    4.09% of all L1-dcache hits    ( +-  0.20% ) [55.49%]
        5,161,624      LLC-loads:HG              #    5.065 M/sec                    ( +-  0.47% ) [44.14%]
  <not supported>      LLC-load-misses:HG       

      1.020225388 seconds time elapsed                                          ( +-  0.48% )

Так что помните, -flto - ваш друг, и неудачное встраивание может иметь экстремальные результаты для сильно шаблонного кода. Используйте perf stat, чтобы узнать, что происходит.

person milianw    schedule 11.11.2014
comment
PS: Я предполагаю, что пара работает медленнее, поскольку она, вероятно, реализована с использованием кортежа, и просто так вышла за встроенный предел глубины. - person milianw; 11.11.2014
comment
Ошибочное предположение. std::pair должен иметь два настоящих элемента данных, называемых first и second, поэтому он не может быть реализован в терминах чего-либо еще. - person Sebastian Redl; 11.11.2014
comment
pair был введен в C ++ до появления tuple в C ++ 11, поэтому он не может быть реализован с помощью кортежа. Более того, кто использует более сложную структуру для простой? - person phuclv; 12.11.2014
comment
@ LưuVĩnhPhúc pair все еще может быть реализован с tuple. Полагаю, код постоянно переписывают. Например, компилятор C ++ написан на C ++ :) - person Slaus; 15.08.2017

arrow_upward
39
arrow_downward

milianw не рассматривал -O0 vs. -O2, поэтому я хотел бы добавить объяснение по этому поводу.

Ожидается, что std::tuple будет медленнее, чем std::pair, когда не оптимизирован, потому что это более сложный объект. В паре ровно два члена, поэтому ее методы легко определить. Но кортеж имеет произвольное количество членов, и единственный способ перебрать список аргументов шаблона - это рекурсия. Поэтому большинство функций для кортежа обрабатывают один член, а затем рекурсивно обрабатывают остальные, поэтому для 2-кортежа у вас в два раза больше вызовов функций.

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

person Jan Hudec    schedule 11.11.2014
comment
Я бы ответил по той же причине (произвольное количество аргументов), тогда я увидел, что std :: tuple имеет дополнительный конструктор для пар (cplusplus.com/reference/tuple/tuple/tuple (5)), что должно предотвратить итерацию списка аргументов. - person Sorin Totuarez; 11.11.2014
comment
@SorinTotuarez: Этот конструктор здесь не используется. И даже он не может избежать рекурсии, поскольку структура самого кортежа рекурсивна. - person Jan Hudec; 11.11.2014
comment
Этого требует язык? Я бы подумал, что std::tuple может быть определен в стандарте таким образом, но реализация может делать то, что хочет. Например, есть специализации для всех распространенных (‹9 элементов) размеров кортежей. - person davidbak; 24.10.2017