순서 하나 바꿨을 뿐인데 20배 빨라졌습니다 - 참조 지역성(Locality of Reference)

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

개발 툴, 성능 최적화

대상자

자바 개발자, Redis 사용자, 성능 최적화에 관심 있는 개발자

핵심 요약

• 참조 지역성(Locality of Reference)은 CPU 캐시의 효율성에 직접적인 영향을 미침
• array[i][j]의 순회 순서가 행 우선(i의 반복이 먼저)일 때 성능이 20배 이상 개선됨
• Redis 설계에서도 데이터 접근 패턴을 고려하는 것이 메모리 배치 및 성능에 긍정적 영향을 미침

섹션별 세부 요약

1. 성능 저하의 원인: for문 순서

• array[i][j]의 열 우선(j의 반복이 먼저) 순회 방식은 캐시 미스가 빈번하게 발생
• 행 우선(i의 반복이 먼저) 방식은 캐시 히트 비율이 높아 성능이 20배 이상 향상
• JVM 설정이나 배열 크기보다 코드의 순서가 성능에 더 큰 영향을 미침

2. 참조 지역성(Locality of Reference) 원리

• 시간적 지역성: 최근에 사용된 데이터가 곧 다시 사용될 가능성이 높음
• 공간적 지역성: 현재 사용된 데이터 주변의 데이터도 사용될 가능성이 높음
• 순차적 지역성: 데이터가 순차적으로 접근될 경우 CPU는 프리페치(prefetch)를 통해 캐시에 미리 데이터를 로드

3. Redis 설계에서의 지역성 적용

• 단일 키로 알림을 저장하는 방식은 개별 접근 시 빠르지만 집합 조회 시 스캔 또는 패턴 조회 필요
• 유저별 키 구조(예: user:notification:{userId})로 묶고 리스트 또는 정렬 집합으로 저장 시
• 메모리 배치가 집중되어 캐시 히트율 증가
• 성능 저하 감소 및 latency 감소 효과

결론

• 성능 최적화는 데이터 접근 패턴을 고려해야 함
• Java에서는 for문 순서, Redis에서는 키 구조를 통해 참조 지역성 효과를 활용
• 캐시 효율성을 높이기 위해서는 데이터의 지역성과 접근 패턴을 반드시 고려해야 함