folly::fbvector — улучшенный std::vector от Facebook

Original author: Helios Alonso Cabanillas
  • Translation
  • Tutorial
Folly — это открытая С++ библиотека, разрабатываемая Facebook и используемая им во внутренних проектах. С целью оптимизации расходов памяти и процессорных ресурсов библиотека включает собственные реализации некоторых стандартных контейнеров и алгоритмов. Одной из них является folly::fbvector — замена стандартного вектора (std::vector). Реализация от Facebook полностью совместима с оригинальным интерфейсом std::vector, изменения всегда не-негативны, почти всегда измеримы, часто — существенно, а иногда даже грандиозно влияют на производительность и\или расход памяти. Просто включите заголовочный файл folly/FBVector.h и замените std::vector на folly::fbvector для использования его в своём коде.

Пример


folly::fbvector<int> numbers({0, 1, 2, 3});
numbers.reserve(10);
for (int i = 4; i < 10; i++) {
  numbers.push_back(i * 2);
}
assert(numbers[6] == 12);


Мотивация


std::vector — устоявшаяся абстракция, которую многие используют для динамически-аллоцируемых массивов в С++. Также это самый известный и самый часто используемый контейнер. Тем большим сюрпризом оказывается то, что его стандартная реализация оставляет достаточно много возможностей по улучшению эффективности использования вектора. Этот документ объясняет, как реализация folly::fbvector улучшает некоторые аспекты std::vector. Вы можете воспользоваться тестами из folly/test/FBVectorTest.cpp чтобы сравнить производительность std::vector и folly::fbvector.

Управление памятью


Известно, что std::vector растёт экспоненциально (с константным коэффициентом роста). Важный нюанс в правильном выборе этой константы. Слишком маленькое число приведёт к частым реаллокациям, слишком большое — будет съедать больше памяти, чем реально необходимо. Изначальная реализация Степанова использовала константу 2 (т.е. каждый раз, когда вызов push_back требовал расширения вектора — его емкость увеличивается вдвое).

Со временем некоторые компиляторы уменьшили эту константу до 1.5, но gcc упорно использует 2. На самом деле можно математически доказать, что константа 2 — строго худшее из всех возможных значений, потому что оно никогда не позволяет переиспользовать ранее выделенную вектором память.

Чтобы понять почему это так — представьте себе вектор размером в n байт, уже полностью заполненный, в который пытаются добавить ещё один элемент. Это приводит, согласно реализации std::vector, к следующим шагам:
  1. Выделяется память, размером в 2 * n байт. Скорее всего, она будет выделена в адресном пространстве ЗА текущим вектором (может быть непосредственно за, может быть через какой-то промежуток).
  2. Старый вектор копируется в начало нового.
  3. В новый вектор добавляется новый элемент.
  4. Старый вектор удаляется.


Когда дело дойдёт до увеличения этого нового вектора — он будет увеличен до 4 * n, далее — до 8 * n и т.д. При каждом новом выделении памяти её будет требоваться больше, чем для всех предыдущих векторов, вместе взятых, поскольку на каждом шаге k нам понадобиться (2 ^ k) * n байт памяти, а это всегда больше суммы (2 ^ (k — 1)) * n + (2 ^ (k — 2)) * n… + ((2 ^ 0 )) * n

Т.е. менеджер памяти никогда не сможет переиспользовать ранее выделенную для вектора память и всегда будет вынужден выделять «новую» память. Вряд ли это действительно то, чего мы хотим. Так вот, любое число, меньшее, чем 2 гарантирует, что на каком-то шаге увеличения ёмкости вектора мы сможем не выделять память в новом адресном пространстве, а переиспользовать уже ранее выделенную на этот вектор память.

График показывает что при константе увеличения ёмкости равной 1.5 (синяя линия) память может быть переиспользована уже послге 4-го шага увеличения вектора, при 1.45 (красная линия) — после третьего, и при 1.3 (чёрная линия) — после второго.

