Comments 70
Малополезная вещь. Хоть какой-то выигрыш будет только если не будет занята область памяти сразу за вектором. При этом если сразу же выделить такой кусок памяти из кучи, эффект будет плюс минус такой же, потому что физические страницы обычно под весь блок сразу не выделяются.
Я когда-то реализовывал схожую идею для Windows, только там толку было сильно больше, т.к. там можно было делать remap физических страниц памяти под новые виртуальные адреса.
Так в итоге какой прирост по скорости получился?
И это только для интов пример, как я понимаю. Там никакие конструкторы не вызываются. А для вектора объектов как будет работать?
Чтобы качественно оценить производительность, надо было бы провести много разных замеров, с использованием разных типов, методов, параметров и так далее - такого исследования я не делал. На простом тесте - видится ускорение от 0.7с до 0.25с.
Это пример не для интов - я специально написал класс, который имеет конструктор и деструктор, потому что для интов можно было бы и с помощью realloc управлять памятью.
Как я понимаю, неоднократный призёр велогонки Тур де Франс в чатике. У стандартного вектора и всех аллоцирующих контейнеров есть шаблонный параметр Allocator, у которого выделение памяти под объект и создание объекта разнесены. Вообще, написание подобных статей мило, конечно, но как бы неявно подразумевает, что никто, буквально никто из C++ комитета не знает о функции realloc() и не думал об этом сценарии, создавая STL.
Я не предполагаю, что люди из комитета не знают об этой функции. Я думал, почему так не сделали, и причин не нашёл. Был бы вам благодарен, если бы вы пояснили.
Сделайте переносимое решение (linux + windows, x86+x64 для начала) и наверное идеи какие-то появятся :)
А почему нельзя на linux по одному, а на windows по-другому? Или это прямо в стандарте написано, что вектор при расширении обязательно всё переносит?
Вы напишите обе реализации, да так чтобы они удовлетворяли стандартному интерфейсу std::vector. Решите все возникающие сопутствующие вопросы и проблемы. Посмотрите на ограничения вашего решения и потом поймете - почему так не делают в стандартном С++, у которого поддерживаемых платформ немного больше, чем четыре.
Как я понял, аллокатор может только выделять и освобождать память, а запихнуть в него логику реаллокации невозможно, поэтому нельзя написать вектор, который и с аллокаторами работает, и по возможности не перемещает элементы.
Ну вообщем то так и есть.
Одна из причин - технически, никто не сказал что аллокатор оперирует на куче. Я уж не упоминаю constexpr. Это нужно, чтобы компилятор имел право оптимизировать аллокацию мелких векторов. Раздутая функциональность аллокатора сделает его оптимизацию значительно труднее, при этом не сильно добавив производительности. Так же есть проблемы организационного характера - нужно будет вводить аналог std::move для resize (если ваш объект должен ощущать изменение памяти за объектом) а это уже как-то слишком.
Предложения по реаллокатору/релокатору были не раз, но в стандарт не прошли.
Ну и не забывайте, что стандартная библиотека она для стандартных операций, а не всех возможных.
Здесь два вопроса. Поленился посмотреть, реализовали ли вы целиком вектор, но даже если и да, то это никак не поможет пользователям контейнеров deque или контейнеров boost . Кроме того, вы написали кода, больше чем следует.
Далее, насколько нужна такая оптимизация? Здесь надо вспомнить теорию. Оказывается, что оптимальная велична увеличения аллоцированной памяти при её нехватке равна золотому сечению (1.618...). При малом количестве количестве элементов, такое умножение, возможно, приведёт к ухудшению производительности. Поэтому умножают на 1.5 (x2 - 1) или на 2. Возможно, реализация Microsoft умножением на 2 делает неэфективным применение аллокатора с использованием realloc.
Контейнеру deque помогать не надо - он и так ничего не копирует и не перемещает.
А почему у него есть аллокатор?
Ну аллокатор есть, потому что он дек всё равно выделяет память.
Я не уверен точно, но, насколько я знаю, дек внутри устроен как-то так:
Он внутри хранит упорядоченный набор отрезков памяти одинакового размера. Если надо добавить элемент в начало - он пишется в начало первого отрезка памяти. Если в нём места нет - выделяется новый отрезок памяти, который становится первым. Аналогично происходит добавление в конец. Таким образом, перемещать элементы при расширении дека не нужно.
Но он может, по идее, если не хватает памяти, вызвать realloc() и не выделять новый "отрезок".
Вообще то под капотом у deque обыкновенный linked list, где один элемент держит в себе указатель на следующий (и предыдущий в случае двустороннего списка) элемент. Соответственно при добавлении нового элемента он создается (копируется) где то там (в куче или на стеке, не суть), а уже имеющиеся элементы никуда не перемещаются и им не нужны конструкторы копирования/перемещения. Но в силу этого же для доступа к произвольному элементу придется пройти весь список с начала до этого элемента, тогда как в векторе доступ по индексу константный (begin + index * sizeof(value)).
Боюсь, что вы ошибаетесь.
https://en.cppreference.com/w/cpp/container/deque/operator_at
Произвольный доступ за константное время
Там на самом деле хитрее и константа только при определённой формулировке выходит. Но да, там не простой linked list.
Что-то по ссылке, которая приведена не написаны "условия", когда не константа и даже не сказано, что это амортизировано за константу.
Могу предположить, что это вызвано не правильным пониманием работы данного контейнера. В общих чертах его работу описали чуть выше:
Он внутри хранит упорядоченный набор отрезков памяти одинакового размера. Если надо добавить элемент в начало - он пишется в начало первого отрезка памяти. Если в нём места нет - выделяется новый отрезок памяти, который становится первым. Аналогично происходит добавление в конец. Таким образом, перемещать элементы при расширении дека не нужно.
Плюс структуры deque - произвольных доступ и отсутсвие копирования\перемещения, но при этом можно ухудшить скорость из-за сильного "разбиения" стурктуры в памяти.
Что-то по ссылке, которая приведена не написаны "условия", когда не константа и даже не сказано, что это амортизировано за константу
Надо смотреть в стандарт. Там сказано
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), но с точки зрения формулировок стандарта там просто константа.
Да, тоже про этот множитель сразу вспомнилось. На эту тему статья про folly::vector была на хабре: https://habr.com/ru/company/infopulse/blog/238131/
Как минимум - C++/STL не требуют поддержки платформой MMAP (которая отсутствует во многих микроконтроллерах).
Так это только под Linux будет работать?
Если тормозит перемещение, то тогда наверное лучше взять вместо вектора список одно/двух направленный и в него элементы сохранять.
Я чисто из любви к науки, решил проверить ваше утверждение, что 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
На этом желание еще тратить время и копаться в велосипеде исчезло.
Меня самого немало удивило, что у меня стандартный вектор работает медленнее, но так действительно почему-то получается на моём ноутбуке, и я написал, что ожидал другого результата. Из-за вашего комментария запустил виртуалку в облаке и протестировал там - результат получился похожий.
Стандартный вектор вызывает аллокатор для выделения и освобождения участков памяти. Насколько я понимаю, стандартный вектор не будет просить аллокатор увеличить размер текущего участка памяти
В принципе идея расширения адресного пространства посредством специфичных сисколов не плохая. Как мне кажется на практике это сталкивается с тем, что для больших векторов можно достаточно точно сделать reserve пусть с некоторым и дополнительным расходом памяти. А для маленьких векторов, сискол это сискол, он проваливается в ядро и не очень понятно какая-там будет задержка.
PS: как мне кажется лучше было бы идти по пути, модификации стандартного вектора и добавления логики realloc к стандартному аллокатору. Но вообще для начала нужна объективная статистика в скольки процентах случаев удается это адресное пространство расширить.
Чудеса работы ноутбуков. Я когда тестировал свои спинлоки на ноутбуке, удивился что мой спинлок медленнее стандартного мьютекса, хотя на основной машине мой показывал в 3 раза большую производительность. 0_0
Юзерспейсовые спинлоки - почти всегда зло. Нормально работают только в условии что из юзер - единственное серьёзное приложение. Поэтому в бенчмарках хорошо себя показывают, но в реальных условиях, где фоном что-то ещё может быть щапущено могут очень сильно проигрывать системным способам синхронизации.
Это слишком спорная тема, как по мне. Юзерские спинлоки работают конкретно для приложения и могут показывать нормальную производительность. Проблема возникает если у нас, допустим +30 ядер и оказывается что наш спинлок на одну блокировку начинает слать запросов по шине на 2КБ. В этом плане спинлоки от ОС вполне себе панацея, так как хранят внутри себя кучу метрик, по которым они автоматически уходят в мьютекс, что бы не нагружать систему сильно, но весят они не "пару байтиков" а под +500, спокойно.
В моём случае спинлок на ноуте фигово работал, ибо это дохлый атом с 2\4 ядра\потоки, и ожидание в 4 потока было раза в 5 медленнее 3 потоков, догоняя по скорости нативный.
Если твоё приложение не является гарантированно единственным потребителем вычислительных ресурсов (например игрушка для консоли), то обычные мьютексы практически всегда будут быстрее в реальных сценариях использования (но не в бенчах, да, по крайней мере типичных). Не говоря уже о том, что спинлоки будут напрасно жрать цпу, приводя к тротлингу и более быстрому разряду аккумуляторов на ноутах или других портативных устройствах.
Линус относительно недавно на эту тему даже гневал: https://www.realworldtech.com/forum/?threadid=189711&curpostid=189723
Всё же написать "свой быстрый спинлок" вполне реально. Мои цифры показывают что в этом есть смысл, хотя то что я на это убил почти две недели меня не оправдает)
Я знаю какие проблемы есть и почему эти метрики в спинлоках ОС имеют смысл, но можно написать код по другому, переложив часть данных на стек, а не хранить всё всё в спец структуре, как пример. В итоге позволяя себе пихать спинлок в каждую строку в догонку, ибо весит мало.
Единственное на счёт чего я не в курсе, так это за энергопотребление. Остановился на использование интристик pause, который на х86, вроде как, понижает энергопотребление в новых процессорах и упорядочивает запросы в память, но это не точно. (Ждать надо очень много, циклов по 500 на одну проверку)
В любом случае, я сейчас веду тяжёлый пет проект, может через месяц отпишу, как оно в итоге. Вдруг я реально не прав, а использовать структуры по 1КБ это реально мастхев, а писать велосипеды зло?
Мои цифры показывают что в этом есть смысл, хотя то что я на это убил почти две недели меня не оправдает)
Цифр не видел, но вот со спинлоками засада как раз в том, что в бенчмарках они себя часто хорошо показывают в виду специфики бенчмарков, но на реальных ворклоадах работают хуже, чем обычные мьютексы (не говоря уже о более специализированных альтернативах, см. например реализацию в WebKit).
Вдруг я реально не прав, а использовать структуры по 1КБ это реально мастхев, а писать велосипеды зло?
1 КБ это шо такое большое? Стандартный мьютекс - 40 байт. Если взять из какой-нибудь специализированной либы, то ещё меньше (вебкитовский, емнип, в 1 байт умещается).
В 1 байт оно не может уместится чисто технически. Минимальный размер, это размер указателя системы. Скорее всего под капотом бэкенд есть, которые нужные вещи делает. Или там та же спинблокировка, но просто со сменой контекста после неудачи.
А за 1КБ я утрирую. Но даже так 40 байт это дохера как-то.
Минимальный мьютекс — это один бит (занято/свободно). Кем занят, хранить не надо. Поток, который занял, знает об этом и сам поменяет состояние при освобождении.
В железе нет атомарных операций с битами, а минимальный размер, с которым оперирует LOCK CMPXCGH — 1 байт, можно считать, что 1 байт на мьютекс — минимальный объём.
Но, учитывая проблему false sharing, идеальный размер мутекса должен быть не менее длины строки кеша, то есть 64 байта. То есть 40 байт — не дофига, а даже мало.
Тут можно вечно спорить как оно должно работать.
В моём понимании мьютекс это системная хрень. Именно система определяет как именно управляются ресурсы компьютера и как именно оно должно находится в блокировке. От чего минимальный размер, того самого мьютекса, это указатель на некую "системную штуку" которая и управляет нашими потоками.
А спинлок это активная проверка, которую делает сам поток. Тоесть если поток сам решает что ему надо "поменять контекст", то это именно спинлок а не мьютекс.
А 1 байтные "мьютексы" о которых ты говоришь, должны представлять в себе переусложнёный бэкенд, ибо непонятно как именно мы скажем ОС что именно ЭТОТ кусок памяти он должен отслеживать. Ведь может мы хотим взять "мьютекс" не только внутри функции но и образно "подождать события\ввода-вывода".
Потому единственно реально работающая "реализация" 1 байтного "мьютекса", без переусложнения, будет заключатся в том, что мы просим поменять контекст у ОС если спинлок прошёл неудачно. Это нельзя назвать ТРУ мьютексом. (вдруг контекст опять сменится на этот поток, а он всё ещё не разблокирован?)
ЗЫ - Ну блин, 64 байта это прям зашквар. Я тут байтоёбить люблю, у меня от таких цифор голова болит) Хотя сам объекты выравниваю всегда по степени двойки... даа
От чего минимальный размер, того самого мьютекса, это указатель на некую «системную штуку»То есть, это размер хендла. Если предположить, что у нас игрушечная ОС, на которую глобально хватит 256 мутексов, то его хендл опять поместится в 1 байт.
Я же говорю о масштабировании. Сколько нужно памяти (теоретический минимум), чтобы хранить ну скажем миллиард мутексов, если система будет спроектирована под такие условия. Можно саму память под состояние мутекса положить в массив, а его номер (хендл) не обязательно хранить, чтобы он занимал размер указателя. Хендл можно вычислять, если имеем дело с массивом однотипных объектов, номер объекта может коррелировать с номером его мутекса.
64 байта это прям зашквар. Я тут байтоёбить люблю, у меня от таких цифор голова болит)Тут надо понимать, что экономия в 60 байт может вылиться в тормоза на сотни тактов при каждом захвате мутекса.
Думаю эта "игрушечная ОС" только для МК подойдёт)
Ну в итоге, все эти "минимальные размер" перерастают в перетаскивании одеяла. Либо у приложения мало памяти, а ОС нагружена, либо наоборот. Условный "минимум" возможен если у нас свой планировщик поверх чего-то. Тогда все мысли верны, но это переусложненная хрень, хотя в некоторых случаях это хорошо работает***.
Я знаю как работает кэш, даже для спинлока в итоге он начинает таскать по 64 байтика по шинам. То есть, тебе надо выравнивать объекты, что бы они в линии кэша хорошо умещались, иначе быть беде.
Мьютекс вполне может занимать в памяти один байт, а в системе при этом может быть больше 256 мьютексов.
Мьютексу внутри себя минимально надо хранить, занят ли он кем-то. Ядро Linux же в системный вызов futex получает указатель на некоторую память, обычно это указатель на мьютекс, но указатель на себя самого мьютексу хранить ни к чему. И этот указатель будет уже 64-ёх битный, а не 1-о байтный.
При этом, если вам мьютекс будет занимать 1 байт и хранить информацию только о том, занят ли он, он будет неэффективен. Дополнительно надо хранить внутри информацию о том, ждёт ли его кто-то, чтобы знать, делать ли системный вызов при освобождении мьютекса.
Ты хоть понимаешь о чём чём я пишу?
Есть ПРИЛОЖЕНИЕ для приложения мьютекс это системная хрень, хандл который имеет значение в системе. Учитывая как работают многозадачный ОС, обычно это тупо указатель на внутреннюю структуру, тоесть разрядность системы.
И мьютекс не может быть 1байтным для приложения, если мы не пишем под МК, ибо ограничивать "ожидающие штуки" для процесса в 255 единиц, это тупо.
Чел начал затирать что мьютекс может быть 1 байт и вотэтовотвсё. Я ему объяснил, он ответил, вроде всё поняли.
И тут ты такой - "ну вот в ядре же оно там работает вот так". Какой смысл обсуждать как оно там в ядре работает? Бл...
Обратился к линуксоидам в чат с просьбами разобраться как OpenGL/Vulkan запустить, а эти идиоты накидали тонну текста как это в ядре работает. Горит просто. У вас все там такие, я не понимаю?
Вы можете себе представлять мьютекс как указатель, но вам совершенно необязательно хранить этот указатель. Мьютекс может храниться где-то, в глобальной переменной или на стеке, или в структуре и занимать один байт. Вы сможете получить его адрес, чтобы передать в системный вызов.
Я не понял, если честно, куда вы обратились и что такое "у нас", но мне кажется, вам стоит руками написать мьютекс своими руками, и вы поймёте. Это будет строчек 15, много времени не займёт
мьютексу внутри себя совершенно ни к чесу хранить указатель на себя - он может внутри себя хранить один байт или два и при выполнении системного вызова futex или его аналога передавать адрес себя.
max_elements?на 32-ух битной платформе тогда могла бы не хватить памяти для чего-то другого, я подозреваю
Тут какое дело, 64 бита это хорошо, но, например, винда при резервировании виртуального адресного пространства резервирует под него место на диске, чтобы было куда свопнутся. Виртуально резервирует, ничего не пишет конечно, но место там должно быть. Если его там нету - приложение получит отказ на резервирование памяти (ну и может крешнутся, например).
Реально наблюдаемая мной ситуация состояла в том, что приложению, которое хранило реально много данных в стандартных контейнерах Qt, не хватало дисковой памяти. На машинке работало несколько десятков виртуалок в каждой из которой жило по злой проге. И в результате получалась совершенно глупая ситуация, что память на самом деле не нужна (она убегала на 'запас', который резервировали контейнеры на возможное расширение), но при этом её не хватает, и не хватает именно дисков.
Админы ругались что нужно ставить дисков на порядок больше, чем реально используется и будет когда либо использовано, и просили это победить.
Так что 64 бита адресного пространства это хорошо, но есть ли у вас под него достаточно дисковой памяти? Даже резервирование на самом деле не бесплатно. Под него должно быть место, даже если его никто никогда не будет использовать.
Звучит как история про то, почему нельзя использовать Windows)
Согласен, ерунду вчера написал на ночи глядя. Стандартные контейнеры не умеют только резервировать. Они выделяют память, но если её не используют то физическая память не выделяется. А вот место в свопе - да. Поэтому получалось, что свой кончается а физической памяти вагон. Тоже интересно, но не в тему.
Почему бы не использовать двумерный массив (T**) внутри "vector"? При добавлении элементов будут добавляться целые куски памяти для вложенных масивов T, при необходимости realloc будет только на внешнем массиве указателей T**. Да, доступ несколько медленнее (лишнее разыменование), нет цельного выделенного куска памяти; но зато кроссплатформенность.
Поздравляю вы изобрели deque https://stackoverflow.com/questions/6292332/what-really-is-a-deque-in-stl
std::vector должен предоставлять неразрывный кусок памяти
(void *)0x7f45c73fd000
а что это за магия? Это какая-то граница страницы?
Не очень понимаю для чего нужен каст к char*
а это опечатка, уже исправил. там должно быть написано start_addr - начало большого отрезка свободной виртуальной памяти, которое мы получили от mmap.
Да, этот адрес - граница страницы. Я тестировал, что мы можем, в принципе, не получать такой адрес от mmap, а захардкодить, если мы знаем, как устроено виртуальное адресное пространство процесса.
char* используется, потому что к указателю void* нельзя ничего прибавлять.
В linux с дефолтными настройками ядра выделение памяти ленивое (именно поэтому нужен OOM killer). Поэтому вызов vector.reserve должен быть аналогичен приведенному коду. Есть правда тонкости с освобождением памяти.
Разница, как мне кажется, только в том, что при использовании vector.reserve будет израсходована виртуальная память, даже если она на самом деле не нужна.
То есть, если вам надо очень много небольших векторов, которые хранят немного элементов, а reserve вы для них укажете большой, про запас, то у вас может кончиться виртуальная память.
Что только не сделают, чтобы initial size не задавать
Ничего удивительного. Нет универсального решения, которое будет всегда хорошо, для любой задачи.
Какие-то частные случаи можно сильно оптимизировать, сделав упор на знание нами контекста использования
Почему нам не нравится копирование при реаллокации ? Оно медленное ? Ускорим. Пусть хранимый объект будет смартпоинтером, или даже равпоинтером (а обёртка над вектором разрулит время жизни без затратных атомарных инкрементов). А может быть нам не нужно последовательное размещение в памяти ? Тогда возьмём какой нибудь дек. Если все же нужен вектор, без лишних косвенных адресаций - выделим разумное количество виртуальной памяти (при этом физическая память расходуется очень слабо, только на дескрипторы описателей страниц). А "подкачивать" физику будем сами, или же отдадим на откуп операционной системе.
Если же рассматривать обобщенную реализацию кучи, то там выделение/освобождение сводится к обмену пары указателей, очень-очень редко сваливающемся в slow path и доходящему до сисколлов. Но даже такое можно "объехать" по скорости Например зная, что в ходе парсингп документа новые объекты только создаются, и имеют тривиальные деструкторы - выделить под них собственный блок памяти. Тогда аллокация будет единственным инкрементов. А все освобождение - вселяется к освобождению блока кучи, без выполнения 100500 бесполезной работы
"Пишем realloc, умеющий расширяться без смены адреса чаще, чем это делает библиотечная функция"
Кажется, что дёргать функции ядра на каждый чих - это расточительно.
Значит, надо писать свою собственную кучу, которая оптимизирована... подо что?
Векторы большего и меньшего размеров, часто/редко меняющиеся, с тривиальными/нетривиальными конструкторами копирования-перемещения.
Так мы придём к тому, что куча должна быть неоднородной.
Ну, или пользоваться специализированной кучей для чётко очерченных нужд. Когда std::vector в конкретном месте не удовлетворяет, а reserve() у него почему-то вызывать нельзя.
Почему, кстати?
Вот как увидел заголовок, так сразу заинтересовался... Хоть и ожидания, что наверняка будет некий костыль, оправдались, всё равно хочется похвалить автора за старания! Быть может когда-нибудь изобретут идеальный универсальный контейнер, но не сегодня...
Чего-то не увидел упоминания главной особенности std::vector.
Реализация std::vector гарантирует, что его элементы лежат в непрерывном блоке памяти. Это прописано в стандарте. Отсюда и копирование элементов, если существующего буфера не достаточно для добавления нового элемента.
Если почитать про функцию realloc, то в документации написано: если блок не может быть увеличен, то происходит выделение нового блока и копирование данных в него из старого.
Вектор из С++ все лишь добавляет использования конструктора копирования (ну или перемещения).
готовая имплементация этой идеи уже есть и была презентована на Meeting C++ 2018 talk "pinned_vector" by Jakob Schweißhelm and Miro Knejp. Ссылка на гитхаб https://github.com/mknejp/vmcontainer
Пишем на С++ вектор, умеющий расширяться без копирования элементов