Кто-нибудь встречал хорошую реализацию cow массива со страничным хранением данных?
То есть если мы копируем массив в другой массив, то у нас никакого копирования данных не происходит. И начтнается копирование только отдельных страниц, если мы что-то в них поменяли (не всего массива, а именно измененных страниц).
Есть такое? Или свой велосипед городить?
Типа такого
Здравствуйте, Hоmunculus, Вы писали:
H>Есть такое? Или свой велосипед городить?
можно реализовать поверх QSharedData (как минимум detach не надо будет самому писать). Хотя всё равно придётся заморочиться с итераторами, конструкторами и пр.
constexpr int PageSize = 1024;
template<typename T>
struct Page : QSharedData
{
Page() : data(PageSize) {}
QVector<T> data;
};
template<typename T>
struct PagedArray
{
explicit PagedArray(int size = 0)
: m_size(size)
{
const int pageCount = (size + PageSize - 1) / PageSize;
m_pages.resize(pageCount);
for (int i = 0; i < pageCount; ++i)
m_pages[i] = QSharedDataPointer<Page<T>>(new Page<T>());
}
int size() const noexcept { return m_size; }
const T& operator[](int index) const
{
int pageIndex = index / PageSize;
int offset = index % PageSize;
return m_pages[pageIndex]->data[offset];
}
T& operator[](int index)
{
int pageIndex = index / PageSize;
int offset = index % PageSize;
if (m_pages[pageIndex].data()->ref.loadRelaxed() > 1)
m_pages[pageIndex].detach();
return m_pages[pageIndex]->data[offset];
}
void resize(int newSize)
{
const int newPageCount = (newSize + PageSize - 1) / PageSize;
m_pages.resize(newPageCount);
for (int i = 0; i < newPageCount; ++i)
{
if (!m_pages[i])
m_pages[i] = QSharedDataPointer<Page<T>>(new Page<T>());
}
m_size = newSize;
}
private:
int m_size;
QVector<QSharedDataPointer<Page<T>>> m_pages;
};
Здравствуйте, sergii.p, Вы писали:
SP>Здравствуйте, Hоmunculus, Вы писали:
H>>Есть такое? Или свой велосипед городить?
SP>можно реализовать поверх QSharedData (как минимум detach не надо будет самому писать). Хотя всё равно придётся заморочиться с итераторами, конструкторами и пр.
SP>SP>constexpr int PageSize = 1024;
SP>template<typename T>
SP>struct Page : QSharedData
SP>{
SP> Page() : data(PageSize) {}
SP> QVector<T> data;
SP>};
SP>template<typename T>
SP>struct PagedArray
SP>{
SP> explicit PagedArray(int size = 0)
SP> : m_size(size)
SP> {
SP> const int pageCount = (size + PageSize - 1) / PageSize;
SP> m_pages.resize(pageCount);
SP> for (int i = 0; i < pageCount; ++i)
SP> m_pages[i] = QSharedDataPointer<Page<T>>(new Page<T>());
SP> }
SP> int size() const noexcept { return m_size; }
SP> const T& operator[](int index) const
SP> {
SP> int pageIndex = index / PageSize;
SP> int offset = index % PageSize;
SP> return m_pages[pageIndex]->data[offset];
SP> }
SP> T& operator[](int index)
SP> {
SP> int pageIndex = index / PageSize;
SP> int offset = index % PageSize;
SP> if (m_pages[pageIndex].data()->ref.loadRelaxed() > 1)
SP> m_pages[pageIndex].detach();
SP> return m_pages[pageIndex]->data[offset];
SP> }
SP> void resize(int newSize)
SP> {
SP> const int newPageCount = (newSize + PageSize - 1) / PageSize;
SP> m_pages.resize(newPageCount);
SP> for (int i = 0; i < newPageCount; ++i)
SP> {
SP> if (!m_pages[i])
SP> m_pages[i] = QSharedDataPointer<Page<T>>(new Page<T>());
SP> }
SP> m_size = newSize;
SP> }
SP>private:
SP> int m_size;
SP> QVector<QSharedDataPointer<Page<T>>> m_pages;
SP>};
SP>
Вы только забыли про то, что QSharedData изначально спроектирован с прицелом на многопоточность. А в такой примерной реализации нужно будет позаморачиваться.
Здравствуйте, Hоmunculus, Вы писали:
H>Кто-нибудь встречал хорошую реализацию cow массива со страничным хранением данных?
H>То есть если мы копируем массив в другой массив, то у нас никакого копирования данных не происходит. И начтнается копирование только отдельных страниц, если мы что-то в них поменяли (не всего массива, а именно измененных страниц).
H>Есть такое? Или свой велосипед городить?
H>Типа такого
H>Image: fff.png
Я бы использовал std::make_shared + std::shared_ptr (вместо QSharedDataPointer).
Чтобы избежать лишней косвенности на странице, можно использовать boost::container::static_vector или std::inplace_vector (С++26).
Оператор [], по возможности, оставил бы только для чтения. Иначе очень легко вместо чтения вызвать клонирование данных.
Аналогично, отказался бы от неконстантных итераторов, или как минимум сделал бы их доступными только через отдельный .
std::views::join — для итераторов.
Это приводит к тому, что итераторы не хранят в себе умных указателей и нет счетчика живых итераторов.
Поэтому все что можно — ввести правила инвалидки итераторов (при вызове любой функции, потенциально могущей изменить содержимое).
Примерно так:
template<typename SubContainer>
class shared_container
{
public:
shared_container() = default; // : ptr( std::make_shared<SubContainer>()) {}
shared_container(const shared_container&) = default;
shared_container(shared_container&&) = default;
shared_container& operator = (const shared_container&) = default;
shared_container& operator = (shared_container&&) = default;
const SubContainer& const_view() const { return *ptr; }
SubContainer& detach() {
if(ptr.use_count()>1)
ptr = std::make_shared<SubContainer>(*ptr);
return *ptr;
}
auto size () const { return const_view().size(); }
const auto& operator[] (auto i) const { return const_view()[i]; }
const auto& at (auto i) const { return const_view().at(i); }
auto begin () const { return const_view().begin(); }
auto end () const { return const_view().end(); }
auto& operator[] (auto i) { return detach()[i]; }
auto& at (auto i) { return detach().at(i); }
auto begin () { return detach().begin(); }
auto end () { return detach().end(); }
private:
std::shared_ptr< SubContainer > ptr = std::make_shared<SubContainer>();
};
template<typename T,
size_t page_size = std::max( (size_t) (1024*16)/sizeof(T), (size_t) 4) >
class page_vector
{
static_assert(page_size > 1 );
using t_page = shared_container< boost::container::static_vector<T, page_size> >;
std::vector<t_page> data;
using t_r_range = decltype( std::declval< const std::vector<t_page>& >() | std::views::join );
using t_rw_range = decltype( std::declval< std::vector<t_page>& >() | std::views::join );
mutable std::optional< t_r_range > r_range;
mutable std::optional< t_rw_range > rw_range;
public:
page_vector() = default;
page_vector(const page_vector&) = default;
page_vector(page_vector&&) = default;
page_vector& operator = (const page_vector& p) { data = p.data; invalidate_iterators(); return *this; }
page_vector& operator = (page_vector&& p) { data = std::move(p.data); invalidate_iterators(); return *this; }
const T& operator [] (size_t i) const { return data[i/page_size][i%page_size]; }
const T& at (size_t i) const { return data.at(i/page_size).at(i%page_size); }
auto begin() const { return const_range().begin(); }
auto end () const { return const_range().end(); }
void assign(size_t i, T&& v) // invalidate iterators
{
data.at( i/page_size ).detach().at(i%page_size) = std::move(v);
invalidate_iterators();
}
void push_back( auto&& v ) // invalidate iterators
{
if(data.empty() || data.back().size() == page_size )
data.push_back({});
data.back().detach().push_back(std::move(v));
invalidate_iterators();
}
auto& const_range() const
{
if(!r_range)
r_range = data | std::views::join;
return *r_range;
}
auto& writable_range()
{
for(auto& p :data)
p.detach();
invalidate_iterators();
rw_range = data | std::views::join;
return *rw_range;
}
private:
void invalidate_iterators()
{
r_range.reset();
rw_range.reset();
}
};
int main()
{
page_vector<int, 8 > data;
for(int i=100; i<111; ++i)
data.push_back(i);
for(auto i : data)
std::cout<<i<<std::endl;
for(int& j : data.writable_range())
j+=200;
for(auto i : data)
std::cout<<i<<std::endl;
return 0;
}
