我需要一個簡單而高效的內存分配算法

Question

我想實現我自己的內存分配代碼，它簡單而高效。任何想法，我可以從哪裏開始。 gcc使用什麼算法？

Answer 1

這是一個已被檢查和實施數百次的問題;你的實施很可能會在非常特殊的情況下運行，在其他任何地方都無法運行。試圖自己解決這個問題花費的時間非常多之前，考慮打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庫實現的一部分。

Answer 2

如果你想要一個很簡單的方法：

// 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--]; 
} 

注意，記憶需要在它被分配這個工作的才能被釋放。

Answer 3

GCC使用由目標平臺的C庫提供的malloc（）。對於Linux，您可以在GNU C庫中找到malloc的實現：http://repo.or.cz/w/glibc.git/blob/HEAD:/malloc/malloc.c

對於通用分配器，您不太可能做得好得多，而且很可能會更糟，因爲默認分配器已經在很多不同的使用場景下進行了多年的調整。

對於某些特殊用途的分配器，那麼是的，擊敗一般用途的分配器肯定是可行的。

Answer 4

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是複雜的，因爲它們試圖有用和高效。它們通常建在現有的syscalls之上（例如在Linux上的mmap(2),munmap等），並且它們經常試圖重用釋放的內存。研究例如GNU libc或musl libc的相關源代碼