/* 재기 전에 *재는 도구*를 잰다.
   시계의 해상도, 시계를 읽는 값, 최적화가 코드를 지우는 것, 데우기, 그리고 평균의 함정. */
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

static double ns(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec * 1e9 + (double)ts.tv_nsec;
}

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

/* 최적화가 지워도 되는 계산: 결과를 아무도 안 쓴다 */
static void sum_discarded(const int *a, size_t n)
{
    long s = 0;
    for (size_t i = 0; i < n; i++) s += a[i];
    (void)s;
}
/* 최적화가 지울 수 없는 계산: 결과를 돌려주고, 부르는 쪽이 쓴다 */
static long sum_kept(const int *a, size_t n)
{
    long s = 0;
    for (size_t i = 0; i < n; i++) s += a[i];
    return s;
}
static volatile long sink;

/* ★ aarch64 리눅스는 CTR_EL0 레지스터를 사용자 프로그램에도 읽게 열어 둔다(glibc 도 이것으로
     줄 크기를 답한다). 안드로이드의 Bionic 은 sysconf 에 0 을 돌려주고, 폰 커널은 sysfs 의 크기
     칸을 비워 두기도 해서(안드로이드 폰 실측) 마지막으로 이 레지스터를 직접 읽는다.
     다만 계층 전체에서 *가장 작은* 줄 크기다. */
#if defined(__aarch64__) && defined(__linux__)
__asm__(".text\n.globl read_ctr_el0\n.type read_ctr_el0, %function\n"
        "read_ctr_el0:\n    mrs x0, ctr_el0\n    ret\n");
unsigned long read_ctr_el0(void);
#endif

/* ★ 캐시의 크기는 C 라이브러리가 CPU 에 물어서 채운다. x86-64 의 glibc 는 CPUID 로 답하지만,
     aarch64 의 glibc(2.44 소스로 확인)는 줄 크기만 CTR_EL0 로 답하고 크기·연관도에는 *0* 을
     돌려준다 --- 그 값을 담은 레지스터를 커널이 사용자 프로그램에 막아 두었기 때문이다.
     그래서 0 이면, 커널이 부팅 때 읽어 sysfs 에 적어 둔 값을 본다. 그것도 없으면 0 이고,
     찍는 쪽이 「모른다」고 말한다 --- 0 바이트짜리 캐시로 읽히게 두지 않는다. */
static long sysfs_cache(int level, const char *field)
{
    const char *dir = "/sys/devices/system/cpu/cpu0/cache";
    for (int i = 0; i < 16; i++) {
        char path[128], buf[32];
        snprintf(path, sizeof path, "%s/index%d/level", dir, i);
        FILE *f = fopen(path, "r");
        if (!f) break;
        int lv = fgets(buf, sizeof buf, f) ? atoi(buf) : 0;
        fclose(f);
        snprintf(path, sizeof path, "%s/index%d/type", dir, i);
        f = fopen(path, "r");
        bool code_only = f && fgets(buf, sizeof buf, f) && strncmp(buf, "Instruction", 11) == 0;
        if (f) fclose(f);
        if (lv != level || code_only) continue;        /* 명령 전용 캐시는 건너뛴다 */
        snprintf(path, sizeof path, "%s/index%d/%s", dir, i, field);
        f = fopen(path, "r");
        if (!f) return 0;
        long v = 0;
        if (fgets(buf, sizeof buf, f)) {
            char *end;
            v = strtol(buf, &end, 10);
            if (*end == 'K') v *= 1024;                /* "32K" 꼴로 적혀 있다 */
            else if (*end == 'M') v *= 1024 * 1024;
        }
        fclose(f);
        return v;
    }
    return 0;
}

static long cache_value(int name, int level, const char *field)
{
    long v = sysconf(name);
    return v > 0 ? v : sysfs_cache(level, field);
}

