В языке С есть функции malloc, free и realloc. При использовании последней вы можете написать этакий расширяющийся массив из примитивных типов или структур (классов-то нет), который, можно надеяться, не будет копировать все данные при каждом расширении. В С++ есть встроенный класс vector, который представляет из себя расширяющийся массив, но он так не умеет: при каждом расширении вектора выделяется новый участок памяти и все элементы перемещаются на него (по возможности, с использованием move-семантики). Но ведь, если можно каждый раз не копировать все старые элементы на новое место, вектор должен работать быстрее? В этой статье я попробую написать вектор, который умеет расширяться без копирования элементов.
Сначала я покажу, что стандартный вектор не умеет расширяться без копирования/перемещения, потом обсужу придуманное решение, потом собственно приведу реализацию вектора, а в конце сравню производительность со стандартным вектором.
Код приведён здесь.
Как работает стандартный вектор
Сначала давайте убедимся в том, что вектор при каждом расширении копирует (перемещает) все элементы. Для этого напишем класс, который содержит счётчик копирований, перемещений и вызовов конструктора:
class Int
class Int {
private:
int value;
public:
static int moves;
static int copies;
static int constructed;
Int() = delete;
explicit Int(int a): value(a) {
constructed++;
}
~Int() {
constructed--;
}
Int(const Int& other) {
value = other.value;
copies++;
constructed++;
}
Int(Int&& other) noexcept {
value = other.value;
other.value = 0;
moves++;
constructed++;
}
Int& operator = (const Int& other) = delete;
Int& operator = (Int&& other) = delete;
};Далее запустим простой код, чтобы увидеть, сколько копирований/перемещений произойдёт:
простой код
int main() {
vector<Int> vec;
for (int i = 0; i < 16; i++) {
vec.emplace_back(i + 1);
}
cout << "copies " << Int::copies << " moves " << Int::moves << "\n";
return 0;
}Этот код выведет: "copies 0 moves 15" - можно легко прикинуть, что сначала вместимость вектора была 1, потом 2, потом 4 и так далее до 16. В итоге при расширениях произошло 1 + 2 + 4 + 8 = 15 перемещений. Плохо! Если в классе Int удалить move-конструктор, то вместо 15-и перемещений будет 15 копирований.
Идея решения
Сначала убедимся в том, что функцию realloc из С использовать нельзя.
Функция realloc принимает на вход указатель на начало уже выделенного участка памяти и размер в байтах. Она пытается выделить кусок памяти нужного размера сразу вслед за уже выделенным участком памяти и вернуть изначальный указатель - таким образом размер выделенной памяти будет увеличен без копирования. Если же выделить новый участок памяти сразу вслед за данным невозможно, то данная функция выделит новый участок памяти и скопирует туда весь старый участок памяти, после чего освободит его.
Проблема в том, что произвольные С++ объекты нельзя копировать просто так - нужно вызывать конструктор копирования или перемещения, а потом вызывать деструктор старого объекта. Ничего такого, конечно, realloc не делает, поэтому использовать его мы не сможем.
Если бы в стандартной библиотеке С была функция, назовём её try_realloc, которая подобно realloc пытается увеличить данный ей участок памяти, а в случае неудачи ничего не делает, то мы могли бы её и использовать. Но такой, насколько мне известно, нет. Поэтому придётся делать что-то другое.
Одним решением могло бы быть написание собственных функций malloc, free, realloc и try_realloc. Однако, написание эффективной реализации этих функций - вопрос сложный. Поэтому пойдём другим путём.
mmap
В Linux есть системный вызов mmap . Если среди флагов указать MAP_ANONYMOUS, то этот системный вызов занимается по сути тем, что выделяет процессу новую память (возможно, по сути ядро ОС не будет сразу же выделять столько же физической памяти, сколько её попросят, но вот участок виртуальной памяти оно выделит, под который по мере необходимости будет выделять страницы физической памяти). Если же указать ненулевой первый аргумент mmap и указать среди флагов MAP_FIXED_NOREPLACE,то ядро по возможности выделит нам память ровно там, где мы попросили, а если не сможет - вернёт ошибку. А если среди флагов указать просто MAP_FIXED, то мы рискуем выстрелить себе в ногу, поскольку в итоге ядро может удалить какую-то другую память, поэтому так мы делать не будем.
Давайте посмотрим, как это работает. Ниже приведён код, который выделяет одну страницу памяти где получится, потом пытается сразу после неё получить ещё одну страницу, потом - две и так далее.
код
void experiment() {
const int PAGE_SIZE = 4096;
char *addr = (char *) mmap(nullptr, PAGE_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
int total_alloc = 1;
auto next_addr = addr + PAGE_SIZE * total_alloc;
for (int i = 0; i < 15; i++) {
char *new_addr = (char *) mmap(next_addr, PAGE_SIZE * total_alloc, PROT_READ | PROT_WRITE,
MAP_ANONYMOUS | MAP_PRIVATE | MAP_FIXED_NOREPLACE, -1, 0);
if (new_addr == MAP_FAILED) {
cerr << "MAP_FAILED\n" << total_alloc;
return ;
}
next_addr = new_addr + PAGE_SIZE * total_alloc;
total_alloc *= 2;
}
cerr << "returning 0" << endl;
cout << "total_alloc: " << total_alloc << endl;
}вывод:
MAP_FAILED
1
Увы, но этот код выводит на моей машине выделяет всего одну страницу памяти, а при попытке выделить ещё одну сразу же после неё происходит ошибка. В чём проблема? Видимо, память сразу после изначально выделенной страницы уже занята. Нам нужно каким-то образом найти большой незанятый участок виртуальной памяти. В принципе, можно было бы изучить то, что и куда ядро Linux размещает в виртуальной памяти, найти место, где начинается какой-нибудь большой участок и захардкодить его. На моей машине, если в примере выше поставить как первый аргумент mmap адрес 0x7f45c73fd000, то выделяется запрошенное количество памяти. Но такой подход будет зависеть от конкретной реализации. Кроме того, придётся думать, как разным векторам найти разные участки виртуальной памяти. Поэтому можно сделать так: вначале с помощью mmap получаем адрес большого свободного куска, а потом сразу же отдаём его, но в дальнейшем начинаем просить память с того адреса, который получили от первого вызова:
Hidden text
void experiment() {
const int PAGE_SIZE = 4096;
int initial_pages = 32768;
char *start_addr = (char *) mmap(nullptr, PAGE_SIZE * initial_pages, PROT_READ | PROT_WRITE,
MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
if (start_addr == MAP_FAILED) {
cerr << "initial mmap failed\n";
return ;
}
munmap(start_addr, PAGE_SIZE * initial_pages);
char *addr = (char *) mmap(start_addr, PAGE_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
// printf("start_addr: %lx\n", (long )start_addr);
int total_alloc = 1;
auto next_addr = addr + PAGE_SIZE * total_alloc;
for (int i = 0; i < 15; i++) {
char *new_addr = (char *) mmap(next_addr, PAGE_SIZE * total_alloc, PROT_READ | PROT_WRITE,
MAP_ANONYMOUS | MAP_PRIVATE | MAP_FIXED_NOREPLACE, -1, 0);
if (new_addr == MAP_FAILED) {
cerr << "MAP_FAILED\n" << total_alloc;
return ;
}
next_addr = new_addr + PAGE_SIZE * total_alloc;
total_alloc *= 2;
}
cout << "total_alloc: " << total_alloc << endl;
}Теперь перейдём к написанию вектора.
Реализация вектора
Внутри вектора будем хранить указатель на имеющийся у вектора участок памяти, количество элементов в векторе и количество страниц памяти, которое выделено.
template<typename T>
class MyVector {
public:
explicit MyVector(size_t max_capacity = 32768);
~MyVector();
MyVector(const MyVector&) = delete;
MyVector(MyVector&& other) noexcept;
MyVector& operator = (const MyVector&) = delete;
MyVector& operator = (MyVector&& other) noexcept;
T& operator [] (size_t ind);
const T& operator [] (size_t ind) const;
void pop();
void push_back(const T& element);
template<typename ...Args>
void emplace_back(Args ...args);
private:
static const int PROT = PROT_WRITE | PROT_READ;
static int DEFAULT_FLAGS;
static size_t PAGE_SIZE;
void clear();
bool need_increasing();
void increase_capacity();
void fallback_allocate();
char* raw_data;
size_t pages_allocated;
size_t size;
};Методы pop, push_back и операторы[] устроены вполне стандартно. Приведу здесь код конструктора, деструктора и методов, расширяющих вектор.
template<typename T>
MyVector<T>::MyVector(size_t max_capacity, bool huge_pages) {
char* initial_address = (char* ) mmap(nullptr, (max_capacity * sizeof(T) / PAGE_SIZE + 1) * PAGE_SIZE, PROT,
DEFAULT_FLAGS, -1, 0);
if (initial_address == MAP_FAILED) {
throw runtime_error(string("MAP_FAILED1 ") + strerror(errno));
}
munmap(initial_address, (max_capacity * sizeof(T) / PAGE_SIZE + 1) * PAGE_SIZE);
raw_data = (char* ) mmap(initial_address, PAGE_SIZE, PROT, DEFAULT_FLAGS | MAP_FIXED_NOREPLACE, -1, 0);
if (raw_data == MAP_FAILED) {
throw runtime_error(string("MAP_FAILED2 ") + strerror(errno));
}
pages_allocated = 1;
size = 0;
}max_capacity - это совет от пользователя вектора, который будет подсказывать, сколько максимально элементов могут положить в вектор, но вектор будет работать и если элементов будет больше. Итак, вначале конструктор находит большой свободный кусок виртуальной памяти (с помощью mmap и затем munmap), затем выделает одну страницу памяти.
Деструктор вызывает метод clear, который приведём ниже:
template<typename T>
void MyVector<T>::clear() {
T* data = (T*) raw_data;
for (size_t i = 0; i < size; i++) {
data[i].~T();
}
if (raw_data) {
munmap(raw_data, pages_allocated * PAGE_SIZE);
}
pages_allocated = 0;
size = 0;
raw_data = nullptr;
}Вызываем деструкторы и возвращаем память.
template<typename T>
void MyVector<T>::increase_capacity() {
char* new_mem = (char* ) mmap(raw_data + pages_allocated * PAGE_SIZE, pages_allocated * PAGE_SIZE, PROT,
DEFAULT_FLAGS | MAP_FIXED_NOREPLACE, -1, 0);
if (new_mem == MAP_FAILED) {
fallback_allocate();
return;
}
pages_allocated *= 2;
}Пытаемся выделить новый участок памяти сразу вслед за уже выделенным. Если не получилось - вызываем другой метод, который выделит новую память где получится и копирует туда все элементы вектора:
template<typename T>
void MyVector<T>::fallback_allocate() {
//cerr << "fallback_allocate called " << pages_allocated << endl;
T* data = (T*) raw_data;
T* new_memory = (T *) mmap(nullptr, pages_allocated * 2 * PAGE_SIZE, PROT, DEFAULT_FLAGS, -1, 0);
if (new_memory == MAP_FAILED) {
throw runtime_error(string("MAP_FAILED in fallback_allocate ") + strerror(errno));
}
for (size_t i = 0; i < size; i++) {
new (&new_memory[i]) T(std::move(data[i]));
data[i].~T();
}
munmap(raw_data, pages_allocated * PAGE_SIZE);
pages_allocated *= 2;
raw_data = (char *) new_memory;
}Тестируем производительность
Для тестирования будем запускать следующий код, замеряя время и раскомментруя разные строки:
// компилируем так: g++ -O2 main.cpp
// запускаем так: time ./a.out
int main() {
{
int initial_size = 100000000;
// auto my_vec = MyVector<Int>(PAGE_SIZE / sizeof(Int));
auto my_vec = MyVector<Int>(initial_size * 2);
//auto my_vec = vector<Int>();
//my_vec.reserve(PAGE_SIZE / sizeof(Int));
// my_vec.reserve(initial_size);
for (size_t i = 0; i < initial_size; i++) {
my_vec.emplace_back(i);
}
}
printf("copied: %d, moved: %d, left: %d\n", Int::copies, Int::moves, Int::constructed);
return 0;
}В конце код выводит число копирований и перемещений элементов типа Int, а ещё число оставшихся в конце. Последнее число должно быть нулём - если это не так, значит, какие-то деструкторы не вызвались.
Первый запуск - мой вектор, с большим max_capacity в конструкторе:
copied: 0, moved: 0, left: 0
real 0m0,245s
user 0m0,136s
sys 0m0,109s
Всё хорошо - копирований нет, перемещений тоже, все деструкторы отработали.
Второй запуск - используем стандартный вектор, но резервируем место для 4096 / sizeof(Int) элементов - столько мой вектор может хранить до первого расширения.
copied: 0, moved: 134216704, left: 0
real 0m0,732s
user 0m0,472s
sys 0m0,252s
Как и ожидалось, видим, что стандартный вектор неистово перемещает элементы по памяти, работает сильно дольше.
Проверим, сколько времени будет работать стандартный вектор, если ему ничего не придётся перемещать (установим правильный .reserve)
copied: 0, moved: 0, left: 0
real 0m0,411s
user 0m0,307s
sys 0m0,104s
Перемещений нет, но работает всё равно не так быстро, как мой вектор.
Под конец, посмотрим, как будет работать мой вектор, если он не будет заранее знать, сколько элементов мы положим (передадим в конструктор небольшое число).
copied: 0, moved: 134215680, left: 0
real 0m0,634s
user 0m0,389s
sys 0m0,245s
На этот раз ему пришлось перемещать элементы, но работает довольно быстро.
Выводы
Пока что данной реализации надо либо дать какую-то хорошую оценку максимального количества элементов в векторе, чтобы она ничего не перемещала по памяти. Если такая оценка есть, то её можно дать и стандартному вектору в метод reserve, но в случае моей реализации, она не займёт столько памяти сразу же, а только когда (и если) будет действительно столько элементов в векторе. Если такой оценки нет, то можно просто передать большое число - на 64-ёх битных машинах виртуальной памяти очень много, скорее всего участок свободной виртуальной памяти найдётся. При этом в реальности, пока не понадобится, ни физическая, ни виртуальная память израсходована не будет.
Отдельно хочу отметить странность - в моих замерах получилось, что, если стандартному вектору правильно сообщить, сколько элементов будет, он всё равно будет работать медленнее. Почему так - не очень понятно, мне думается, что есть какой-то подвох. Если честно, когда я начинал писать этот код, я вообще не думал, что будет работать быстрее - я предполагал, что из-за большого числа системных вызовов работать будет не очень быстро.
P. S.
На самом деле, стандартные дек, стек и очередь не перемещают свои элементы никуда, но видимо, за счёт более медленного выполнения некоторых операций.
Комментарии (53)
Racheengel
26.11.2022 18:32+1Так в итоге какой прирост по скорости получился?
И это только для интов пример, как я понимаю. Там никакие конструкторы не вызываются. А для вектора объектов как будет работать?
vda19999 Автор
26.11.2022 18:37+1Чтобы качественно оценить производительность, надо было бы провести много разных замеров, с использованием разных типов, методов, параметров и так далее - такого исследования я не делал. На простом тесте - видится ускорение от 0.7с до 0.25с.
Это пример не для интов - я специально написал класс, который имеет конструктор и деструктор, потому что для интов можно было бы и с помощью realloc управлять памятью.
p07a1330
26.11.2022 21:55+3видится ускорение от 0.7с до 0.25с.
Мне кажется, корректнее во первых, бенчмарки считать в %, а во-вторых - вынести их в статью
sergegers
26.11.2022 19:16+10Как я понимаю, неоднократный призёр велогонки Тур де Франс в чатике. У стандартного вектора и всех аллоцирующих контейнеров есть шаблонный параметр Allocator, у которого выделение памяти под объект и создание объекта разнесены. Вообще, написание подобных статей мило, конечно, но как бы неявно подразумевает, что никто, буквально никто из C++ комитета не знает о функции realloc() и не думал об этом сценарии, создавая STL.
vda19999 Автор
26.11.2022 19:28+2Я не предполагаю, что люди из комитета не знают об этой функции. Я думал, почему так не сделали, и причин не нашёл. Был бы вам благодарен, если бы вы пояснили.
zzzzzzerg
26.11.2022 19:38Сделайте переносимое решение (linux + windows, x86+x64 для начала) и наверное идеи какие-то появятся :)
vda19999 Автор
26.11.2022 19:54А почему нельзя на linux по одному, а на windows по-другому? Или это прямо в стандарте написано, что вектор при расширении обязательно всё переносит?
zzzzzzerg
26.11.2022 20:01+6Вы напишите обе реализации, да так чтобы они удовлетворяли стандартному интерфейсу std::vector. Решите все возникающие сопутствующие вопросы и проблемы. Посмотрите на ограничения вашего решения и потом поймете - почему так не делают в стандартном С++, у которого поддерживаемых платформ немного больше, чем четыре.
vda19999 Автор
26.11.2022 20:46Как я понял, аллокатор может только выделять и освобождать память, а запихнуть в него логику реаллокации невозможно, поэтому нельзя написать вектор, который и с аллокаторами работает, и по возможности не перемещает элементы.
tzlom
26.11.2022 23:45+1Ну вообщем то так и есть.
Одна из причин - технически, никто не сказал что аллокатор оперирует на куче. Я уж не упоминаю constexpr. Это нужно, чтобы компилятор имел право оптимизировать аллокацию мелких векторов. Раздутая функциональность аллокатора сделает его оптимизацию значительно труднее, при этом не сильно добавив производительности. Так же есть проблемы организационного характера - нужно будет вводить аналог std::move для resize (если ваш объект должен ощущать изменение памяти за объектом) а это уже как-то слишком.
Предложения по реаллокатору/релокатору были не раз, но в стандарт не прошли.
Ну и не забывайте, что стандартная библиотека она для стандартных операций, а не всех возможных.
sergegers
26.11.2022 20:26Здесь два вопроса. Поленился посмотреть, реализовали ли вы целиком вектор, но даже если и да, то это никак не поможет пользователям контейнеров deque или контейнеров boost . Кроме того, вы написали кода, больше чем следует.
Далее, насколько нужна такая оптимизация? Здесь надо вспомнить теорию. Оказывается, что оптимальная велична увеличения аллоцированной памяти при её нехватке равна золотому сечению (1.618...). При малом количестве количестве элементов, такое умножение, возможно, приведёт к ухудшению производительности. Поэтому умножают на 1.5 (x2 - 1) или на 2. Возможно, реализация Microsoft умножением на 2 делает неэфективным применение аллокатора с использованием realloc.
vda19999 Автор
26.11.2022 20:34+1Контейнеру deque помогать не надо - он и так ничего не копирует и не перемещает.
sergegers
26.11.2022 20:40А почему у него есть аллокатор?
vda19999 Автор
26.11.2022 20:54Ну аллокатор есть, потому что он дек всё равно выделяет память.
Я не уверен точно, но, насколько я знаю, дек внутри устроен как-то так:
Он внутри хранит упорядоченный набор отрезков памяти одинакового размера. Если надо добавить элемент в начало - он пишется в начало первого отрезка памяти. Если в нём места нет - выделяется новый отрезок памяти, который становится первым. Аналогично происходит добавление в конец. Таким образом, перемещать элементы при расширении дека не нужно.
sergegers
26.11.2022 21:08Но он может, по идее, если не хватает памяти, вызвать realloc() и не выделять новый "отрезок".
doo000
27.11.2022 14:44-3Вообще то под капотом у deque обыкновенный linked list, где один элемент держит в себе указатель на следующий (и предыдущий в случае двустороннего списка) элемент. Соответственно при добавлении нового элемента он создается (копируется) где то там (в куче или на стеке, не суть), а уже имеющиеся элементы никуда не перемещаются и им не нужны конструкторы копирования/перемещения. Но в силу этого же для доступа к произвольному элементу придется пройти весь список с начала до этого элемента, тогда как в векторе доступ по индексу константный (begin + index * sizeof(value)).
vda19999 Автор
27.11.2022 14:45+3Боюсь, что вы ошибаетесь.
https://en.cppreference.com/w/cpp/container/deque/operator_at
Произвольный доступ за константное время
flashmozzg
27.11.2022 15:47Там на самом деле хитрее и константа только при определённой формулировке выходит. Но да, там не простой linked list.
VadVergasov
29.11.2022 07:08+1Что-то по ссылке, которая приведена не написаны "условия", когда не константа и даже не сказано, что это амортизировано за константу.
Могу предположить, что это вызвано не правильным пониманием работы данного контейнера. В общих чертах его работу описали чуть выше:
Он внутри хранит упорядоченный набор отрезков памяти одинакового размера. Если надо добавить элемент в начало - он пишется в начало первого отрезка памяти. Если в нём места нет - выделяется новый отрезок памяти, который становится первым. Аналогично происходит добавление в конец. Таким образом, перемещать элементы при расширении дека не нужно.
Плюс структуры deque - произвольных доступ и отсутсвие копирования\перемещения, но при этом можно ухудшить скорость из-за сильного "разбиения" стурктуры в памяти.
flashmozzg
29.11.2022 14:32+1Что-то по ссылке, которая приведена не написаны "условия", когда не константа и даже не сказано, что это амортизировано за константу
Надо смотреть в стандарт. Там сказано
All of the complexity requirements in this Clause are stated solely in terms of the number of operations on the contained objects. [ Example: The copy constructor of type
vector<vector<int>>has linear complexity, even though the complexity of copying each containedvector<int>is itself linear. — end example ]В частности, для деки это означает, что хотя complexity для [] обычно вполне честная константа, но вот для всяких push_front/back она на самом деле ближе к амортизированной величине, как у вектора (т.к. массив указателей на куски так же нужно будет иногда ресайзить, хоть и реже, но тут уже implementation defined), но с точки зрения формулировок стандарта там просто константа.
sourcerer
26.11.2022 20:54+1Да, тоже про этот множитель сразу вспомнилось. На эту тему статья про folly::vector была на хабре: https://habr.com/ru/company/infopulse/blog/238131/
Paskin
26.11.2022 21:48Как минимум - C++/STL не требуют поддержки платформой MMAP (которая отсутствует во многих микроконтроллерах).
shasoftX
26.11.2022 19:32Так это только под Linux будет работать?
Если тормозит перемещение, то тогда наверное лучше взять вместо вектора список одно/двух направленный и в него элементы сохранять.
vda19999 Автор
26.11.2022 19:38+2список требует больше памяти, так как хранит кучу указателей, дёргает выделение памяти для нод очень часто, не поддерживает обращение по произвольному индексу
Kotofay
26.11.2022 22:01+1не поддерживает обращение по произвольному индексу
Поэтому в Qt сделали QList без указателей, на массивах.
И получилось быстро и просто.
thevlad
26.11.2022 20:52+4Я чисто из любви к науки, решил проверить ваше утверждение, что emplace_back для зарезервированного вектора у вас работает быстрее стандартного. Склонировал код с гитхаба и добавил -O2 в CMake.
auto my_vec = MyVector<Int>(initial_size);real 0m0,763s
user 0m0,715s
sys 0m0,048sВторой запуск:
auto my_vec = vector<Int>();my_vec.reserve(initial_size);real 0m0,135s
user 0m0,115s
sys 0m0,020sНа этом желание еще тратить время и копаться в велосипеде исчезло.
vda19999 Автор
26.11.2022 21:08+1Меня самого немало удивило, что у меня стандартный вектор работает медленнее, но так действительно почему-то получается на моём ноутбуке, и я написал, что ожидал другого результата. Из-за вашего комментария запустил виртуалку в облаке и протестировал там - результат получился похожий.
Стандартный вектор вызывает аллокатор для выделения и освобождения участков памяти. Насколько я понимаю, стандартный вектор не будет просить аллокатор увеличить размер текущего участка памяти
thevlad
26.11.2022 21:14+1В принципе идея расширения адресного пространства посредством специфичных сисколов не плохая. Как мне кажется на практике это сталкивается с тем, что для больших векторов можно достаточно точно сделать reserve пусть с некоторым и дополнительным расходом памяти. А для маленьких векторов, сискол это сискол, он проваливается в ядро и не очень понятно какая-там будет задержка.
PS: как мне кажется лучше было бы идти по пути, модификации стандартного вектора и добавления логики realloc к стандартному аллокатору. Но вообще для начала нужна объективная статистика в скольки процентах случаев удается это адресное пространство расширить.
yatanai
27.11.2022 06:38Чудеса работы ноутбуков. Я когда тестировал свои спинлоки на ноутбуке, удивился что мой спинлок медленнее стандартного мьютекса, хотя на основной машине мой показывал в 3 раза большую производительность. 0_0
flashmozzg
27.11.2022 15:51+2Юзерспейсовые спинлоки - почти всегда зло. Нормально работают только в условии что из юзер - единственное серьёзное приложение. Поэтому в бенчмарках хорошо себя показывают, но в реальных условиях, где фоном что-то ещё может быть щапущено могут очень сильно проигрывать системным способам синхронизации.
yatanai
27.11.2022 21:09Это слишком спорная тема, как по мне. Юзерские спинлоки работают конкретно для приложения и могут показывать нормальную производительность. Проблема возникает если у нас, допустим +30 ядер и оказывается что наш спинлок на одну блокировку начинает слать запросов по шине на 2КБ. В этом плане спинлоки от ОС вполне себе панацея, так как хранят внутри себя кучу метрик, по которым они автоматически уходят в мьютекс, что бы не нагружать систему сильно, но весят они не "пару байтиков" а под +500, спокойно.
В моём случае спинлок на ноуте фигово работал, ибо это дохлый атом с 2\4 ядра\потоки, и ожидание в 4 потока было раза в 5 медленнее 3 потоков, догоняя по скорости нативный.flashmozzg
27.11.2022 22:49+1Если твоё приложение не является гарантированно единственным потребителем вычислительных ресурсов (например игрушка для консоли), то обычные мьютексы практически всегда будут быстрее в реальных сценариях использования (но не в бенчах, да, по крайней мере типичных). Не говоря уже о том, что спинлоки будут напрасно жрать цпу, приводя к тротлингу и более быстрому разряду аккумуляторов на ноутах или других портативных устройствах.
Линус относительно недавно на эту тему даже гневал: https://www.realworldtech.com/forum/?threadid=189711&curpostid=189723
skozharinov
26.11.2022 20:55А не проще сразу попросить кусок виртуальной памяти на
max_elements?vda19999 Автор
26.11.2022 21:10на 32-ух битной платформе тогда могла бы не хватить памяти для чего-то другого, я подозреваю
Serge78rus
27.11.2022 15:23+1Если еще на этапе постановки задачи возникают хоть малейшие сомнения в нехватке 32-разрядного адресного пространства — это уже серьезный повод заранее задуматься об использовании 64-разрядной платформы, благо это уже давно не экзотика, а мейнстрим. Гораздо хуже столкнуться с подобными ограничениями на поздних стадиях проекта.
Akon32
26.11.2022 21:10Почему бы не использовать двумерный массив (T**) внутри "vector"? При добавлении элементов будут добавляться целые куски памяти для вложенных масивов T, при необходимости realloc будет только на внешнем массиве указателей T**. Да, доступ несколько медленнее (лишнее разыменование), нет цельного выделенного куска памяти; но зато кроссплатформенность.
thevlad
26.11.2022 21:19+5Поздравляю вы изобрели deque https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl
domix32
27.11.2022 01:17(void *)0x7f45c73fd000
а что это за магия? Это какая-то граница страницы?
Не очень понимаю для чего нужен каст к
char*vda19999 Автор
27.11.2022 07:03-1а это опечатка, уже исправил. там должно быть написано start_addr - начало большого отрезка свободной виртуальной памяти, которое мы получили от mmap.
Да, этот адрес - граница страницы. Я тестировал, что мы можем, в принципе, не получать такой адрес от mmap, а захардкодить, если мы знаем, как устроено виртуальное адресное пространство процесса.
char* используется, потому что к указателю void* нельзя ничего прибавлять.
kibergus
27.11.2022 03:36В linux с дефолтными настройками ядра выделение памяти ленивое (именно поэтому нужен OOM killer). Поэтому вызов vector.reserve должен быть аналогичен приведенному коду. Есть правда тонкости с освобождением памяти.
vda19999 Автор
27.11.2022 07:07Разница, как мне кажется, только в том, что при использовании vector.reserve будет израсходована виртуальная память, даже если она на самом деле не нужна.
То есть, если вам надо очень много небольших векторов, которые хранят немного элементов, а reserve вы для них укажете большой, про запас, то у вас может кончиться виртуальная память.
flashmozzg
27.11.2022 16:45Если нужно много небольших векторов, то тогла лучше уже какой-нибудь smallvector использовать.
screwer
27.11.2022 20:58+2Ничего удивительного. Нет универсального решения, которое будет всегда хорошо, для любой задачи.
Какие-то частные случаи можно сильно оптимизировать, сделав упор на знание нами контекста использованияПочему нам не нравится копирование при реаллокации ? Оно медленное ? Ускорим. Пусть хранимый объект будет смартпоинтером, или даже равпоинтером (а обёртка над вектором разрулит время жизни без затратных атомарных инкрементов). А может быть нам не нужно последовательное размещение в памяти ? Тогда возьмём какой нибудь дек. Если все же нужен вектор, без лишних косвенных адресаций - выделим разумное количество виртуальной памяти (при этом физическая память расходуется очень слабо, только на дескрипторы описателей страниц). А "подкачивать" физику будем сами, или же отдадим на откуп операционной системе.
Если же рассматривать обобщенную реализацию кучи, то там выделение/освобождение сводится к обмену пары указателей, очень-очень редко сваливающемся в slow path и доходящему до сисколлов. Но даже такое можно "объехать" по скорости Например зная, что в ходе парсингп документа новые объекты только создаются, и имеют тривиальные деструкторы - выделить под них собственный блок памяти. Тогда аллокация будет единственным инкрементов. А все освобождение - вселяется к освобождению блока кучи, без выполнения 100500 бесполезной работы
nickolaym
27.11.2022 21:58"Пишем realloc, умеющий расширяться без смены адреса чаще, чем это делает библиотечная функция"
Кажется, что дёргать функции ядра на каждый чих - это расточительно.
Значит, надо писать свою собственную кучу, которая оптимизирована... подо что?
Векторы большего и меньшего размеров, часто/редко меняющиеся, с тривиальными/нетривиальными конструкторами копирования-перемещения.
Так мы придём к тому, что куча должна быть неоднородной.Ну, или пользоваться специализированной кучей для чётко очерченных нужд. Когда std::vector в конкретном месте не удовлетворяет, а reserve() у него почему-то вызывать нельзя.
Почему, кстати?
YungFlaeva
28.11.2022 06:30+1Вот как увидел заголовок, так сразу заинтересовался... Хоть и ожидания, что наверняка будет некий костыль, оправдались, всё равно хочется похвалить автора за старания! Быть может когда-нибудь изобретут идеальный универсальный контейнер, но не сегодня...
avbochagov
29.11.2022 12:10Чего-то не увидел упоминания главной особенности std::vector.
Реализация std::vector гарантирует, что его элементы лежат в непрерывном блоке памяти. Это прописано в стандарте. Отсюда и копирование элементов, если существующего буфера не достаточно для добавления нового элемента.
Если почитать про функцию realloc, то в документации написано: если блок не может быть увеличен, то происходит выделение нового блока и копирование данных в него из старого.
Вектор из С++ все лишь добавляет использования конструктора копирования (ну или перемещения).
cdriper
Малополезная вещь. Хоть какой-то выигрыш будет только если не будет занята область памяти сразу за вектором. При этом если сразу же выделить такой кусок памяти из кучи, эффект будет плюс минус такой же, потому что физические страницы обычно под весь блок сразу не выделяются.
Я когда-то реализовывал схожую идею для Windows, только там толку было сильно больше, т.к. там можно было делать remap физических страниц памяти под новые виртуальные адреса.