캐시, 지역성, 코딩

지역성

프로그램이 메모리에 접근할 때, 가까운 메모리 주소들이 접근될 가능성이 높는 점을 활용,

캐시 메모리 효율 향상, 그에따른 성능 향상

• 시간적 지역성 (Temporal Locality): 최근 접근한 데이터를 다시 접근할 가능성이 높음
• 공간적 지역성 (Spatial Locality): 인접한 데이터가 함께 접근될 가능성이 높음

콤퓨우타는 이걸로 예측해서 캐시를 채워두는데, 지역성에 반하는 접근이 발생하면 캐시 미스가 낫다구 함

캐시 종류	위치	크기	속도	용도
L1 캐시	코어 내부	매우 작음	갓갓굿	가장 자주 접근하는 데이터 저장
L2 캐시	코어 내부	중간	굿굿	L1 미스 시 대체
L3 캐시	코어간 공유	큼	긋…?	코어 간 데이터 공유, L2 미스 시 사용
RAM (메인 메모리)	CPU 외부	GB단위	느려	프로그램 상차🚚

CPU는 L1 → L2 → L3 → RAM 검색

L3는 코어전체가 공유… 그래서 상품설명에 L3만 적어두는구만? 🤧

L3가 384MB??… 192 코어와 공유해야함. = 2MB

그럼 어터케 하면 미스가 남?

• 공간 지역성 예시

# Python 3.12.9
import time
size = 1000
arr = [[i * j for j in range(size)] for i in range(size)]

# Column-wise, vertical traversal
start = time.time()
for j in range(size):
    for i in range(size):
        _ = arr[i][j]
end = time.time()
print(f"Column-wise exection time: {end - start:.4f}sec")

# Row-wise, horizontal traversal
start = time.time()
for i in range(size):
    for j in range(size):
        _ = arr[i][j]
end = time.time()
print(f"Row-wise execution time: {end - start:.4f}sec")

• 시간 지역성 예시

# Bad
cache = {}
start = time.time()
for i in range(10_000_000):
    cache[i] = i * 2  # no second use
end = time.time()
print(f"Barbaric locality: {end - start:.4f}sec")

# Gut
cache = {}
start = time.time()
for _ in range(100):
    for i in range(100_000):  # 동일한 범위를 반복 접근
        if i not in cache:
            cache[i] = i * 2
end = time.time()
print(f"Yes locality: {end - start:.4f}sec")

두 줄로 풀어서 쓰니까 더 빠를지는 몰랏다 … 😥

그런데 넘파이로 실험을 해봄

• 사이즈 2x2부터 1000x1000인 2차원 배열 (가로세로가 같아야 행기반 열기반 비교가능하니까)
• 파이써닉한 루프로 돌림

• import matplotlib.pyplot as plt
  import numpy as np
  
  # How could python not have a native truncate?
  def truncate(f, n):
      return int(f * 10**n) / 10**n
  
  ordinary_list = [[], [], []]
  x_axis = np.arange(2, 1001)
  
  # Traverse
  for size in x_axis:
      arr = np.random.rand(size, size)
  
      # Row-wise
      start = time.time()
      for i in range(size):
          for j in range(size):
              _ = arr[i, j]
      ordinary_list[0].append(truncate(time.time() - start, 4))
  
      # Col-wise
      start = time.time()
      for j in range(size):
          for i in range(size):
              _ = arr[i, j]
      ordinary_list[1].append(truncate(time.time() - start, 4))
  
      # Diff
      ordinary_list[2].append(ordinary_list[1][-1]-ordinary_list[0][-1])
  
  # To numpy array and extract columns
  namba_py_list = np.array(ordinary_list)
  del ordinary_list
  row_wise, col_wise, diff = namba_py_list[0], namba_py_list[1], namba_py_list[2]
  
  # CHART
  fig, ax1 = plt.subplots(figsize=(14, 6))
  width = 0.6
  ax1.bar(x_axis - width/2, row_wise, width=width, label='Row-wise exc time', color='green')
  ax1.bar(x_axis + width/2, col_wise, width=width, label='Col-wise exc time', color='salmon')
  
  ax1.set_xlabel("Size of the matrix")
  ax1.set_ylabel("Execution time")
  
  ax2 = ax1.twinx()
  ax2.plot(x_axis, diff, label='Time difference', color='black', linewidth=1.5)
  ax2.set_ylabel("Time difference")
  
  ax1.legend()
  ax2.legend()
  
  plt.title("Locality experiment with py")
  plt.tight_layout()
  plt.show()

• 음수가 많이 나오는대? … 그럼 col-wise가 더 빠름?! 🥴

파이써닉 조은거 맞음? 왜이랴?