int main(void)
{
    printf("== 1. this machine's numbers (the example reads them itself) ==\n");
    const char *unknown = "unknown --- this system does not report it";
    long l1 = cache_value(_SC_LEVEL1_DCACHE_SIZE, 1, "size");
    long line = cache_value(_SC_LEVEL1_DCACHE_LINESIZE, 1, "coherency_line_size");
#if defined(__aarch64__) && defined(__linux__)
    if (line <= 0)
        line = 4L << ((read_ctr_el0() >> 16) & 0xf);
#endif
    long ways = cache_value(_SC_LEVEL1_DCACHE_ASSOC, 1, "ways_of_associativity");
    long l2 = cache_value(_SC_LEVEL2_CACHE_SIZE, 2, "size");
    long l3 = cache_value(_SC_LEVEL3_CACHE_SIZE, 3, "size");
    printf("  %-22s %s\n", "L1 data cache", "");
    if (l1 > 0)   printf("    size        : %ld bytes (%ld KiB)\n", l1, l1 / 1024);
    else          printf("    size        : %s\n", unknown);
    if (line > 0) printf("    line size   : %ld bytes\n", line);
    else          printf("    line size   : %s\n", unknown);
    if (ways > 0) printf("    associativity: %ld-way\n", ways);
    else          printf("    associativity: %s\n", unknown);
    if (l2 > 0)   printf("  L2 cache      : %ld KiB\n", l2 / 1024);
    else          printf("  L2 cache      : %s\n", unknown);
    if (l3 > 0)   printf("  L3 cache      : %ld KiB (%.0f MiB)\n", l3 / 1024, l3 / 1048576.0);
    else          printf("  L3 cache      : %s\n", unknown);
    printf("  page size     : %ld bytes\n", sysconf(_SC_PAGESIZE));
    printf("  logical cores : %ld\n\n", sysconf(_SC_NPROCESSORS_ONLN));

    printf("== 2. clock resolution --- how finely can it be seen ==\n");
    struct { const char *name; clockid_t id; } clocks[] = {
        { "CLOCK_MONOTONIC   (never goes backwards)", CLOCK_MONOTONIC },
        { "CLOCK_REALTIME    (wall clock --- it jumps when adjusted)", CLOCK_REALTIME },
        { "CLOCK_PROCESS_CPUTIME_ID (CPU time I used)", CLOCK_PROCESS_CPUTIME_ID },
    };
    for (unsigned i = 0; i < sizeof clocks / sizeof *clocks; i++) {
        struct timespec r;
        clock_getres(clocks[i].id, &r);
        printf("  %-42s resolution %ld ns\n", clocks[i].name,
               (long)(r.tv_sec * 1000000000L + r.tv_nsec));
    }
    printf("  * a resolution of 1 ns does not mean 1 ns can be measured.\n");
    printf("    Reading the clock costs more than that --- measured next.\n\n");

    printf("== 3. the cost of reading the clock ==\n");
    const long N = 200000;
    double t0 = ns();
    for (long i = 0; i < N; i++) { struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts); sink += ts.tv_nsec; }
    double t1 = ns();
    double call_ns = (t1 - t0) / (double)N;
    printf("  one clock_gettime : %.1f ns\n", call_ns);

    /* 실제로 볼 수 있는 가장 짧은 간격 --- 두 번 읽어 차이가 0 이 아닌 최솟값 */
    double min_gap = 1e18;
    for (long i = 0; i < 100000; i++) {
        double a = ns(), b = ns();
        if (b - a > 0 && b - a < min_gap) min_gap = b - a;
    }
    printf("  smallest interval actually distinguishable : %.1f ns\n", min_gap);
    printf("  * so anything shorter than this is never measured once. Repeat and divide.\n");
    printf("    Every measurement in this appendix is built that way.\n\n");

    printf("== 4. trap one: the optimiser removes what you meant to measure ==\n");
    const size_t NA = 1u << 20;                 /* 4 MiB 짜리 배열 */
    int *a = malloc(NA * sizeof *a);
    for (size_t i = 0; i < NA; i++) a[i] = (int)i;

    sum_discarded(a, NA); sink += sum_kept(a, NA);      /* 데우기 */

    t0 = ns(); for (int r = 0; r < 20; r++) sum_discarded(a, NA); t1 = ns();
    double disc = (t1 - t0) / 20.0;
    t0 = ns(); for (int r = 0; r < 20; r++) sink += sum_kept(a, NA); t1 = ns();
    double kept = (t1 - t0) / 20.0;

    printf("  a sum whose result is discarded : %10.0f ns  (%.2f ns per element)\n", disc, disc / NA);
    printf("  a sum whose result is used      : %10.0f ns  (%.2f ns per element)\n", kept, kept / NA);
    printf("  factor                          : %.1f x\n", kept / (disc > 0 ? disc : 1));
    printf("  * if the first is near zero, that code never ran. The compiler removed it as\n");
    printf("    a value nobody uses. When the result says your code is infinitely fast,\n");
    printf("    suspect this before suspecting the machine.\n\n");

    printf("== 5. trap two: the first round is slow (warming up) ==\n");
    int *b = malloc(NA * sizeof *b);
    memset(b, 0, NA * sizeof *b);       /* 쪽을 실제로 잡아 둔다 */
    free(b);
    b = malloc(NA * sizeof *b);         /* 새로 잡으면 쪽이 아직 없다 */
    /* ★ 여기서도 ④ 의 함정이 먼저 걸렸다: 채운 결과를 아무도 안 읽으면 memset 이
       통째로 사라져 「4 MiB 를 38 나노초에 채웠다」는 헛것이 나온다. 그래서 잰 *뒤에*
       한 바이트를 읽어 결과가 쓰였음을 알린다. */
    t0 = ns(); memset(b, 1, NA * sizeof *b); t1 = ns();
    double first = t1 - t0;  sink += ((unsigned char *)b)[NA / 2];
    t0 = ns(); memset(b, 2, NA * sizeof *b); t1 = ns();
    double second = t1 - t0; sink += ((unsigned char *)b)[NA / 2];
    printf("  filling the same 4 MiB --- first  : %8.0f ns\n", first);
    printf("                          second : %8.0f ns\n", second);
    printf("  factor: %.1f x\n", first / second);
    printf("  * the first round mixes in the cost of the OS attaching pages one by one (page faults).\n");
    printf("    So warm up before measuring, and discard the warm-up rounds.\n\n");

    printf("== 6. trap three: one interruption drags the mean ==\n");
    const int S = 201;
    double *samp = malloc((size_t)S * sizeof *samp);
    for (int i = 0; i < S; i++) {
        t0 = ns(); sink += sum_kept(a, NA >> 4); t1 = ns();
        samp[i] = t1 - t0;
    }
    double mean = 0; for (int i = 0; i < S; i++) mean += samp[i]; mean /= S;
    qsort(samp, (size_t)S, sizeof *samp, cmp_d);
    printf("  results over %d rounds\n", S);
    printf("  %-10s %12.0f ns\n", "minimum", samp[0]);
    printf("  %-10s %12.0f ns  <- what this appendix uses\n", "median", samp[S / 2]);
    printf("  %-10s %12.0f ns\n", "mean", mean);
    printf("  %-10s %12.0f ns\n", "99th percentile", samp[(int)(S * 0.99)]);
    printf("  %-10s %12.0f ns\n", "maximum", samp[S - 1]);
    printf("  mean / median = %.2f x  (the further from 1, the more other work interfered)\n",
           mean / samp[S / 2]);
    printf("  * this machine is shared. So the median is used rather than the mean, with the\n");
    printf("    minimum alongside to show what it would be with no interference.\n");

    free(samp); free(b); free(a);
    return 0;
}

