/* bench2 - pointer chase (random vs page-local) and branch mispredicts,
 * median of many short windows; cycles relative to a dependent add */
#include <stdio.h>
#include <stdlib.h>

#define UNROLL 128
#define MHZ 249.4
extern long k_add(long, long, long);
extern long k_chase(long, long), k_br(long, long);
extern unsigned long long k_tb(void);


/* cycles per op relative to a dependent add (cancels stolen time) */
static unsigned long rng = 12345;
static unsigned long rnd(void) { rng = rng * 1103515245UL + 12345UL; return rng >> 8; }

static void
shuffle(long *a, long n)
{
    long i, j, t;
    for (i = n - 1; i > 0; i--) { j = rnd() % (i + 1); t = a[i]; a[i] = a[j]; a[j] = t; }
}

/* ring visiting pages in random order, all lines of a page (random order) before the next */
static long
pagering(char *buf, long size)
{
    long npages = size / 4096, lpp = 128, i, j, k, *pages, *lines, *order, t;

    pages = malloc(npages * sizeof *pages);
    lines = malloc(lpp * sizeof *lines);
    order = malloc(npages * lpp * sizeof *order);
    for (i = 0; i < npages; i++) pages[i] = i;
    shuffle(pages, npages);
    for (k = 0, i = 0; i < npages; i++) {
        for (j = 0; j < lpp; j++) lines[j] = j;
        shuffle(lines, lpp);
        for (j = 0; j < lpp; j++) order[k++] = pages[i] * 4096 + lines[j] * 32;
    }
    for (i = 0; i < k; i++)
        *(char **)(buf + order[i]) = buf + order[(i + 1) % k];
    t = (long)(buf + order[0]);
    free(pages); free(lines); free(order);
    return t;
}

static long
ring(char *buf, long nlines)
{
    long *order, i, t;

    order = malloc(nlines * sizeof *order);
    for (i = 0; i < nlines; i++) order[i] = i;
    shuffle(order, nlines);
    for (i = 0; i < nlines; i++)
        *(char **)(buf + order[i] * 32) = buf + order[(i + 1) % nlines] * 32;
    t = (long)(buf + order[0] * 32);
    free(order);
    return t;
}

static int
cmpd(const void *a, const void *b)
{
    double x = *(const double *)a, y = *(const double *)b;
    return x < y ? -1 : x > y;
}

static double
median(double *v, int n)
{
    qsort(v, n, sizeof *v, cmpd);
    return v[n / 2];
}

#define W 301
int
main(void)
{
    static double v[W];
    double ref;
    long n, size, p, i, j, *arr;
    char *buf;
    unsigned long long t0;

    for (j = 0; j < W; j++) { t0 = k_tb(); k_add(40, 1, 1); v[j] = (double)(k_tb() - t0) / (40 * 128.0); }
    ref = median(v, W);
    printf("dependent add (median of %d windows): %.5f ticks -> core/TB %.3f\n\n", W, ref, 1 / ref);

    printf("pointer chase, median of %d windows (continuing through the ring):\n", W);
    printf("     size   random order       page-local order\n");
    buf = malloc(16 * 1024 * 1024 + 4096);
    buf = (char *)(((unsigned long)buf + 4095) & ~4095UL);
    for (size = 8192; size <= 16 * 1024 * 1024; size *= 2) {
        double r1, r2;
        n = size <= 1024 * 1024 ? 16 : 4;            /* windows of 2048 / 512 loads */
        p = ring(buf, size / 32);
        for (j = 0; j < size / 32 / 128 + 1; j++) p = k_chase(1, p);   /* warm: one lap */
        for (j = 0; j < W; j++) { t0 = k_tb(); p = k_chase(n, p); v[j] = (double)(k_tb() - t0) / (n * 128.0); }
        r1 = median(v, W) / ref;
        p = pagering(buf, size);
        for (j = 0; j < size / 32 / 128 + 1; j++) p = k_chase(1, p);
        for (j = 0; j < W; j++) { t0 = k_tb(); p = k_chase(n, p); v[j] = (double)(k_tb() - t0) / (n * 128.0); }
        r2 = median(v, W) / ref;
        printf("  %6ld KB  %6.2f cyc %5.0f ns   %6.2f cyc %5.0f ns\n", size / 1024,
               r1, r1 * 1000 / MHZ, r2, r2 * 1000 / MHZ);
    }

    printf("\nbranches (16 KB array of 0/1 words, 128 static beq):\n");
    arr = malloc(4096 * sizeof *arr);
    for (i = 0; i < 4096; i++) arr[i] = 0;
    for (j = 0; j < W; j++) { t0 = k_tb(); k_br(32, (long)arr); v[j] = (double)(k_tb() - t0) / 4096.0; }
    {
        double pred = median(v, W) / ref, rnd50, alt;
        for (i = 0; i < 4096; i++) arr[i] = rnd() & 1;
        for (j = 0; j < W; j++) { t0 = k_tb(); k_br(32, (long)arr); v[j] = (double)(k_tb() - t0) / 4096.0; }
        rnd50 = median(v, W) / ref;
        for (i = 0; i < 4096; i++) arr[i] = 1;
        for (j = 0; j < W; j++) { t0 = k_tb(); k_br(32, (long)arr); v[j] = (double)(k_tb() - t0) / 4096.0; }
        alt = median(v, W) / ref;
        printf("  always taken      %5.2f cycles/step\n", pred);
        printf("  never taken       %5.2f cycles/step\n", alt);
        printf("  random 50/50      %5.2f cycles/step\n", rnd50);
        printf("  -> penalty ~ %.2f cycles per mispredict (assuming 50%% mispredicted)\n",
               2 * (rnd50 - (pred + alt) / 2));
    }
    return 0;
}