Comments 50
Интересная статья. Но если им так критично выделение памяти, зачем копировать объекты на новый участок и удалять со старого? Ведь можно иметь много массивов. К примеру, есть вектор, в нем массив A[2000], в него нужно добавить 2001 элемент, мы создаем массив B[vector.length*1.3], добавляем в B[0] наш элемент, length вернет 2001, capacity будет 4600.
Вектор же при вызове get(2001) просто пройдет все массивы (по какому-либо оптимизированному алгоритму, ведь суммарная длина всех известна) и вернет из нужного искомый элемент.
Вектор же при вызове get(2001) просто пройдет все массивы (по какому-либо оптимизированному алгоритму, ведь суммарная длина всех известна) и вернет из нужного искомый элемент.
Стандарт С++ требует от вектора связного хранения всего блока данных, так, чтобы можно было взять указатель на первый элемент и дальше арифметикой указателей бегать по вектору. Есть другие структуры данных, где этого требования нет, но это уже будет не вектор.
Такая реализация в стандартной библиотеке уже есть в std::deque, но это все равно медленнее при последовательном чтении, как ни оптимизируй. Работу кэша процессора, задержки при рандомном доступе к памяти и prefetch никто не отменял.
Если сделать, как вы предлагаете, то vector уже не будет единым массивом в памяти, а будет представлять собой более сложную структуру данных. К ней будет более медленный доступ (т. к. надо будет выяснять, к какому именно из массивов относится наш элемент). И тогда в соответствии с принципом «гулять, так гулять» нужно будет использовать не несколько массивов, а тогда уж сразу красно-чёрные деревья или ещё что-нибудь в этом роде
Объекты первого типа всегда могут быть переделаны с минимальными затратами. Объекты второго типа не должны создаваться оператором new и удаляться оператором delete — они должны быть управляемы умными указателями и никаких проблем не будет.
Кажется, что если объект имеет указатели на другие объекты, то это не делает его неперемещаемым — простое побитовое копирование не меняет состояние объекта. А значит затрат нет вообще никаких.
По поводу второго типа вообще не понятно. Интересно, как же это так создать объект и управлять им с помощью умного указателя без оператора new… Вдобавок возникает вопрос, как умный указатель решает проблему неперемещаемости объекта, на который есть указатели.
Я это место тоже не понял.
Если на объект есть указатель, переместить его нельзя, не поменяв сам указатель каким-то образом. Описанный «Пикардовский цикл» эту проблему не решает. То, что объект будет пересоздан с помощью конструктора, никак не пофиксит внешние указатели.
Если на объект есть указатель, переместить его нельзя, не поменяв сам указатель каким-то образом. Описанный «Пикардовский цикл» эту проблему не решает. То, что объект будет пересоздан с помощью конструктора, никак не пофиксит внешние указатели.
Побитовое копирование объекта с указателем даст, конечно, валидный объект. Но что дальше? При удалении оригинального объекта нужно освободить этот указатель? А при удалении копии? А как они узнают, не произошло ли уже удаление? Всё это можно исправить использованием вместо голых указателей, в зависимости от ситуации: ссылок, агрегации, синглтонов или умных указателей — в каждой из этих ситуаций однозначно понятно, что будет с ресурсом при удалении объекта. Но это нужно взять и сделать.
И то же самое по поводу второго типа — разные типы умных указателей (unique_ptr, shared_ptr, weak_ptr, auto_ptr) дают объектам понимание, кто из них реально владеет ресурсом, а кому просто временно позволено иметь к нему доступ.
И то же самое по поводу второго типа — разные типы умных указателей (unique_ptr, shared_ptr, weak_ptr, auto_ptr) дают объектам понимание, кто из них реально владеет ресурсом, а кому просто временно позволено иметь к нему доступ.
Каюсь, видимо я уже настолько привык использовать scoped_ptr/unique_ptr, что простой указатель внутри объекта для меня уже стал сущностью, которой явно владеет какой-то другой объект. В таком случае да, согласен, простое копирование вносит путаницу в понимание, кто владеет указателем. С другой стороны, в данной статье речь о перемещении, а не о копировании, а с перемещением такой проблемы не стоит.
Во втором случае умные указатели не решают проблему того, что при перемещении объекта нужно поправить все указатели на этот объект. Банально, если в стеке во время перемещения есть вызов метода этого объекта, то после возврата в этот метод станет невалидным указатель this, а значит, при доступе к любым данным объекта, программа свалится.
Во втором случае умные указатели не решают проблему того, что при перемещении объекта нужно поправить все указатели на этот объект. Банально, если в стеке во время перемещения есть вызов метода этого объекта, то после возврата в этот метод станет невалидным указатель this, а значит, при доступе к любым данным объекта, программа свалится.
Не путайте перемещение и копирование. Если в объекте есть указатель, то не совсем понятно, можно ли его так просто скопировать. А вот переместить его можно (если нет других вещей, мешающих перемещению). То есть можно взять объект, побайтово скопировать и считать предыдущую копию недействительной. И не вызывать ни деструкторов, ни конструкторов, ничего. Тогда объект по-прежнему останется существующим в единственном экземпляре, предыдущая копия объекта будет считаться мусором, размещённым в памяти.
В общем, наличие в объекте указателей никак не мешает его перемещению, так что, плз, уберите этот пункт из статьи или поставьте примечание переводчика.
Ну и учтите замечание alexac и TechThink и напишите отчётливо (можно опять-таки в примечании переводчика), что «пикаровское» копирование не спасает от инвалидации внешних указателей.
(Ну и заодно напишите где-нибудь, что Пикар — это персонаж Стар Трек, а то еле нашёл в инете.)
P. S. В этом моём сообщении под копированием я понимаю копирование объекта в памяти, при котором далее предполагается работа с обоими копиями. Под перемещением — такое копирование, при котором дальнейшая работа будет происходить только с новой копией. Т. е. в этом сообщении разница между копированием и перемещением чисто ментальная. Копирование — это когда в коде стоит, скажем, memcpy, после чего программист мысленно себе говорит: «Дальше я не буду работать с исходной копией», даже если в коде это никак не выражено. Т. е. разница в копировании и перемещении в цели, с которой это копирование происходит, а в коде эта цель может быть никак не выражена. К move semantics в C++11 моё перемещение никакого отношения не имеет
В общем, наличие в объекте указателей никак не мешает его перемещению, так что, плз, уберите этот пункт из статьи или поставьте примечание переводчика.
Ну и учтите замечание alexac и TechThink и напишите отчётливо (можно опять-таки в примечании переводчика), что «пикаровское» копирование не спасает от инвалидации внешних указателей.
(Ну и заодно напишите где-нибудь, что Пикар — это персонаж Стар Трек, а то еле нашёл в инете.)
P. S. В этом моём сообщении под копированием я понимаю копирование объекта в памяти, при котором далее предполагается работа с обоими копиями. Под перемещением — такое копирование, при котором дальнейшая работа будет происходить только с новой копией. Т. е. в этом сообщении разница между копированием и перемещением чисто ментальная. Копирование — это когда в коде стоит, скажем, memcpy, после чего программист мысленно себе говорит: «Дальше я не буду работать с исходной копией», даже если в коде это никак не выражено. Т. е. разница в копировании и перемещении в цели, с которой это копирование происходит, а в коде эта цель может быть никак не выражена. К move semantics в C++11 моё перемещение никакого отношения не имеет
А вот переместить его можно (если нет других вещей, мешающих перемещению). То есть можно взять объект, побайтово скопировать и считать предыдущую копию недействительной.Если у других объектов (или у этого же объекта) есть ссылки на поля перемещаемого объекта, то его нельзя вот так взять и передвинуть. Если этот объект лежал себе в каком-нибудь пуле, то его тоже нехорошо оттуда убирать, не сказав об этом пулу.
Дело в том, что и в стандартном векторе при изменении размера итераторы могут стать невалидными. Поэтому если вы получили указатель на элемент через vec[i], то вы сами должны следить за тем, чтобы размер вектора не менялся. А вот если объект отдал указатель на часть себя внутри какой-то функции, то он сам и должен за этим указателем следить. Вот умные указатели это умеют — при копировании объект, содержащийся внутри умного указателя, останется на том же месте.
Да, при изменении размера вектора указатели на его элементы могут стать не валидными. Но умные указатели никак не решают эту проблему.
Разве что вы сделаете конструкцию
Вы не можете написать:
Разве что вы сделаете конструкцию
std::vector<std::unique_ptr<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 может быть битой.
Так и есть. Но если вы сделали
std::unique_ptr<A>& ptr = vector[i];, а потом vector.push_back(...); ptr.reset(new A());, то сами виноваты. Но если у вас был сначала vector<A>, а вы заменили его на vector<unique_ptr<A>>, и вам нужно было именно сохранить указатель на A, то проблему таки обошли. Вот они и предлагают такой способ обходить проблему, собственно.Как-то это костыльно… Имхо, на доступе к объектам через unique_ptr, хранящийся в векторе, можно потерять больше, чем на переаллокациях в этом векторе. То есть гнаться за Relocatable только ради Relocatable — это странно. А судя по фразе «Если вы не сделаете этого, fbvector не скомпилируется с BOOST_STATIC_ASSERT.» Бравым ребятам из фэйсбука без этого никак.
Вообще предельная оптимизация аллокаций/перемещений вектором это выделить ровно столько сколько потребуется. А тащить к себе лишнюю библиотеку только изза того что в ней один коэфициент меньше чем в gcc это както чересчур
выделить ровно столько сколько потребуется
Т.е. каждый новый push_back должен приводить к аллокации нового вектора, на 1 элемент большего, чем предыдущий? Чудовищное решение.
Учесть статистику по итоговым длинам при выборе изначальной емкости?
Нет. Если вы на каждый новый push_back аллоцируете новый вектор, значит Вы таки выделили не столько сколько нужно.
leventov выше один из вариантов написал.
leventov выше один из вариантов написал.
Если сразу точно знать, сколько нужно, то тут и вектор не нужен — достаточно массива.
На самом деле можно математически доказать, что константа 2 — строго худшее из всех возможных значений, потому что оно никогда не позволяет переиспользовать ранее выделенную вектором память.
Мне это фраза напомнила тот анекдот, «и не выиграл, а проиграл».
Во-первых, 2 — это всего лишь минимальное значение с таким свойством, непонятно, чем оно «строго хуже», например, константы 3.
Во-вторых, у этой константы есть и более важные свойства, например, ожидаемый коэффициент memory overuse, см. github.com/OpenHFT/Koloboke/wiki/Magic-Factors#grow-factor
Во-третьих, я вообще не понимаю этот случай. Зачем вообще аллоцировать целиком новый вектор сразу за старым, если в этом случае можно сделать просто реаллок?) А если сразу за вектором или на небольшом расстоянии к моменту расширения уже что-то есть, то мы в любом случае не сможем переиспользовать эту память при последующих увеличениях.
Короче говоря, безотносительно того, что константа 1,5 и правда кажется лучше, чем 2, объяснение под это подбито просто нелепейшее.
По-моему, в этой статье (ее оригинальном варианте) вообще почти все притянуто за уши. Такое ощущение, что автор не понимает, как STL реализована в большинстве дистрибутивов.
Зачем вообще аллоцировать целиком новый вектор сразу за старым, если в этом случае можно сделать просто реаллок?)Там же объясняется, почему нельзя так делать для неперемещаемых объектов. В Си++ не предусмотрена переносимая функция «попробовать расширить кусок памяти в куче, но не трогать его, если не получается». realloc() может взять и переместить данные вектора в другое место, что может печально сказаться на объектах. Разумеется, для всяких интов и структурок из интов так делать можно. Для этого-то у них и добавлен трейт IsRelocatable, который позволяет использовать realloc().
я аналогично выпад на realloc() не понял:
а что если он реально не может расширить тещую область на указанный размер, т.к. за этим блоком уже что-то есть. Почему это неудачный дизайн? И как он должен в этой ситуации поступать, кроме как выделить новый блок и скопировать туда старые данные?
Это результат не слишком удачного дизайна сишной функции realloc(), которая сама решает, переиспользовать ли ей ранее выделенную память, или выделить новую, скопировать туда данные и освободить старую.
а что если он реально не может расширить тещую область на указанный размер, т.к. за этим блоком уже что-то есть. Почему это неудачный дизайн? И как он должен в этой ситуации поступать, кроме как выделить новый блок и скопировать туда старые данные?
Имеется в виду, как раз таки описанное выше «попробовать расширить кусок памяти в куче, но не трогать его, если не получается». Выделить новую память, и скопировать данные, пользователь всегда может и сам, при необходимости. А вот проверить возможность расширяемости текущего куска — нет.
А понял, эдакий try_realloc().
Поправьте меня если я неправ:
Можно ли просто по возвращаемому realloc указателю понять — выделила она в новом месте или просто расширила?
Если указатель изменился, мы вызываем конструкторы перемещения, если нет, то не вызываем.
Можно ли просто по возвращаемому realloc указателю понять — выделила она в новом месте или просто расширила?
Если указатель изменился, мы вызываем конструкторы перемещения, если нет, то не вызываем.
Конечно, можно понять, но откуда и для чего вы будете вызывать конструкторы перемещения? Для перемещения объектов с нового места на то же самое новое место?
Понять по указателю, изменилось ли место расположения данных в памяти, мы можем, а вот сделать что-то с этим уже нет, поскольку старый блок памяти был уже удалён.
А где тесты?
FBVectorTest.cpp (smoke test), StlVectorTest.cpp (соответствие требованиям STL)
Кстати говоря, кто-нибудь, кроме меня, обратил внимание на образцовые коммит-логи в репозитории?
Повторное использование памяти — это хорошо. Но будет ли это реально работать в системе, где в куче выделяется не только память под один вектор, а еще много всего другого, что может запросто заполнить освобожденную вектором память до того, как он решит реаллоцироваться?
Предположение С++ о том, что объекты являются неперемещаемыми вредит всем и делает это лишь ради нескольких спорных моментов архитектуры.Вот когда-нибудь реализуют is_trivially_copyable trait, и стандартный вектор тоже оптимизируют.
Такое впечатление, что почти все улучшения являются таковыми только относительно g++/libstdc++.
любое число, меньшее, чем 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 попадает в этот интервал.
Sign up to leave a comment.
folly::fbvector — улучшенный std::vector от Facebook