캐시 메모리 — L1부터 L3까지, 지역성 원리가 성능에 미치는 영향

L1 (<1ns) → L2 (5ns) → L3 (16ns) → RAM (80ns)
    ×5          ×3           ×5
          점진적               급격한 점프!

// 루프 변수 sum은 매 반복마다 접근 → 시간적 지역성
int sum = 0;
for (int i = 0; i < 1000; i++) {
    sum += arr[i];  // sum은 L1 캐시에 계속 머무름
}

// 배열 순차 접근 → 공간적 지역성 극대화
int[] arr = new int[1000];
for (int i = 0; i < 1000; i++) {
    arr[i] = i;  // 연속 메모리 접근
}

int 배열에서 arr[0]을 읽으면:
  → 캐시 라인 64바이트가 통째로 로드
  → int는 4바이트이므로 arr[0]~arr[15]까지 16개가 함께 캐시에 올라옴
  → arr[1]~arr[15]는 이미 캐시에 있으므로 히트!

메모리 레이아웃:
[1][2][3][4][5][6][7][8][9][10][11][12][13][14][15][16]
|____________캐시 라인 1____________||__캐시 라인 2__|...

→ 첫 접근 1번 미스 + 이후 15번 히트 = 히트율 93.75%

메모리 레이아웃 (힙에 흩어짐):
[Node1] → ... [Node2] → ... [Node3] → ...
  0x100       0x5F00       0x2A00

→ 노드가 서로 다른 캐시 라인에 위치 → 매 접근마다 캐시 미스 가능
→ 히트율이 극도로 낮음

배열 순회:    ~0.5ms  (L1/L2 캐시 히트 극대화)
연결 리스트:  ~5-15ms (캐시 미스 → RAM 접근 반복)

// 두 스레드가 각자 다른 카운터를 증가시킴
class SharedCounters {
    volatile long counter1;  // 스레드 A가 사용
    volatile long counter2;  // 스레드 B가 사용
}

// Java에서 @Contended 어노테이션 또는 수동 패딩
class PaddedCounters {
    volatile long counter1;
    long p1, p2, p3, p4, p5, p6, p7;  // 56바이트 패딩 → 다른 캐시 라인으로 밀어냄
    volatile long counter2;
}

// Java 8+에서는 @sun.misc.Contended 사용 가능
// JVM 옵션: -XX:-RestrictContended

// 구조체 배열: 한 객체의 모든 필드가 연속
class Particle {
    float x, y, z;    // 위치
    float vx, vy, vz; // 속도
    float mass;        // 질량
}
Particle[] particles = new Particle[10000];

// x 좌표만 순회할 때:
// [x,y,z,vx,vy,vz,mass][x,y,z,vx,vy,vz,mass]...
// 캐시 라인에 불필요한 y,z,vx,vy,vz,mass도 함께 로드

// 배열의 구조체: 같은 필드끼리 연속
class Particles {
    float[] x  = new float[10000];
    float[] y  = new float[10000];
    float[] z  = new float[10000];
    float[] vx = new float[10000];
    float[] vy = new float[10000];
    float[] vz = new float[10000];
    float[] mass = new float[10000];
}

// x 좌표만 순회할 때:
// [x0, x1, x2, x3, x4, x5, x6, x7, x8, ...]
// 캐시 라인에 x 값만 빽빽하게 → 히트율 극대화

// 좋음: 행 우선 순회 (Row-major, 메모리 연속)
int[][] matrix = new int[1000][1000];
for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 1000; j++) {
        matrix[i][j] = 0;  // 연속 메모리 접근
    }
}

// 나쁨: 열 우선 순회 (캐시 미스 폭증)
for (int j = 0; j < 1000; j++) {
    for (int i = 0; i < 1000; i++) {
        matrix[i][j] = 0;  // 매번 다른 행으로 점프
    }
}

// 캐시 친화적: ArrayList (내부 배열, 연속 메모리)
List<Integer> list = new ArrayList<>();

// 캐시 비친화적: LinkedList (노드가 힙에 흩어짐)
List<Integer> list = new LinkedList<>();

// 순회 성능: ArrayList가 LinkedList보다 수 배~수십 배 빠름