HashMap 의 최적화 기법 - 스택 vs 힙

해시맵의 코드를 보면 특이한 부분을 볼 수 있습니다.

if ((tab = table) == null || (n = tab.length) == 0)

tab = table을 이용해 해시맵 내부 테이블 변수에 값을 할당하는 것을 볼 수 있습니다.

왜 굳이 인스턴스 변수 table을 사용하지 않고 tab이라는 변수에 담아준걸까요?
이는 지역변수(tab)는 스택에, 인스턴스 변수(table)는 Heap에 저장하기 때문입니다.

왜 스택이 힙보다 빠를까요?

설명하기 전에 먼저 표현을 정정해야 합니다.
우리가 흔히 "스택이 힙보다 빠르다"고 하는 건, 사실 스택 할당된 변수에 접근하는 것이 힙 할당 변수에 접근하는 것보다 빠르다는 것입니다.

스택 메모리 영역이 힙 메모리 영역보다 그 자체로 빠르다는 것은 아닙니다. 스택이나 힙이나 가상메모리 영역에 불과하고, 하드웨어로 내려가면 똑같이 RAM의 어딘가에 저장된 페이지에 불과하니까 둘의 속도가 다를 이유는 없습니다.

그런데 접근하는 속도는 왜 차이가 날까요?

스택 할당 변수의 장점

주소 계산의 단순함

• 컴파일러는 컴파일 시점에 스택에 할당될 변수들의 크기와 순서를 정확히 알 수 있어요
  이를 통해 스택 기준 상대 위치(offset)를 정확하게 결정할 수 있습니다.
  실행 중에는 스택 레지스터에 항상 현재 스택 바닥 주소가 저장되어 있어요
  따라서 변수 주소 = 스택 포인터 + offset으로 간단히 계산이 가능 합니다. (예: addr ← SP + 36)

메모리 지역성 이점

• 스택의 변수들은 보통 메모리에 연속적으로 할당되어 있어서 -> 공간 지역성
  단일 페이지 테이블이나 캐시 라인 내에 함께 존재할 가능성이 높음
  이로 인해 캐시 효율성과 메모리 접근 속도가 향상됨

힙 할당 변수의 단점

주소 계산의 복잡성

• 힙은 OS가 관리하므로 컴파일 시점에 변수가 어떤 위치에 할당될지 알 수 없어요
  OS에서 할당받은 주소를 스택 변수에 저장한 다음
  실제 힙 데이터에 접근하려면:
  add 후 load로 포인터(주소값)를 먼저 얻고
  그 주소를 다시 load해야 합니다.

메모리 지역성 부족

힙의 변수들은 OS가 임의로 할당하기 때문에 메모리상 흩어져 있을 가능성이 높음
같은 페이지나 캐시 라인에 있을 확률이 낮아 캐시 미스가 더 자주 발생
이는 물리적 접근 속도 저하로 이어짐

세 줄 요약

쉽게 말해 스택 변수가 힙 변수보다 접근이 빠른 이유는 스택은 컴파일 시점에 참조에 필요한 값을 가지고 있어 주소 계산이 단순하고(포인터 역참조 없음) 메모리 지역성이 좋아 캐시 효율성이 높기 때문입니다.
그래서 해시맵에서 인스턴스 변수에 참조하기보단, 지역변수를 선언해 일종의 캐싱을 해두어 tab 변수를 사용하게 됩니다 :)