STL-ные allocator-ы, сохраняющие свое состояние, c++11
Возможно, будет проще написать кастомную коллекцию, заточенную под свои нужды, чем допиливать напильником существующие.
В твоем случае, например, может получится упаковать дерево в бинарную кучу, и память выделять только когда нужен следующий уровень в куче. В зависимости от того, как ты по этому дереву ходишь, можешь еще и заметный бонус от локальности получить. Это так, с потолка, конечно, но мало ли.
В твоем случае, например, может получится упаковать дерево в бинарную кучу, и память выделять только когда нужен следующий уровень в куче. В зависимости от того, как ты по этому дереву ходишь, можешь еще и заметный бонус от локальности получить. Это так, с потолка, конечно, но мало ли.
Результат беглого гуглинга:
http://www.sjbrown.co.uk/2004/05/01/pooled-allocators-for-th...
http://www.sjbrown.co.uk/2004/05/01/pooled-allocators-for-th...
Если замедляются вычисления, а не аллокация, то проблема гораздо сложнее и заключается в плохой локальности данных в памяти. Если это так, надо менять структуру данных, а не аллокатор.
Попробуй вот этот.
Код С++11какой компилятор? в студии >= 2012 есть набор зачетных аллокаторов
будет проще написать кастомную коллекцию, заточенную под свои нужды, чем допиливать напильником существующие.Самый здравый метод, главное что в этом случае ты точно будешь уверен, что код максимально заточен на конкретную задачу.
А вообще, многое лечится рестартами.
Вроде как в стандартной реализации вызов new в одном потоке блокирует вызовы new в рстальных потоках. Поэтому у тебя замедление не только из-за фрагментации, но и за счет того, что вызовов new из разных потоков.
А в чем сложность-то аллокатор с состоянием завести? Передавать в конструкторе ссылку на распределитель памяти. Только тебе надо длч каждого потока свой распределитель памяти получается сделать.
Кстати, с чем связано нежелание использовать буст? Я подозреваю, что там это все уже реализовано в нескольких вариантах
А в чем сложность-то аллокатор с состоянием завести? Передавать в конструкторе ссылку на распределитель памяти. Только тебе надо длч каждого потока свой распределитель памяти получается сделать.
Кстати, с чем связано нежелание использовать буст? Я подозреваю, что там это все уже реализовано в нескольких вариантах
Так плохая локальность данных как раз и возникает из-за того, что стандартный аллокатор ее не обеспечивает. И как раз кастомный алокатор, который будет выделять память из пула, и решит эту проблему
Может я не правильно понял, но как бы я решал то, что понял...
Я бы завел список свободных мелких объектов и брал бы из него, вместо создания, и вместо удаления вставлял бы в него обратно. При опустошении списка, выделял бы большой кусок объектов и вставлял бы их в этот список.
Я может и чушь пишу, но учился программированию очень давно
Я бы завел список свободных мелких объектов и брал бы из него, вместо создания, и вместо удаления вставлял бы в него обратно. При опустошении списка, выделял бы большой кусок объектов и вставлял бы их в этот список.
Я может и чушь пишу, но учился программированию очень давно
когда-то пробовал http://warp.povusers.org/FSBAllocator/ - по сравнению с "обычным" прирост был ощутимый. Но он не для всех коллекций подходит.
Еще можешь попробовать jemalloc (или еще какой-нибудь распространенный) через LD_PRELOAD подсунуть - тогда даже перекомпилировать ничего не придется. Это если не винда, конечно
Еще можешь попробовать jemalloc (или еще какой-нибудь распространенный) через LD_PRELOAD подсунуть - тогда даже перекомпилировать ничего не придется. Это если не винда, конечно
Пример простого аллокатора - http://www.josuttis.com/cppcode/myalloc.hpp
Вместо сохранения состояния new и delete можно заменить на обращение к синглтону/статическому члену, реализующему что-нибудь наподобие кольцевого буфера.
Вместо сохранения состояния new и delete можно заменить на обращение к синглтону/статическому члену, реализующему что-нибудь наподобие кольцевого буфера.
Я бы завел список свободных мелких объектов и брал бы из него, вместо создания, и вместо удаления вставлял бы в него обратно. При опустошении списка, выделял бы большой кусок объектов и вставлял бы их в этот список.ты сейчас пул и описал
Я может и чушь пишу, но учился программированию очень давно
Пример простого аллокатора - http://www.josuttis.com/cppcode/myalloc.hppне то
Вместо сохранения состояния new и delete можно заменить на обращение к синглтону/статическому члену, реализующему что-нибудь наподобие кольцевого буфера.
мне как раз и не надо никаких статических членов и singleton-ов. Грубо говоря, у меня прога обсчитывает вычисления по запросам со стороны клиентов. Каждый запрос - это вычислений секунд на 30. То есть, взялся из пула поток, ему говорят "посчитай это" - он козыряет и идет считать. При вычислениях порождается туча map-ов и vector-ов, и все было бы хорошо, если бы не многопоточность и фрагментация памяти + проблема нелокальности.
В идеальном случае, если бы я мог как угодно работать с памятью с STL-ными контейнерами, я бы выделял (или брал из пула) на каждый поток непрырывный блок размером в гигабайт, и чтобы STL-совместимый аллокатор просто брал бы память из пула, но не освобождал ее. После завершения потока этот гигабайт бы просто клался назад в пул. То есть, мне многопоточный хитровыдуманный менеджер памяти типа TCMalloc или Hoard не нужен. Проблема именно в том, как завести STL-совместимый аллокатор с привязкой к нестатичному буферу в пределах класса или даже процедуры.
Можно, конечно, сделать так, чтобы каждый аллокатор ссылался на некий статичный memory manager, который бы выделял в начале работы программы гигабайт эдак 40 непрырывным блоком и выдавал бы разным потокам адреса типа thread_id * 1GB + current_thread_offset, но это как-то неизящно.
Можно, конечно, сделать так, чтобы каждый аллокатор ссылался на некий статичный memory manager, который бы выделял в начале работы программы гигабайт эдак 40 непрырывным блоком и выдавал бы разным потокам адреса типа thread_id * 1GB + current_thread_offset, но это как-то неизящно.Выделяй при выполнении запроса кусками размером с page size.
проблема решилась использованием intel-овского scalable-allocator-ов из TBB
Оставить комментарий
NataNata
В с++-шной проге постоянно заводятся и удаляются сотни тысяч мелких объектов (листья деревьев, например). Прога многопоточная, скажем, 30 потоков сразу работает. В результате, через некоторое время память становится жутко фрагментированной, вычисления сильно замедляются.Сейчас в проге используются STL-ные контейнеры (потому что было удобно разрабатывать). Код С++11, boost не используется (и очень не хочется его использовать). Переделывать код в стиль обычного Си - можно, но упадет его читаемость.
Знает ли кто-нибудь пример кода, из которого было бы понятно, как завести\запрогать stl-ный allocator, который бы сохранял свое состояние, и, значит, позволил бы завести пул объектов (листьев деревьев)? Гугление наводило на allocator_traits и scoped_allocator_traits, но я там сходу мало что понял.