perf-statとの性能比較

perf-statとの性能比較

下記のコードをご確認ください。このコードは2つのソリューションで実装できます。 1つは配列で、もう1つは接続リストです。

キャッシュの欠落により、アレイのバージョンが接続リストのバージョンよりも高速であると予想されます。

Perfプログラムを使って確認しました。しかし、結果は私が期待したものとは異なりました。以下のPerf出力を確認してください。

実際にリンクされたリストバージョンは、アレイバージョンよりもキャッシュミスが高い。ただし、接続リストのバージョンが高速です。理由はわかりません。

2つの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;
}

ここに画像の説明を入力してください。

ここに画像の説明を入力してください。

答え1

まず、固有名詞の誤用を避けるべきです。上記のプログラムでは接続リストは、整数値と次のノードへのリンクという2つのフィールドを含む一連のノードです。これが「接続された」リストではなく、「接続された」リストと呼ばれる理由です。再割り当てするプログラムから多く呼び出され、悪影響を及ぼす可能性があります。配列と接続のリストと公平に比較​​するには、繰り返しから予期しないメモリ割り当てを削除する必要があります。つまり、メモリ割り当てはプログラムの開始と終了で行う必要があります。

関連情報