准备

警告：这可以说是 CSAPP 所有的 lab 里面最难的一个，datalab 也很难，但是 datalab 只是难在思路，代码量少，二进制数据操作简明，犯错惩罚小；而 malloc lab… 恩，虽 然几种解题思路其实书里面已经给了明确的解释，但代码实现上还是很复杂很容易出错的， 比如指针操作几乎没有容错可能性，稍有不慎就会跳 Segment Fault; 再者，malloc lab 的性能优化是一个无底洞，做到 80⁄100 不难，再调优的话，性能的提高和时间的投入就不 成比例了。

所以：

  1. 一定要仔细阅读 malloc lab 的要求文档，pdf 文档在 CSAPP labs 官网上；
  2. 一定要仔细阅读 CSAPP3e 9.9 章节，没有看完或完全理解之前不要碰这个 lab;
  3. 一定要理解 C 语言中指针的各种操作，比如 int *number; number + 1 中输入只是 +1, 但得到的指针值是 +4 的，因为这个指针指向的是一个 int 型数据，每一个该类 型的数据占4字节；
  4. 在代码中最好把一些频繁出现的的指针操作定义为宏，降低维护成本；
  5. 性能调优适可而止，有时候几个小时的投入换不来 1% 的性能提升；

做这个 lab 的过程中有4次比较大的改动，以及2个针对 trace 文件的小改动，每次改动相 应的性能都提高一点，当然，越到后面，提高的程度越少：

  1. 隐式空闲链表
  2. 地址顺序显式空闲链表
  3. LIFO顺序显式空闲链表
  4. 分离适配LIFO顺序显式空闲链表
  5. 优化 mm_realloc 函数
  6. 针对 coalesce trace 文件优化定制

策略与代码

隐式空闲链表

CSAPP3e 9.9.12 已经拿出了一个实现隐式空闲链表的分配器，只是还没实现 mm_realloc find_fit place, 实现这些功能：

mm_realloc

这个版本的 =mm_realloc= 是完全建立在前面 =mm_malloc mm_free 的基础上的，性能 并不如意，文档中也提到了，要想让该功能有更好的性能表现，函数必须是 standalone (怎么翻译？理解为独立的，不依赖其他主要功能函数):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

void *mm_realloc(void *ptr, size_t size)
{
  size_t oldsize;
  void *newptr;

  /* If size == 0 then this is just free, and we return NULL. */
  if(size == 0) {
    mm_free(ptr);
    return 0;
  }

  /* If oldptr is NULL, then this is just malloc. */
  if(ptr == NULL) {
    return mm_malloc(size);
  }

  newptr = mm_malloc(size);

  /* If realloc() fails the original block is left untouched  */
  if(!newptr) {
    return 0;
  }

  /* Copy the old data. */
  oldsize = GET_SIZE(HDRP(ptr));
  if(size < oldsize) oldsize = size;
  memcpy(newptr, ptr, oldsize);

  /* Free the old block. */
  mm_free(ptr);

  return newptr;
}

find_fit & place

这两个功能函数在书中是做为习题的，见习题 9.8 和 9.9, 实现起来不难；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

static void *find_fit(size_t asize)
{
  /* First-fit search */
  void *bp;

  for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
    if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp)))) {
      return bp;
    }
  }
  return NULL; /* No fit */
}

static void place(void *bp, size_t asize)
{
  size_t csize = GET_SIZE(HDRP(bp));

  if ((csize - asize) >= (2*DSIZE)) {
    PUT(HDRP(bp), PACK(asize, 1));
    PUT(FTRP(bp), PACK(asize, 1));
    bp = NEXT_BLKP(bp);
    PUT(HDRP(bp), PACK(csize-asize, 0));
    PUT(FTRP(bp), PACK(csize-asize, 0));
  }
  else {
    PUT(HDRP(bp), PACK(csize, 1));
    PUT(FTRP(bp), PACK(csize, 1));
  }
}