image

Конечно, график выше делает несколько упрощений по поводу того, как в реальном мире работают аллокаторы памяти, но факт того, что выбранная gcc константа 2 является теоретически худшим случаем, от этого не меняется. fbvector использует константу 1.5. И это не бьёт по производительности на малых размерах векторов, из-за того, как fbvector взаимодействует с jemalloc.

Взаимодействие с jemalloc


Практически все современные аллокаторы памяти выделяют память определёнными квантами, выбранными так, чтобы минимизировать накладные расходы на управление памятью и в то же время дать хорошую производительность на малых размерах выделяемых блоков. К примеру, аллокатор может выбирать блоки примерно так: 32, 64, 128,… 4096, затем пропорционально размеру страницы до 1 МБ, затем инкременты по 512 КБ и так далее.

Как обсуждалось выше, std::vector также требует выделения памяти квантами. Размер следующего кванта определяется исходя из текущей ёмкости вектора и константы роста. Таким образом в почти каждый момент времени у нас имеется некоторое количество неиспользуемой в текущий момент времени памяти в конце вектора, и сразу за ним — некоторое количество неиспользуемой памяти в конце блока памяти, выделенного аллокатором. Сам по себе напрашивается вывод о том, что союз аллокатора вектора и общего аллокатора памяти может дать оптимизацию расхода ОЗУ — ведь вектор может попросить у аллокатора блок «идеального» размера, исключив неиспользуемую память в блоке, выделенном аллокатором. Ну и вообще общую стратегию выделения памяти вектором и аллокатором можно заточить лучше, если знать точную реализацию того и другого. Именно это и делает fbvector — он автоматически определяет использование jemalloc и подстраивается под его алгоритмы выделения памяти.

Некоторые аллокаторы памяти не поддерживают in-place реаллокацию (хотя большинство современных всё-же поддерживают). Это результат не слишком удачного дизайна сишной функции realloc(), которая сама решает, переиспользовать ли ей ранее выделенную память, или выделить новую, скопировать туда данные и освободить старую. Этот недостаток контроля выделения памяти сказывается и на операторе new в С++ и на поведении std:allocator. Это серьёзный удар по производительности, поскольку in-place реаллокация, будучи очень дешевой, приводит к значительно менее аггрессивной стратегии роста потребляемой памяти.

Реаллокация объектов


Одним из важных вопросов размещения объектов С++ в памяти является то, что по-умолчанию они считаются неперемещаемыми. Перемещаемым считается объект типа, который может быть скопирован в другое место памяти путём побитового копирования и при этом в новом месте объект полностью сохранит свою валидность и целостность. К примеру, int32 является перемещаемым, потому что 4 байта полностью описывают состояние 32-битного знакового числа, если скопировать эти 4 байта в другое место памяти — этот блок памяти может полностью однозначно быть интерпретирован как то же самое число.

Предположение С++ о том, что объекты являются неперемещаемыми вредит всем и делает это лишь ради нескольких спорных моментов архитектуры. Перемещение объекта предполагает выделение памяти под новый объект, вызов его конструктора копирования, уничтожение старого объекта. Это не очень приятно и вообще против здравого смысла. Представьте себе теоретический разговор капитана Пикара и Скептического Инопланетянина:

Скептический Инопланетянин: Итак, этот ваш телепорт — как он работает?
Пикар: Он берёт человека, дематериализует его в одном месте и материализует в другом
Скептический Инопланетянин: Хм… это безопасно?
Пикар: Да, правда в первых моделях были мелкие недочёты. Сначала человек просто клонировался, создавался в новом месте. После этого оператор телепорта должен был вручную застрелить оригинал. Спроси О'Браяна, он работал интерном как-раз на этой должности. Не очень элегантная была реализация.

(прим. переводчика: видимо, это писалось до внедрения конструкторов перемещения в последних стандартах С++).

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


