How to get full points on malloc lab

Preface

malloc lab 是 ICS 中具有挑战性的一个实验,笔者当时在 malloc lab 中取得了唯一的满分,下文简要阐述一些 malloc lab 的思路。

Rank

Preparation

  • read through CS:APP Chapter 9 carefully and finish exercises

    • understand some concepts:
      • implementation
        • implicit free list
        • explicit free list
        • segregated free list
      • fit strategy
        • first fit
        • next fit
        • best fit
      • throughput
      • memory utilization
        • payload
  • read through malloclab-writeup.pdf

  • read two files in malloclab-handout

    • mm-naive.c
    • mm-textbook.c

Goal

malloc lab 的目标是实现类似 GNU libc 的 malloc, free, realloc, calloc函数,即实现一个动态内存分配器,以理解堆的内存分配机制。

Evaluation

  • Throughput (39%)
    • we would like to maximize an allocator’s throughput, which is defined as the number of requests that it completes per unit time.
  • memory utilization (61%)
    • The peak ratio between the aggregate amount of memory used by the driver (i.e., allocated via malloc but not yet freed via free) and the size of the heap used by your allocator.

得分的评估包括两个方面

  • 吞吐量 (39%)
  • 空间利用率 (61%)

Analysis

在malloc lab中,free操作会产生空闲的块,我们需要一个数据结构,支持这些块的插入,删除操作。并且在较少的时间内最大限度地利用空间。

如何维护这些空闲的块?

Binary Search Tree

为了提高空间利用率,我们考虑采用best fit策略,并使用平衡树维护。平衡树相比线段树,trie,附带的空间复杂度较低,并且能在$O(logn)$时间下完成插入,删除操作,具有十分不错的性质。

我们将平衡树的每个节点的结构体存入到空闲列表中。以 treap 为例,以如下这种方法,我们至少需要20 bytes的空闲链表来存储一个节点。

1
2
3
4
struct node {
node *left, *right, *next;
int size, random_value;
}
  • left, right
    • 节点的左右子节点
  • next
    • 指向一个链表,用来维护所有和该节点相同size的空闲块
  • size
    • 空闲块的大小
  • random_value
    • 节点分配到的随机值

Linkedlist

为了提高吞吐量,我们考虑用数组维护较小空闲块的链表头。

每次产生空闲块时,若

  • 空闲块的$size <= LIMIT$,我们直接在这个数组中查找这些链表头
    • 必定能找到相应的链表头,我们直接往这个节点的链表中插入这个空闲块
  • 空闲块的$size > LIMIT$,我们在平衡树中查找相应的链表头
    • 如果平衡树中存在相应$size$的节点,就往这个节点的链表中插入这个空闲块
    • 如果平衡树中不存在相应$size$的节点,就往平衡树中插入这样的一个节点

Fragment Pool

注意到trace 中的 exhaust.rep,boat.rep 等数据中,有大量小块的malloc, free操作,产生了大量无用的碎片。尤其是 8 bytes 的空闲块,一旦产生这样的碎片,除非coalesce,否则很难被再利用。

针对这一点,我们可以在heap的最前面开一个这样的池,管理这些碎片。

Some Tricks

Trick 1

writeup中提到:堆的大小不会超过 $2^{32}$ 字节。

尽管 x86-64 机器下指针的空间是 8 bytes,但我们完全可以只记录4字节的偏移量完成寻址。

Trick 2

一个 thou 的瓶颈是系统调用。感谢当初sy菊苣提醒:)

pku 服务器的主频非常低,提交到服务器上时系统调用简直慢到怀疑人生。

  • 一个优化:每次申请空间时,直接sbrk一大块,以减少系统调用次数。
    • 这是个空间与时间的 trade-off
      • 单次sbrk过少,Throughput 下降
      • 单次sbrk过多,Space Utilization 大打折扣