/* 같은 입자를 세 가지로 늘어놓고, 각각에 두 가지 일을 시킨다.
   ★ 이 예제는 시간을 잰다. 그래서 나오는 수는 기계마다, 회차마다 다르다.
     절대 시간은 찍지 않고 배수만 낸다 --- 남길 것은 결론뿐이다. */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* 입자 약 백만 개: AoS 로 64 MiB --- 캐시보다 훨씬 크다 */
#define N      (1u << 20)
#define ROUNDS 5
#define PICKS  (1u << 18)

/* (1) AoS: 입자마다 구조체 하나, 모든 것을 함께 --- 64바이트, 캐시 라인 하나 */
struct particle {
    float x, y, z, vx, vy, vz;
    float mass, charge;
    uint32_t flags, owner;
    char name[24];
};
static_assert(sizeof(struct particle) == 64);

/* (2) 뜨거운·찬 쪼개기: 갱신 반복문이 쓰는 것과 쓰지 않는 것을 가른다 */
struct hot  { float x, y, z, vx, vy, vz; };          /* 24바이트 */
struct cold { float mass, charge; uint32_t flags, owner; char name[24]; };

/* (3) SoA: 필드마다 배열 하나 */
struct particles { float *x, *y, *z, *vx, *vy, *vz, *mass; };

static struct particle *aos;
static struct hot *hot;
static struct cold *cold;
static struct particles soa;
static uint32_t *pick;
static volatile float sink;

static double now(void) { return (double)clock() / CLOCKS_PER_SEC; }

/* 일 A: 모든 입자를 움직인다 --- 멤버 11개 가운데 6개(위치 · 속도)를 쓴다 */
static double move_aos(void)
{
    double t = now();
    for (uint32_t i = 0; i < N; i++)
        { aos[i].x += aos[i].vx; aos[i].y += aos[i].vy; aos[i].z += aos[i].vz; }
    return now() - t;
}
static double move_hot(void)
{
    double t = now();
    for (uint32_t i = 0; i < N; i++)
        { hot[i].x += hot[i].vx; hot[i].y += hot[i].vy; hot[i].z += hot[i].vz; }
    return now() - t;
}
static double move_soa(void)
{
    double t = now();
    for (uint32_t i = 0; i < N; i++) soa.x[i] += soa.vx[i];
    for (uint32_t i = 0; i < N; i++) soa.y[i] += soa.vy[i];
    for (uint32_t i = 0; i < N; i++) soa.z[i] += soa.vz[i];
    return now() - t;
}

/* 일 B: 흩어진 입자들의 필드 일곱 개(위치 · 속도 · 질량)를 한꺼번에 읽는다 */
static double look_aos(void)
{
    double t = now(); float acc = 0;
    for (uint32_t k = 0; k < PICKS; k++) { const struct particle *p = &aos[pick[k]];
        acc += p->x + p->y + p->z + p->vx + p->vy + p->vz + p->mass; }
    sink = acc; return now() - t;
}
static double look_soa(void)
{
    double t = now(); float acc = 0;
    for (uint32_t k = 0; k < PICKS; k++) { uint32_t i = pick[k];
        acc += soa.x[i] + soa.y[i] + soa.z[i] + soa.vx[i] + soa.vy[i] + soa.vz[i]
             + soa.mass[i]; }
    sink = acc; return now() - t;
}

static int cmp(const void *a, const void *b)
{ double x = *(const double *)a, y = *(const double *)b; return (x > y) - (x < y); }
static double median(double (*job)(void))
{
    double r[ROUNDS];
    job();                                        /* 데우기 --- 버린다 */
    for (int i = 0; i < ROUNDS; i++) r[i] = job();
    qsort(r, ROUNDS, sizeof *r, cmp);
    return r[ROUNDS / 2];
}

