Мне нужен простой, но эффективный алгоритм распределения памяти - PullRequest
Новая
       0

Мне нужен простой, но эффективный алгоритм распределения памяти

1 голос
/ 16 января 2012

Я пытаюсь реализовать свой собственный код выделения памяти, который прост, но эффективен.Любая идея, откуда я могу начать.Какой алгоритм использует gcc?

Ответы [ 4 ]

7 голосов
/ 16 января 2012

Это проблема, которая была рассмотрена и реализована сотни раз;Скорее всего, ваша реализация будет работать в очень специфической ситуации и больше нигде.Прежде чем тратить огромное количество времени на попытки решить эту проблему самостоятельно, рассмотрите существующие реализации, которые побеждают обобщенный механизм выделения gcc:

http://goog -perftools.sourceforge.net / doc / tcmalloc.html

http://www.canonware.com/jemalloc/

Вы также можете проверить реализацию самого GCC / glibc, просмотрев исходные версии:

http://gcc.gnu.org/releases.html

http://ftp.gnu.org/gnu/glibc/

Malloc является частью реализации библиотеки GNU C.

5 голосов
/ 16 января 2012

A malloc, который всегда возвращает NULL, соответствует букве стандарта.Поэтому я предлагаю 

/* always return NULL, following the letter but not the spirit 
   of the standard */
inline void *malloc(size_t sz)
{  errno = ENOMEM;
   return NULL;   }

Если скорость является вашим основным критерием, она достаточно эффективна.Я не утверждаю, что это полезно, но вы не просили о полезности.

Реальные malloc являются сложными, потому что они пытаются быть полезными и эффективными.Они часто создаются поверх существующих системных вызовов (например, mmap (2) , munmap в Linux и т. Д.) И часто пытаются повторно использовать освобожденную память.Изучите, например, соответствующий исходный код GNU libc или musl libc

2 голосов
/ 16 января 2012

GCC использует malloc (), как это предусмотрено библиотекой C целевой платформы. Для Linux вы можете найти реализацию malloc в библиотеке GNU C здесь: http://repo.or.cz/w/glibc.git/blob/HEAD:/malloc/malloc.c

В распределителе общего назначения вы вряд ли добьетесь гораздо больших успехов и, скорее всего, чего-то ужасно худшего, поскольку распределитель по умолчанию настраивался в течение многих лет для многих различных сценариев использования.

Для какого-то специального назначения распределителя, тогда да, конечно, возможно превзойти универсальный распределитель.

1 голос
/ 16 января 2012

Если вы хотите действительно простой метод: 

// 1 KB of data that can be allocated
#define MAX_DATA 1024

char pointers[MAX_DATA];
int  currentOffset = 0;
int ptrNum = 0;
int sizes[MAX_DATA];

void *malloc(int numBytes)
{
    char *ptr = pointers + currentOffset;

    currentOffset += numBytes;

    if (currentOffset >= MAX_DATA)
        return NULL;

    sizes[ptrNum++] = numBytes;

    return ptr;
}

void free(void *ptr)
{
    currentOffset -= sizes[ptrNum--];
}

Обратите внимание, что память должна быть освобождена в том порядке, в котором она была выделена для этой работы.

...