Вектор 20 000 малых объектов против вектора 20 000 указателей объектов до 20 000 объектов кучи

Question

Разработка 32-разрядного приложения C++/carbon под OS X Snow Leopard, столкнулось с проблемой, когда вектор stl содержит около 20 000 мелких объектов (по 72 байта каждый) не удалось во время перераспределения. Кажется, что вектор размером в несколько мегабайт не мог расширяться до смежной части памяти, которая в момент отказа составляла всего 1,2 МБ.

GuardMalloc[Appname-33692]: *** mmap(size=2097152) failed (error code=12) 
*** error: can't allocate region 

GuardMalloc[Appname-35026]: Failed to VM allocate 894752 bytes 
GuardMalloc[ Appname-35026]: Explicitly trapping into debugger!!! 

#0 0x00a30da8 in GMmalloc_zone_malloc_internal 
#1 0x00a31710 in GMmalloc 
#2 0x94a54617 in operator new 
#3 0x0026f1d3 in __gnu_cxx::new_allocator<DataRecord>::allocate at new_allocator.h:88 
#4 0x0026f1f8 in std::_Vector_base<DataRecord, std::allocator<DataRecord> >::_M_allocate at stl_vector.h:117 
#5 0x0026f373 in std::vector<DataRecord, std::allocator<DataRecord> >::_M_insert_aux at vector.tcc:275 
#6 0x0026f5a6 in std::vector<DataRecord, std::allocator<DataRecord> >::push_back at stl_vector.h:610 

Я могу назвать несколько стратегий:

1) Резерв() действительно, действительно большой вектор, как только запуски приложений. Однако это предполагает, что пользователь может не загружать дополнительные файлы, которые способствуют этому вектору, выталкивая его за пределы заранее выделенного предела и, возможно, возвращаясь к той же ситуации.

2) Измените вектор объектов/распределений памяти в вектор указателей на объекты/распределения памяти. Ясно, что сам вектор является более управляемым размером, но затем создает 20 000 небольших объектов (которые в конечном итоге могут стать похожими на 50 000 объектов, в зависимости от того, какие дополнительные файлы загружаются пользователем). Означает ли это гигантскую проблему с накладными расходами?

3) Переход от вектора к списку, который может иметь свои собственные служебные проблемы.

Вектор постоянно повторяется и, как правило, только прилагается.

Любые мыслители мудрецов по этим вопросам?

===============

ДОПОЛНИТЕЛЬНОГО ПРИМЕЧАНИЕ: этот конкретный вектор только держит все импортируемые записи, так что они могут быть индексированы и отсортированы по другому вектору, который содержит порядок сортировки , Как только элемент помещается в этот вектор, он остается там на время жизни приложения (также помогает поддерживать операции отмены, убедившись, что индекс в вектор всегда остается неизменным для этого конкретного объекта).

Answer 1

если даже в куче, там не хватает замкнутого пространства, используйте deque; deque выделяет не смежное пространство, когда это необходимо. так что он мог бы работать с лимитом в 1,2 МБ.

deque выполнен из некоторого количества блоков памяти не только одного смежного пространства. поэтому он может работать. но он не уверен (/ полностью безопасен), потому что вы не контролируете поведение deque.

см this о фрагментации памяти (следующее копирование/вставка с веб-страницы): http://www.design-reuse.com/articles/25090/dynamic-memory-allocation-fragmentation-c.html:

Фрагментация памяти

Лучший способ понять фрагментации памяти, это посмотреть на пример. Для этого примера предполагается, что имеется куча 10K. Во-первых, площадь 3К запрашивается, таким образом:

 #define K (1024) 
    char *p1; 
    p1 = malloc(3*K); 

Затем дополнительно 4K запрашивается:

p2 = malloc(4*K); 

3K памяти теперь свободен.

Через некоторое время, то первое выделение памяти, на которую указывает p1, является де-Распределить:

free(p1); 

Это оставляет 6K памяти бесплатно в двух 3K куски. Еще просьба о выделении 4K выдаются:

p1 = malloc(4*K); 

Это приводит к неудаче - NULL возвращается в p1 - потому что, несмотря на то, кИ памяти доступны, не существует 4K непрерывного блока доступен. Это фрагментация памяти.

Это проблема даже для ядер, использующих виртуальную память, например osx.

Answer 2

Не используйте постоянное хранилище, например, vector. Перейдите для deque или list, и перераспределение не будет больше.

Если вам действительно нужна высокая производительность, подумайте о написании собственного контейнера (например, ArrayList).

Answer 3

Я думаю, что std::deque будет более подходящим, чем std::list или std::vector в вашем случае. std::list неэффективен при итерации или случайном индексировании, а std::vector медленно меняет размер (как вы заметили). A std::deque не требует больших объемов памяти при изменении размера, за счет немного более медленной случайной индексации, чем вектор.

Answer 4

Из трех вариантов 1 не кажется гарантированным решением, а 2 добавляет сложности, и вектор все еще должен расти.

Вариант 3 представляется несколько разумным (или, возможно, использовать deque, как указано в другом ответе), поскольку, хотя он семантически подобен варианту 2, он обеспечивает более нормализованный метод выделения нового объекта данных. Конечно, это предполагает, что вы только добавляете данные и не нуждаетесь в произвольном доступе.

Однако все сказанное я считаю невероятным, что ваша программа настолько фрагментировала память, что на достаточно современном оборудовании она не может выделить 1,2 МБ памяти. Скорее всего, в вашей программе существует неопределенное поведение, скрывающееся (или, возможно, утечка памяти), заставляющее его вести себя таким образом, не выделяя память. Вы можете использовать valgrind, чтобы помочь выследить, что может происходить. Возникает ли та же проблема, если вы используете встроенные new и delete, а не GMalloc?

Является ли ваша программа ulimit ed доступ только к небольшому объему памяти?

И, наконец, если valgrind ничего не находит, и ваша программа действительно ужасно фрагментирует память, я бы подумал о том, чтобы отступить и пересмотреть ваш подход. Вы можете оценить альтернативный подход, который не полагается на миллионы (?) Распределений (я просто не вижу большого количества распределений, фрагментирующих кучу).