Есть некоторое количество типов (думаю, пара сотен), объекты которых (от десятков до тысяч) будут храниться в списках. Хочется это дело сделать грамотно на аллокаторах, а не просто выделять в куче память для каждого объекта.
В MFC CList<> есть такая штука, которая выделяет память блоками (по умолчанию по 10 штук) и новые элементы списка размещает в ней, т.е. выделение памяти происходит в 10 раз реже; все свободные блоки связываются в односвязный список-"стек", так что при удалении блока из основного списка он просто скидывается в конец односвязного списка свободных блоков, а при последующем добавлении берется оттуда. Все достаточно быстро, по идее сложность константная.
Хочу сделать похожий алгоритм для себя (без MFC).
Первый вопрос — есть ли готовые реализации?
Второй вопрос — а как принято их передавать? Просто передается тип аллокатора шаблонным параметром?
On 03.04.2014 18:13, Άнoним wrote:
> Есть некоторое количество типов (думаю, пара сотен), объекты которых (от > десятков до тысяч) будут храниться в списках. Хочется это дело сделать > грамотно на аллокаторах, а не просто выделять в куче память для каждого > объекта.
Аллокаторы не нужны. Тебе в данном случае тем более.
Здравствуйте, Άнoним, Вы писали:
Ά>Первый вопрос — есть ли готовые реализации? Ά>Второй вопрос — а как принято их передавать? Просто передается тип аллокатора шаблонным параметром?
Здравствуйте, Άнoним, Вы писали:
Ά>Есть некоторое количество типов (думаю, пара сотен), объекты которых (от десятков до тысяч) будут храниться в списках. Хочется это дело сделать грамотно на аллокаторах, а не просто выделять в куче память для каждого объекта. Ά>В MFC CList<> есть такая штука, которая выделяет память блоками (по умолчанию по 10 штук) и новые элементы списка размещает в ней, т.е. выделение памяти происходит в 10 раз реже; все свободные блоки связываются в односвязный список-"стек", так что при удалении блока из основного списка он просто скидывается в конец односвязного списка свободных блоков, а при последующем добавлении берется оттуда. Все достаточно быстро, по идее сложность константная. Ά>Хочу сделать похожий алгоритм для себя (без MFC). Ά>Первый вопрос — есть ли готовые реализации? Ά>Второй вопрос — а как принято их передавать? Просто передается тип аллокатора шаблонным параметром?
Не нужно писать аллокаторы никогда. По крайней мере до тех пор, пока профилирование не показало, что проблема в выделении/освобождении памяти. Современные аллокаторы, вроде tmalloc отлично справляются с "тяжелыми" режимами работы, вроде создания множества мелких объектов на куче. Если дейстительно тормозит выделение/освобождение памяти, либо память сильно фрагментирована, то можно сначала попытаться помочь аллокатору, выделяя память кусками фикс. размера, либо размера пропорционального степеням двойки, например.
Здравствуйте, Άнoним, Вы писали:
Ά>Есть некоторое количество типов (думаю, пара сотен), объекты которых (от десятков до тысяч) будут храниться в списках. Хочется это дело сделать грамотно на аллокаторах, а не просто выделять в куче память для каждого объекта. Ά>В MFC CList<> есть такая штука, которая выделяет память блоками (по умолчанию по 10 штук) и новые элементы списка размещает в ней, т.е. выделение памяти происходит в 10 раз реже; все свободные блоки связываются в односвязный список-"стек", так что при удалении блока из основного списка он просто скидывается в конец односвязного списка свободных блоков, а при последующем добавлении берется оттуда. Все достаточно быстро, по идее сложность константная. Ά>Хочу сделать похожий алгоритм для себя (без MFC). Ά>Первый вопрос — есть ли готовые реализации? Ά>Второй вопрос — а как принято их передавать? Просто передается тип аллокатора шаблонным параметром?
Здравствуйте, Lazin, Вы писали:
L>Не нужно писать аллокаторы никогда. Аллокаторы, вроде tmalloc отлично справляются с "тяжелыми" режимами работы, вроде создания множества мелких объектов на куче. Если дейстительно тормозит выделение/освобождение памяти, либо память сильно фрагментирована, то можно сначала попытаться помочь аллокатору, выделяя память кусками фикс. размера, либо размера пропорционального степеням двойки, например.
Для контейнеров в котором предпологается сохранять
объекты фиксированого размера с постоянным
интенсивным их внесением/удалением, и количество
которых в контейнере может сильно варьироваться от 0
и до "очень много" (cетевой сервис), необходимость в своём пул аллокаторе
очевидна.
Здравствуйте, smeeld, Вы писали:
S>Для контейнеров в котором предпологается сохранять S>объекты фиксированого размера с постоянным S>интенсивным их внесением/удалением, и количество S>которых в контейнере может сильно варьироваться от 0 S>и до "очень много" (cетевой сервис), необходимость в своём пул аллокаторе S>очевидна.
вовсе не очевидна
для начала нужно изучить как работают современные алокаторы, вроде tcmalloc, понять что там внутри уже реализован "пул алокатор", к тому же параллельный, который будет работать намного быстрее вашего наколенного "пул алокатора" (речь же о сетевом сервисе, а значит пул алокатор должен быть параллельным, что очень не тривиально, ну либо просто потоко-беопасным, а значит — медленным)
Здравствуйте, Lazin, Вы писали:
L>вовсе не очевидна L>для начала нужно изучить как работают современные алокаторы, вроде tcmalloc, понять что там внутри уже реализован "пул алокатор", к тому же параллельный, который будет работать намного быстрее вашего наколенного "пул алокатора" (речь же о сетевом сервисе, а значит пул алокатор должен быть параллельным, что очень не тривиально, ну либо просто потоко-беопасным, а значит — медленным)
В сетевых сервисах ресурсы выделяет, как правило, один поток-реактор,
он же их освобождает, остальные потоки занимаются обработкой запросов
и формированием результатов. Так что массив для пула будет в ведении
одного потока. Он, при выделении памяти, просто возвращает готовый указатель из
массива-сложность O(1). Что касается tcmalloc, то вопрос: при вызове tcmalloc-овского
malloc не дёргается системный вызов? Если да, то тогда согласен, что вариант.
Но сколько уже в интернетах криков о кривости или своеобразности сторонних библиотек и необходимости
проверок и тестов перед их использованием. Последний такой пост читал про boost::shared_ptr,
который опускал в отдельном случае производительность проги на порядок.
Здравствуйте, smeeld, Вы писали:
S>В сетевых сервисах ресурсы выделяет, как правило, один поток-реактор, S>он же их освобождает, остальные потоки занимаются обработкой запросов S>и формированием результатов. Так что массив для пула будет в ведении S>одного потока. Он, при выделении памяти, просто возвращает готовый указатель из S>массива-сложность O(1). Что касается tcmalloc, то вопрос: при вызове tcmalloc-овского S>malloc не дёргается системный вызов? Если да, то тогда согласен, что вариант.
Во первых, любой нормальный аллокатор, даже алокатор из стандартной библиотеки, не дергает системный вызов каждый раз. Там есть кэш, который переиспользуется и память у ОС запрашивается большими кусками, когда программа забрала все из кэша или когда программа попросила очень большой кусок памяти, за которым не грех и в ядро сходить.
Во вторых, не стоит обобщать свой опыт на все сетевые сервисы. Может у меня по отдельному реактору на каждое ядро, может у меня обработка сложная, требующая выделния и освобождения памяти, мало ли.
В третьих, когда один и тот же поток выделяет и освобождает память, это свит спот для большинства параллельных алокаторов, все эти обращения будут попадать в fast path, не будут требовать синхронизации, будут удовлетворяться из кэша потока, ну и по сути, там получится тот же алгоритм что и у пула памяти, если выделяются и освобождаются блоки одинакового размера. Вот например тот же tcmalloc, выделяет память блоками фикс размера у ОС и потом использует каждый такой блок для того, чтобы выделять в нем куски памяти фикс. размера.
S>Но сколько уже в интернетах криков о кривости или своеобразности сторонних библиотек и необходимости S>проверок и тестов перед их использованием. Последний такой пост читал про boost::shared_ptr, S>который опускал в отдельном случае производительность проги на порядок.
Ну таки shared_ptr действительно может опускать производительность проги. Там же память динамически выделяется + синхронизация при каждом копировании или выходе копии указателя из scope-а. Если какой-то shared_ptr активно использьуется в программе разными потоками, то это будет просаживать производительность. Если программа работает с коллекциями shared_ptr-ов, то это тоже не всегда эффективно, копирование и удаление таких коллекций могут выполняться очень медленно. Я видел исследование, в котором показывалось, что во многих кейсах, управление памятью с помощью shared_ptr менее эффективно, чем сборка мусора. Ссылка на объект в .net или java это просто указатель, который может легко копироваться и передаваться куда угодно не создавая нагрузки на GC, shared_ptr это сложный объект, который содержит указатель на счетчик ссылок в динамической памяти.
