优化我的 malloc 函数的吞吐量

Question

我有自己的 malloc 函数，带有显式的空闲列表来管理堆中的空间。空间使用的监管几乎完美，但我的吞吐量非常慢，我能对此做些什么吗？这已经是第一次适合（后进先出），其他任何东西在我耳中听起来都不会更快。

该内存分配器实现了显式空闲列表以实现高效的内存管理。 分配器使用堆空间进行内存分配。堆上的每个块要么被分配 用于管理未使用空间的使用或空闲列表的一部分。

区块结构： 每个块，无论是分配的还是空闲的，都包括页眉和页脚。页眉和页脚 每个都包含一个块大小指示符和一个分配位（0 表示空闲，1 表示已分配），其中 最小块大小为 16 字节（其中 8 字节用于有效负载，每个 4 字节用于传输） 页眉和页脚）。

在显式空闲列表中，空闲块还包含指向下一个和上一个空闲的指针 其有效负载空间内的块。这有利于有效地遍历和操纵自由 块。此外，我们还实现了序言和尾声块来处理免费的边缘情况 列表管理。

#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define MAX(x, y) ((x) > (y)? (x) : (y))
#define PACK(size, alloc) ((size) | (alloc))
#define GET(p)        (*(size_t *)(p))
#define PUT(p, val)   (*(size_t *)(p) = (val))
#define GET_SIZE(p)  (GET(p) & ~0x1)
#define GET_ALLOC(p) (GET(p) & 0x1)
#define HDRP(bp)     ((void *)(bp) - WSIZE)
#define FTRP(bp)     ((void *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)

#define NEXT_BLKP(bp) ((void *)(bp) + GET_SIZE(HDRP(bp)))
#define PREV_BLKP(bp) ((void *)(bp) - GET_SIZE(HDRP(bp) - WSIZE))
#define NEXT_FREE(bp)(*(void **)(bp))
#define PREV_FREE(bp)(*(void **)(bp + WSIZE))




static char *heap_list = 0;
static char *free_list = 0;

int mm_init(void)
{
    
    /* Create empty Heap */
    if ((heap_list = mem_sbrk(INITSIZE + MINBLOCKSIZE)) == (void *)-1)
        return -1;
    
    PUT(heap_list,              PACK(MINBLOCKSIZE, 1)); //  Prologue
    PUT(heap_list + (1*WSIZE),  PACK(MINBLOCKSIZE, 0)); //  Free block Header
    PUT(heap_list + (2*WSIZE),  PACK(0, 0));            //  Pointer to next free (space)
    PUT(heap_list + (3*WSIZE),  PACK(0, 0));            //  Pointer to previous free (space)
    PUT(heap_list + (4*WSIZE),  PACK(MINBLOCKSIZE, 0));  //  Free block footer
    PUT(heap_list + (5*WSIZE),  PACK(0, 1));            //  Epilogue
    free_list   =   heap_list + (WSIZE);
    
    

    
    
    return 0;

}


void *mm_malloc(size_t size)
{
    

    size_t asize ;
    
    void *bp;

    // Ignore useless allocation
    if(size == 0) 
    {
        return 0;
    }

    // Adjust the blocksize to include header and footer
    if(size <= DSIZE)
        asize = MINBLOCKSIZE;
    else
        // Align the size and add space for the header and footer
        asize = ALIGN(size) + DSIZE;
    
    // Search the free list for a fit, if found, place it.
    if ((bp = find_fit(asize)) != NULL)
    {

        place(bp, asize);
        return bp;
    }


    /* If there is no free space anymore, extend the Heap and then place it */
    
    if((bp = extend_heap(asize/WSIZE)) == NULL)
    {

        return NULL;

    }

    place(bp, asize);

    return bp;


}

/*
 * mm_free - Freeing a block does nothing.
 */
