malloc/realloc/оптимизация свободной емкости

Если у вас есть динамически выделяемый буфер, размер которого изменяется во время выполнения непредсказуемым образом (например, вектор или строка), один из способов оптимизации его выделения — изменить размер резервного хранилища только в степени двойки (или в каком-либо другом наборе границ). пороги) и оставьте дополнительное пространство неиспользованным. Это помогает амортизировать затраты на поиск новой свободной памяти и копирование данных за счет небольшого дополнительного использования памяти. Например, спецификация интерфейса (reserve vs resize vs trim) многих контейнеров C++ stl имеет в виду такую ​​схему.

Мой вопрос заключается в том, имеет ли стандартная реализация менеджера памяти malloc/realloc/free в Linux 3.0 x86_64, GLIBC 2.13, GCC 4.6 (Ubuntu 11.10) такую ​​оптимизацию?

void* p = malloc(N);
... // time passes, stuff happens
void* q = realloc(p,M);

Иными словами, при каких значениях N и M (или при каких других обстоятельствах) p == q?


gcc linux memory glibc allocation
person Andrew Tomazos    schedule 30.01.2012    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Из реализации realloc в транке glibc по адресу http://sources.redhat.com/git/gitweb.cgi?p=glibc.git;a=blob;f=malloc/malloc.c;h=12d2211b0d6603ac27840d6f629071d1c78586fe.;hb=HEAD

Во-первых, если память была получена с помощью mmap() вместо sbrk(), что делает glibc malloc для больших запросов, >= 128 КБ по умолчанию IIRC:


   if (chunk_is_mmapped(oldp))
   {
     void* newmem;

 #if HAVE_MREMAP
     newp = mremap_chunk(oldp, nb);
     if(newp) return chunk2mem(newp);
 #endif
     /* Note the extra SIZE_SZ overhead. */
     if(oldsize - SIZE_SZ >= nb) return oldmem; /* do nothing */
     /* Must alloc, copy, free. */
     newmem = public_mALLOc(bytes);
     if (newmem == 0) return 0; /* propagate failure */
     MALLOC_COPY(newmem, oldmem, oldsize - 2*SIZE_SZ);
     munmap_chunk(oldp);
     return newmem;
   }

(В Linux есть функция mremap(), поэтому на практике так и делается).

Для небольших запросов несколькими строками ниже у нас есть

newp = _int_realloc(ar_ptr, oldp, oldsize, nb);

где _int_realloc немного великовато для копирования и вставки, но вы найдете его начиная со строки 4221 в приведенной выше ссылке. AFAICS, это НЕ увеличивает оптимизацию постоянного фактора, например. С++ std::vector делает, а скорее выделяет именно ту сумму, которую запросил пользователь (округленную до границ следующего фрагмента + материал выравнивания и т. д.).

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

person janneb    schedule 30.01.2012

arrow_upward
0
arrow_downward

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

См. также Как узнать, как много места выделяется вызовом malloc()?

person Alexey Kukanov    schedule 30.01.2012