/* 기억의 사다리를 잰다 --- 작업 집합을 키워 가며 「한 번 읽는 데 드는 시간」을 본다.
   비결은 *포인터 추적*이다: 다음에 읽을 자리가 지금 읽은 값에 들어 있으면, 기계가
   미리 가져올 수 없고 한 번에 하나씩만 진행된다. 그래서 처리량이 아니라 *지연*이 보인다. */
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <stdint.h>

static double ns(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec * 1e9 + (double)ts.tv_nsec;
}
static int cmp_d(const void *a, const void *b)
{ double x = *(const double *)a, y = *(const double *)b; return x < y ? -1 : x > y; }

static uint64_t rng_state = 0x123456789ABCDEFull;
static uint64_t rnd(void)
{ rng_state ^= rng_state << 13; rng_state ^= rng_state >> 7; rng_state ^= rng_state << 17; return rng_state; }

/* 사톨로 알고리즘: 배열 전체를 도는 *하나의 고리*를 만든다(작은 고리로 갈라지지 않는다) */
static void make_cycle(size_t *next, size_t n)
{
    for (size_t i = 0; i < n; i++) next[i] = i;
    for (size_t i = n - 1; i > 0; i--) {
        size_t j = (size_t)(rnd() % i);
        size_t t = next[i]; next[i] = next[j]; next[j] = t;
    }
    /* 순열을 고리로 바꾼다: next[a]=b 를 「a 다음은 b」로 읽게 이어 붙인다 */
    size_t *cyc = malloc(n * sizeof *cyc);
    for (size_t i = 0; i < n; i++) cyc[next[i]] = next[(i + 1) % n];
    memcpy(next, cyc, n * sizeof *cyc);
    free(cyc);
}

static volatile size_t sink;