• 매 연산마다 인터프리터가 동작하고 타입 체크 등 추가 작업을 한다
• 넘파이가 C기반이긴 하지만 transpose같은 객체 생성자는 메모리를 스트라이드하게 사용하기도 함 (여기서는 안사용했지만...) 껑츙 🐇
• 파이써닉하게는 CPU 벤치마크를 하기 힘들다!

• 💡그래서 등장: np.ascontiguousarray()
• 🔍 np.ascontiguousarray()는 배열을 메모리에 연속되도록 강제 → 캐시미스 줄임
• 💡 또등장: numba.njit
• 🔍 Numba는 파이썬 코드를 자동으로 컴파일해줌. 어셈블리 레벨로 변환해줌
• → 파이썬 인터프리터가 원시인처럼 보임 🐒
• 결과적으로 Python이 아닌 C처럼 동작해서 캐시 성능 실험을 정확히 측정할 수 있게 하는 것이 목표

두번째 시도

!pip install numba

import numpy as np
import time
from numba import njit

# Aside from the decorators, nothing has changed.
@njit
def row_traverse(arr):
    total = 0.0
    for i in range(arr.shape[0]):
        for j in range(arr.shape[1]):
            total += arr[i, j]
    return total

@njit
def col_traverse(arr):
    total = 0.0
    for j in range(arr.shape[1]):
        for i in range(arr.shape[0]):
            total += arr[i, j]
    return total

# Apparently, njin needs a "Warm-up"
_ = row_traverse(np.ones((2,2)))
_ = col_traverse(np.ones((2,2)))

x_axis = np.arange(2, 1001)
row_wise = []
col_wise = []
diff = []

for size in x_axis:
    # Converting it to use contiguos addresses
    arr = np.ascontiguousarray(np.random.rand(size, size))

    start = time.time()
    row_traverse(arr)
    row_wise.append(truncate(time.time() - start, 4))

    start = time.time()
    col_traverse(arr)
    col_wise.append(truncate(time.time() - start, 4))

    diff.append(truncate(col_wise[-1] - row_wise[-1], 4))

fig, ax1 = plt.subplots(figsize=(14, 6))
width = 0.6
ax1.bar(x_axis - width/2, row_wise, width=width, label='Row-wise exc time', color='green')
ax1.bar(x_axis + width/2, col_wise, width=width, label='Col-wise exc time', color='salmon')

ax1.set_xlabel("Size of the matrix")
ax1.set_ylabel("Execution time")

ax2 = ax1.twinx()
ax2.plot(x_axis, diff, label='Time difference', color='black', linewidth=1.5)
ax2.set_ylabel("Time difference")

ax1.legend()
ax2.legend()

plt.title("Locality experiment with py")
plt.tight_layout()
plt.show()

이번엔 한군데 뺴곤 음수 업다

• 그런데 왜 계단형으로 나오는가?
• 캐시 계층 구조 (L1, L2, L3) 의 한계점 도달
• 즉, 크기가 캐시 경계(L1/L2/L3) 를 넘을 때마다 단계별 성능 저하가 발생
• 그래프에서 계단처럼 보임

• 작은 루프에선 CPU가 루프를 미리 전개(unroll) 하거나 predictive execution을 통해 거의 일정한 속도로 처리가능
• 하지만 크기가 커지면 이 최적화가 잘 안 되고 실제 접근 비용이 명확하게 증가하면서 계단현상 발생

• 실험 개선 방법
  • time.time()은 초 단위로 측정하며 정밀도가 낮다 (ms ~ 15ms 단위)
  • time.perf_counter() 로 정밀 측정
  • arr.nbytes로 정확히 몇 바이트의 배열인지 표시하고, 캐시 경계 추정
  • 캐시 경계 기반으로 그래프에 수직선 표시
  • diff가 거의 0이라는 점... 더 큰 size를 사용해야 차이가 나타날지?
  • 넘파이 인덱싱을 [i, j]가 아닌 [i][j]로 하면 성능차이가 있을지 체크
  • 스레딩과 락을 사용하면 ... 로우가 뒤죽박죽되려나?

그 외의 예시

• 판다스에서의 필터링 방법에 따라 캐시 미스가 생길 수 있다
• 선택성이 높은 조건을 먼저 배치 ㅇㅇ

# Col1의 조건이 대부분 True라고 치고
# Col2가 'babo'인 경우가 희귀하다고 가정

# Bad locality
df[(df['col1'] > 1000) & (df['col2'] == 'babo')]

# Good locality: selectivity-first principle
# foo만 딱 걸러내고 나서 시작해새요
df[(df['col2'] == 'foo') & (df['col1'] > 1000)]

끗

• 좋은 로컬리티: 캐시 히트율을 높여 CPU가 기다리지 않게함 어터케 CPU를 기다리게할수이써
• 코드에서 루프 순서, 조건 순서, 데이터 배열 방법 등이 성능과 직결!
• 하드웨어를 이해하면 코드도 더 잘 최적화할 수 잇엇다니 … 😱