malloc / realloc / свободная оптимизация емкости - PullRequest
Новая
       42

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

3 голосов
/ 30 января 2012

Когда у вас есть динамически распределенный буфер, который изменяет свой размер во время выполнения непредсказуемым образом (например, вектор или строка), один из способов оптимизировать его распределение - это только изменить размер своего резервного хранилища на степени 2 (или некоторый другой наборграниц / порогов), и оставьте дополнительное пространство неиспользованным.Это помогает амортизировать стоимость поиска новой свободной памяти и копирования данных за счет небольшого дополнительного использования памяти.Например, спецификация интерфейса (резерв против изменения размера и обрезка) многих контейнеров st ++ C ++ имеет в виду такую ​​схему.

У меня вопрос, является ли реализация по умолчанию диспетчера памяти 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?

Ответы [ 2 ]

3 голосов
/ 30 января 2012

Из реализации 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, он НЕ делает увеличения при постоянном коэффициенте оптимизации, как, например, в C ++ std :: vector, а скорее выделяет именно то количество, которое запрашивает пользователь (округляется до границ следующего куска + выравнивающие элементы и т. Д.).

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

0 голосов
/ 30 января 2012

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

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

...