Comments 24
В описании std::vector
небольшая неточность - стратегия роста емкости никак не указана в стандарте, так что это деталь реализации. В stdlibc++ и libc++ это удвоение размера, но вроде бы в Visual C++ используется множитель 1.5
Еще у Matthew Bentley, автора Colony, есть интересный документ про рост емкости для deque-like контейнера: https://plflib.org/matt_bentley_-_pot_blocks_bit_tricks.pdf
Спасибо! Да, проверил что для Visual C++ в 1.5 раза увеличивается
Добавлю, что в теории оптимально использовать золотое сечение как коэффициент увеличения буфера. Но умножать на 1.61803398875 и потом округлять накладно да и не не имеет особого смысла практически. Поэтому используют сдвиг вправо или сдвиг влево и сложение с исходной величиной.
Я конечно не специалист по C, и возможно что-то не так понял, но... Если ваш контейнер содержит не ссылку на объект, а сам объект, то использовать ссылку на него, во вне работы с контейнером - ну... будет беда. Либо copy on write (value type), без ссылок, либо ссылки в контейнере.
Возможно я был не прав, но сама идея ссылки на элемент контейнера, инстинктивно вызывает у меня отторжение, и это мягко сказано. Тем более, тип контейнера имеет тенденцию меняться, а код который его использует, нет.
Иногда без этого никак. Например, вам нужен быстрый поиск и одновременно определенный порядок: придется завести map и скажем list, и иметь перекрестные ссылки между контейнерами. Хорошая практика конечно абстрагировать это как новый тип контейнера, но внутри будут ссылки между используемыми контейнерами.
fbvector не cache-friendly, а снижает фрагментацию памяти (или, лучше сказать, в случае удвоения фрагментация практически гарантирована).
Это одно и то же в данном контексте: рост с фактором меньше 2х позволяет вектору при росте использовать свои предыдущие куски памяти. Это и снижает фрагментацию и делает это cache-friendly поскольку предыдущие куски вероятно в кеше.
Так ли важно, находится ли в кэше память, которую вы перезаписываете?
Да, хотя не так сильно как на чтение конечно, и от конкретной системы зависит.
Всё что вы перезапишите должно быть рано или поздно скинуто в основную память. Если новый вектор расположен поверх старых, а старые версии еще не попали в основную память - то сброс этих старых версий в основную память вы сэкономили. В результате вам надо меньше пропускной способности шины.
Плюс в многопроцессорных системах экономия на координации в каком кеше какая память лежит.
Потрясающая статья, спасибо за труды!
более оптимально аллоцировать
классическая ошибка, не бывает более или менее оптимально, бывает либо оптимально, либо нет, это же определение оптимальности :)
Спасибо, хорошая подборка. Вы не упомянули boost::intrusive (как концепцию и как набор конкретных контейнеров). Она хорошего качества (я использую в проде много лет) и позволяет клепать вещи типа multi-index или queue-map правильно и быстро.
Искренне интеретсуюсь, почему std::valarray пропущен в статье ?
Часто провожу собеседования, статистически о std::valarray, кандидаты знают +- как и о std::deque = ничего.
В статье рассматривается скорее внутреннее устройство контейнеров и управление памятью.
std::valarray
по своему внутреннему устройству имеет незначительное отличие от std::vector
(а именно 2 указателя вместо 3, так как там size = capacity).
"Синтаксический сахар" (методы min
, sqrt
, и тд) для std::valarray
отличается от такового у std::vector
, но это не так важно. В мире C++ есть много vector-like объектов, но они не принесли бы принципиально новой информации в статью.
std::valarray имеет довольно таки интересный "сахар", как например, запись для обнуления элементов меньших нуля:
data[ data < 0 ] = 0;
Само по себе, существование такого сахара вызывает как минимум - любопытство. (Кто сможет реализовать такое API в векторе, не зная изначально и не подглядывая как это сделано в valarray ?).
Ну и в отличии от vector`а стандрат разрешает распарралеливать "сахар" (интересно реализовано ли это в современных компиляторах ?), и имеет дополнительные правила для aliasинга элементов что ещё больше делает его особенным.
Спасибо за отличный обзор!
Можете что-нибудь сказать о библиотеке Bitmagic, как альтернативе bitset или vector<bool>?
К сожалению, не пользовался библиотекой Bitmagic. Прочитав про нее, увидел что это очень мощная библиотека. Про устройство - последовательность битов там может иметь очень разные представления. Все зависит от сценариев использования, мне хватало функционала bitset и dynamic_bitset.
Единственно (на мой взгляд) минус в том, что библиотека Bitmagic является header-only, это негативно влияет на время компиляции.
таких классов довольно мало и это событие маловероятно
что-то мне такой подход не очень
Я на всякий случай проверил работу алгоритма перемещения.
Изначально есть capacity для 10 объектов, при превышении делается реаллокация. Move-конструктор (не-noexcept) на 5-м объекте бросает исключение.
Если есть конструктор копирования, то вызывается именно он - https://godbolt.org/z/8qnEavP1f и strong exception guarantee выполнится
Widget(const Widget&) = default;
Если его нет, то вызывается move-конструктор за неимением другого варианта и после ловли исключения часть объектов "побита" - https://godbolt.org/z/x5hjcGTqE
Widget(const Widget&) = delete;
Поэтому лучше стараться делать move-конструктор noexcept, а то много проблем может быть
Почему итератор у vector не сделан в виде 2 чисел - ссылка на сам вектор и номер позиции в векторе (начиная с 0)? Ведь в этом случае итератор бы не протухал, когда вектор ресайзится.
Думаю что это сделано из соображений перфоманса.
С вашим дизайном было бы так: разыменовать (1) ссылку на вектор, посмотреть на .data()
, разыменовать (2) сам объект в нужном адресе.
С текущим дизайном разыменование одно, так как сразу знаем нужный адрес.
Можно считать что итератор станет работать в 2 раза медленнее.
Режет глаз упоминание терминов “на стеке" и "в куче". Они относятся к регионам памяти, которые можно использовать произвольно - можно, например, выделить через new vector с кастомным аллокатором над куском стека, тогда вектор будет в куче, а элементы на стеке. А может быть всё в статической памяти. Поэтому лучше бы использовать термины вроде "непосредственно в объекте контейнера" и "аллоцируется отдельно".
Неклассические контейнеры в C++