/* 무작위 고리를 따라 steps 번 밟는다 --- 매 걸음이 앞 걸음의 결과에 의존한다 */
static double chase(size_t *next, size_t n, long steps)
{
    size_t p = 0;
    for (long i = 0; i < (long)n * 4 && i < 4000000L; i++) p = next[p];   /* 데우기 */
    double t0 = ns();
    for (long i = 0; i < steps; i++) p = next[p];
    double t1 = ns();
    sink = p;
    return (t1 - t0) / (double)steps;
}

/* 견주기용: 차례로 훑는다 --- 기계가 다음 자리를 미리 가져올 수 있다 */
static double sweep(size_t *buf, size_t n, long rounds)
{
    size_t acc = 0;
    for (size_t i = 0; i < n; i++) acc += buf[i];                    /* 데우기 */
    double t0 = ns();
    for (long r = 0; r < rounds; r++)
        for (size_t i = 0; i < n; i++) acc += buf[i];
    double t1 = ns();
    sink = acc;
    return (t1 - t0) / ((double)n * (double)rounds);
}

/* ★ 캐시의 크기는 C 라이브러리가 CPU 에 물어서 채운다. x86-64 의 glibc 는 CPUID 로 답하지만,
     aarch64 의 glibc(2.44 소스로 확인)는 줄 크기만 CTR_EL0 로 답하고 크기·연관도에는 *0* 을
     돌려준다 --- 그 값을 담은 레지스터를 커널이 사용자 프로그램에 막아 두었기 때문이다.
     그래서 0 이면, 커널이 부팅 때 읽어 sysfs 에 적어 둔 값을 본다. 그것도 없으면 0 이고,
     찍는 쪽이 「모른다」고 말한다 --- 0 바이트짜리 캐시로 읽히게 두지 않는다. */
static long sysfs_cache(int level, const char *field)
{
    const char *dir = "/sys/devices/system/cpu/cpu0/cache";
    for (int i = 0; i < 16; i++) {
        char path[128], buf[32];
        snprintf(path, sizeof path, "%s/index%d/level", dir, i);
        FILE *f = fopen(path, "r");
        if (!f) break;
        int lv = fgets(buf, sizeof buf, f) ? atoi(buf) : 0;
        fclose(f);
        snprintf(path, sizeof path, "%s/index%d/type", dir, i);
        f = fopen(path, "r");
        bool code_only = f && fgets(buf, sizeof buf, f) && strncmp(buf, "Instruction", 11) == 0;
        if (f) fclose(f);
        if (lv != level || code_only) continue;        /* 명령 전용 캐시는 건너뛴다 */
        snprintf(path, sizeof path, "%s/index%d/%s", dir, i, field);
        f = fopen(path, "r");
        if (!f) return 0;
        long v = 0;
        if (fgets(buf, sizeof buf, f)) {
            char *end;
            v = strtol(buf, &end, 10);
            if (*end == 'K') v *= 1024;                /* "32K" 꼴로 적혀 있다 */
            else if (*end == 'M') v *= 1024 * 1024;
        }
        fclose(f);
        return v;
    }
    return 0;
}

static long cache_value(int name, int level, const char *field)
{
    long v = sysconf(name);
    return v > 0 ? v : sysfs_cache(level, field);
}