Объекты первого типа всегда могут быть переделаны с минимальными затратами. Объекты второго типа не должны создаваться оператором new и удаляться оператором delete — они должны быть управляемы умными указателями и никаких проблем не будет.

Перемещаемые объекты весьма интересны для std::vector, поскольку знание о том, как перемещать объекты внутри вектора существенно влияет на эффективность реаллокации вектора этих объектов. Вместо вышеописанного Пикардовского цикла перемещения, объекты можно перемещать простым memcpy или memmove. К примеру, работа с типами вроде vector<vector> или vector<hash_map<int, string>> может быть значительно быстрее.

Для того, чтобы поддерживать безопасное перемещение объектов, fbvector использует типаж (trait) folly::IsRelocatable, определённый в «folly/Traits.h». По-умолчанию, folly::IsRelocatable::value консервативно возвращает false. Если вы точно знаете, что ваш тип Widget является перемещаемым, вы можете сразу после объявления этого типа дописать:

namespace folly {
  struct IsRelocatable<Widget> : boost::true_type {};
}


Если вы не сделаете этого, fbvector не скомпилируется с BOOST_STATIC_ASSERT.

Дополнительные ограничения


Некоторые улучшения также возможны для «простых» типов (точнее для тех, которые имеют тривиальную операцию присваивания) или для тех типов, которые имеют конструктор, не выбрасывающий исключений (nothrow default constructor). К счастью, эти типажи уже присутствуют в стандарте С++ (ну или в Boost). Суммируя, для работы с fbvector тип Widget должен удовлетворять условию:

BOOST_STATIC_ASSERT( IsRelocatable::value && (boost::has_trivial_assign::value || boost::has_nothrow_constructor::value));


Эти типажи на самом деле очень близки — достаточно сложно сконструировать класс, который будет удовлетворять одной части условия и нарушить другую (разве что специально очень постараться). fbvector использует эти простые условия для минимизации операций копирования для основных операций с вектором (push_back, insert, resize).

Для упрощения проверки типа на совместимость с fbvector в Traits.h есть макрос FOLLY_ASSUME_FBVECTOR_COMPATIBLE.

Разное


Реализация fbvector сконцентрирована на эффективности использования памяти. В будущем может быть улучшена реализация копирования из-за того, что memcpy не является intrinsic-функцией в gcc и не идеально работает для больших блоков данных. Также возможно улучшение в области взаимодействия с jemalloc.