int main(void)
{
    aos = calloc(N, sizeof *aos);
    hot = calloc(N, sizeof *hot); cold = calloc(N, sizeof *cold);
    float **f[] = { &soa.x, &soa.y, &soa.z, &soa.vx, &soa.vy, &soa.vz, &soa.mass };
    for (size_t k = 0; k < sizeof f / sizeof f[0]; k++) *f[k] = calloc(N, sizeof(float));
    pick = malloc(PICKS * sizeof *pick);
    if (!aos || !hot || !cold || !pick || !soa.x || !soa.y || !soa.z
        || !soa.vx || !soa.vy || !soa.vz || !soa.mass)
    { puts("out of memory"); return 1; }

    uint64_t rng = 0x9E3779B97F4A7C15u;
    for (uint32_t k = 0; k < PICKS; k++) {
        rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17;
        pick[k] = (uint32_t)(rng >> 32) % N;
    }
    for (uint32_t i = 0; i < N; i++) {
        float v = (float)(i % 7) * 0.25f;
        aos[i].vx = aos[i].vy = aos[i].vz = v;
        hot[i].vx = hot[i].vy = hot[i].vz = v;
        soa.vx[i] = soa.vy[i] = soa.vz[i] = v;
    }

    double a = median(move_aos), h = median(move_hot), s = median(move_soa);
    double la = median(look_aos), ls = median(look_soa);

    printf("%u particles; a struct is %zu bytes, a hot part %zu bytes\n\n",
           N, sizeof *aos, sizeof *hot);
    puts("job A: move every particle (6 of the 11 members)");
    if (s > 0 && h > 0) {
        printf("  AoS took            %.1f times as long as SoA\n", a / s);
        printf("  hot/cold split took %.1f times as long as SoA\n", h / s);
    } else puts("  the clock is too coarse on this machine to tell them apart");
    puts("job B: read seven fields of particles picked at random");
    if (la > 0) printf("  SoA took            %.1f times as long as AoS\n", ls / la);
    else puts("  the clock is too coarse on this machine to tell them apart");
    puts("\n(ratios only: they change with the machine, the compiler and the run.)");

    free(aos); free(hot); free(cold); free(pick);
    for (size_t k = 0; k < sizeof f / sizeof f[0]; k++) free(*f[k]);
    return 0;
}

/* 같은 백만 개의 수를 세 가지로 더한다: 배열, 노드가 마침 차례대로 놓인 연결 목록,
   그리고 힙을 「한동안 쓴 뒤」의 같은 목록(노드를 섞인 순서로 이음).
   ★ 이 예제는 시간을 잰다. 배수만 인쇄한다. */
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N      (1u << 20)
#define ROUNDS 5

struct node { struct node *next; uint32_t value; };     /* 목록 */
static uint32_t *arr;                                    /* 배열 */
static struct node *pool, *in_order, *shuffled;
static volatile uint64_t sink;

static double now(void) { return (double)clock() / CLOCKS_PER_SEC; }
static double sum_array(void)
{
    double t = now(); uint64_t s = 0;
    for (uint32_t i = 0; i < N; i++) s += arr[i];
    sink = s; return now() - t;
}
static double walk(const struct node *p)
{
    double t = now(); uint64_t s = 0;
    for (; p; p = p->next) s += p->value;
    sink = s; return now() - t;
}
static double walk_in_order(void) { return walk(in_order); }
static double walk_shuffled(void) { return walk(shuffled); }

static int cmp(const void *a, const void *b)
{ double x = *(const double *)a, y = *(const double *)b; return (x > y) - (x < y); }
static double median(double (*job)(void))
{
    double r[ROUNDS];
    job();
    for (int i = 0; i < ROUNDS; i++) r[i] = job();
    qsort(r, ROUNDS, sizeof *r, cmp);
    return r[ROUNDS / 2];
}

static struct node *make_list(uint32_t *order)
{
    for (uint32_t k = 0; k + 1 < N; k++) pool[order[k]].next = &pool[order[k + 1]];
    pool[order[N - 1]].next = nullptr;
    return &pool[order[0]];
}

