Write Up 1

DEBUG=0时

image.png

DEBUG=1时

image.png

比较：可以发现debug模式下refs几乎大了一倍，而misses几乎没有变化，因此在关闭debug后，miss rate增加。

优点：指令条数是一个可量化的指标，一般来说指令条数越少性能越好。并且是一种静态分析，不需要允许程序就可以比较不同版本程序的性能。

缺点：每条指令的执行时间可能不同，同时指令条数不能反映出程序中的内存访问模式和指令间的数据依赖性，可能指令条数少但是指令见相互依赖强的程序性能会更差。

Write Up 2

我选择的inline函数为merge_i、copy_i以及util中的mem_alloc、mem_free。sort_i由于其递归的特性，无法进行inline展开，故没有选择。

未使用内联：

由于默认-O3优化会尽量内联，所以需要用__attribute__((noinline))定义，让函数不内联。

如：

static __attribute__((noinline)) void merge_i(data_t* A, int p, int q, int r);
static __attribute__((noinline)) void copy_i(data_t* source, data_t* dest, int n);

image.png

image.png

使用内联：

image.png

image.png

可以发现在使用内联之后，refs减少了大概8,000,000条，同时在随机数组和倒序数组（应该是最差情况）进行排序的时间都有所提升。

Write Up 3

可能带来的性能劣势：如果在一个文件中多次调用内联函数，多次展开，那整个程序的体积就会变大，在一定程度上，会造成 CPU 的取址效率降低，程序执行效率降低。同时如果在inline扩展之前，程序频繁执行的部分适合内存层次结构的一个级别(例如，L1缓存)，但是在扩展之后它不再适合，导致该级别的缓存频繁丢失，导致程序效率降低。

分析器可以帮助我们分析加减inline后的指令条数的数量以及各个缓存的命中率等因素，我们通过这些指标可以对结果进行衡量。

Write Up 4

指针可能提高性能的原因：使用数组每次访问时都需要使用 下标*元素大小 + 数组首地址 进行查找，而使用指针，每次只需要+4，减少很多乘法用的时间。

修改代码：

static inline void merge_p(data_t *A, int p, int q, int r) {
    assert(A);
    assert(p <= q);
    assert((q + 1) <= r);
    int n1 = q - p + 1;
    int n2 = r - q;

    data_t *left = 0, *right = 0;
    mem_alloc(&left, n1 + 1);
    mem_alloc(&right, n2 + 1);
    if (left == NULL || right == NULL) {
        mem_free(&left);
        mem_free(&right);
        return;
    }

    copy_p(&(*(A + p)), left, n1);
    copy_p(&(*(A + q + 1)), right, n2);
    left[n1] = UINT_MAX;
    right[n2] = UINT_MAX;

    data_t *l = left, *ri = right;
    for (int k = p; k <= r; k++) {
        if (*left <= *right) {
            *(A + k) = *left;
            left++;
        } else {
            *(A + k) = *right;
            right++;
        }
    }
    mem_free(&l);
    mem_free(&ri);
}

static inline void copy_p(data_t *source, data_t *dest, int n) {
    assert(dest);
    assert(source);

    for (int i = 0; i < n; i++) {
        *(dest++) = *(source++);
    }
}

image.png

image.png

可以发现使用指针后，refs减少了6,000,000，但运行速度却慢了一点。

Write Up 5

排序算法采用的isort.c里的插入排序isort。通过从2开始以每次两倍进行尝试，发现16的速度是最快的，并且在大于16后，速度开始下降。

image.png

image.png

Write Up 6

修改代码：

static inline void merge_m(data_t *A, int p, int q, int r) {
    assert(A);
    assert(p <= q);
    assert((q + 1) <= r);
    int n1 = q - p + 1;
    int n2 = r - q;

    data_t *left = 0;
    mem_alloc(&left, n1 + 1);
    if (left == NULL) {
        mem_free(&left);
        return;
    }

    copy_m(&(*(A + p)), left, n1);
    left[n1] = UINT_MAX;

    data_t *l = A + p, *right = A + q + 1, *left_pre = left;

    while (n1 > 0 && n2 > 0) {
        int cmp = (*left <= (*right));
        int min = *right ^ ((*left ^ *right) & -cmp);
        *(l++) = min;
        left+=cmp;
        right+=!cmp;
        n1-=cmp;
        n2-=!cmp;
    }

    while (n1 > 0)
    {
        *(l++) = *(left++);
        n1--;
    }

    mem_free(&left_pre);
}

image.png

优化前使用了堆中的58,032字节空间，优化后使用了25,176字节，减少到了一半。

编译器不能自己进行我们这部分优化，因为它需要对代码进行深入的理解和分析才能确定哪些部分可以被优化。此外，即使编译器能够自动进行这种优化，也不能保证实现的结果完全相同。

Write Up 7

修改代码：

void sort_f_wrap(data_t *A, int p, int r, data_t *left) {
    assert(A);
    if (r - p < C) {
        isort(A + p, A + r);
        return;
    }
    if (p < r) {
        int q = (p + r) / 2;
        sort_f_wrap(A, p, q, left);
        sort_f_wrap(A, q + 1, r, left);
        merge_f(A, p, q, r, left);
    }
}

void sort_f(data_t *A, int p, int r) {
    static data_t *left = NULL;
    mem_alloc(&left, (r - p + 2) / 2);
    if (left == NULL) {
        mem_free(&left);
        return;
    }
    sort_f_wrap(A, p, r, left);
    mem_free(&left);
}

// A merge routine. Merges the sub-arrays A [p..q] and A [q + 1..r].
// Uses two arrays 'left' and 'right' in the merge operation.
static inline void merge_f(data_t *A, int p, int q, int r, data_t *left) {
    assert(A);
    assert(p <= q);
    assert((q + 1) <= r);
    int n1 = q - p + 1;
    int n2 = r - q;

    copy_f(&(*(A + p)), left, n1);
    left[n1] = UINT_MAX;

    data_t *l = A + p, *right = A + q + 1, *left_pre = left;

    while (n1 > 0 && n2 > 0) {
        int cmp = (*left <= (*right));
        int min = *right ^ ((*left ^ *right) & -cmp);
        *(l++) = min;
        left += cmp;
        right += !cmp;
        n1 -= cmp;
        n2 -= !cmp;
    }

    while (n1 > 0) {
        *(l++) = *(left++);
        n1--;
    }
}

image.png

优化前使用了25,176字节，优化后使用了13,032字节。