malloc() и др. требуются стандартом C для предоставления достаточно выровненных указателей для любого типа данных, поэтому, чтобы уменьшить накладные расходы на выделение, вам необходимо реализовать свой собственный распределитель (или использовать какой-либо существующий).
Одной из возможностей было бы иметь цепочку пулов для каждого возможного размера распределения. В каждом пуле вы можете использовать битовую карту, чтобы отслеживать, какие элементы выделены, а какие свободны. Накладные расходы составляют чуть более одного бита на элемент, но в итоге у вас может быть много цепочек пулов; это делает free() медленным, потому что ему приходится искать правильный пул.
Я думаю, что лучшей возможностью является создание цепочки пулов для небольших распределений. В каждом пуле небольшие фрагменты образуют связанный список, при этом один unsigned char отслеживает длину и статус распределения. Это дает невыровненные указатели, но с накладными расходами чуть более одного символа.
Например:
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <errno.h>
#include <stdio.h>
#define SMALL_POOL_SIZE 131072
#define SMALL_LIMIT ((UCHAR_MAX + 1U) / 2U)
struct small_pool {
struct small_pool *next;
unsigned int size;
unsigned int used;
unsigned char data[];
};
static struct small_pool *list = NULL;
В элементе data[] первый символ равен от 1 до SMALL_LIMIT-1 для свободного фрагмента этого размера или SMALL_LIMIT+1 или больше для используемого фрагмента из 1 символа или более. Ноль и SMALL_LIMIT указывают на ошибки. Распределитель, агрессивный по пространству, может быть реализован, например, как
void *small_alloc(const size_t size)
{
struct small_pool *pool;
if (size < 1 || size >= SMALL_LIMIT) {
errno = EINVAL;
return NULL;
}
pool = list;
while (pool != NULL) {
/* Unused space in the pool? */
if (pool->used + size < pool->size) {
unsigned char *const ptr = pool->data + pool->used;
/* Grab it. */
pool->used += size + 1U;
/* Create new slot. */
(*ptr) = size + SMALL_LIMIT;
/* Done. */
return ptr + 1U;
}
/* Check the free slots in the pool. */
{
unsigned char *const end = pool->data + pool->used;
unsigned char *ptr = pool->data;
unsigned char big_len = SMALL_LIMIT;
unsigned char *big_ptr = NULL;
while (ptr < end)
if (*ptr == 0U || *ptr == SMALL_LIMIT) {
/* Invalid pointer */
errno = EDOM;
return NULL;
} else
if (*ptr > SMALL_LIMIT) {
/* Used slot, skip */
ptr += (*ptr) - SMALL_LIMIT + 1U;
continue;
} else {
if (*ptr < size) {
/* Slot is too small, skip it */
ptr += (*ptr) + 1U;
continue;
} else
if (*ptr == size) {
/* Perfect slot; grab it. */
(*ptr) = size + SMALL_LIMIT;
return ptr + 1U;
} else
/* Remember smallest of the large enough slots */
if (*ptr < big_len) {
big_len = *ptr;
big_ptr = ptr;
}
ptr += (*ptr) + 1U;
}
if (big_ptr != NULL) {
(*big_ptr) = big_len + SMALL_LIMIT;
return big_ptr + 1;
}
}
/* Check the next pool. */
pool = pool->next;
}
/* Need a new pool. */
pool = malloc(SMALL_POOL_SIZE);
if (pool == NULL) {
errno = ENOMEM;
return NULL;
}
/* Initialize pool; use the initial slot for the new allocation. */
pool->used = size + 1;
pool->size = SMALL_POOL_SIZE - sizeof (struct small_pool);
pool->data[0] = size + SMALL_LIMIT;
/* Prepend this pool to the pool chain. */
pool->next = list;
list = pool;
/* Return the slot we used. */
return pool->data + 1;
}
У него простая стратегия: если в пуле есть неиспользуемое конечное пространство, используйте его. В противном случае просмотрите пул, чтобы найти неиспользуемые слоты. Если есть слот идеального размера, используйте его; в противном случае используйте наименьший достаточно большой неиспользуемый слот.
Возможно много улучшений. Например, вы можете хранить полные пулы в отдельном списке, чтобы избежать их сканирования. Также может быть хорошей идеей переместить пул, в котором был найден свободный слот, в начало списка пулов.
Разводка более сложная. Если среди выделений у нас будет относительно мало освобождений и мы не беспокоимся об освобождении целых пулов, освобождение может быть таким же простым, как
int small_free(void *const item)
{
if (item == NULL)
return 0;
else {
struct small_pool *pool = list;
while (pool != NULL && !((unsigned char *)item > pool->data && (unsigned char *)item < pool->data + pool->used))
pool = pool->next;
if (pool != NULL) {
unsigned char *const ptr = (unsigned char *)item - 1;
if (*ptr > SMALL_LIMIT)
(*ptr) -= SMALL_LIMIT;
return 0;
}
return ENOENT;
}
}
предполагая, что вам нужна функция для возврата ENOENT в случае, если распределение на самом деле не является маленьким. Если важно убедиться, что освобождаемый указатель действителен, скажем, для отладки, тогда
int small_free(void *const item)
{
if (item == NULL)
return 0;
else {
struct small_pool *pool = list;
while (pool != NULL && !((unsigned char *)item > pool->data && (unsigned char *)item < pool->data + pool->used))
pool = pool->next;
if (pool != NULL) {
unsigned char *const end = pool->data + pool->used;
unsigned char *ptr = pool->data;
while (ptr < end)
if (*ptr == 0U || *ptr == SMALL_LIMIT)
return EDOM;
else
if (*ptr < SMALL_LIMIT) {
size_t len = (*ptr) + 1U;
/* Coalesce consecutive slots, if possible. */
while (len + ptr[len] < SMALL_LIMIT) {
(*ptr) = len + ptr[len];
len = (*ptr) + 1U;
}
ptr += len;
} else {
const size_t len = (*ptr) + 1U - SMALL_LIMIT;
/* Within the current slot.. probably should just
* compare item to ptr+1 instead. */
if ((unsigned char *)item > ptr && (unsigned char *)item < ptr + len) {
*ptr = len - 1U;
return 0;
}
ptr += len;
}
}
return ENOENT;
}
}
Даже эта последняя версия не обрезает ->used, когда освобождаются последние фрагменты в пуле, а также не освобождает полностью неиспользуемые пулы. Другими словами, приведенное выше освобождение — лишь грубый пример.
Что касается скорости, вышеприведенное кажется как минимум на порядок медленнее, чем GLIBC malloc()/free() на моей машине. Вот простой тест для проверки линейного распределения — шаблон полуслучайного освобождения:
/* Make sure this is prime wrt. 727 */
#define POINTERS 1000000
int main(void)
{
void **array;
size_t i;
fprintf(stderr, "Allocating an array of %lu pointers: ", (unsigned long)POINTERS);
fflush(stderr);
array = malloc((size_t)POINTERS * sizeof array[0]);
if (array == NULL) {
fprintf(stderr, "Failed.\n");
return EXIT_FAILURE;
}
fprintf(stderr, "Done.\n\n");
fprintf(stderr, "Allocating pointers in varying sizes.. ");
fflush(stderr);
for (i = 0; i < POINTERS; i++) {
const size_t n = 1 + ((i * 727) % (SMALL_LIMIT - 1));
if (!(array[i] = small_alloc(n))) {
if (errno == EDOM)
fprintf(stderr, "Failed at %lu; corrupted list.\n", (unsigned long)i + 1UL);
else
fprintf(stderr, "Failed at %lu: %s.\n", (unsigned long)i + 1UL, strerror(errno));
return EXIT_FAILURE;
}
}
fprintf(stderr, "Done.\n\n");
fprintf(stderr, "Deallocating pointers in a mixed order.. ");
fflush(stderr);
for (i = 0; i < POINTERS; i++) {
const size_t p = (i * 727) % POINTERS;
if (small_free(array[p])) {
if (errno == EDOM)
fprintf(stderr, "Failed at %lu: corrupted list.\n", (unsigned long)i + 1UL);
else
fprintf(stderr, "Failed at %lu: %s.\n", (unsigned long)i + 1UL, strerror(errno));
return EXIT_FAILURE;
}
}
fprintf(stderr, "Done.\n\n");
fprintf(stderr, "Deallocating the pointer array.. ");
fflush(stderr);
free(array);
fprintf(stderr, "Done.\n\n");
fflush(stderr);
return EXIT_SUCCESS;
}
Истинная сила распределителя на основе пула, на мой взгляд, заключается в том, что вы можете одновременно освобождать целые пулы. Имея это в виду, возможно, ваша рабочая нагрузка могла бы использовать специализированный распределитель при построении ваших структур с фазой уплотнения (способной настраивать указатели), запускаемой по крайней мере в конце, и, возможно, во время построения, если было выполнено достаточное количество удалений. . Такой подход позволит вам освободить временно необходимую память обратно в ОС. (Без уплотнения у большинства пулов, скорее всего, останется как минимум одно выделение, что сделает невозможным его освобождение.)
Я не думаю, что это вообще хороший ответ, но лучший ответ потребует более подробной информации, особенно о хранимых структурах данных и шаблоне выделения/освобождения, который происходит на практике. В отсутствие таковых, я надеюсь, это даст хотя бы некоторые идеи о том, как действовать дальше.
person
Nominal Animal
schedule
23.01.2015
free(ptr, size)); тогда вам нужно сканировать только пулы совместимого размера, а не все пулы. Если вы освобождаете не отдельные элементы, а целые пулы за раз, вы можете сделать выделение очень быстрым и потокобезопасным, используя атомарные встроенные функции. - person Nominal Animal schedule 23.01.2015