与 perf-stat 的性能比较

Question

请检查下面的代码。该代码可以通过两种解决方案来实现。一种是数组，另一种是链表。

我预计数组版本应该比链接列表版本更快，因为缓存未命中。

我用Perf程序来检查。但结果不是我想的那样。请检查下面的 Perf 输出。

确实，链接列表版本的缓存未命中高于数组版本。然而，链接列表版本更快。我不知道为什么。

请帮助解释两个 Perf 输出，并说明原因。

谢谢！

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#ifdef ARRAY
static int *head = NULL;
static int prime_size = 0;
#elif LINKING_LIST
struct prime {
        int value;
        struct prime *next;
};

static struct prime *head = NULL;
static struct prime *tail = NULL;
#endif

static bool is_prime(int n)
{
        int i = 0;
        int half = n / 2;

        if (n <= 1)
                return false;

#ifdef ARRAY
        for (i = 0; i < prime_size && head[i] <= half; i++) {
                if (!(n % head[i]))
                        return false;
        }
#elif LINKING_LIST
        struct prime *tmp = head;

        while (tmp && tmp->value <= half) {
                if (!(n % tmp->value))
                        return false;

                tmp = tmp->next;
        }
#endif

        return true;
}

static void stash(int p)
{
#ifdef ARRAY
        head = (int *)realloc(head, ++prime_size * sizeof(int));
        head[prime_size - 1] = p;
#elif LINKING_LIST
        struct prime *tmp = (struct prime *)calloc(1, sizeof(struct prime));
        tmp->next = NULL;
        tmp->value = p;

        if (!head)
                head = tail = tmp;
        else {
                tail->next = tmp;
                tail = tmp;
        }
#endif
}

int countPrimes(int n)
{
        int retval = 0;
        int i = 0;

        for (i = 0; i < n; i++) {
                if (is_prime(i)) {
                        stash(i);
                        retval += 1;
                }
        }

        return retval;
}

int main(void)
{
        int input = 499979;
        printf("%d ->  %d\n", input, countPrimes(input));

        return 0;
}

Answer 1

首先，应避免滥用专有名词。上面的程序包含一个链表，它是包含两个字段的节点序列：整数值和到下一个节点的链接。这就是为什么它被称为“链接”列表而不是“链接”列表的原因。重新分配在您的程序中被大量调用，这会产生不利影响。如果您想公平地与数组和链表进行比较，则应该消除迭代中意外的内存分配。也就是说，内存（取消）分配应该发生在程序的开始和结束时。