0

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.

please help interpreting the both Perf output, and illustrating why.

thanks!

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

enter image description here

enter image description here

1 Answer 1

0

First, you should avoid the misuse of proper nouns. The above program contains a linked list, which is a sequence of nodes that contain two fields: an integer value and a link to the next node. That is the reason why it is called a "linked" list rather than a "linking" list. realloc was heavily called in your program, which has a detrimental effect. If you would like to fairly compare with an array and a linked list, you should eliminate unintended memory allocations in the iterations. That is, memory (de-)allocations should happen at the very beginning and the end of a program.

5
  • thanks for correcting misuse nouns! you are right. i do not consider this part. let me check, thanks! Sep 16, 2022 at 2:46
  • Hi @jserv, i modified the code, like v0.0.2. the linked list version is faster than array version still. after that, i do another test. i removed traversing array/linked list part, like v0.0.3. the linked list version is slower than array version, it is expectation, because calloc was called heavily, as you mention before. Sep 17, 2022 at 3:32
  • base on test v0.0.2 and v0.0.3, does it mean the cost of traversing array is higher than linked list one? it sounds a little strange. Sep 17, 2022 at 3:33
  • The experiments need to be improved: memory allocations should appear before you are about to traverse, otherwise you can only figure out the impact due to frequent library calls.
    – jserv
    Oct 2, 2022 at 17:07
  • yes, you are right. for my purpose, i should measure time of traversing part only. i will use perf-probe to measure the part code again. thanks! Oct 26, 2022 at 1:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .