Что вызывает такую ​​большую разницу в производительности между двумя способами построения вектора static_vectors? - PullRequest
Новая
       13

Что вызывает такую ​​большую разницу в производительности между двумя способами построения вектора static_vectors?

0 голосов
/ 05 июля 2019

Я написал тест для тестирования двух способов изменения и отправки boost :: container :: static_vector в std :: vector. Они выглядят странным образом.

Первый: 

typedef boost::container::static_vector<int, 4> Bar;

void foo(Bar& bar, std::vector<Bar>& bars)
{
    const auto oldSize = bar.size();
    bar.emplace_back(4);
    bars.emplace_back(bar);
    bar.resize(oldSize);
}

Он изменяет локальную версию, копирует ее в вектор и затем возвращает локальную версию в исходное состояние.

Второй: 

typedef boost::container::static_vector<int, 4> Bar;

void foo(Bar& bar, std::vector<Bar>& bars)
{
    bars.emplace_back(bar);
    bars.back().emplace_back(4);
}

Вместо того, чтобы изменять и возвращать локальную версию, он просто изменяет свою копию прямо на вектор.

Я считаю, что vector::emplace_back в обеих версиях должны работать одинаково хорошо, так как оба просто копируют объект фиксированного размера. Кроме того, обе реализации foo вызывают static_vector::emplace_back ровно один раз. resize кажется довольно дешевым. Он должен сводиться к проверке, является ли oldSize меньше текущего bar размера (он всегда есть), и перезаписывать внутреннюю переменную bar размера. Очевидно, здесь нет деструктора. Второе внедрение вызывает вместо этого vector::back, который обращается к памяти кучи.

В общем, я ожидал, что обе версии будут одинаково производительными, возможно даже с небольшим преимуществом первой версии (видя, что она обращается к куче памяти только один раз, в отличие от второй). Тем не менее, простой тест показывает совершенно другие результаты.

Benchmark: 

std::vector<Bar> bars;
for(int i = 0; i < 100; ++i)
{
    bars.clear();
    Bar bar = {5, 6, 7};
    for(int j = 0; j < 10000000; ++j)
        foo(bar, bars);
}

Первый: 

real    0m8,044s
user    0m7,846s
sys     0m0,152s

Во-вторых: 

real    0m5,754s
user    0m5,559s
sys     0m0,184s

Вопрос в том, откуда взялась эта огромная разница?

Как ни странно, изменение емкости static_vector, похоже, уменьшает этот разрыв. Э.Г. 

typedef boost::container::static_vector<int, 16> Bar;

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

Я использую g ++ 8.3.0 с флагами -Ofast -std=c++17 -flto.

EDIT:

Вот немного более длинный тест с большей static_vector емкостью (8): 

std::vector<Bar> bars;
for(int i = 0; i < 1000; ++i)
{
    bars.clear();
    Bar bar = {5, 6, 7, 8, 9, 10, 11};
    for(int j = 0; j < 10000000; ++j)
        foo(bar, bars);
}

1m42,282s против 1m31,387s все еще показывает аналогичную разницу. Действительно, первая реализация может сойти с объяснения, что она просто копирует больше байтов. Но тогда возникает вопрос, почему аналогичный тест с увеличением емкости до 16 показывает всего лишь 2m46,733s против 2m45,128s. Я ожидаю увидеть ту же разницу в 11 с.

1 Ответ

0 голосов
/ 06 июля 2019

Прежде всего, мы должны признать, что два метода на самом деле не эквивалентны. Давайте назовем их fooA и fooB. 

typedef boost::container::static_vector<int, 4> Bar;

void fooA(Bar& bar, std::vector<Bar>& bars)
{
    const auto oldSize = bar.size();
    bar.emplace_back(4);
    bars.emplace_back(bar);
    bar.resize(oldSize);
}

void fooB(Bar& bar, std::vector<Bar>& bars)
{
    bars.emplace_back(bar);
    bars.back().emplace_back(4);
}

Изучение fooA

когда мы вызываем fooA, происходят следующие вещи:

  • Получаем размер bar
  • Мы пытаемся добавить 4 к концу bar. Если это не удается, генерируется исключение, и функция завершается без добавления чего-либо в bars. bar может быть оставлено в недопустимом состоянии.
  • bar копируется в bars
  • bar возвращается в исходное состояние.

Изучение fooB

fooB имеет такое же поведение в случае успеха, но другое поведение в случае сбоя.

  • Копируем bar в bars
  • Мы пытаемся добавить 4 к новому вектору в конце bars. Если это не удается, генерируется исключение, и функция завершается (но к концу bars добавляется что-то ЕСТЬ). bar никогда не находится в недопустимом состоянии, потому что никогда не изменяется.

Что это значит?

Поведение fooA и fooB одинаково в случае успеха (без исключения), но они отличаются по поведению при возникновении исключения. В результате компилятор не может применить одинаковые оптимизации к обоим из них, и не может удалить поведение, подобное resize. Это приводит к тому, что fooB быстрее.

...