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