Growable Arrays and Linked Lists: The Cost of Growth

/* Chapter 8 companion: how far apart two 16-byte blocks land on glibc.
 * malloc_usable_size is a glibc extension, so build with -std=gnu17. */
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    char *a = malloc(16), *b = malloc(16);
    if (a == NULL || b == NULL) return 1;
    printf("usable %zu bytes, blocks %td bytes apart\n",
           malloc_usable_size(a), b - a);
    free(a);
    free(b);
    return 0;
}

/* Chapter 8 companion: push n readings with realloc-based growth,
 * +1 (policy "plus1") or doubling ("double"); report the time and how
 * many times realloc returned a different address (a move).
 * Usage: ./realloc_moves plus1|double n */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

struct reading { uint32_t sensor_id; int64_t time_s; double value; uint8_t flags; };

static double seconds(void) {
    struct timespec t;
    timespec_get(&t, TIME_UTC);
    return (double)t.tv_sec + (double)t.tv_nsec / 1e9;
}

int main(int argc, char *argv[]) {
    if (argc != 3) { fprintf(stderr, "usage: %s plus1|double n\n", argv[0]); return 2; }
    int doubling = strcmp(argv[1], "double") == 0;
    size_t n = strtoul(argv[2], NULL, 10);
    struct reading *data = NULL;
    size_t size = 0, cap = 0, moves = 0;
    double start = seconds();
    for (size_t i = 0; i < n; i++) {
        if (size == cap) {
            size_t new_cap = doubling ? (cap ? 2 * cap : 1) : cap + 1;
            struct reading *tmp = realloc(data, new_cap * sizeof *tmp);
            if (tmp == NULL) { free(data); return 1; }
            if (tmp != data) moves++;
            data = tmp;
            cap = new_cap;
        }
        data[size++] = (struct reading){1001, (int64_t)i * 60, 20.0, 1};
    }
    printf("%s n=%zu time=%.4f s moves=%zu\n", argv[1], n, seconds() - start, moves);
    free(data);
    return 0;
}

/* Chapter 8 companion: sum 1,000,000 values from an array, from a list
 * whose nodes are linked in allocation order, and from the same nodes
 * linked in shuffled order. Best of five runs each. Build with -O2. */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct node { double value; struct node *next; };

static double seconds(void) {
    struct timespec t;
    timespec_get(&t, TIME_UTC);
    return (double)t.tv_sec + (double)t.tv_nsec / 1e9;
}

int main(void) {
    const size_t n = 1000000;
    double *a = malloc(n * sizeof *a);
    struct node **nodes = malloc(n * sizeof *nodes);
    size_t *order = malloc(n * sizeof *order);
    if (a == NULL || nodes == NULL || order == NULL) return 1;
    for (size_t i = 0; i < n; i++) {
        a[i] = (double)i;
        nodes[i] = malloc(sizeof **nodes);
        if (nodes[i] == NULL) return 1;
        nodes[i]->value = (double)i;
        order[i] = i;
    }
    for (int shuffled = 0; shuffled <= 1; shuffled++) {
        if (shuffled) {
            srand(1);
            for (size_t i = n - 1; i > 0; i--) {
                size_t j = ((size_t)rand() * ((size_t)RAND_MAX + 1) + (size_t)rand()) % (i + 1);
                size_t t = order[i]; order[i] = order[j]; order[j] = t;
            }
        }
        for (size_t i = 0; i < n; i++)
            nodes[order[i]]->next = (i + 1 < n) ? nodes[order[i + 1]] : NULL;
        struct node *head = nodes[order[0]];
        double best_a = 1e9, best_l = 1e9, check = 0;
        for (int r = 0; r < 5; r++) {
            double t0 = seconds(), s = 0;
            for (size_t i = 0; i < n; i++) s += a[i];
            double t1 = seconds();
            for (struct node *p = head; p != NULL; p = p->next) s += p->value;
            double t2 = seconds();
            check += s;
            if (t1 - t0 < best_a) best_a = t1 - t0;
            if (t2 - t1 < best_l) best_l = t2 - t1;
        }
        printf("%s: array %.1f ms, list %.1f ms (checksum %g)\n",
               shuffled ? "shuffled" : "in order", best_a * 1e3, best_l * 1e3, check);
    }
    for (size_t i = 0; i < n; i++) free(nodes[i]);
    free(nodes); free(order); free(a);
    return 0;
}