Пользовательские распределители как альтернатива вектору интеллектуальных указателей?
Этот вопрос касается владения указателями, использования указателей, интеллектуальных указателей, векторов и распределителей.
Я немного потерялся в своих мыслях об архитектуре кода. Кроме того, если на этот вопрос где-то уже есть ответ, 1. извините, но я пока не нашел удовлетворительного ответа и 2. пожалуйста, укажите мне на него.
Моя проблема заключается в следующем:
У меня есть несколько «вещей», хранящихся в векторе, и несколько «потребителей» этих «вещей». Итак, моя первая попытка была такой:
std::vector<thing> i_am_the_owner_of_things;
thing* get_thing_for_consumer() {
// some thing-selection logic
return &i_am_the_owner_of_things[5]; // 5 is just an example
}
...
// somewhere else in the code:
class consumer {
consumer() {
m_thing = get_thing_for_consumer();
}
thing* m_thing;
};
В моем приложении это было бы безопасно, потому что «вещи» в любом случае переживут «потребителей». Однако во время выполнения можно добавить больше «вещей», и это может стать проблемой, потому что, если std::vector<thing> i_am_the_owner_of_things; перераспределяется, все указатели thing* m_thing становятся недействительными.
Исправлением этого сценария было бы хранение уникальных указателей на «вещи» вместо «вещей» напрямую, т.е. следующим образом:
std::vector<std::unique_ptr<thing>> i_am_the_owner_of_things;
thing* get_thing_for_consumer() {
// some thing-selection logic
return i_am_the_owner_of_things[5].get(); // 5 is just an example
}
...
// somewhere else in the code:
class consumer {
consumer() {
m_thing = get_thing_for_consumer();
}
thing* m_thing;
};
Недостатком здесь является то, что связь памяти между «вещами» теряется. Можно ли как-то восстановить эту когерентность памяти с помощью пользовательских распределителей? Я думаю о чем-то вроде распределителя, который всегда будет выделять память, например, для 10 элементов за раз, и при необходимости добавляет больше фрагментов памяти размером с 10 элементов.
Пример:
изначально:
v = ☐☐☐☐☐☐☐☐☐☐
больше элементов:
v = ☐☐☐☐☐☐☐☐☐☐ ? ☐☐☐☐☐☐☐☐☐☐
и еще раз:
v = ☐☐☐☐☐☐☐☐☐☐ ? ☐☐☐☐☐☐☐☐☐☐ ? ☐☐☐☐☐☐☐☐☐☐
Используя такой распределитель, мне даже не пришлось бы использовать std::unique_ptrs «вещей», потому что во время перераспределения std::vector адреса памяти уже существующих элементов не изменились бы.
В качестве альтернативы я могу думать только о ссылке на «вещь» в «потребителе» через std::shared_ptr<thing> m_thing, в отличие от текущего thing* m_thing, но это кажется мне худшим подходом, потому что «вещь» не должна владеть «потребителем» и с общими указателями я бы создал совместное владение.
Итак, хорош ли подход с аллокатором? И если да, то как это можно сделать? Должен ли я реализовать распределитель самостоятельно или он уже существует?
Вы знаете максимальное количество things впереди? Если да, то вызов reserve по вектору и перераспределения элементов не будет.
Да, несколько потребителей могут использовать одну и ту же вещь. В том-то и дело, что право собственности не должно переходить к потребителю.
Я сомневаюсь, что можно дать вам достойный отзыв, не имея понятия, что такое thing и как он себя ведет.
@MarekR Да, возможно, это вариант. Но это никогда не может быть чистым решением, потому что, с одной стороны, вы хотите, чтобы эта верхняя граница была как можно более жесткой. А что, если вам в какой-то редкой ситуации понадобится больше?
@MarekR «Вещь» живет дольше, чем «потребитель», и «вещей» может быть произвольное количество. И независимо от того, как часто перераспределяется вектор-владелец, указатели m_thing должны оставаться действительными.
Насколько большой thing? Принимает ли он обратные вызовы? Или это ведет себя как структурный тип? Общаются ли несколько потребителей с помощью thing (изменяют ли потребители thing)? Содержит ли он другие указатели?
@MarekR Вы можете предположить худшее для thing: несколько потребителей могут изменить его, и он может даже содержать другие указатели.
Можете ли вы пойти на другой подход, например: do_something_on_thing(functor, consumer)? Это вызвало бы функцию потребителя непосредственно для вещи в векторе вместо того, чтобы назначать вещь потребителю.
Если нескольким потребителям необходимо получить доступ к одному и тому же thing, разумным подходом будет использование вектора каких-либо указателей. Выделите каждый thing отдельно и передайте указатель потребителям. Указатели могут быть простыми указателями или, лучше, std::shared_ptr<>, потому что вы фактически разделяете владение имеют: вы не должны удалять thing, пока жив один из его потребителей.
@MikevanDyke Это интересный момент, но consumer нужно сохранить указатель на thing, чтобы позже проверить, нужно ли ему обновлять себя на основе изменений, которые произошли с thing. (Я хотел опустить эту информацию, потому что вопрос должен быть по существу и не перегружен лишними подробностями.)
Добавляются или удаляются ли вещи только на концах владельца и никогда не добавляются и не удаляются из середины? Если это так, вы можете использовать std::deque.
@ j00hi, можно ли сказать, что ваша цель похожа на шаблон локатора сервисов?
@IgorG Когерентность памяти важна (или может быть) важна, когда есть сотни вещей, и обновление должно выполняться для всех этих сотен вещей. Их размещение в одной строке (строках) кэша может значительно повысить производительность.
Ответы 4
Если вы можете рассматривать thing как тип значения, сделайте это. Это упрощает работу, вам не нужен интеллектуальный указатель, чтобы обойти проблему недействительности указателя/ссылки. Последнее можно решить по-разному:
- Если новые экземпляры
thingвставляются черезpush_frontиpush_backво время работы программы, используйтеstd::dequeвместоstd::vector. Затем никакие указатели или ссылки на элементы в этом контейнере не становятся недействительными (хотя итераторы недействительны — спасибо @odyss-jii за указание на это). Если вы опасаетесь, что сильно полагаетесь на преимущество в производительности от полностью непрерывного расположения памятиstd::vector: создайте тест и профиль. - Если новые экземпляры
thingвставляются в середину контейнера во время программы, рассмотрите возможность использованияstd::list. Никакие указатели/итераторы/ссылки не становятся недействительными при вставке или удалении элементов контейнера. Итерация поstd::listнамного медленнее, чем поstd::vector, но убедитесь, что это реальная проблема в вашем сценарии, прежде чем слишком беспокоиться об этом.
Это несколько хороших моментов для рассмотрения, спасибо! Как память управляется в std::deque? Разве это не какой-то связанный список или он хранит память непрерывно?
Он хранит память в непрерывных кусках. Это делает его своего рода гибридом между std::list и std::vector. Посмотрите эта тема для получения дополнительной информации о std::deque.
@ j00hi Это и то, и другое, он использует своего рода связанные списки блоков типа макета. Недостатком является то, что в большинстве реализаций размер блока действительно мал и не растет — небольшой размер обычно можно в некоторой степени уменьшить с помощью определения макроса — но опять же это должно быть результатом профилирования, а не спекуляции.
Такое поведение std::deque на самом деле именно то, что я искал, когда спрашивал о пользовательских распределителях в своем вопросе. Я оставлю вопрос открытым еще немного, надеясь, что кто-нибудь может указать мне дополнительную информацию о пользовательских распределителях для этого случая, потому что я просил об этом в заголовке моего вопроса. В противном случае большое спасибо. Информация в этом ответе и его комментариях очень краткая и полезная.
@ j00hi вы также можете проверить «круговой буфер» (не в стандартном формате) - в зависимости от потребностей.
Придирка, но разве не так, что итераторы на самом деле недействительны для std::deque::push_back и std::deque::push_front, но не ссылки на фактические элементы? Стоит упомянуть, чтобы кто-то не хранил итератор, ожидая, что он останется действительным после вставки сзади.
@odyss-jii Вы правы, спасибо за отличный совет. Я поправлю ответ.
На этот вопрос нет единственно правильного ответа, так как он во многом зависит от точных шаблонов доступа и желаемых характеристик производительности.
Сказав это, вот моя рекомендация:
Продолжайте хранить данные непрерывно, как и раньше, но не сохраняйте указатели псевдонимов на эти данные. Вместо этого рассмотрите более безопасную альтернативу (это проверенный метод), когда вы извлекаете указатель на основе идентификатора непосредственно перед его использованием — в качестве побочного примечания, в многопоточном приложении вы можете блокировать попытки такая слабая ссылка живет.
Таким образом, ваш потребитель будет хранить идентификатор и получать указатель на данные из «магазина» по запросу. Это также дает вам контроль над всеми «извлечениями», чтобы вы могли отслеживать их, применять меры безопасности и т. д.
void consumer::foo() {
thing *t = m_thing_store.get(m_thing_id);
if (t) {
// do something with t
}
}
Или более продвинутая альтернатива для синхронизации в многопоточном сценарии:
void consumer::foo() {
reference<thing> t = m_thing_store.get(m_thing_id);
if (!t.empty()) {
// do something with t
}
}
Где reference будет неким потокобезопасным «слабым указателем» RAII.
Есть несколько способов реализовать это. Вы можете использовать хеш-таблицу с открытой адресацией и использовать идентификатор в качестве ключа; это даст вам время доступа примерно O (1), если вы правильно его сбалансируете.
Другой альтернативой (в лучшем случае O (1), в худшем случае O (N)) является использование «ссылочной» структуры с 32-битным идентификатором и 32-битным индексом (такой же размер, как 64-битный указатель) -- индекс служит своего рода кешем. Когда вы выбираете, вы сначала пробуете индекс, если элемент в индексе имеет ожидаемый идентификатор, вы сделали. В противном случае вы получаете «промах кеша» и выполняете линейное сканирование хранилища, чтобы найти элемент на основе идентификатора, а затем сохраняете последнее известное значение индекса в своей ссылке.
Доступ к «вещи» по идентификатору приносит некоторые новые проблемы: что, если данный идентификатор повторно используется другой вещью (как в проблеме ABA), что, если потребителю нужен RAII, но «вещь» не наступает время уничтожения, производительность этого метода выборки по идентификатору важна?
@IgorG правда, но для них есть достойные проверенные в боях значения по умолчанию. Для идентификатора используйте постоянно возрастающую последовательность + заблокированный приращение (lock xadd) через std::atomic. Что касается владения thing: с этим решением потребитель может никогда не владеть thing, им владеет магазин. Таким образом, ни один потребитель не может предполагать, что thing будет существовать в любое время, его всегда нужно проверять. Это также то, что гарантирует безопасность памяти, но вы должны проектировать на основе этого принципа. Производительность выборки по идентификатору, вероятно, будет важна. Если все сделано правильно, напр. хэш-таблица с открытой адресацией, это будет очень быстро.
Мне нравится этот ответ (и я не понимаю, почему за него проголосовали), потому что он предлагает другой, но жизнеспособный подход к проблеме. Разве это не именно тот подход, который делают API, такие как OpenGL или Vulkan, при обращении к ресурсам? Я имею в виду, что я не знаю, как они справляются с этим внутри, но я могу представить, как они справятся с этим, как предложено в этом ответе, поскольку они всегда возвращают последовательные числа для дескрипторов, которые указывают на такие ресурсы, как текстуры или буферы графического процессора. Эти номера также называются «именами» ресурса.
Лучшим подходом IMO было бы создание нового контейнера, который будет вести себя безопасно.
Плюсы:
- изменение будет сделано на отдельном уровне абстракции
- изменения в старом коде будут минимальными (просто замените
std::vectorновым контейнером). - это будет "чистый код" способ сделать это
Минусы:
- может показаться, что есть еще немного работы
В другом ответе предлагается использовать std::list, который выполнит эту работу, но с большим количеством выделений и более медленным произвольным доступом. Так что IMO лучше составить собственный контейнер из пары std::vectors.
Таким образом, это может начать выглядеть примерно так (минимальный пример):
template<typename T>
class cluster_vector
{
public:
static const constexpr cluster_size = 16;
cluster_vector() {
clusters.reserve(1024);
add_cluster();
}
...
size_t size() const {
if (clusters.empty()) return 0;
return (clusters.size() - 1) * cluster_size + clusters.back().size();
}
T& operator[](size_t index) {
thowIfIndexToBig(index);
return clusters[index / cluster_size][index % cluster_size];
}
void push_back(T&& x) {
if_last_is_full_add_cluster();
clusters.back().push_back(std::forward<T>(x));
}
private:
void thowIfIndexToBig(size_t index) const {
if (index >= size()) {
throw std::out_of_range("cluster_vector out of range");
}
}
void add_cluster() {
clusters.push_back({});
clusters.back().reserve(cluster_size);
}
void if_last_is_full_add_cluster() {
if (clusters.back().size() == cluster_size) {
add_cluster();
}
}
private:
std::vector<std::vector<T>> clusters;
}
Таким образом, вы предоставите контейнер, который не будет перераспределять элементы. Он не измеряет то, что делает Т.
Downvote: предложение «свернуть самостоятельно» (когда существуют стандартные решения)
ты имеешь в виду std::list? Это не так std::list.
[A shared pointer] seems like the worst approach to me, because a "thing" shall not own a "consumer" and with shared pointers I would create shared ownership.
И что? Может быть, код немного менее самодокументирован, но он решит все ваши проблемы. (Кстати, вы путаете вещи, используя слово «потребитель», которое в традиционной парадигме производителя/потребителя было бы берет на себя ответственность.)
Кроме того, возврат необработанного указателя в вашем текущем коде уже полностью неоднозначен в отношении владения. В общем, я бы сказал, что хорошей практикой является по возможности избегать необработанных указателей (например, вам не нужно вызывать delete). Я бы вернул ссылку, если вы пойдете с unique_ptr
std::vector<std::unique_ptr<thing>> i_am_the_owner_of_things;
thing& get_thing_for_consumer() {
// some thing-selection logic
return *i_am_the_owner_of_things[5]; // 5 is just an example
}
Нет, общие указатели предназначены для выражения права собственности. И «потребитель» в моем примере НЕ должен получать право собственности на «вещь», как я ясно заявил. Цитируя Херба Саттера в его замечательном выступлении Вернуться к истокам! Основы современного стиля C++: Необработанные указатели, не являющиеся владельцами, по-прежнему хороши.
«избегайте необработанных указателей» - это миф. Следует избегать необработанных указателей владения. Тогда также нет двусмысленности, необработанные указатели не владеют вещами.
Используют ли несколько потребителей одно и то же? Потому что если нет, то не было бы более уместно передать право собственности от вектора к потребителю?