int main(void)
{
    const long L1 = cache_value(_SC_LEVEL1_DCACHE_SIZE, 1, "size");
    const long L2 = cache_value(_SC_LEVEL2_CACHE_SIZE, 2, "size");
    const long L3 = cache_value(_SC_LEVEL3_CACHE_SIZE, 3, "size");
    const bool known = L1 > 0 || L2 > 0 || L3 > 0;

    printf("== the caches of this machine ==\n");
    if (known)
        printf("  L1 %ld KiB · L2 %ld KiB · L3 %ld KiB (%.0f MiB)\n\n",
               L1 / 1024, L2 / 1024, L3 / 1024, L3 / 1048576.0);
    else
        printf("  unknown --- this system does not report them, so the \"where\" column shows ?\n\n");

    printf("== time for one read, by working set size ==\n");
    printf("  it follows a random ring, so prefetching does not help --- pure latency.\n\n");
    printf("  %-12s %-10s %-14s %-10s %s\n",
           "working set", "where", "random access", "factor", "sequential");

    double base = 0;
    printf("#DATA-BEGIN\n");
    for (size_t kib = 4; kib <= 131072; kib *= 2) {
        size_t bytes = kib * 1024;
        size_t n = bytes / sizeof(size_t);
        size_t *buf = malloc(bytes);
        if (!buf) { printf("  (%zu KiB allocation failed)\n", kib); break; }

        make_cycle(buf, n);

        long steps = n < 1000000 ? 4000000L : 2000000L;
        double s[5];
        for (int r = 0; r < 5; r++) s[r] = chase(buf, n, steps);
        qsort(s, 5, sizeof *s, cmp_d);
        double lat = s[2];                       /* 중앙값 */

        /* 차례로 훑기: 같은 크기를 순서대로 --- 지연이 아니라 처리량이 보인다 */
        for (size_t i = 0; i < n; i++) buf[i] = i;
        long rounds = bytes < (1u << 22) ? 200 : 5;
        double seq = sweep(buf, n, rounds);

        /* 모르는 단은 건너뛴다 --- 크기 0 과 견주면 전부 「주기억」으로 읽힌다 */
        const char *where = !known                          ? "?"
                          : L1 > 0 && (long)bytes <= L1     ? "L1"
                          : L2 > 0 && (long)bytes <= L2     ? "L2"
                          : L3 > 0 && (long)bytes <= L3     ? "L3" : "main memory";
        if (base == 0) base = lat;

        char size_s[16];
        if (kib < 1024) snprintf(size_s, sizeof size_s, "%zu KiB", kib);
        else            snprintf(size_s, sizeof size_s, "%zu MiB", kib / 1024);

        printf("  %-12s %-10s %8.2f ns %7.1fx %8.2f ns\n",
               size_s, where, lat, lat / base, seq);
        printf("#DATA %zu %.3f %.3f %s\n", kib, lat, seq, where);
        free(buf);
    }
    printf("#DATA-END\n");

    printf("\n== how to read this ==\n");
    printf("  1. reading down the table shows steps. Wherever the working set passes\n");
    printf("     the size of a cache, the cost jumps.\n");
    printf("  2. the last column (sequential) barely changes. Reading in order lets the\n");
    printf("     machine prefetch the next line --- the latency is the same, but nothing waits.\n");
    printf("  3. so \"it is fast if it fits in cache\" is only half right. More precisely:\n");
    printf("     access it unpredictably and outside the cache is tens of times slower.\n");
    return 0;
}

/* 캐시 「줄」이 시간으로 드러나는가 --- 걸음 폭을 바꿔 가며 잰다.
   그리고 같은 자료를 배치만 바꿔(구조체 배열 vs 배열들) 재 본다. */
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

static double ns(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec * 1e9 + (double)ts.tv_nsec;
}
static int cmp_d(const void *a, const void *b)
{ double x = *(const double *)a, y = *(const double *)b; return x < y ? -1 : x > y; }

static volatile long sink;

/* ★ aarch64 리눅스는 CTR_EL0 레지스터를 사용자 프로그램에도 읽게 열어 둔다(glibc 도 이것으로
     줄 크기를 답한다). 안드로이드의 Bionic 은 sysconf 에 0 을 돌려주고, 폰 커널은 sysfs 의 크기
     칸을 비워 두기도 해서(안드로이드 폰 실측) 마지막으로 이 레지스터를 직접 읽는다.
     다만 계층 전체에서 *가장 작은* 줄 크기다. */
#if defined(__aarch64__) && defined(__linux__)
__asm__(".text\n.globl read_ctr_el0\n.type read_ctr_el0, %function\n"
        "read_ctr_el0:\n    mrs x0, ctr_el0\n    ret\n");
unsigned long read_ctr_el0(void);
#endif

static long cache_line(void)
{
    long v = sysconf(_SC_LEVEL1_DCACHE_LINESIZE);
    if (v > 0)
        return v;
    FILE *f = fopen("/sys/devices/system/cpu/cpu0/cache/index0/coherency_line_size", "r");
    if (f) {
        if (fscanf(f, "%ld", &v) != 1)
            v = 0;
        fclose(f);
        if (v > 0)
            return v;
    }
#if defined(__aarch64__) && defined(__linux__)
    return 4L << ((read_ctr_el0() >> 16) & 0xf);
#else
    return 0;                                  /* 모른다 --- 부르는 쪽이 밝힌다 */
#endif
}