性能

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.009700   587
 1       yes   99%    5848  0.008555   684
 2       yes   99%    6648  0.015160   439
 3       yes  100%    5380  0.013171   408
 4       yes   66%   14400  0.000184 78389
 5       yes   92%    4800  0.012939   371
 6       yes   92%    4800  0.012109   396
 7       yes   55%   12000  0.190475    63
 8       yes   51%   24000  0.442376    54
 9       yes   27%   14401  0.244156    59
10       yes   34%   14401  0.003677  3917
Total          74%  112372  0.952503   118

Perf index = 44 (util) + 8 (thru) = 52/100

地址顺序显式空闲链表

实现 CSAPP3e 9.9.13 介绍的显式空闲链表，按照地址顺序维护链表中的元素，也就是说链 中每个块的地址都小于它后继的地址：

链表起始标识位

需要一个固定的链表起始位来帮助定位，这里使用在 mm_init 函数中为了对齐而设置的 一个字的起始位置，这个位置绝对不会被使用；

另外，为了所有显式空闲链表中的元素都可以保持接口上的一致性，这个固定的起始位虽然 没有前驱，但还是会留一个内容永远为0的前驱位；

所以，现在 =mm_init= 中在真正的堆开始之前需要留出三个字的空间（第一个还是用来 对齐），所以现在初始化堆区就需要6个字了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/*
   A pointer whose value is an address of second heap byte
   That place always sotres 0 for there would be no prev free block
   the next word stores an address of the successive free block
   If there is no successive one, the content is 0
*/
static unsigned int *starter = 0;

