Почему итерация по std :: set намного медленнее, чем по std :: vector?

Question

При оптимизации кода, критичного к производительности, я заметил, что перебор по std :: set был немного медленным.

Затем я написал бенчмаркер и протестировал скорости итерации по вектору с помощью итератора (auto it : vector), итерации по набору с помощью итератора и итерации по вектору по индексу (int i = 0; i < vector.size(); ++i).

Контейнеры построены одинаково, с 1024 случайными числами. (Конечно, каждый int уникален, так как мы работаем с наборами). Затем для каждого запуска мы перебираем контейнер и суммируем их целые в длинное целое. Каждый прогон состоит из 1000 итераций, которые составляют сумму, и тест был усреднен за 1000 прогонов.

Вот мои результаты:

Testing vector by iterator
✓           
Maximum duration: 0.012418
Minimum duration: 0.007971
Average duration: 0.008354

Testing vector by index
✓           
Maximum duration: 0.002881
Minimum duration: 0.002094
Average duration: 0.002179

Testing set by iterator
✓           
Maximum duration: 0.021862
Minimum duration: 0.014278
Average duration: 0.014971

Как мы видим, повторение набора с помощью итератора в 1,79 раза медленнее, чем по вектору, и колоссальное в 6,87 раза медленнее, чем по индексу.

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

Редактировать: Спасибо за ваши ответы! Хорошие объяснения. По запросу вот код эталонного теста.

#include <chrono>
#include <random>
#include <string>
#include <functional>
#include <set>
#include <vector>

void benchmark(const char* name, int runs, int iterations, std::function<void(int)> func) {
    printf("Testing %s\n", name);

    std::chrono::duration<double> min = std::chrono::duration<double>::max();
    std::chrono::duration<double> max = std::chrono::duration<double>::min();
    std::chrono::duration<double> run = std::chrono::duration<double>::zero();
    std::chrono::duration<double> avg = std::chrono::duration<double>::zero();

    std::chrono::high_resolution_clock::time_point t1;
    std::chrono::high_resolution_clock::time_point t2;

    // [removed] progress bar code
    for (int i = 0; i < runs; ++i) {
        t1 = std::chrono::high_resolution_clock::now();

        func(iterations);

        t2 = std::chrono::high_resolution_clock::now();

        run = std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);

        // [removed] progress bar code

        if (run < min) min = run;
        if (run > max) max = run;   
        avg += run / 1000.0;
    }
    // [removed] progress bar code

    printf("Maximum duration: %f\n", max.count());
    printf("Minimum duration: %f\n", min.count());
    printf("Average duration: %f\n", avg.count());

    printf("\n");
}

int main(int argc, char const *argv[]) {
    const unsigned int arrSize = 1024;

    std::vector<int> vector; vector.reserve(arrSize);
    std::set<int> set;

    for (int i = 0; i < arrSize; ++i) {
        while (1) {
            int entry = rand() - (RAND_MAX / 2);
            auto ret = set.insert(entry);
            if (ret.second) {
                vector.push_back(entry);
                break;          
            }
        }
    }

    printf("Created vector of size %lu, set of size %lu\n", vector.size(), set.size());

    benchmark("vector by iterator", 1000, 1000, [vector](int runs) -> void {
        for (int i = 0; i < runs; ++i) {
            long int sum = 0;

            for (auto it : vector) {
                sum += it;
            }
        }
    });

    benchmark("vector by index", 1000, 1000, [vector, arrSize](int runs) -> void {
        for (int i = 0; i < runs; ++i) {
            long int sum = 0;

            for (int j = 0; j < arrSize; ++j) {
                sum += vector[j];
            }
        }
    });

    benchmark("set by iterator", 1000, 1000, [set](int runs) -> void {
        for (int i = 0; i < runs; ++i) {
            long int sum = 0;

            for (auto it : set) {
                sum += it;
            }
        }
    });

    return 0;
}

