什么是下一步骤，以改善的malloc（）算法？ [英] What are the next step to improve malloc() algorithm?

问题描述

我在写我自己的简单的malloc（）的功能，我想创造出更多更快速和有效的变体。我所著使用线性搜索功能，并在内存中依次连续地分配。

这是下一个步骤，以改善该算法？什么是我的当前版本的主要缺点？我将非常感谢任何反馈意见和建议。

  typedef结构heap_block
{
    结构heap_block *接下来的;
    为size_t大小;
    布尔isfree;
}头;

＃定义Heap_Capacity 100000
静态炭堆[Heap_Capacity]
为size_t heap_size;

无效* malloc的（为size_t SZ）
{
    如果（SZ == 0 || SZ＆GT; Heap_Capacity）{返回NULL; }

    头*块=（头*）堆;
    如果（heap_size == 0）
    {
        set_data_to_block（块，SZ）;
        回报（无效*）（块+ 1）;
    }

    而（块级＆GT;！接下来= NULL）{块=块级＆gt;接着， }

    块级＆gt;接下来=（头*）（（字符*）to_end_data（块）+ 8）;
    头* new_block =块级＆gt;接着，
    set_data_to_block（new_block，SZ）;

    回报（无效*）（new_block + 1）;
}

无效set_data_to_block（头*块，为size_t SZ）
{
    块级＆GT;大小= SZ;
    块级＆GT; isfree = FALSE;
    嵌段＆gt;接着= NULL;
    heap_size + = SZ;
}

头* to_end_data（头*块）
{
    返程（头*）（（为size_t）（块+ 1）+块级＆GT;大小）;
}
 

解决方案

注意的malloc 通常高于低级别的内存相关的系统调用内置（如的的mmap（2）在Linux上）。请参见这个答案其中提到GNU 的glibc 和 MUSL-libc中。还往里 tcmalloc ，因此研究的源头code的几个的免费软件的malloc实现。

你的 malloc的一些一般性的想法：

• 使用 MMAP 检索来自操作系统的内存（与则munmap 将其释放回操作系统内核最终）。你当然不应该分配一个固定大小的堆（因为64位计算机的RAM 128Gbytes你想在的malloc -ing 10十亿字节区成功）。
• 在隔离从大的小的拨款，所以不同的处理的malloc 从一兆字节的malloc 16个字节。小型和大型分配之间典型的门槛一般是页面大小的小多（这常常是4K字节）。小拨款发生的内页。大分配是四舍五入到网页。你甚至可以处理非常特别的malloc （在许多链表等）的两个词。
• 向上舍所请求的大小，以一些花式数（2如权力，或3倍的2的幂）。
• 在管理一起类似大小的内存区，这是一样的花哨的大小。
• 对于小内存的区域，避免回收太早的存储区，所以要previously 免费 -d相同的（小）规模的区域，以重新使用他们在今后的调用的malloc 。
• 您可以使用一些技巧上的地址（但你的系统可能有 ASLR ），或保持邻近每个存储器区域的元数据描述块，其中它是一个成员的一个字。
• 在一个显著的问题是，鉴于的malloc 免费的和论证pviously返回某个地址$ P $，以找出存储器区域的分配的大小。你可以操作的地址位，之前还是可以存储大小的话，你可以使用一些哈希表等详细信息的是的棘手。

注意的细节是棘手的，很可能是相当难写一个的malloc 实施比您的系统更好。在实践中，写一个良好的的malloc 是没有的一个简单的任务。你应该找到关于这个问题的许多学术论文。

还应考虑垃圾收集技术。考虑也许贝姆保守的GC ：你将代替的malloc 按 GC_MALLOC ，你会不会理会免费 ...了解的内存池。

I'm writing my own simple malloc() function and I would like to create more faster and efficient variant. I'm writed function that use linear search and allocated sequentially and contiguously in memory.

What is the next step to improve this algorithm? What are the main shortcomings of my current version? I would be very grateful for any feedback and recommendation.

typedef struct heap_block
{  
    struct heap_block* next;
    size_t size;
    bool isfree;
}header;

#define Heap_Capacity 100000
static char heap[Heap_Capacity];
size_t heap_size;

void* malloc(size_t sz) 
{
    if(sz == 0 || sz > Heap_Capacity) { return NULL; }

    header* block = (header*)heap;
    if(heap_size == 0)
    {
        set_data_to_block(block, sz);
        return (void*)(block+1);
    }

    while(block->next != NULL) { block = block->next; }

    block->next = (header*)((char*)to_end_data(block) + 8);
    header* new_block = block->next;
    set_data_to_block(new_block, sz);

    return (void*)(new_block+1);
}

void set_data_to_block(header* block, size_t sz)
{
    block->size = sz;
    block->isfree = false;
    block->next = NULL;
    heap_size += sz;
}

header* to_end_data(header* block)
{
    return (header*)((size_t)(block+1) + block->size);
}

解决方案

Notice that malloc is often built above lower level memory related syscalls (e.g. mmap(2) on Linux). See this answer which mentions GNU glibc and musl-libc. Look also inside tcmalloc, so study the source code of several free software malloc implementations.

Some general ideas for your malloc:

• retrieve memory from the OS using mmap (and release it back to the OS kernel eventually with munmap). You certainly should not allocate a fixed size heap (since on a 64 bits computer with 128Gbytes of RAM you would want to succeed in malloc-ing a 10 billion bytes zone).
• segregate small allocations from big ones, so handle differently malloc of 16 bytes from malloc of a megabyte. The typical threshold between small and large allocation is generally a small multiple of the page size (which is often 4Kbytes). Small allocations happen inside pages. Large allocations are rounded to pages. You might even handle very specially malloc of two words (like in many linked lists).
• round up the requested size to some fancy number (e.g. powers of 2, or 3 times a power of 2).
• manage together memory zones of similar sizes, that is of same "fancy" size.
• for small memory zones, avoid reclaiming too early the memory zone, so keep previously free-d zones of same (small) size to reuse them in future calls to malloc.
• you might use some tricks on the address (but your system might have ASLR), or keep near each memory zone a word of meta-data describing the chunk of which it is a member.
• a significant issue is, given some address previously returned by malloc and argument of free, to find out the allocated size of that memory zone. You could manipulate the address bits, you could store that size in the word before, you could use some hash table, etc. Details are tricky.

Notice that details are tricky, and it might be quite hard to write a malloc implementation better than your system one. In practice, writing a good malloc is not a simple task. You should find many academic papers on the subject.

Look also into garbage collection techniques. Consider perhaps Boehm's conservative GC: you will replace malloc by GC_MALLOC and you won't bother about free... Learn about memory pools.

这篇关于什么是下一步骤，以改善的malloc（）算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！