Удачного вам использования fbvector.
Инфопульс Украина
Creating Value, Delivering Excellence
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 50

    +77
      +1
      Не стреляйте в переводчика, график из оригинала.
        0
        Переводчик он как пианист в салуне.

        Вспомнилось из какой-то игры 15летней давности. Салун, NPC пианист.
        — Тут работа хорошая, в пианиста только раз в неделю стреляют.
      0
      Интересная статья. Но если им так критично выделение памяти, зачем копировать объекты на новый участок и удалять со старого? Ведь можно иметь много массивов. К примеру, есть вектор, в нем массив A[2000], в него нужно добавить 2001 элемент, мы создаем массив B[vector.length*1.3], добавляем в B[0] наш элемент, length вернет 2001, capacity будет 4600.

      Вектор же при вызове get(2001) просто пройдет все массивы (по какому-либо оптимизированному алгоритму, ведь суммарная длина всех известна) и вернет из нужного искомый элемент.
        +5
        Стандарт С++ требует от вектора связного хранения всего блока данных, так, чтобы можно было взять указатель на первый элемент и дальше арифметикой указателей бегать по вектору. Есть другие структуры данных, где этого требования нет, но это уже будет не вектор.
          0
          Понял, спасибо.
          Ради любопытства посмотрел в исходники ArrayList в Java. Там множитель 1.5 (size + (size>>1)), при этом минимальный инкремент равен 12.
          +4
          Такая реализация в стандартной библиотеке уже есть в std::deque, но это все равно медленнее при последовательном чтении, как ни оптимизируй. Работу кэша процессора, задержки при рандомном доступе к памяти и prefetch никто не отменял.
            +1
            Если сделать, как вы предлагаете, то vector уже не будет единым массивом в памяти, а будет представлять собой более сложную структуру данных. К ней будет более медленный доступ (т. к. надо будет выяснять, к какому именно из массивов относится наш элемент). И тогда в соответствии с принципом «гулять, так гулять» нужно будет использовать не несколько массивов, а тогда уж сразу красно-чёрные деревья или ещё что-нибудь в этом роде
              0
              B-деревья надо тут использовать, а не красно-черные
            +3
            Объекты первого типа всегда могут быть переделаны с минимальными затратами. Объекты второго типа не должны создаваться оператором new и удаляться оператором delete — они должны быть управляемы умными указателями и никаких проблем не будет.


            Кажется, что если объект имеет указатели на другие объекты, то это не делает его неперемещаемым — простое побитовое копирование не меняет состояние объекта. А значит затрат нет вообще никаких.

            По поводу второго типа вообще не понятно. Интересно, как же это так создать объект и управлять им с помощью умного указателя без оператора new… Вдобавок возникает вопрос, как умный указатель решает проблему неперемещаемости объекта, на который есть указатели.
              0
              Я это место тоже не понял.

              Если на объект есть указатель, переместить его нельзя, не поменяв сам указатель каким-то образом. Описанный «Пикардовский цикл» эту проблему не решает. То, что объект будет пересоздан с помощью конструктора, никак не пофиксит внешние указатели.
                +1
                Побитовое копирование объекта с указателем даст, конечно, валидный объект. Но что дальше? При удалении оригинального объекта нужно освободить этот указатель? А при удалении копии? А как они узнают, не произошло ли уже удаление? Всё это можно исправить использованием вместо голых указателей, в зависимости от ситуации: ссылок, агрегации, синглтонов или умных указателей — в каждой из этих ситуаций однозначно понятно, что будет с ресурсом при удалении объекта. Но это нужно взять и сделать.

                И то же самое по поводу второго типа — разные типы умных указателей (unique_ptr, shared_ptr, weak_ptr, auto_ptr) дают объектам понимание, кто из них реально владеет ресурсом, а кому просто временно позволено иметь к нему доступ.
                  0
                  Каюсь, видимо я уже настолько привык использовать scoped_ptr/unique_ptr, что простой указатель внутри объекта для меня уже стал сущностью, которой явно владеет какой-то другой объект. В таком случае да, согласен, простое копирование вносит путаницу в понимание, кто владеет указателем. С другой стороны, в данной статье речь о перемещении, а не о копировании, а с перемещением такой проблемы не стоит.

                  Во втором случае умные указатели не решают проблему того, что при перемещении объекта нужно поправить все указатели на этот объект. Банально, если в стеке во время перемещения есть вызов метода этого объекта, то после возврата в этот метод станет невалидным указатель this, а значит, при доступе к любым данным объекта, программа свалится.
                    +5
                    Не путайте перемещение и копирование. Если в объекте есть указатель, то не совсем понятно, можно ли его так просто скопировать. А вот переместить его можно (если нет других вещей, мешающих перемещению). То есть можно взять объект, побайтово скопировать и считать предыдущую копию недействительной. И не вызывать ни деструкторов, ни конструкторов, ничего. Тогда объект по-прежнему останется существующим в единственном экземпляре, предыдущая копия объекта будет считаться мусором, размещённым в памяти.

                    В общем, наличие в объекте указателей никак не мешает его перемещению, так что, плз, уберите этот пункт из статьи или поставьте примечание переводчика.

                    Ну и учтите замечание alexac и TechThink и напишите отчётливо (можно опять-таки в примечании переводчика), что «пикаровское» копирование не спасает от инвалидации внешних указателей.

                    (Ну и заодно напишите где-нибудь, что Пикар — это персонаж Стар Трек, а то еле нашёл в инете.)

                    P. S. В этом моём сообщении под копированием я понимаю копирование объекта в памяти, при котором далее предполагается работа с обоими копиями. Под перемещением — такое копирование, при котором дальнейшая работа будет происходить только с новой копией. Т. е. в этом сообщении разница между копированием и перемещением чисто ментальная. Копирование — это когда в коде стоит, скажем, memcpy, после чего программист мысленно себе говорит: «Дальше я не буду работать с исходной копией», даже если в коде это никак не выражено. Т. е. разница в копировании и перемещении в цели, с которой это копирование происходит, а в коде эта цель может быть никак не выражена. К move semantics в C++11 моё перемещение никакого отношения не имеет
                      0
                      А вот переместить его можно (если нет других вещей, мешающих перемещению). То есть можно взять объект, побайтово скопировать и считать предыдущую копию недействительной.
                      Если у других объектов (или у этого же объекта) есть ссылки на поля перемещаемого объекта, то его нельзя вот так взять и передвинуть. Если этот объект лежал себе в каком-нибудь пуле, то его тоже нехорошо оттуда убирать, не сказав об этом пулу.
                        0
                        В этом посте на хабре написано:
                        На самом деле только часть объектов действительно неперещаемы:
                        * Те, в которых есть указатели на внешние объекты
                        * Те, на которые указывают указатели из других объектов

                        Моё сообщение было критикой первого пункта. Со вторым пунктом я согласен
                    +1
                    Дело в том, что и в стандартном векторе при изменении размера итераторы могут стать невалидными. Поэтому если вы получили указатель на элемент через vec[i], то вы сами должны следить за тем, чтобы размер вектора не менялся. А вот если объект отдал указатель на часть себя внутри какой-то функции, то он сам и должен за этим указателем следить. Вот умные указатели это умеют — при копировании объект, содержащийся внутри умного указателя, останется на том же месте.
                      +1
                      Да, при изменении размера вектора указатели на его элементы могут стать не валидными. Но умные указатели никак не решают эту проблему.

                      Разве что вы сделаете конструкцию
                      std::vector<std::unique_ptr<T> >
                      . Но это не решает проблемы того, что указатели и ссылки на сами умные указатели все равно будут битыми после изменения размера вектора, просто потому что умный указатель — это тоже объект. То есть, такими методами вы добьетесь неизменства указателя на объект класса T, но в такой схеме этот объект уже никакого отношения к вектору не имеет, и проблему вы не решили, а обошли.

                      Вы не можете написать:
                      
                      class A {};
                      
                      std::vector<std::unique_ptr<A> > vector;
                      
                      std::unique_ptr<A>& ptr = vector[i];
                      vector.push_back(...);
                      ptr.reset(new A()); // ссылка ptr может быть битой.
                      
                      
                        0
                        Так и есть. Но если вы сделали std::unique_ptr<A>& ptr = vector[i];, а потом vector.push_back(...); ptr.reset(new A());, то сами виноваты. Но если у вас был сначала vector<A>, а вы заменили его на vector<unique_ptr<A>>, и вам нужно было именно сохранить указатель на A, то проблему таки обошли. Вот они и предлагают такой способ обходить проблему, собственно.
                          +1
                          Как-то это костыльно… Имхо, на доступе к объектам через unique_ptr, хранящийся в векторе, можно потерять больше, чем на переаллокациях в этом векторе. То есть гнаться за Relocatable только ради Relocatable — это странно. А судя по фразе «Если вы не сделаете этого, fbvector не скомпилируется с BOOST_STATIC_ASSERT.» Бравым ребятам из фэйсбука без этого никак.
                            0
                            Тут альтернатива smart_ptr по сути только std::list, или std::deque, если не удаляете с середины. Так что нужно уже по задаче смотреть, что лучше будет.
                    +5
                    Вообще предельная оптимизация аллокаций/перемещений вектором это выделить ровно столько сколько потребуется. А тащить к себе лишнюю библиотеку только изза того что в ней один коэфициент меньше чем в gcc это както чересчур
                      –1
                      выделить ровно столько сколько потребуется

                      Т.е. каждый новый push_back должен приводить к аллокации нового вектора, на 1 элемент большего, чем предыдущий? Чудовищное решение.
                        +1
                        Учесть статистику по итоговым длинам при выборе изначальной емкости?
                          +1
                          Нет. Если вы на каждый новый push_back аллоцируете новый вектор, значит Вы таки выделили не столько сколько нужно.

                          leventov выше один из вариантов написал.
                            +1
                            Если сразу точно знать, сколько нужно, то тут и вектор не нужен — достаточно массива.
                              +1
                              И реализовывать самому insert(), erase(), size() etc? :)
                                0
                                Ну, если мы точно знаем сколько нужно, то и размер не меняется. А для этого есть std::array.
                                  0
                                  Вы путаете сколько нужно на время работы программы и сколько там лежит в конкретный момент времени
                                    +2
                                    Так бы и говорили сразу что вы .reserve() имеете в виду
                                      0
                                      Я имел ввиду выделение памяти. В контексте «оптимально». Как оно может быть сделано — зависит от задачи. Может быть reserve() достаточно, а может сразу:
                                      std::vector v( desired_size, A() );
                                      или
                                      v( my_generator.begin(), my_generator.end() );
                        +5
                        На самом деле можно математически доказать, что константа 2 — строго худшее из всех возможных значений, потому что оно никогда не позволяет переиспользовать ранее выделенную вектором память.

                        Мне это фраза напомнила тот анекдот, «и не выиграл, а проиграл».

                        Во-первых, 2 — это всего лишь минимальное значение с таким свойством, непонятно, чем оно «строго хуже», например, константы 3.

                        Во-вторых, у этой константы есть и более важные свойства, например, ожидаемый коэффициент memory overuse, см. github.com/OpenHFT/Koloboke/wiki/Magic-Factors#grow-factor

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

                        Короче говоря, безотносительно того, что константа 1,5 и правда кажется лучше, чем 2, объяснение под это подбито просто нелепейшее.
                          +1
                          По-моему, в этой статье (ее оригинальном варианте) вообще почти все притянуто за уши. Такое ощущение, что автор не понимает, как STL реализована в большинстве дистрибутивов.
                            +2
                            Зачем вообще аллоцировать целиком новый вектор сразу за старым, если в этом случае можно сделать просто реаллок?)
                            Там же объясняется, почему нельзя так делать для неперемещаемых объектов. В Си++ не предусмотрена переносимая функция «попробовать расширить кусок памяти в куче, но не трогать его, если не получается». realloc() может взять и переместить данные вектора в другое место, что может печально сказаться на объектах. Разумеется, для всяких интов и структурок из интов так делать можно. Для этого-то у них и добавлен трейт IsRelocatable, который позволяет использовать realloc().
                              0
                              Кстати, вот очень бы хотелось увидеть, рано или поздно, в C++ такой интерфейс.
                                0
                                Спасибо, теперь понятно. Значит мой третий пункт невалиден.
                                0
                                я аналогично выпад на realloc() не понял:
                                Это результат не слишком удачного дизайна сишной функции realloc(), которая сама решает, переиспользовать ли ей ранее выделенную память, или выделить новую, скопировать туда данные и освободить старую.


                                а что если он реально не может расширить тещую область на указанный размер, т.к. за этим блоком уже что-то есть. Почему это неудачный дизайн? И как он должен в этой ситуации поступать, кроме как выделить новый блок и скопировать туда старые данные?
                                  +1
                                  Имеется в виду, как раз таки описанное выше «попробовать расширить кусок памяти в куче, но не трогать его, если не получается». Выделить новую память, и скопировать данные, пользователь всегда может и сам, при необходимости. А вот проверить возможность расширяемости текущего куска — нет.
                                    0
                                    А понял, эдакий try_realloc().
                                      0
                                      Поправьте меня если я неправ:
                                      Можно ли просто по возвращаемому realloc указателю понять — выделила она в новом месте или просто расширила?
                                      Если указатель изменился, мы вызываем конструкторы перемещения, если нет, то не вызываем.
                                        +1
                                        Конечно, можно понять, но откуда и для чего вы будете вызывать конструкторы перемещения? Для перемещения объектов с нового места на то же самое новое место?
                                          0
                                          Понять по указателю, изменилось ли место расположения данных в памяти, мы можем, а вот сделать что-то с этим уже нет, поскольку старый блок памяти был уже удалён.
                                            0
                                            Спасибо, точно, не сообразил. Стыд мне (ибо пишу на плюсах давно).
                                    0
                                    А где тесты?
                                      0
                                      FBVectorTest.cpp (smoke test), StlVectorTest.cpp (соответствие требованиям STL)
                                        +2
                                        Хотелось бы видеть результаты пары бенчмарков в статье, но тут уж к автору вопрос, а не к переводчику.
                                      0
                                      Кстати говоря, кто-нибудь, кроме меня, обратил внимание на образцовые коммит-логи в репозитории?
                                        0
                                        Повторное использование памяти — это хорошо. Но будет ли это реально работать в системе, где в куче выделяется не только память под один вектор, а еще много всего другого, что может запросто заполнить освобожденную вектором память до того, как он решит реаллоцироваться?

                                        Предположение С++ о том, что объекты являются неперемещаемыми вредит всем и делает это лишь ради нескольких спорных моментов архитектуры.
                                        Вот когда-нибудь реализуют is_trivially_copyable trait, и стандартный вектор тоже оптимизируют.
                                          +1
                                          Такое впечатление, что почти все улучшения являются таковыми только относительно g++/libstdc++.
                                            0
                                            любое число, меньшее, чем 2 гарантирует, что на каком-то шаге увеличения ёмкости вектора мы сможем не выделять память в новом адресном пространстве, а переиспользовать уже ранее выделенную на этот вектор память.
                                            Гарантирует только в том случае, если мы можем использовать память предыдущих (n-1) аллоакций на n-м шаге. Действительно, пусть мы хотим найти такой коэффициент роста, что
                                            an ≤ an-1 + an-2 +… + a + 1
                                            Заметим, что справа стоит сумма геометрической прогрессии
                                            an ≤ (an — 1) / (a — 1)
                                            (a — 1) an ≤ an — 1 // тут было использовано предположение a > 1
                                            an+1 — 2 an ≤ -1
                                            an (a — 2) ≤ -1
                                            Видно, что начиная с 2 левая часть неотрицательна и условие никогда не выполняется.

                                            Однако, это сопряжено с некоторыми трудностями, ибо для этого придётся как-то переиспользовать то место, где у нас сейчас находится вектор, а нам ведь ещё скопировать элементы надо (Хотя теоретически это всё же возможно).

                                            Если же чуть ослабить условия и потребовать наличие достаточно количества памяти с предыдущих n-2 аллокаций, то мы получим
                                            an ≤ an-2 +… + a + 1
                                            (a-1) an ≤ an-1 — 1
                                            an+1 — an — an-1 ≤ — 1
                                            a2 — a — 1 ≤ — 1 / a(n-1) < 0

                                            Если в последнем неравенстве заметить, что правая часть стремится к нулю, или каким-либо другим способом убедить себя в том, что её можно выкинуть, то мы получим неравенство для многочлена второй степени, чей единственный корень, лежащий в интервале (1, 2), в точности равен золотому сечению. Разумеется, так как у нас неравенство, то сгодится любое число, большее 1 и меньшее φ. Например, 1.5 попадает в этот интервал.

                                            Only users with full accounts can post comments. Log in, please.