Есть приложение, создаёт в динамической памяти много маленьких объектов (20-50 байт) и часто удаляет и новые создаёт.
Так же нужно ещё делать обход всех созданных объектов.
Всего около 4 типов объектов, решил я сделать класс который будет реализовывать malloc+free для каждого типа объекта.
Вот такое ТЗ:
// Данный класс позволяет
// 1. быстро выделять и освобждать память для объекта, за счёт того, что:
// 1.1 память выделяется сразу большим кусом (страницей) на count_in_page=2^N объектов, когда закончится, выделяется новая страница.
// 1.2 при free() память физически не освобождается, а лишь помечается как освобождённая, при следующем alloc он заберёт возможно её (или освобождённую из другой страници)
// 2. Выделенная память не поменяет адрес (в отличии от std::vector) и не возникнет задержки при увеличении количества элементов (в отличии от std::vector)
// 3. Так же есть индекс объекта, он не будет изменён и будет уникальным в экземпляре данного класса. Есть быстрое получение адреса объекта по его индексу
// 4. Есть возможность пройтись по всем содержайщимся объектам, но немного медленнее чем std::vector
Соотвественно данный класс выделит память, а конструктор/деструктор уже самому нужно будет вызвать.
Здравствуйте, maks1180, Вы писали:
M>Может есть готовое решение или что-то лучше ?
можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке.
В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.
Здравствуйте, sergii.p, Вы писали:
SP>можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке.
Стек имеет шансы закончиться раньше, чем куча.
SP>В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.
Да, но сложность такого алогритма составит даже не O(N^2), а скорее Premature-O
Здравствуйте, maks1180, Вы писали:
M>// 2. Выделенная память не поменяет адрес (в отличии от std::vector) и не возникнет задержки при увеличении количества элементов (в отличии от std::vector)
sergii.p:
SP>можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке. SP>В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.
Думаешь, содержимое std::string создается в стеке? Тогда у меня для тебя плохие новости...
SP>можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке. SP>В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.
Здравствуйте, Bill Baklushi, Вы писали:
SP>>можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке. SP>>В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы. BB>Думаешь, содержимое std::string создается в стеке? Тогда у меня для тебя плохие новости...
Зависит от размера содержимого. Я как-то то заменил std::vector на std::string и получил ускорение на порядок. Почитай на досуге про Small String Optimization
Здравствуйте, maks1180, Вы писали:
SP>>можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке. SP>>В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.
M>На стеке нельзя, они же долго жить должны.
Короткие строки хранятся в самом std::string, без аллокации памяти. Где скажешь хранится, там и будет хранится, хоть на стеке, хоть где
Здравствуйте, Marty, Вы писали:
M>Здравствуйте, maks1180, Вы писали:
M>>// 2. Выделенная память не поменяет адрес (в отличии от std::vector) и не возникнет задержки при увеличении количества элементов (в отличии от std::vector)
M>Интересно, а как ты себе это представляешь?
например через chunks, кажется есть что-то похожее в Boost Pool Library
Здравствуйте, maks1180, Вы писали:
M>>>// 2. Выделенная память не поменяет адрес (в отличии от std::vector) и не возникнет задержки при увеличении количества элементов (в отличии от std::vector)
M>>Интересно, а как ты себе это представляешь?
M>например через chunks, кажется есть что-то похожее в Boost Pool Library
Ну, std::vector гарантирует непрерывность своего блока, взамен гарантирует произвольный доступ O(1).
Можешь взять std::list какой-нибудь, но тогда " Выделенная память не поменяет адрес" теряет смысл, и быстрого индексирования не получится.
Вообще, тебе нужен контейнер, а не new/delete, у тебя кони и люди смешались с мухами и котлетами
тест №1
1) делаем malloc 100.000 тыс объектов * 40 байт + free всех обхектов
malloc+free = 40 тактов. Т.е. искать дырки не нужно, поэтому он быстро работает. В 6 раз быстрее чем MinGW+gcc.
тест №2
1) содаём 100.000 тыс объектов * 40 байт
2) случайным выбираем 1% объектов (1000 шт)
3) Делаем 2000 циклов { делаем free выбранных объект в п2 + снова делаем malloc 1000 шт }. Измеряем это время, получилось:
free+malloc = 140/190 тактов на x32/x64. Быстрее всего в 1.1-1.4 раз чем MinGW+gcc. Я сильно удивлён, обогнать существенно НЕ получилось.
Здесь мой алгоритм ищёт до последней дырки, возможно поэтому скорость не намного выше чем у gcc.
Странно, что gcc наоборот быстрее работает когда есть дырки, чем когда нужно новую память запрашивать.
Я удивлён, что malloc+free оказались не такими уж и медленными как пугали во многих статьях!
Здравствуйте, maks1180, Вы писали:
M>Может есть готовое решение или что-то лучше ?
зачем все эти извращения? стандартный аллокатор и так работает очень быстро. как альтернативный готовый вариант можно взять tcmalloc
а вообще верхний предел количества аллоцируемых объектов?
например если их максимум 128к одновременно живых и хочется странного, то заводится фиксированный буфер на 128к объектов, и битовая карта, где бит — свободен объект или нет.
аллокация — поиск первого нулевого бита в битовой карте (и устанавливаем его в единицу, ессно) и возврат индекса этого бита, помноженного на размер объекта
деалокация — получаем индекс объекта в буфере (разность указателя на объект и указателя на начало буфера) и устанавливаем бит с этим индексом в 0
128к бит это 16к байт, целиком влезет в кеш L1 и сканироваться (аллоцировать один объект) будет за десяток наносекунд
УК>а вообще верхний предел количества аллоцируемых объектов?
Пока планируется до 1 млн объектов, если комп будет больше тянуть, то нужно будет больше.
УК>например если их максимум 128к одновременно живых и хочется странного, то заводится фиксированный буфер на 128к объектов, и битовая карта, где бит — свободен объект или нет.
УК>аллокация — поиск первого нулевого бита в битовой карте (и устанавливаем его в единицу, ессно) и возврат индекса этого бита, помноженного на размер объекта УК>деалокация — получаем индекс объекта в буфере (разность указателя на объект и указателя на начало буфера) и устанавливаем бит с этим индексом в 0
УК>128к бит это 16к байт, целиком влезет в кеш L1 и сканироваться (аллоцировать один объект) будет за десяток наносекунд
Я примерно так и сделал только:
— разбил на страницы по 1-64k объектов, и помечал сколько в ней пустот осталось, если 0 то её не сканирую.
— записываю адрес последного free блока в каждой странице, что-бы его отдать первым без сканирования
— сохраняю место последнее найденого блока, что-бы следующее сканирования начинать с этого места
Всё равно результат лучше чем glibc, но не намного.
Здравствуйте, maks1180, Вы писали:
M>Спасибо, что-то конкретное можете посоветовать ?
В свое время я выбрал одну из таких реализаций с постраничной организацией.
И допилил под свои хотелки.
Там, конечно, не по классам было все разведено, а по sizeof.
Все что больше 256 байт выделяется обычным new, а мелочь выделяется в преаллоцированных страницах.
Есть массив 1..255 на хвост списка страниц. Например, страниц с объектами размером 73 байта.
По отрицательному смещению каждого аллоцированного указателя есть служебный блок с указателем на страницу (slot) и на следующий блок (block_hdr*).
Основное ускорение из-за отсутствия межпоточной синхронизации — по условию этот пул только в одном потоке живет.
Код не могу выложить, т.к. это в коммерческом продукте.
Здравствуйте, maks1180, Вы писали:
M>Есть приложение, создаёт в динамической памяти много маленьких объектов (20-50 байт) и часто удаляет и новые создаёт. M>Так же нужно ещё делать обход всех созданных объектов. M>Всего около 4 типов объектов, решил я сделать класс который будет реализовывать malloc+free для каждого типа объекта. M>Вот такое ТЗ: M>// Данный класс позволяет M>// 1. быстро выделять и освобждать память для объекта, за счёт того, что: M>// 1.1 память выделяется сразу большим кусом (страницей) на count_in_page=2^N объектов, когда закончится, выделяется новая страница. M>// 1.2 при free() память физически не освобождается, а лишь помечается как освобождённая, при следующем alloc он заберёт возможно её (или освобождённую из другой страници) M>// 2. Выделенная память не поменяет адрес (в отличии от std::vector) и не возникнет задержки при увеличении количества элементов (в отличии от std::vector)
Вектор тоже не поменяет, если сделать reserve().
M>// 3. Так же есть индекс объекта, он не будет изменён и будет уникальным в экземпляре данного класса. Есть быстрое получение адреса объекта по его индексу M>// 4. Есть возможность пройтись по всем содержайщимся объектам, но немного медленнее чем std::vector
M>Соотвественно данный класс выделит память, а конструктор/деструктор уже самому нужно будет вызвать.
Не понял, какая связь деструктора с аллокатором? Деструктор -- это такая функция. Его аллокатор сам
никогда не вызывает. Когда ты пишешь delete xxx, то компилятор это превращает в xxx->~XXX(), ::operator delete(xxx).
Вот последнее -- вызов деаллокатора. И он может быть любой. Можно для класса переопределить. Можно глобально.
А деструктор всегда привязан к конкретному классу. Можно вызвать xxx->~XXX() и будет вызван только деструктор,
но память освобождена не будет и в неё через new (xxx) XXX() можно посадить новый инстанс класса.
Зачем использовать C-функции malloc и free в явном виде не понятно. В C++ для этого существуют
operator new (size) и operator delete(ptr). В принципе это может быть (а может и не быть) одно и то же.
M>Может есть готовое решение или что-то лучше ?
Аллокатор из библиотеки всё это будет делать скорей не так уж и плохо, а то и лучше, чем самодельное решение.
Может быть имеет смысл заимствовать решение из геймдева: аллоцировать в преаллоцированном стеке (std stack) и не деаллоцировать
до конца какого-либо цикла работы (игрового уровня). Деструкторы, понятно, вызывать придётся. Т.е. разница только в том,
что operator delete указатель стека двигать не будет, т.е. вообще ничего делать не будет. А потом в конце уровня все
объекты должны быть удалены и указатель стека вернётся на вершину. В не игровой программе это может быть какой-то
цикл работы. В GUI-программе это может быть цикл обработки событий. Т.е. если есть дофига временных объектов, то нет их
смысла постоянно деаллоцировать, а всем скопом выкинуть в конце цикла. Обычно для таких объектов специальный аллокатор
со своим специальным пулом делается. Потому, что есть же ещё долгоживущие аллокации, которых так не выкинешь.
Здравствуйте, T4r4sB, Вы писали:
M>>Интересно, а как ты себе это представляешь?
TB>Выделить себе огромный блок адресного пространства, но память выделять лишь по потребности. Работает потому, что адреса на самом деле виртуальные.
