Developer Tales or everything about everything

14Дек/126

Анализ производительности std::vector, std::list & std::deque

В этой статье рассматривается тестирование производительности стандартных STL-контейнеров C++: std::vector, std::list и std::deque. Тестирование скорости работы контейнеров проводится для операций вставки, поиска и удаления.

Эта статья является переводом, оригинальная статья находится здесь.

В основном std::list следует использовать, если ожидается выполнение операций случайных вставок и удалений элементов из контейнера (сложность O(1) против O(n) для вектора (vector) или двусвязной очереди (deque)). Если рассматривать только сложность выполнения, то линейный поиск в обоих контейнерах эквивалентен - его сложность составляет O(n). Когда осуществляется вставка или удаление элементов в векторе или двусвязной очереди, все данные, следующие за позицией, над которой проводится операция, должны быть перемещены в памяти, фактически это означает, что каждый элемент должен быть скопирован. Именно по этой причине при определении производительности очень важен размер данных, короые будут помещены или уже находятся в контейнере.

Однако, теория обычно расходится с практикой: на практике часто используют кэш памяти. Данные в векторе располагаются последовательно, в то время, как данные списка могут быть размещены в разных участках памяти. Что это дает? Двусвязная очередь - это структура, которая нацелена на получение всех преимуществ std::list и std::vector и избежание их недостатков.

Все тесты проводились на Intel Core i7 Q 820 @ 1.73GHz на GCC 4.7.2 с параметрами -02 и -march=native. Код скомпилирован с поддержкой C++11 (-std=c++11).

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

Добавление в конец

Первый проведенный тест - заполнение контейнеров данными, т.е. добавление элементов в конец контейнера (push_back). Здесь vector_pre означает контейнер, для которого был вызван метод resize() перед вставкой данных - благодаря этому память в контейнере выделяется всего один раз. Размер типа - 8 байт.

Вектор с предварительно выделенной память немного быстрее всех, а список в три раза медленнее, чем вектор.

Теперь возьмем тип с большим размером (4096 байт):

Здесь ситуация меняется. Вектор и список имеют схожую скорость. Двусвязная очередь немного быстрее, чем вектор и список. Вектор с заранее выделенной памятью по-прежнему выигрывает.

Наконец, если использовать нетривиальный тип данных:

Все контейнеры имеют схожую производительность за исключением вектора с заранее выделенной памятью - он выигрывает.

Вывод: Для операций добавления в конец контейнера (push_back) наиболее хорошо подходят векторы с заранее выделенной памятью.

Линейный поиск

Для осуществления линейного поиска контейнеры заполняются числами от 0 до N. Затем все элементы контейнера перемешиваются и используется функция std::find(), которая и осуществляет линейный поиск в контейнере.

Из графика видно, что список (std::list) имеет очень низкую производительность поиска данных.

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

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

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

Если взять тип данных большего размера:

Список по-прежнему намного медленнее других контейнеров. Но интересно то, что разница между вектором и двусвязной очередью уменьшается. Еще увеличим размер:

Ситуация со списком не изменилась - поиск по-прежнему медленный. Однако, двусвязная очередь теперь работает быстрее, чем вектор! Причиной тому может служить тот факт, что чем больше размер данных, тем больше появляется ошибок кэша из-за того, что меньше данных помещается в очереди.

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

Случайная вставка с линейным поиском

В теории случайная вставка должна работать наиболее быстро для списка (std::list) - сложность этой операции для списка O(1) вместо O(n) у вектора и двусвязной очереди.

Контейнер заполняется числами от 0 до N, затем данные перемешиваются. После этого в контейнер вставляется 1000 элементов в случайные позиции. Случайные позиции ищутся с помоью линейного поиска. В предыдущих тестах было видно, что список работает очень медленно при линейном поиске, поэтому имеет смысл оценить, насколько помогает исправить ситуацию быстрая вставка.

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

Увеличим размер типа данных:

Результат довольно инетересен. Недостаток производительности списка уменьшается по сравнению с другими контейнерами, а двусвязная очередь оказывается быстрее всех. Еще увеличим размер:

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

Список более чем в 20 раз быстрее вектора. В случае с двусвязной очередью элементы можно добавлять в начало или конец, вставка в середину является наиболее дорогой операцией составляющей по сложности O(n/2). Однако, даже в этом случае, вставка в двусвязную очередь работает быстрее, чем вставка в вектор.

