Вектор из 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) Reserve () действительно очень большой вектор, как только приложение запускается.Однако это предполагает, что пользователь может не загружать дополнительные файлы, которые вносят вклад в этот вектор, выталкивая его за пределы предварительно выделенного предела и, возможно, возвращаясь к той же ситуации.

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

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

Вектор постоянно повторяется и обычно добавляется толькок.

Есть какие-нибудь мудрые мысли по этим вопросам?

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

см. это о фрагментации памяти (ниже приведено копирование / вставка с веб-страницы): http://www.design -reuse.com / Articles / 25090 / Динамическое распределение памяти-Фрагментация-c.html :

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

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

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

Затем запрашивается еще 4K:

    p2 = malloc(4*K);

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

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

    free(p1);

Это оставляет 6 КБ памяти свободными в двух блоках по 3 КБ. Выдается дополнительный запрос на выделение 4K:

   p1 = malloc(4*K);

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

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