Вектор против смещения производительности карты

edit: Я специально сравниваю операции std::vector линейного поиска с бинарными поисковыми операциями std::map, потому что это, по-видимому, относится к утверждению Herb. Я знаю, что использование двоичного поиска приведет к переходу производительности с O (N) на O (log N), но это не будет проверять утверждение Herb

Bjarne Stroustrup и Herb Sutter недавно говорили о том, насколько удивительным std::vector является ситуация, в которой можно было бы ожидать использования std::list из-за стоимости промахов в кэше во время связанного обхода списка. (см. http://channel9.msdn.com/Events/Build/2014/2-661 с отметкой 48 минут)

Herb сделал еще одно утверждение, однако, что операции над упорядоченным вектором были даже быстрее, чем std::map (см. http://i.imgur.com/zX07TZR.png, взятый из 51:30), что было трудно понять. Поэтому я создал небольшой тест, чтобы продемонстрировать это, и с трудом воспроизводил эти результаты: https://ideone.com/MN7DYK

Это тестовый код:

template <typename C>
void test(std::string name, std::vector<int> shuffledInputValues, C & c)
{
   // fill container 'c' with values from 'shuffledInputValues' then erase them all
   {
      std::cout << "testing " << name << "..." << std::endl;
      timer t;

      for (auto val : shuffledInputValues) insert(c, val);
      for (auto val : shuffledInputValues) remove(c, val);
  }
}

// output:
// testing vector...99.189ms
// testing deque...120.848ms
// testing set...4.077ms

Обратите внимание, как std::vector выполняет порядок медленнее, чем std::set. Конечно, это результат, которого я ожидал, но я смущен тем утверждением, которое пыталась сделать Herb.

Что я делаю неправильно? Или я не понимаю претензии Herb?

Примечания к моему тестовому приложению:

он должен использовать линейные операции - вся цель упражнения - продемонстрировать магию кэша кэша, это ограничения, которые Herb и Bjarne накладывают на упражнение.
Я не пробовал какой-либо сложный цикл для моей векторной итерации, но я считаю, что итерация никак не влияет на производительность.
Я ограничил цикл до 10 тыс. элементов, потому что идеонизирует время на больших наборах, но увеличение размера не изменяет результаты.

edit: см. https://ideone.com/916fVd для модифицированного примера, который сравнивает только производительность поисковых запросов. Линейный поиск показывает ту же производительность.

Ответ 1

Я нашел слайды для упрощения ссылки (я не вижу графиков, но я предполагаю, что это может быть из-за запатентованного формата файла), Соответствующим слайдом является номер 39, который описывает проблему, которая решается:

§ Генерировать N случайных целых чисел и вставлять их в последовательность, чтобы каждый был вставлен в свое правильное положение в числовом порядке.

§ Удалите элементы по одному, выбирая случайную позицию в последовательности и удаляя там элемент.

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

Саттер предлагает, чтобы карта (или дерево вообще) казалось естественным выбором для этого алгоритма, потому что вы получаете поиск O (log n). И действительно, он довольно легко разбивает вектор для больших значений N в части вставки.

Здесь идет, но. Вам нужно удалить n-й элемент (для случайного n). Вот где я считаю, что ваш код обманывает. Вы удаляете элементы в том порядке, в котором они были вставлены, эффективно используя вектор ввода в качестве справочной таблицы для поиска значения элемента в "случайной" позиции, чтобы вы могли искать его в O (log n). Таким образом, вы действительно используете комбинацию set и vector для решения проблемы.

Обычное двоичное дерево поиска, например, используемое для std::map или std::set (которое, как я полагаю, использует Sutter), не имеет быстрого алгоритма для нахождения n-го элемента. Здесь один, который, как утверждается, является O (log n) в среднем и O (n) в худшем случае. Но std::map и std::set не предоставляют доступ к базовой структуре дерева, поэтому для тех, с которыми вы застряли в обходном порядке (исправьте меня, если я ошибаюсь), который является линейным поиском снова! Я действительно удивлен, что версия карты является конкурентоспособной с векторной в результатах Sutter.

Для сложности log (n) вам нужна структура, такая как Заказать дерево статистики, которая, к сожалению, не предоставляется стандартной библиотекой. Там GNU на основе политик STL MAP, как показано здесь.

Вот быстрый тестовый код, который я сделал для вектора vs set vs ost (vs vector с бинарным поиском для хорошей оценки) https://ideone.com/DoqL4H Набор намного медленнее, тогда как другая структура на основе дерева быстрее, чем вектор, что не соответствует результатам Sutter.

order statistics tree: 15.958ms
vector binary search: 99.661ms
vector linear search: 282.032ms
set: 2004.04ms

(N = 20000, разница только будет больше в пользу ost с большими значениями)

Короче говоря, я пришел к такому же выводу, что исходные результаты Саттера кажутся странными, но по несколько иной причине. Мне кажется, что лучшая асимптотическая сложность на этот раз выигрывает на более низких постоянных множителях.

Обратите внимание, что описание проблемы не исключает возможности дублирования случайных значений, поэтому использование map/set вместо multimap/multiset немного изменяет предпочтение карты/набора, но я предполагаю, что иметь только небольшое значение когда область значений намного больше, чем N. Кроме того, предварительное резервирование вектора существенно не улучшает производительность (около 1% при N = 20000).

Ответ 2

Конечно, трудно дать точный ответ в отсутствие исходного кода плюс информация о параметрах компилятора, оборудовании и т.д.

Пара возможных различий:

Я думаю, что оратор каждый раз говорит о вставках/удалении в середине вектора (тогда как вы всегда добавляете в конец и удаляете с самого начала в вашем примере);
Оратор не упоминает, как определить, какие элементы добавлены/удалены, но в этом случае мы можем также предположить, что минимальное усилие делается для определения этого: каждый раз вы делаете векторный доступ, тогда как значения вставки (например, использовать недорогую PNRG для определения следующего значения для вставки) или всегда быть одинаковым, и для удаления средний элемент удаляется каждый раз, поэтому никакое значение не нужно искать/вычислять.

Однако, как заметил еще один комментатор, я бы отбрал общий принцип, а не конкретное число/тайминги. По сути, сообщение о выводе: то, что вы считали "счетными операциями" для оценки производительности/масштабируемости алгоритма, больше не соответствует современным системам.