int mm_init(void)
/* based on explicit free list */
{
  void *bp;
  mem_init();

  /* Create the initial empty heap */
  if ((heap_listp = (char *)mem_sbrk(6*WSIZE)) == (char *)-1)
    return -1;

  starter = (unsigned int *)mem_heap_lo() + 1;
  PUT(heap_listp, 0);	                         /* Alignment padding */
  PUT_PREV(starter, 0);
  PUT_SUCC(starter, 0);                        /* First, starter is alone */
  PUT(heap_listp + (3*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
  PUT(heap_listp + (4*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
  PUT(heap_listp + (5*WSIZE), PACK(0, 1));     /* Epilogue header */
  heap_listp += (4*WSIZE);
  /* Extend the empty heap with a free block of CHUNKSIZE bytes */
  bp = extend_heap(CHUNKSIZE/WSIZE);
  if (bp == NULL)
    return -1;
  return 0;
}

指针操作宏

为了方便后面大量指针操作的维护，也为了尽量避免在繁琐的指针操作中犯错，指针操作宏 是很有必要的（一开始作者没有使用宏，后果惨烈）， unsigned int * 指定指针类型， 当然也可以指定为 void *, 这样的话指针加减就得明确桉照一个字的大小操作了：

1
2
3
4
5

/* Doubly linked free list manipulations */
#define GET_PREV(p)      (GET(p))	  /* Just a alias of former GET */
#define PUT_PREV(p, val) (PUT(p, val))  /* Alias of former PUT */
#define GET_SUCC(p)      (*((unsigned int *)p + 1))
#define PUT_SUCC(p, val) (*((unsigned int *)p + 1) = (val))

前面提到的链表元素接口一致性，就是说，包括起始标识位，所有链表元素都可以使用这几个宏。

coalesce

处理可能存在的空闲块前后合并情形。

第一种情况需要注意，这个空闲块没有可合并的前后块，它需要按照地址顺序链接到显式空 闲链表中；另外三种情况只需要继承被合并块的链接关系（如何继承视情况而定）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

/*
 * coalesce - Boundary tag coalescing. Return ptr to coalesced block
 */
static void *coalesce(void *bp)
/* based on a explicit free list */
{
  void *prev_bp, *next_bp;
  unsigned int succ_free, prev_free;
  size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
  size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
  size_t size = GET_SIZE(HDRP(bp));

  if (prev_alloc && next_alloc) {            /* Case 1 */
    succ_free = GET_SUCC(starter);
    prev_free = (unsigned int)starter;
    for(; succ_free != 0; succ_free = GET_SUCC(succ_free))
      {
	if(succ_free > (unsigned int)bp)
	  {
	    PUT_PREV(succ_free, (unsigned int)bp);
	    PUT_SUCC(bp, succ_free);
	    PUT_SUCC(prev_free, (unsigned int)bp);
	    PUT_PREV(bp, prev_free);
	    return bp;
	  }
	prev_free = succ_free;
      }
    PUT_SUCC(bp, succ_free);
    PUT_SUCC(prev_free, (unsigned int)bp);
    PUT_PREV(bp, prev_free);
    return bp;
  }

  else if (prev_alloc && !next_alloc) {      /* Case 2 */
    next_bp = NEXT_BLKP(bp);
    size += GET_SIZE(HDRP(next_bp));
    prev_free = GET_PREV(next_bp);
    succ_free = GET_SUCC(next_bp);
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size,0));
    PUT_PREV(bp, prev_free);
    PUT_SUCC(bp, succ_free);
    if(succ_free)
      {
	PUT_PREV(succ_free, (unsigned int)bp);
      }
    PUT_SUCC(prev_free, (unsigned int)bp);
  }

  else if (!prev_alloc && next_alloc) {      /* Case 3 */
    prev_bp = PREV_BLKP(bp);
    size += GET_SIZE(HDRP(prev_bp));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(prev_bp), PACK(size, 0));
    bp = PREV_BLKP(bp);
  }

  else {                                     /* Case 4 */
    prev_bp = PREV_BLKP(bp);
    next_bp = NEXT_BLKP(bp);
    size += GET_SIZE(HDRP(prev_bp)) +
      GET_SIZE(FTRP(next_bp));
    succ_free = GET_SUCC(next_bp);
    PUT(HDRP(prev_bp), PACK(size, 0));
    PUT(FTRP(next_bp), PACK(size, 0));
    bp = PREV_BLKP(bp);
    PUT_SUCC(bp, succ_free);
    if(succ_free)
      {
	PUT_PREV(succ_free, (unsigned int)bp);
      }
  }
  return bp;
}

find_fit & place

place 方法需要注意空闲块被占用以后该块在空闲链表中的脱离，以及它前后空闲块的重 新链接；如果被占用的剩下的大小大于两个双字，那么分割出这个残馀块并让它继承被占块的链接关系。

=find_fit 方法使用一个 for 循环从头遍历显式空闲链表，寻找是否有空闲块的大小合适；

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

static void place(void *bp, size_t asize)
{
  size_t csize = GET_SIZE(HDRP(bp));
  unsigned int prev_free, succ_free;
  prev_free = GET_PREV(bp);
  succ_free = GET_SUCC(bp);

  if ((csize - asize) >= (2*DSIZE)) {
    PUT(HDRP(bp), PACK(asize, 1));
    PUT(FTRP(bp), PACK(asize, 1));
    bp = NEXT_BLKP(bp);
    PUT(HDRP(bp), PACK(csize-asize, 0));
    PUT(FTRP(bp), PACK(csize-asize, 0));
    if(succ_free)
      {
	PUT_PREV(succ_free, (unsigned int)bp);
      }
    PUT_SUCC(prev_free, (unsigned int)bp);
    PUT_PREV(bp, prev_free);
    PUT_SUCC(bp, succ_free);
  }
  else {
    PUT(HDRP(bp), PACK(csize, 1));
    PUT(FTRP(bp), PACK(csize, 1));
    PUT_SUCC(prev_free, succ_free);
    if(succ_free) PUT_PREV(succ_free, prev_free);
  }
}


static void *find_fit(size_t asize)
{
  /* First-fit search */
  unsigned int bp;

  for (bp = GET_SUCC(starter); bp != 0; bp = GET_SUCC(bp))
    {
      if (asize <= GET_SIZE(HDRP(bp)))
	return (void *)bp;
    }
  return NULL; /* No fit */
}

性能

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.001094  5206
 1       yes   99%    5848  0.000709  8249
 2       yes   99%    6648  0.001228  5413
 3       yes  100%    5380  0.001258  4276
 4       yes   66%   14400  0.000327 44010
 5       yes   92%    4800  0.004428  1084
 6       yes   92%    4800  0.003971  1209
 7       yes   55%   12000  0.033867   354
 8       yes   51%   24000  0.153993   156
 9       yes   27%   14401  0.243775    59
10       yes   34%   14401  0.003742  3849
Total          74%  112372  0.448392   251

Perf index = 44 (util) + 17 (thru) = 61/100

评分比隐式空闲列表多了9分。

LIFO顺序显式空闲链表

实现 CSAPP3e 9.9.13 介绍的显式空闲链表，按照LIFO顺序维护链表中的元素，将新释放的块放置在链表的开始处：

链表起始标识位

不变

指针操作宏

为了无痛使用宏，加了两个类型转换，其余不变：

1
2
3

#define PUT_PREV(p, val) (PUT(p, (unsigned int)val))  /* Alias of former PUT */

#define PUT_SUCC(p, val) (*((unsigned int *)p + 1) = (unsigned int)(val))

coalesce

为了代码的维护方便，以及复用性，定义了两个帮助函数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/*
 * chain2starter - chain a free blk to starter
 */
void chain2starter(void* bp)
{
  unsigned int starter_succ_free = GET_SUCC(starter);
  PUT_PREV(bp, starter);
  PUT_SUCC(starter, bp);
  PUT_SUCC(bp, starter_succ_free);
  if(starter_succ_free) PUT_PREV(starter_succ_free, bp);
}

/*
 * chain2prevnext - chain the free prev and next of a free blk
 */
void chain2prevnext(void *bp)
{
  unsigned int succ_free, prev_free;
  succ_free = GET_SUCC(bp);
  prev_free = GET_PREV(bp);
  PUT_SUCC(prev_free, succ_free);
  if(succ_free) PUT_PREV(succ_free, prev_free);
}

这样接下来的代码简洁多了，需要注意的问题和 地址顺序显式空闲链表 差不多，无合并空 闲块时的链接，有合并空闲块时的链接关系继承以及修复：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

static void *coalesce(void *bp)
/* based on a explicit free list */
{
  void *prev_bp = PREV_BLKP(bp), *next_bp = NEXT_BLKP(bp);
  size_t prev_alloc = GET_ALLOC(FTRP(prev_bp));
  size_t next_alloc = GET_ALLOC(HDRP(next_bp));
  size_t size = GET_SIZE(HDRP(bp));

  if (prev_alloc && next_alloc) {            /* Case 1 */
    chain2starter(bp);
  }

  else if (prev_alloc && !next_alloc) {      /* Case 2 */
    size += GET_SIZE(HDRP(next_bp));
    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(next_bp), PACK(size,0));
    chain2prevnext(next_bp);
    chain2starter(bp);
  }

  else if (!prev_alloc && next_alloc) {      /* Case 3 */
    size += GET_SIZE(HDRP(prev_bp));
    PUT(FTRP(bp), PACK(size, 0));
    PUT(HDRP(prev_bp), PACK(size, 0));
    chain2prevnext(prev_bp);
    bp = prev_bp;
    chain2starter(bp);
  }

  else {                                     /* Case 4 */
    size += GET_SIZE(HDRP(prev_bp)) +
      GET_SIZE(FTRP(next_bp));
    PUT(HDRP(prev_bp), PACK(size, 0));
    PUT(FTRP(next_bp), PACK(size, 0));
    chain2prevnext(next_bp);
    chain2prevnext(prev_bp);
    bp = prev_bp;
    chain2starter(bp);
  }
  return bp;
}

