perf-stat과의 성능 비교

아래 코드를 확인해주세요. 이 코드는 두 가지 솔루션으로 구현될 수 있습니다. 하나는 배열이고 다른 하나는 연결리스트입니다.

캐시 누락으로 인해 배열 버전이 연결 목록 버전보다 더 빠를 것으로 예상됩니다.

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;
}