int main(void)
{
    long line = cache_line();
    if (line <= 0) {                         /* 모르면 흔한 값을 쓰되, 가정이라고 밝힌다 */
        line = 64;
        printf("(this system does not report its cache line --- 64 bytes is assumed below)\n");
    }
    const size_t BUF = 64u << 20;            /* 64 MiB --- L3(16 MiB)보다 크게 */
    const long TOUCH = 2000000;              /* 걸음 폭이 달라도 *접근 횟수는 같게* */
    unsigned char *buf = malloc(BUF);
    memset(buf, 1, BUF);                     /* 쪽을 미리 붙여 둔다(데우기) */

    printf("== the cache line of this machine: %ld bytes ==\n\n", line);
    printf("== varying the stride --- the number of accesses fixed at %ld ==\n", TOUCH);
    printf("  %-10s %-14s %-10s %-16s %s\n",
           "stride", "each", "factor", "lines touched", "bytes fetched in vain");
    printf("#DATA-BEGIN\n");

    double base = 0;
    for (long stride = 1; stride <= 4096; stride *= 2) {
        size_t mask = BUF - 1;               /* BUF 가 2의 거듭제곱이라 & 로 감쌀 수 있다 */
        double s[5];
        for (int r = 0; r < 5; r++) {
            size_t p = 0;
            long acc = 0;
            double t0 = ns();
            for (long i = 0; i < TOUCH; i++) { acc += buf[p]; p = (p + (size_t)stride) & mask; }
            double t1 = ns();
            sink = acc;
            s[r] = (t1 - t0) / (double)TOUCH;
        }
        qsort(s, 5, sizeof *s, cmp_d);
        if (base == 0) base = s[2];
        double lines_per_touch = stride >= line ? 1.0 : (double)stride / (double)line;
        double wasted = stride >= line ? (double)line - 1 : 0;
        printf("  %-10ld %8.2f ns %7.1fx  %-16.3f %.0f bytes\n",
               stride, s[2], s[2] / base, lines_per_touch, wasted);
        printf("#DATA %ld %.3f\n", stride, s[2]);
    }
    printf("#DATA-END\n");

    printf("\n  * the cost rises until the stride reaches %ld bytes (the line size), and\n", line);
    printf("    then flattens. A stride narrower than a line uses one line several times,\n");
    printf("    while a wider one takes a new line each step and has little room to worsen.\n");
    printf("    (the rise again at very wide strides is pages and the TLB --- the next section.)\n");

    /* ── 배치를 바꾸면 --- 구조체 배열 vs 배열들 ────────────────── */
    printf("\n== the same data, laid out differently ==\n");
    const size_t N = 4u << 20;               /* 원소 400만 개 */

    struct particle { double x, y, z, vx, vy, vz; int id, flags; };  /* 실제 크기는 아래에서 찍는다 */
    struct particle *aos = malloc(N * sizeof *aos);
    double *xs = malloc(N * sizeof *xs);
    for (size_t i = 0; i < N; i++) {
        aos[i].x = xs[i] = (double)i * 0.5;
        aos[i].y = aos[i].z = aos[i].vx = aos[i].vy = aos[i].vz = 1.0;
        aos[i].id = (int)i; aos[i].flags = 0;
    }
    printf("  size of one struct : %zu bytes (line %ld bytes)\n", sizeof(struct particle), line);
    printf("  %zu elements --- %zu MiB in total\n\n", N, N * sizeof *aos / (1u << 20));

    double s1[5], s2[5];
    for (int r = 0; r < 5; r++) {
        double acc = 0, t0 = ns();
        for (size_t i = 0; i < N; i++) acc += aos[i].x;      /* 구조체 배열에서 x 만 */
        double t1 = ns(); sink = (long)acc; s1[r] = (t1 - t0) / (double)N;

        acc = 0; t0 = ns();
        for (size_t i = 0; i < N; i++) acc += xs[i];         /* x 만 모아 둔 배열에서 */
        t1 = ns(); sink = (long)acc; s2[r] = (t1 - t0) / (double)N;
    }
    qsort(s1, 5, sizeof *s1, cmp_d); qsort(s2, 5, sizeof *s2, cmp_d);

    printf("  %-34s %10s %10s %s\n", "layout", "per element", "factor", "bytes used per line");
    printf("  %-34s %7.3f ns %8.1fx  %ld / %ld\n",
           "array of structs (AoS) --- reading x only", s1[2], s1[2] / s2[2],
           (long)sizeof(double), (long)sizeof(struct particle));
    printf("  %-34s %7.3f ns %8.1fx  %ld / %ld\n",
           "structs of arrays (SoA) --- reading the x array only", s2[2], 1.0, line, line);

    printf("\n  * the same values were added the same number of times. Only the layout changed.\n");
    printf("    In the array of structs, %zu bytes are fetched to use 8 --- the rest merely\n",
           sizeof(struct particle));
    printf("    occupy cache and are thrown away. So when one field is swept often,\n");
    printf("    splitting into one array per field (SoA) wins.\n");
    printf("  * the reverse holds too. Code using several fields of one element together\n");
    printf("    prefers the array of structs --- there the whole fetched line is used. The access pattern decides.\n");

    free(aos); free(xs); free(buf);
    return 0;
}