void mm_free(void *bp)
{

    size_t size = GET_SIZE(HDRP(bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    /*
     * ATTENTION: You do not need to implement realloc for this assignment
     */

    void *oldptr = ptr;
    void *newptr;
    size_t copySize;

    newptr = mm_malloc(size);
    if (newptr == NULL)
      return NULL;
    copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
    if (size < copySize)
      copySize = size;
    memcpy(newptr, oldptr, copySize);
    mm_free(oldptr);
    return newptr;
}

// Helper functions


/* Function to extend the size of the heap */

static void *extend_heap (size_t words)
{


    char *bp;
    size_t size;
    
    /* Allocate an even number of words to maintain alignment */
    
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;

    if ((bp = mem_sbrk(size)) == -1 ) 
    {   

        return NULL;
    }
    
    /* Initialize free block header / footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0));   //Free block header
    PUT(FTRP(bp), PACK(size, 0));   //Free block footer
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));   //New Epiloge Header
    
    /* Coalesce if the previous block was free */
    return coalesce(bp);
}


static void *coalesce(void *bp)
{


    size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)))||PREV_BLKP(bp) == bp;
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));         

    
    /* Case1 : The previos and the next block are both allocated*/
    if ( prev_alloc && next_alloc )
    {

        PREV_FREE(free_list) = bp;
        NEXT_FREE(bp) = free_list;
        PREV_FREE(bp) = NULL;
        free_list = bp;

        return bp; 
    }

    /* Case2 : The previos block is allocates and the next block is free */
    else if ( prev_alloc && !next_alloc) 
    {

        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        remove_freeblock(NEXT_BLKP(bp));
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size, 0));
    }

    /* The previos block is free and the next block is allocated */
    else if (!prev_alloc && next_alloc )
    {
        
        
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        


        PUT(FTRP(bp), PACK(size, 0));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
        bp = PREV_BLKP(bp);
        remove_freeblock(bp);
    }

    /* The previos and the next block are both free */
    else if (!prev_alloc && !next_alloc)
    {
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
        GET_SIZE(FTRP(NEXT_BLKP(bp)));
        remove_freeblock(PREV_BLKP(bp));
        remove_freeblock(NEXT_BLKP(bp));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size,0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size,0));
        bp = PREV_BLKP(bp);
    }
   

    PREV_FREE(free_list) = bp;
    NEXT_FREE(bp) = free_list;
    PREV_FREE(bp) = NULL;
    free_list = bp;

    return bp;
}



static void *find_fit(size_t asize)
{
    

    // Iterate through the free list to find a suitable block
    void *bp;
    
    for (bp = free_list; GET_ALLOC(HDRP(bp)) == 0; bp = NEXT_FREE(bp))
    {
        
        // Check if the block is free and large enough
        if (GET_SIZE(HDRP(bp)) >= asize)
        {

            return bp; // Suitable block found
        }
    }
    return NULL; // No suitable block found
}




static void place(void* bp, size_t asize)
{


    // Retrieve the size of the entire free block
    size_t bsize = GET_SIZE(HDRP(bp));

    // Check if the remaining space after allocation is sufficient for splitting
    if ((bsize - asize) >= MINBLOCKSIZE)
    {
        // Allocate the required space and adjust the remaining free block
        // The new header and footer are set up for the remaining free space
        PUT(HDRP(bp), PACK(asize, 1));
        PUT(FTRP(bp), PACK(asize, 1));
        remove_freeblock(bp); // Remove the block from the free list
        bp = NEXT_BLKP(bp);   // Move to the next block
        PUT(HDRP(bp), PACK(bsize - asize, 0)); // Set header for the new free block
        PUT(FTRP(bp), PACK(bsize - asize, 0)); // Set footer for the new free block
        coalesce(bp); // Coalesce if adjacent blocks are free
    }
    else
    {
        // Allocate the entire block if splitting is not feasible
        PUT(HDRP(bp), PACK(bsize, 1));
        PUT(FTRP(bp), PACK(bsize, 1));
        remove_freeblock(bp); // Remove the block from the free list
    }
    
}



 
static void remove_freeblock(void *bp)
{


    if(bp) {  // Ensure bp is not NULL

    // Adjust the previous block's next pointer
    // If there is a previous free block, update its next pointer to skip the current block.
    // If there is no previous block, reset the start of the free list to the next free block.
    if (PREV_FREE(bp))
      NEXT_FREE(PREV_FREE(bp)) = NEXT_FREE(bp);
    else
      free_list = NEXT_FREE(bp);

    // Adjust the next block's previous pointer
    // If there is a next free block, update its previous pointer to skip the current block.
    if(NEXT_FREE(bp) != NULL)
      PREV_FREE(NEXT_FREE(bp)) = PREV_FREE(bp);
  }
}

Answer 1