быстрый new/delete
От: maks1180  
Дата: 28.11.22 09:36
Оценка:
Есть приложение, создаёт в динамической памяти много маленьких объектов (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

Соотвественно данный класс выделит память, а конструктор/деструктор уже самому нужно будет вызвать.

Может есть готовое решение или что-то лучше ?
===============================================
(реклама, удалена модератором)
Отредактировано 28.11.2022 9:37 maks1180 . Предыдущая версия . Еще …
Отредактировано 28.11.2022 9:36 maks1180 . Предыдущая версия .
Re: быстрый new/delete
От: qaz77  
Дата: 28.11.22 09:46
Оценка: +2
Здравствуйте, maks1180, Вы писали:

M>Может есть готовое решение или что-то лучше ?


Такая штука называется memory pool.
Их есть в ассортименте: memory pool c++
Re: быстрый new/delete
От: sergii.p  
Дата: 28.11.22 10:08
Оценка: :))
Здравствуйте, maks1180, Вы писали:

M>Может есть готовое решение или что-то лучше ?


можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке.
В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.
Re[2]: быстрый new/delete
От: Mr.Delphist  
Дата: 28.11.22 11:04
Оценка:
Здравствуйте, sergii.p, Вы писали:

SP>можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке.


Стек имеет шансы закончиться раньше, чем куча.

SP>В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.


Да, но сложность такого алогритма составит даже не O(N^2), а скорее Premature-O
Re: быстрый new/delete
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 28.11.22 11:16
Оценка:
Здравствуйте, maks1180, Вы писали:

M>// 2. Выделенная память не поменяет адрес (в отличии от std::vector) и не возникнет задержки при увеличении количества элементов (в отличии от std::vector)


Интересно, а как ты себе это представляешь?
Маньяк Робокряк колесит по городу
Re[2]: быстрый new/delete
От: Bill Baklushi СССР  
Дата: 28.11.22 11:43
Оценка:
sergii.p:

SP>можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке.

SP>В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.
Думаешь, содержимое std::string создается в стеке? Тогда у меня для тебя плохие новости...
Re[2]: быстрый new/delete
От: maks1180  
Дата: 28.11.22 16:58
Оценка:
SP>можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке.
SP>В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.

На стеке нельзя, они же долго жить должны.
===============================================
(реклама, удалена модератором)
Re[3]: быстрый new/delete
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 28.11.22 17:02
Оценка: +1
Здравствуйте, Bill Baklushi, Вы писали:

SP>>можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке.

SP>>В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.
BB>Думаешь, содержимое std::string создается в стеке? Тогда у меня для тебя плохие новости...

Зависит от размера содержимого. Я как-то то заменил std::vector на std::string и получил ускорение на порядок. Почитай на досуге про Small String Optimization
Маньяк Робокряк колесит по городу
Re[3]: быстрый new/delete
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 28.11.22 17:03
Оценка:
Здравствуйте, maks1180, Вы писали:

SP>>можно поискать, что за объекты спамят память и поменять их по типу std::string, чтобы они создавались и разрушались на стеке.

SP>>В различные "аллокаторы" не верю. Завтра всё поменяется и новый аллокатор создаст новые проблемы.

M>На стеке нельзя, они же долго жить должны.


Короткие строки хранятся в самом std::string, без аллокации памяти. Где скажешь хранится, там и будет хранится, хоть на стеке, хоть где
Маньяк Робокряк колесит по городу
Re[2]: быстрый new/delete
От: maks1180  
Дата: 28.11.22 17:04
Оценка:
Q>Такая штука называется memory pool.
Q>Их есть в ассортименте: memory pool c++

Спасибо, что-то конкретное можете посоветовать ?
===============================================
(реклама, удалена модератором)
Re[2]: быстрый new/delete
От: maks1180  
Дата: 28.11.22 17:12
Оценка:
Здравствуйте, Marty, Вы писали:

M>Здравствуйте, maks1180, Вы писали:


M>>// 2. Выделенная память не поменяет адрес (в отличии от std::vector) и не возникнет задержки при увеличении количества элементов (в отличии от std::vector)


M>Интересно, а как ты себе это представляешь?


например через chunks, кажется есть что-то похожее в Boost Pool Library
===============================================
(реклама, удалена модератором)
Re[3]: быстрый new/delete
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 28.11.22 17:25
Оценка:
Здравствуйте, maks1180, Вы писали:

M>>>// 2. Выделенная память не поменяет адрес (в отличии от std::vector) и не возникнет задержки при увеличении количества элементов (в отличии от std::vector)


M>>Интересно, а как ты себе это представляешь?


M>например через chunks, кажется есть что-то похожее в Boost Pool Library


Ну, std::vector гарантирует непрерывность своего блока, взамен гарантирует произвольный доступ O(1).

Можешь взять std::list какой-нибудь, но тогда " Выделенная память не поменяет адрес" теряет смысл, и быстрого индексирования не получится.

Вообще, тебе нужен контейнер, а не new/delete, у тебя кони и люди смешались с мухами и котлетами
Маньяк Робокряк колесит по городу
Re: сделал
От: maks1180  
Дата: 29.11.22 04:16
Оценка:
Хух, сделал первую версию за целый день!

Вообщем получился такой результат:

тест №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 оказались не такими уж и медленными как пугали во многих статьях!