Я работаю над публикацией результатов, используя O2, но я пытаюсь получить компилятор, чтобы избежать оптимизации суммы.

Answer 1

Разве набор не является просто структурированным вектором, который проверяет, является ли каждый элемент уникальным при вставке?

Нет, далеко нет.Эти структуры данных совершенно разные, и основное отличие здесь заключается в расположении памяти: std::vector помещает свой элемент в непрерывное расположение в памяти, в то время как std::set является контейнером на основе узлов, где каждый элементраспределяется отдельно и располагается в разных местах памяти, возможно, далеко друг от друга, и определенно таким образом, что предварительная выборка данных для быстрого обхода невозможна для процессора.Это совершенно противоположно для std::vector - поскольку следующий элемент всегда находится «прямо рядом» с текущим в памяти, ЦП загружает элементы в свой кэш, а при фактической обработке элементов ему нужно только перейти ккэш для извлечения значений - который очень быстрый по сравнению с доступом к ОЗУ.

Обратите внимание, что обычно требуется иметь отсортированный, уникальный набор данных, который непрерывно размещается в памятии C ++ 2a или его последующая версия может на самом деле поставляться с flat_set, посмотрите на P1222 .

Matt Austern's "Почему вы не должны использовать set(и что вы должны использовать вместо этого) " тоже интересное чтение.

Answer 2

Основная причина в том, что когда вы перебираете std::vector, который сохраняет свой элемент в непрерывном блоке памяти , вы в основном делаете:

++p;

, где p - этоT* необработанный указатель.Код stl:

 __normal_iterator&
 operator++() _GLIBCXX_NOEXCEPT
 {
    ++_M_current;                            // <--- std::vector<>: ++iter
    return *this;
 }

Для std::set базовый объект является более сложным, и в большинстве реализаций вы итерируете по древовидной структуре .В простейшем виде это выглядит примерно так:

p=p->next_node;

, где p - указатель на структуру узла дерева:

struct tree_node {
   ...
   tree_node *next_node;
};

, но на практике "настоящий" код stlгораздо более сложный:

_Self&
operator++() _GLIBCXX_NOEXCEPT
{
    _M_node = _Rb_tree_increment(_M_node);   // <--- std::set<> ++iter
    return *this;
}

// ----- underlying code \/\/\/

static _Rb_tree_node_base*
local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
{
  if (__x->_M_right != 0) 
    {
      __x = __x->_M_right;
      while (__x->_M_left != 0)
        __x = __x->_M_left;
    }
  else 
    {
      _Rb_tree_node_base* __y = __x->_M_parent;
      while (__x == __y->_M_right) 
        {
          __x = __y;
          __y = __y->_M_parent;
        }
      if (__x->_M_right != __y)
        __x = __y;
    }
  return __x;
}

_Rb_tree_node_base*
_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
{
  return local_Rb_tree_increment(__x);
}

const _Rb_tree_node_base*
_Rb_tree_increment(const _Rb_tree_node_base* __x) throw ()
{
  return local_Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
}

(см .: Каково определение _Rb_tree_increment в битах / stl_tree.h? )

Answer 3

Прежде всего следует отметить, что std::set отсортировано. Обычно это достигается сохранением данных в древовидной структуре.

Вектор обычно хранится в непрерывной области памяти (например, в простом массиве), которая поэтому может быть кэширована. И вот почему это быстрее.

Answer 4

std::vector является непрерывной структурой.Все элементы располагаются в памяти последовательно, поэтому итерирование требует только добавления и поиска одного указателя на элемент.Кроме того, он очень удобен для кэша, поскольку получение элемента обычно приводит к загрузке целого куска вектора в кэш.

std::set - это структура на основе узлов;вообще красно-черное дерево.Итерации по нему более сложны и требуют погони за несколькими указателями на элемент.Это также не очень удобно для кэширования, так как элементы не обязательно находятся рядом друг с другом в памяти.