/* 주소 번역에도 값이 있다 --- TLB 를 넘어서면 무슨 일이 벌어지나.
   쪽마다 한 바이트씩만 무작위로 밟아, 캐시가 아니라 *번역*이 병목이 되게 만든다. */
#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <sys/mman.h>

static double ns(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec * 1e9 + (double)ts.tv_nsec;
}
static int cmp_d(const void *a, const void *b)
{ double x = *(const double *)a, y = *(const double *)b; return x < y ? -1 : x > y; }

static uint64_t st = 0x2545F4914F6CDD1Dull;
static uint64_t rnd(void) { st ^= st << 13; st ^= st >> 7; st ^= st << 17; return st; }


/* 커널이 「큰 쪽」 권고를 실제로 받아들였는가 --- /proc/self/smaps 에서 이 구간을 찾아
   AnonHugePages 값을 읽는다. 권고는 부탁이지 명령이 아니므로 *확인해야 한다.* */
static long anon_huge_kib(const void *addr)
{
    FILE *f = fopen("/proc/self/smaps", "r");
    if (!f) return -1;
    char line[512];
    unsigned long lo = 0, hi = 0;
    int in_range = 0;
    long result = -1;
    while (fgets(line, sizeof line, f)) {
        unsigned long a, b;
        if (sscanf(line, "%lx-%lx", &a, &b) == 2 && strchr(line, ' ')) {
            lo = a; hi = b;
            in_range = ((uintptr_t)addr >= lo && (uintptr_t)addr < hi);
        } else if (in_range && strncmp(line, "AnonHugePages:", 14) == 0) {
            result = strtol(line + 14, NULL, 10);
            break;
        }
    }
    fclose(f);
    return result;
}

static volatile size_t sink;

/* 쪽 하나에 한 칸씩 --- 쪽 사이를 무작위 고리로 잇는다 */
static double walk(unsigned char *mem, size_t pages, size_t page, long steps)
{
    size_t *order = malloc(pages * sizeof *order);
    for (size_t i = 0; i < pages; i++) order[i] = i;
    for (size_t i = pages - 1; i > 0; i--) {
        size_t j = (size_t)(rnd() % i);
        size_t t = order[i]; order[i] = order[j]; order[j] = t;
    }
    /* 각 쪽의 첫 8바이트에 「다음 쪽의 오프셋」을 적어 고리를 만든다 */
    for (size_t i = 0; i < pages; i++) {
        size_t cur = order[i], nxt = order[(i + 1) % pages];
        *(size_t *)(mem + cur * page) = nxt * page;
    }
    free(order);

    size_t p = 0;
    for (size_t i = 0; i < pages; i++) p = *(size_t *)(mem + p);      /* 데우기 */
    double t0 = ns();
    for (long i = 0; i < steps; i++) p = *(size_t *)(mem + p);
    double t1 = ns();
    sink = p;
    return (t1 - t0) / (double)steps;
}

