シンプルで効率的なメモリ割り当てアルゴリズムが必要

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

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