Блог

Главная - Вопросы по программированию - Существует ли контейнер, похожий на `std :: deque`, но с настраиваемым размером блока и лучшей производительностью?

Существует ли контейнер, похожий на `std :: deque`, но с настраиваемым размером блока и лучшей производительностью?

#c #performance #stdvector #deque #stddeque

#c #Производительность #stdvector #deque #стандартный формат

Вопрос:

Недостатками std::deque являются более низкая производительность по сравнению std::vector с доступом к элементам в случайных позициях и тот факт, что блоки памяти, в которых хранятся данные, имеют заранее определенный фиксированный размер.

Существуют ли альтернативные (даже из STL) классы контейнеров, которые позволяют:

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

Примечание: меня интересует производительность, связанная с доступом к элементам, а не с их вставкой / удалением.

Комментарии:

1. «Размер блока» и «разыменование двух указателей» — это детали реализации. Контейнеры не определяются их реализацией; они определяются их интерфейсами и свойствами этих интерфейсов. Что вы хотите сделать с этим гипотетическим контейнером?

2. Было бы полезно, если бы вы могли описать, что вы хотите сделать со своими данными, а не как, по вашему мнению, это должно работать. У вас есть отсортированные данные? Вы чаще читаете или пишете, получаете ли вы к нему предсказуемый доступ (попадание в кэш / прогнозирование ветвления) и т. Д. И какую реальную проблему вы хотите решить. Производительность — это не пони с одним трюком

3. @TedLyngmo я тоже думал об этом. И в конце OP должен измерять фактические данные, если производительность соответствует ожидаемой / указанной. Измерять всегда измерять…

4. Если вы планируете скрыть сложность реализации целевой структуры данных в итераторах (например, то, что в основном делает STL), то вы вряд ли сможете быть такими же быстрыми, как a std::vector . Действительно, a std::vector является непрерывным в памяти и имеет тривиальную реализацию итератора. Таким образом, компилятор может выполнять множество расширенных оптимизаций (например, векторизацию), что во многих случаях приводит к значительному повышению производительности. При такой блочной структуре вам необходимо использовать медленное условие (или трюки, приводящие к эквивалентной зависимости, переносимой циклом), что, как правило, предотвращает оптимизацию компилятора.

5. Если вы когда-нибудь хотели узнать, насколько «непредсказуемой» может быть производительность (прирост), посмотрите это: youtube.com/watch?v=FJJTYQYB1JQ ( youtube.com/watch?v=FJJTYQYB1JQ ).

Ответ №1:

Пожалуйста, проверьте мою библиотеку на GitHub: https://github.com/slavenf/sfl-library

Эта библиотека предлагает контейнер sfl::segmented_vector . Этот контейнер похож на std::deque . Размер блоков (я называю их сегментами) указывается во время компиляции в качестве параметра шаблона.

Метки: , ,