performance comparison with perf-stat

please check the below code. the code be implemented with two solutions. one is array, the other one is linking list.

i expected the array version should be faster than the linking list one, because the cache miss.

i used Perf program to check. but the result is not what i think. please check the below Perf output.

the cache miss of the linking list version is higher than the array version, indeed. however, the linking list version is more faster. i do not know why.

thanks!

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

#ifdef ARRAY
static int prime_size = 0;
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++) {
return false;
}

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

tmp = tmp->next;
}
#endif

return true;
}

static void stash(int p)
{
#ifdef ARRAY
struct prime *tmp = (struct prime *)calloc(1, sizeof(struct prime));
tmp->next = NULL;
tmp->value = p;

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