int main(void)
{
    const size_t page = (size_t)sysconf(_SC_PAGESIZE);
    printf("== the page size of this machine: %zu bytes ==\n\n", page);

    printf("== 1. how many pages before translation becomes the bottleneck ==\n");
    printf("  only 8 bytes are touched per page. Little data, but the page count grows.\n\n");
    printf("  %-10s %-12s %-12s %s\n", "pages", "data touched", "each", "factor");
    printf("#DATA-BEGIN\n");
    double base = 0;
    for (size_t pages = 16; pages <= 131072; pages *= 4) {
        size_t bytes = pages * page;
        unsigned char *mem = mmap(NULL, bytes, PROT_READ | PROT_WRITE,
                                  MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        if (mem == MAP_FAILED) { printf("  (%zu pages: allocation failed)\n", pages); break; }
        memset(mem, 0, bytes);                       /* 쪽을 미리 붙인다 */

        double s[5];
        for (int r = 0; r < 5; r++) s[r] = walk(mem, pages, page, 2000000);
        qsort(s, 5, sizeof *s, cmp_d);
        if (base == 0) base = s[2];

        char amount[24];
        if (bytes < (1u << 20)) snprintf(amount, sizeof amount, "%zu KiB", bytes / 1024);
        else                    snprintf(amount, sizeof amount, "%zu MiB", bytes / (1u << 20));
        printf("  %-10zu %-12s %8.2f ns %6.1fx\n", pages, amount, s[2], s[2] / base);
        printf("#DATA %zu %.3f\n", pages, s[2]);
        munmap(mem, bytes);
    }
    printf("#DATA-END\n");
    printf("\n  * the data is small (8 bytes per page), and yet more pages costs more.\n");
    printf("    The bottleneck is address translation, not the cache. When the table\n");
    printf("    holding translations (the TLB) runs out of room, the machine must walk\n    the page tables again.\n");

    printf("\n== 2. what happens with huge pages ==\n");
    const size_t big_pages = 65536;                 /* 4 KiB × 65536 = 256 MiB */
    const size_t bytes = big_pages * page;
    double normal = 0, huge = 0;
    for (int mode = 0; mode < 2; mode++) {
        unsigned char *mem = mmap(NULL, bytes + (2u << 20), PROT_READ | PROT_WRITE,
                                  MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
        if (mem == MAP_FAILED) break;
        unsigned char *aligned = (unsigned char *)(((uintptr_t)mem + (2u << 20) - 1) & ~(uintptr_t)((2u << 20) - 1));
#ifdef MADV_HUGEPAGE
        madvise(aligned, bytes, mode ? MADV_HUGEPAGE : MADV_NOHUGEPAGE);
#endif
        memset(aligned, 0, bytes);
        long ah = anon_huge_kib(aligned);
        double s[5];
        for (int r = 0; r < 5; r++) s[r] = walk(aligned, big_pages, page, 2000000);
        qsort(s, 5, sizeof *s, cmp_d);
        if (mode) huge = s[2]; else normal = s[2];
        printf("  %-28s backed by huge pages: %ld KiB (%.0f%%)\n",
               mode ? "huge pages advised" : "normal pages advised", ah,
               ah < 0 ? 0.0 : 100.0 * (double)ah * 1024.0 / (double)bytes);
        munmap(mem, bytes + (2u << 20));
    }
    printf("  the same 256 MiB is walked the same way.\n");
    printf("  %-28s %8.2f ns\n", "normal pages (4 KiB)", normal);
    printf("  %-28s %8.2f ns\n", "huge pages advised (MADV_HUGEPAGE)", huge);
    if (huge > 0 && normal > 0)
        printf("  difference: %.2f x %s\n", normal / huge,
               normal / huge > 1.15 ? "--- huge pages won" : "--- no great difference in this run");
    printf("  * one huge page replaces 512 pages of 4 KiB, so the translations needed to\n");
    printf("    sweep the same data fall to a 512th. But madvise is a request, not an order.\n");
    printf("    The \"backed by huge pages\" figure above says whether the request was taken ---\n");
    printf("    if both runs are backed alike, similar times are only to be expected.\n");
    /* 이 문장은 큰 쪽이 기본값인 기계에서만 참이다 --- 설정을 읽고 나서 말한다 */
    FILE *thp = fopen("/sys/kernel/mm/transparent_hugepage/enabled", "r");
    char mode_s[64] = "";
    if (thp) {
        if (!fgets(mode_s, sizeof mode_s, thp))
            mode_s[0] = '\0';
        fclose(thp);
    }
    if (strstr(mode_s, "[always]")) {
        printf("    (this machine uses huge pages by default, so even the \"normal pages\" run\n");
        printf("     may already have some mixed in.)\n");
    } else if (!thp) {
        printf("    (this kernel offers no transparent huge pages at all, so the request cannot be taken.)\n");
    }

    printf("\n== 3. the cost of touching a page for the first time ==\n");
    const size_t fp = 32768;                        /* 128 MiB */
    unsigned char *mem = mmap(NULL, fp * page, PROT_READ | PROT_WRITE,
                              MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    double t0 = ns();
    for (size_t i = 0; i < fp; i++) mem[i * page] = 1;      /* 쪽마다 첫 접촉 */
    double t1 = ns();
    double first = (t1 - t0) / (double)fp;
    t0 = ns();
    for (size_t i = 0; i < fp; i++) mem[i * page] = 2;      /* 이미 붙은 쪽 */
    t1 = ns();
    double later = (t1 - t0) / (double)fp;
    munmap(mem, fp * page);
    printf("  touching a page the first time : %8.1f ns\n", first);
    printf("  touching an already-mapped page: %8.1f ns\n", later);
    printf("  factor: %.0f x\n", first / later);
    printf("  * the address `malloc` returned is not memory yet. At each first touch the\n");
    printf("    operating system attaches one page --- and that is its cost. Allocate a large\n");
    printf("    buffer and measure at once and this cost is mixed in entire (hence warming up).\n");
    return 0;
}