Где-бы почитать про алгоритм malloc/free в gcc ?
===============================================
(реклама, удалена модератором)
Отредактировано 29.11.2022 5:15 maks1180 . Предыдущая версия . Еще …
Отредактировано 29.11.2022 4:41 maks1180 . Предыдущая версия .
Отредактировано 29.11.2022 4:24 maks1180 . Предыдущая версия .
Отредактировано 29.11.2022 4:23 maks1180 . Предыдущая версия .
Отредактировано 29.11.2022 4:20 maks1180 . Предыдущая версия .
Отредактировано 29.11.2022 4:19 maks1180 . Предыдущая версия .
Re[2]: сделал
От: Kernan Ниоткуда https://rsdn.ru/forum/flame.politics/
Дата: 29.11.22 05:42
Оценка: +1
Здравствуйте, maks1180, Вы писали:

M>Где-бы почитать про алгоритм malloc/free в gcc ?

В соседнем разделе алгоритмы выделения памяти.
Sic luceat lux!
Re: быстрый new/delete
От: Умака Кумакаки Ниоткуда  
Дата: 29.11.22 22:07
Оценка:
Здравствуйте, maks1180, Вы писали:

M>Может есть готовое решение или что-то лучше ?


зачем все эти извращения? стандартный аллокатор и так работает очень быстро. как альтернативный готовый вариант можно взять tcmalloc

а вообще верхний предел количества аллоцируемых объектов?

например если их максимум 128к одновременно живых и хочется странного, то заводится фиксированный буфер на 128к объектов, и битовая карта, где бит — свободен объект или нет.

аллокация — поиск первого нулевого бита в битовой карте (и устанавливаем его в единицу, ессно) и возврат индекса этого бита, помноженного на размер объекта
деалокация — получаем индекс объекта в буфере (разность указателя на объект и указателя на начало буфера) и устанавливаем бит с этим индексом в 0

128к бит это 16к байт, целиком влезет в кеш L1 и сканироваться (аллоцировать один объект) будет за десяток наносекунд
нормально делай — нормально будет
Отредактировано 29.11.2022 22:14 Умака Кумакаки . Предыдущая версия . Еще …
Отредактировано 29.11.2022 22:13 Умака Кумакаки . Предыдущая версия .
Отредактировано 29.11.2022 22:09 Умака Кумакаки . Предыдущая версия .
Re[2]: быстрый new/delete
От: maks1180  
Дата: 29.11.22 23:55
Оценка:
УК>а вообще верхний предел количества аллоцируемых объектов?
Пока планируется до 1 млн объектов, если комп будет больше тянуть, то нужно будет больше.

УК>например если их максимум 128к одновременно живых и хочется странного, то заводится фиксированный буфер на 128к объектов, и битовая карта, где бит — свободен объект или нет.


УК>аллокация — поиск первого нулевого бита в битовой карте (и устанавливаем его в единицу, ессно) и возврат индекса этого бита, помноженного на размер объекта

УК>деалокация — получаем индекс объекта в буфере (разность указателя на объект и указателя на начало буфера) и устанавливаем бит с этим индексом в 0

УК>128к бит это 16к байт, целиком влезет в кеш L1 и сканироваться (аллоцировать один объект) будет за десяток наносекунд


Я примерно так и сделал только:
— разбил на страницы по 1-64k объектов, и помечал сколько в ней пустот осталось, если 0 то её не сканирую.
— записываю адрес последного free блока в каждой странице, что-бы его отдать первым без сканирования
— сохраняю место последнее найденого блока, что-бы следующее сканирования начинать с этого места

Всё равно результат лучше чем glibc, но не намного.
===============================================
(реклама, удалена модератором)
Отредактировано 29.11.2022 23:56 maks1180 . Предыдущая версия .
Re[3]: быстрый new/delete
От: qaz77  
Дата: 01.12.22 10:30
Оценка:
Здравствуйте, maks1180, Вы писали:

M>Спасибо, что-то конкретное можете посоветовать ?


В свое время я выбрал одну из таких реализаций с постраничной организацией.
И допилил под свои хотелки.

Там, конечно, не по классам было все разведено, а по sizeof.
Все что больше 256 байт выделяется обычным new, а мелочь выделяется в преаллоцированных страницах.
Есть массив 1..255 на хвост списка страниц. Например, страниц с объектами размером 73 байта.
По отрицательному смещению каждого аллоцированного указателя есть служебный блок с указателем на страницу (slot) и на следующий блок (block_hdr*).
Основное ускорение из-за отсутствия межпоточной синхронизации — по условию этот пул только в одном потоке живет.

Код не могу выложить, т.к. это в коммерческом продукте.
Re: быстрый new/delete
От: fk0 Россия https://fk0.name
Дата: 07.12.22 13:03
Оценка:
Здравствуйте, 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-программе это может быть цикл обработки событий. Т.е. если есть дофига временных объектов, то нет их
смысла постоянно деаллоцировать, а всем скопом выкинуть в конце цикла. Обычно для таких объектов специальный аллокатор
со своим специальным пулом делается. Потому, что есть же ещё долгоживущие аллокации, которых так не выкинешь.
Re[2]: быстрый new/delete
От: T4r4sB Россия  
Дата: 07.12.22 13:08
Оценка:
Здравствуйте, Marty, Вы писали:

M>Интересно, а как ты себе это представляешь?


Выделить себе огромный блок адресного пространства, но память выделять лишь по потребности. Работает потому, что адреса на самом деле виртуальные.
Нет такой подлости и мерзости, на которую бы не пошёл gcc ради бессмысленных 5% скорости в никому не нужном синтетическом тесте
Re[3]: быстрый new/delete
От: Marty Пират https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата: 07.12.22 13:28
Оценка:
Здравствуйте, T4r4sB, Вы писали:

M>>Интересно, а как ты себе это представляешь?


TB>Выделить себе огромный блок адресного пространства, но память выделять лишь по потребности. Работает потому, что адреса на самом деле виртуальные.


Это вариант, но на 32ух битах не взлетит
Маньяк Робокряк колесит по городу
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.