int main(void)
{
    arr = malloc(N * sizeof *arr);
    pool = malloc(N * sizeof *pool);
    uint32_t *order = malloc(N * sizeof *order);
    if (!arr || !pool || !order) { puts("out of memory"); return 1; }
    for (uint32_t i = 0; i < N; i++) { arr[i] = i; pool[i].value = i; order[i] = i; }

    in_order = make_list(order);
    double a = median(sum_array), l = median(walk_in_order);

    /* 노드가 아니라 연결을 섞는다 */
    uint64_t rng = 0x2545F4914F6CDD1Du;
    for (uint32_t i = N - 1; i > 0; i--) {
        rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17;
        uint32_t j = (uint32_t)(rng >> 32) % (i + 1), t = order[i];
        order[i] = order[j]; order[j] = t;
    }
    shuffled = make_list(order);
    double s = median(walk_shuffled);

    printf("%u numbers; a node is %zu bytes, a number %zu\n\n",
           N, sizeof *pool, sizeof *arr);
    if (a > 0) {
        printf("list, nodes in memory order : %5.1f times as long as the array\n", l / a);
        printf("list, nodes scattered       : %5.1f times as long as the array\n", s / a);
    } else puts("the clock is too coarse on this machine to tell them apart");
    puts("\n(same nodes, same values; only where the next one lives has changed.)");
    free(arr); free(pool); free(order);
    return 0;
}

/* 열린 주소법 해시 표는 캐시에 유리하다: 배열 하나에서 이웃 칸을 차례로 본다.
   그 대신 해시만큼만 좋다. 부딪히도록 고른 열쇠를 넣으면 넣을 때마다 덩어리 전체를
   훑는다. 아래의 수는 시간이 아니라 탐색 횟수다 --- 실행마다 같다. */
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define SLOTS (1u << 16)
#define KEYS  4000u

static uint64_t table[SLOTS];
static bool used[SLOTS];

/* 누구나 짐작할 수 있는 해시: 열쇠의 아래 비트 */
static uint32_t hash_plain(uint64_t k, uint64_t seed) { (void)seed; return (uint32_t)k; }

/* 열쇠를 넣은 섞기: 바깥은 `seed` 를 모른다. (보여 주기용이다 --- 네트워크를 마주한
   실제 표는 이 목적으로 설계된 해시를 쓴다. 흔히 SipHash 다.) */
static uint32_t hash_keyed(uint64_t k, uint64_t seed)
{
    k ^= seed;
    k ^= k >> 33; k *= 0xFF51AFD7ED558CCDu;
    k ^= k >> 33; k *= 0xC4CEB9FE1A85EC53u;
    k ^= k >> 33;
    return (uint32_t)k;
}

static unsigned long insert_all(const uint64_t *keys,
                                uint32_t (*h)(uint64_t, uint64_t), uint64_t seed)
{
    memset(used, 0, sizeof used);
    unsigned long probes = 0;
    for (uint32_t i = 0; i < KEYS; i++) {
        uint32_t s = h(keys[i], seed) & (SLOTS - 1);
        while (used[s]) { probes++; s = (s + 1) & (SLOTS - 1); }   /* 선형 탐사 */
        used[s] = true; table[s] = keys[i];
        probes++;
    }
    return probes;
}

int main(void)
{
    static uint64_t ordinary[KEYS], crafted[KEYS];
    uint64_t rng = 0x853C49E6748FEA9Bu;
    for (uint32_t i = 0; i < KEYS; i++) {
        rng ^= rng << 13; rng ^= rng >> 7; rng ^= rng << 17;
        ordinary[i] = rng;
        crafted[i]  = (uint64_t)i << 16;          /* 모두 아래 16비트가 같다 */
    }
    /* 실제 프로그램에서는 프로세스마다 무작위로 */
    uint64_t seed = 0x5DEECE66Du;

    printf("%u keys into %u slots, linear probing\n\n", KEYS, SLOTS);
    printf("plain hash, ordinary keys : %8lu probes\n",
           insert_all(ordinary, hash_plain, seed));
    printf("plain hash, crafted keys  : %8lu probes\n",
           insert_all(crafted, hash_plain, seed));
    printf("keyed hash, crafted keys  : %8lu probes\n",
           insert_all(crafted, hash_keyed, seed));
    puts("\n(n keys that all collide cost about n*n/2 probes:");
    puts(" the work grows with the square.)");
    return 0;
}