find_fit & place

find_fit 函数大体上与地址顺序的那个版本保持一致。

place 函数使用了帮助函数，精简了不少，并且有LIFO针对性的改动：修复原空闲块占 后的前后链接关系，如果有重新配置为空闲块的残馀块要链接到链表中最开端。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

static void place(void *bp, size_t asize)
{
  size_t csize = GET_SIZE(HDRP(bp));

  chain2prevnext(bp);

  if ((csize - asize) >= (2*DSIZE)) {
    PUT(HDRP(bp), PACK(asize, 1));
    PUT(FTRP(bp), PACK(asize, 1));
    bp = NEXT_BLKP(bp);
    PUT(HDRP(bp), PACK(csize-asize, 0));
    PUT(FTRP(bp), PACK(csize-asize, 0));
    coalesce(bp);
  }
  else {
    PUT(HDRP(bp), PACK(csize, 1));
    PUT(FTRP(bp), PACK(csize, 1));
  }
}

性能

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   89%    5694  0.001245  4572
 1       yes   92%    5848  0.000840  6964
 2       yes   94%    6648  0.001846  3601
 3       yes   96%    5380  0.001490  3611
 4       yes   66%   14400  0.000275 52383
 5       yes   88%    4800  0.003161  1518
 6       yes   85%    4800  0.003893  1233
 7       yes   55%   12000  0.003694  3249
 8       yes   51%   24000  0.004607  5210
 9       yes   26%   14401  0.242558    59