Последний тест можно провести с использованием нетривиального типа данных:

Результат получился примерно таким же, как и в предыдущем графике, но сейчас размер типа - всего 16 байт. Цена использования копирующих конструкторов и операторов присваивания очень важна для вектора и двусвязной очереди. Для списка это не важно потому что в данном случае производится только одно копирование - копирование вставляемого элемента.

Случайное удаление

В теории случайное удаление в плане производительности приближается к случайной вставке.

Контейнер заполняется числами от 0 до N и перемешивается. Затем 1000 случайных элементов удаляется из случайных позиций контейнера.

Действительно, по графикам видно, что операция удаления показывает ту же производительность, что и вставка.

Добавление в начало

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

Как и ожидалось - вектор показывает очень плохую производительность. Графики списка и двусвязной очереди почти не видны, т.к. для этих контейнеров данная операция является простой. Изменение размера данных не имеет смысла - ситуация не поменяется.

Сортировка

Следующая операция - сортировка данных. Для двусвязной очереди и вектора используется функция std::sort(), а для списка - встроенная функция sort().

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

Если увеличить размер типа данных:

Результаты почти такие же, но разница между списком и очередью начинает уменьшаться.

Список почти в 5 раз быстрее вектора, очередь по производительности становится близкой к вектору. Используем нетривиальный тип данных:

Снова цена операций для очереди и вектора имеет большой вес - список выигрывает.

Разрушение

Теперь давайте посмотрим на производительность разрушения объектов-контейнеров и удаление данных. Создаются динамические контейнеры и заполняются N элементами.

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

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

При увеличении размера типа данных:

На этот раз становится заметно, что двусвязная очередь в 3 раза медленнее, чем вектор. Список по-прежнему показывает очень плохую производительность.

Еще увеличим размер:

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

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

Сложные вычисления

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

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

Заключение

Несколько фактов о каждом контейнере:

  • std::list очень медленно осуществляет обход элементов из-за особенностей размещения данных;
  • std::vector и std::deque всегда работают быстрее с типами данных небольших размеров;
  • std::list хорошо обрабатывает большие элементы;
  • std::deque показывает лучшую производительность при вставке элементов в случайные позиции, в особенности - в начало очереди;
  • std::deque и std::vector плохо справляются с данными с высокой стоимостью копирующих конструкторов и операторов присваивания.

Соответственно, заключение о том, где использовать контейнеры:

  • Сложные вычисления: std::vector или std::deque;
  • Линейный поиск: std::vector или std::deque;
  • Случайная вставка или удаление: std::deque или std::list. Если размер данных мал, то лучше использовать std::deque;
  • Работа с данными больших размеров: std::list;
  • Нетривиальные типы данных: std::list;
  • Вставка в начало: std::deque или std::list.

Исходный код тестов: https://github.com/wichtounet/articles/blob/master/src/vector_list/bench.cpp

Необходимые заголовочные файлы можно найти в том же репозитории.

Просмотров: 11447
Комментарии (6) Пинги (0)
  1. Наконец-то нашёл наглядное чёткое объяснение сфере применения векторов и списков. Автору большое спасибо!http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_yahoo.gif

  2. УРА! Нормальное объяснение + статистика. Спасибо автору и переводчику.

  3. Супер, спасибо! Отличная статья. За картинки отдельный +, хотел расшарить vk, жаль у тебя нету этой штуки, хоть pluso уже подключи) А так, спасибо.http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_good.gif

  4. Спасибо за статью! Давно хотел пройтись по всем стандартным контейнерам, добавлю сортированный контейнер в анализ поиска и анализ по остальным контейнерам.

  5. Автору огромное спасибо за статью. Очень помогла. Респект! http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_good.gif


Leave a comment


− 3 = шесть

http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_bye.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_good.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_negative.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_scratch.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_wacko.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_yahoo.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_cool.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_heart.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_rose.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_smile.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_whistle3.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_yes.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_cry.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_mail.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_sad.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_unsure.gif 
http://microfork.com/wp-content/plugins/wp-monalisa/icons/wpml_wink.gif 
 

Trackbacks are disabled.