10       yes   34%   14401  0.003702  3890
Total          71%  112372  0.267311   420

Perf index = 42 (util) + 28 (thru) = 70/100

相比地址顺序维护的空闲链表，性能提高了9分。

分离适配LIFO顺序显式空闲链表

实现 CSAPP3e 9.9.14 介绍的分离空闲链表，按照大小分为多个空闲链表，每个空闲链表按照LIFO顺序维护链表中的元素：

链表起始标识位

既然有有多个桉大小分类的空闲链表，那么就有相应数量的链表起始标识位，为了在 =mm_init= 初始化时不至于浪费太多的存储位置，每个标识位一个字，只包含指向后继空 闲块的指针，这一次链表起始位置指针操作不通过预先定义的指针操作宏。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

static unsigned int *segregate_starter = 0; /* Pointer to first one of segregated list */
int mm_init(void)
{
  void *bp;
  mem_init();

  /* Create the initial empty heap */
  if ((heap_listp = (char *)mem_sbrk(14*WSIZE)) == (char *)-1)
    return -1;

  segregate_starter = (unsigned int *)heap_listp;

  PUT(heap_listp,0);              /* free list, block size <=16 */
  PUT(heap_listp+(1*WSIZE),0);    /* block size <=32 */
  PUT(heap_listp+(2*WSIZE),0);    /* block size <=64 */
  PUT(heap_listp+(3*WSIZE),0);    /* block size <=128 */
  PUT(heap_listp+(4*WSIZE),0);    /* block size <=256 */
  PUT(heap_listp+(5*WSIZE),0);    /* block size <=512 */
  PUT(heap_listp+(6*WSIZE),0);    /* block size <=1024 */
  PUT(heap_listp+(7*WSIZE),0);    /* block size <=2048 */
  PUT(heap_listp+(8*WSIZE),0);    /* block size <=4096 */
  PUT(heap_listp+(9*WSIZE),0);    /* block size >4096 */
  PUT(heap_listp+(10*WSIZE),0);	  /* Align padding */
  PUT(heap_listp + (11*WSIZE), PACK(DSIZE, 1)); /* Prologue header */
  PUT(heap_listp + (12*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
  PUT(heap_listp + (13*WSIZE), PACK(0, 1));     /* Epilogue header */
  heap_listp += (12*WSIZE);
  /* Extend the empty heap with a free block of CHUNKSIZE bytes */
  bp = extend_heap(CHUNKSIZE/WSIZE);
  if (bp == NULL)
    return -1;
  return 0;
}

指针操作宏

保持不变。

coalesce

LIFO顺序显式空闲链表 中定义的两个帮助函数有针对性的更改；新定义一个函数，功能是 检查传入的 size 参数检索分离的空闲链表组返回相应的空闲链表头。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

static void *find_segregate(size_t size)
{
  int patch = 0;

  if(size <= 16) patch = 0;
  else if(size <= 32) patch = 1;
  else if(size <= 64) patch = 2;
  else if(size <= 128) patch = 3;
  else if(size <= 256) patch = 4;
  else if(size <= 512) patch = 5;
  else if(size <= 1024) patch = 6;
  else if(size <= 2048) patch = 7;
  else if(size <= 4096) patch = 8;
  else patch = 9;

  return segregate_starter + patch;
}

void chain2segregate(void* bp, size_t size)
{
  unsigned int *starter;
  starter = find_segregate(size);
  unsigned int segregate_succ_free = *starter;
  PUT_PREV(bp, starter);
  *starter = (unsigned int)bp;
  PUT_SUCC(bp, segregate_succ_free);
  if(segregate_succ_free) PUT_PREV(segregate_succ_free, bp);
}


void chain2prevnext(void *bp)
{
  unsigned int succ_free, *prev_free;
  succ_free = GET_SUCC(bp);
  prev_free = (unsigned int *)GET_PREV(bp);
  if((segregate_starter + 9) >= prev_free) *prev_free = succ_free;
  else PUT_SUCC(prev_free, succ_free);
  if(succ_free) PUT_PREV(succ_free, prev_free);
}

coalesce 函数就是把 chain2starter 的调用改成了调用 chain2segregate, 其余不变。

find_fit & place

place 函数保持不变。

find_fit= 函数针对分离空闲链表组有更改，添加一个内嵌 for 循环来寻找匹配的空闲块：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

static void *find_fit(size_t asize)
{
  /* First-fit search */
  unsigned int *bp, *starter, *maxstarter = segregate_starter + 9;

  for(starter = find_segregate(asize); starter <= maxstarter; starter += 1)
    {
      for (bp = (unsigned int *)(*starter); bp != 0; bp = (unsigned int *)GET_SUCC(bp))
	{
	  if (asize <= GET_SIZE(HDRP(bp)))
	    return (void *)bp;
	}
    }
  return NULL; /* No fit */
}

性能

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   98%    5694  0.001120  5085
 1       yes   94%    5848  0.000890  6573
 2       yes   98%    6648  0.001313  5064
 3       yes   99%    5380  0.001334  4031
 4       yes   66%   14400  0.000380 37925
 5       yes   89%    4800  0.002676  1794
 6       yes   86%    4800  0.002755  1742
 7       yes   55%   12000  0.001006 11928
 8       yes   51%   24000  0.001006 23852
 9       yes   30%   14401  0.242134    59
10       yes   34%   14401  0.003921  3673
Total          73%  112372  0.258535   435

Perf index = 44 (util) + 29 (thru) = 73/100

3分 …

优化 mm_realloc 函数

trace 文件中最后两个是检查 mm_realloc 函数性能的，从前面的性能数据可以看出，完 全依赖与 mm_free 和 =mm_malloc 来定义的 mm_realloc 函数性能很糟糕，特别是空间利用率。

性能糟糕的主要原因就是， =mm_realloc 函数在进行重新分配的过程中，没有考虑重分 配大小和原始大小的比较、被重分配的块前后空闲块的问题。

两个帮助函数 - place & coalesce 的特别定制版本

当然可以直接修改原有的 place 和 coalesce 函数，添加一些 if/esle 条件调整，不过那样又难看，又不利于后期维护。

这两个特别定制函数和它们母版的不同在于：

  1. realloc_place 传入的地址的块不是空闲块（可能是空闲块和已占用块的合并），它 没有前后链接关系，所以不需要处理它的链接关系；
  2. realloc_coalesce 中如果有空闲块合并，要检查它的合并后大小是否大于等于重分配 大小，如果是再进行合并；合并后的‘空闲块’马上就要被使用，所以不需要链接。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

static void realloc_place(void *bp, size_t asize)
{
  size_t csize = GET_SIZE(HDRP(bp));

  if ((csize - asize) >= (2*DSIZE)) {
    PUT(HDRP(bp), PACK(asize, 1));
    PUT(FTRP(bp), PACK(asize, 1));
    bp = NEXT_BLKP(bp);
    PUT(HDRP(bp), PACK(csize-asize, 0));
    PUT(FTRP(bp), PACK(csize-asize, 0));
    coalesce(bp);
  }
  else {
    PUT(HDRP(bp), PACK(csize, 1));
    PUT(FTRP(bp), PACK(csize, 1));
  }
}

static void *realloc_coalesce(void *bp, size_t asize, int *is_next_free)
{
  void *prev_bp = PREV_BLKP(bp), *next_bp = NEXT_BLKP(bp);
  size_t prev_alloc = GET_ALLOC(FTRP(prev_bp));
  size_t next_alloc = GET_ALLOC(HDRP(next_bp));
  size_t size = GET_SIZE(HDRP(bp));
  *is_next_free = 0;

  if (prev_alloc && next_alloc) {}           /* Case 1 */

  else if (prev_alloc && !next_alloc) {      /* Case 2 */
    size += GET_SIZE(HDRP(next_bp));
    if(size >= asize)
      {
	PUT(HDRP(bp), PACK(size, 0));
	PUT(FTRP(next_bp), PACK(size,0));
	chain2prevnext(next_bp);
	*is_next_free = 1;
      }
  }

  else if (!prev_alloc && next_alloc) {      /* Case 3 */
    size += GET_SIZE(HDRP(prev_bp));
    if(size >= asize)
      {
	PUT(FTRP(bp), PACK(size, 0));
	PUT(HDRP(prev_bp), PACK(size, 0));
	chain2prevnext(prev_bp);
	bp = prev_bp;
      }
  }

  else {                                     /* Case 4 */
    size += GET_SIZE(HDRP(prev_bp)) +
      GET_SIZE(FTRP(next_bp));
    if(size >= asize)
      {
	PUT(HDRP(prev_bp), PACK(size, 0));
	PUT(FTRP(next_bp), PACK(size, 0));
	chain2prevnext(next_bp);
	chain2prevnext(prev_bp);
	bp = prev_bp;
      }
  }
  return bp;
}

重分配策略优化的 mm_realloc

实现前面所说的大小比较以及可能的前后空闲块合并1。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

void *mm_realloc(void *ptr, size_t size)
{
  int is_next_free;
  size_t oldsize, asize, cp_size;
  void *newptr;

  /* If size == 0 then this is just free, and we return NULL. */
  if(size == 0) {
    mm_free(ptr);
    return 0;
  }

  /* If oldptr is NULL, then this is just malloc. */
  if(ptr == NULL) return mm_malloc(size);

  asize = ALIGN(size+DSIZE);
  oldsize = GET_SIZE(HDRP(ptr));
  cp_size = oldsize - DSIZE;

  if(oldsize == asize) return ptr;
  else if(oldsize < asize)
    {
      newptr = realloc_coalesce(ptr, asize, &is_next_free);
      if(is_next_free)
	{
	  realloc_place(newptr, asize);
	  return newptr;
	}
      else if(!is_next_free && newptr != ptr)
	{
	  memmove(newptr, ptr, cp_size);
	  realloc_place(newptr, asize);
	  return newptr;
	}
      else
	{
	  newptr = mm_malloc(asize);
	  memmove(newptr, ptr, cp_size);
	  mm_free(ptr);
	  return newptr;
	}
    }
  else
    {
      realloc_place(ptr, asize);
      return ptr;
    }
}

性能

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   98%    5694  0.000978  5820
 1       yes   94%    5848  0.001058  5528
 2       yes   98%    6648  0.001298  5123
 3       yes   99%    5380  0.001286  4184
 4       yes   66%   14400  0.000377 38156
 5       yes   89%    4800  0.002689  1785
 6       yes   86%    4800  0.002700  1778
 7       yes   55%   12000  0.001030 11650
 8       yes   51%   24000  0.001012 23713
 9       yes   48%   14401  0.037905   380
10       yes   45%   14401  0.001295 11124
Total          75%  112372  0.051629  2177

Perf index = 45 (util) + 40 (thru) = 85/100

性能提高不少。

针对 coalesce trace 文件优化定制

迭代了这么几个版本，有没有注意到，第四个检测的空间利用率总是铁打不动的 66%, 这个 检测的 trace 文件是关于 coalesce 函数的。

分析 trace 文件

摘录一小段 trace：

1
2
3
4

a 0 4095
a 1 4095
f 0
f 1

这是一个陷阱，不是给人的，而是给程序的。

如果仔细看过 =mm_init 函数就会知道，在初始化堆最开始的一些标识位之后，会调用 extend_heap 函数来预分配一块 4096 字节大小的空间做为起始空闲块。

坏就坏在这里，trace 文件中每次分配占用的空间大小在经过8字节的对齐补全计算之后， 总是大于4096, 或大于4096的整数倍。

在 mm_malloc 函数当中在遇到当前空闲链表中没有合适空闲块的情况下，总是会调用 extend_heap 函数来扩展一块空闲块空间，而这块空间的大小取4096与待分配大小中大的 那一个。

这就导致了一个很尴尬的问题，如果像 coalesce trace 文件中的这样分配之后，初始的 4096空间大小是永远不够的，每次都要扩展，每次初始4096大小的空闲块都不能被利用起来。

这样就导致了 coalesce 测试空间利用率一直都不理想。

改动

改动很简单，修改 mm_init 函数中 extend_heap 初始扩展大小就可以了，空闲块可以 接受的最小大小是两个双字，就桉这个来：

1

bp = extend_heap(2*DSIZE/WSIZE);

性能

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   97%    5694  0.001187  4795
 1       yes   94%    5848  0.000901  6493
 2       yes   98%    6648  0.001301  5111
 3       yes   99%    5380  0.001549  3473
 4       yes   99%   14400  0.000391 36829
 5       yes   89%    4800  0.003036  1581
 6       yes   86%    4800  0.002891  1660
 7       yes   55%   12000  0.001089 11018
 8       yes   51%   24000  0.001046 22953
 9       yes   48%   14401  0.040135   359
10       yes   45%   14401  0.001318 10925
Total          78%  112372  0.054844  2049

Perf index = 47 (util) + 40 (thru) = 87/100

提高了2分。

可能的优化

传说还可以针对最后的两个 realloc trace 做定制优化，这两个测试，特别是第一个，性 能确实很差。

但就像准备中所说的，到了这一步，性能的提高和时间的投入就很不成比例了，暂时搁置， 还有其他更重要的事情要做。

  1. mm_realloc 中处理旧块数据向新块迁移的函数是 memcpy, 结果在分离适配这 个版本检查 trace 文件时无法通过第十个检测；问题是，如果还是这个函数，在 LIFO顺序显式空闲链表 版本做检查时确实可行的；这两个版本虽然有差异，但除了外围有无分离适 配空闲链表数组之外，内部结构大致相同，暂时排查不出原因；所以最后在分离适配的版本 中还是使用 memmove 函数。 [return]