번역도 공짜가 아니다

가상 주소는 페이지 테이블을 거쳐 물리 주소가 됩니다. 표에 프레임 번호가 적혀 있으면 그대로 진행합니다. 번역이 빗나갔을 때 무슨 일이 생기는지는 페이지 폴트는 오류가 아니지만 프레임은 흔든다에 적었습니다.

이 글은 빗나가지 않았을 때의 이야기입니다. 그냥 지나간다고 했지만 그게 공짜라는 뜻은 아닙니다.

페이지 테이블도 메모리에 있습니다. 표를 보려면 메모리를 읽어야 합니다. 그대로 두면 값 하나를 읽으려고 메모리를 두 번 읽는 셈이 됩니다.

표를 한 장으로 만들 수 없다

문제는 두 번으로 끝나지 않는다는 것입니다. 표가 한 장이 아니기 때문입니다.

x86-64 는 가상 주소의 아래 48비트를 씁니다. 페이지가 4KB 니까 줄이 몇 개나 필요한지 세어 보면 이렇습니다.

주소 48비트 중 아래 12비트가 오프셋
남은 36비트가 페이지 번호

2^36 = 약 687억 줄
한 줄에 8바이트면 → 약 512GB

표를 담을 자리가 램보다 큽니다. 게다가 이 표가 프로세스마다 하나씩 필요합니다. 한 장짜리 표는 애초에 만들 수 없습니다.

그래서 표를 나눕니다

페이지 번호 36비트를 9비트씩 네 토막으로 자릅니다. 그리고 단계마다 표를 하나씩 둡니다.

9비트면 한 표에 512줄이고, 한 줄이 8바이트니까 표 하나가 정확히 4KB 입니다. 페이지 하나에 딱 들어갑니다.

이렇게 나누면 안 쓰는 영역의 표를 아예 안 만들어도 됩니다. 주소 공간의 대부분은 비어 있는데, 비어 있는 가지는 중간 단계에서 끊어 두면 그만입니다. 실제로 쓰는 만큼만 표가 생깁니다.

대신 값을 치릅니다. 번역 한 번에 표를 네 번 읽습니다. 값 하나를 읽으려고 메모리를 다섯 번 만지는 꼴입니다. 이걸 그대로 두면 모든 프로그램이 다섯 배 느려집니다.

TLB 가 그 값을 없앤다

그래서 CPU 안에 번역 결과를 담아 두는 작은 캐시가 따로 있습니다. TLB 입니다.

• 한 번 번역한 페이지 번호와 프레임 번호의 짝을 담아 둡니다
• 다음에 같은 페이지 안의 주소를 만지면 표를 안 보고 끝납니다
• 크기는 대체로 1단계가 수십 개, 2단계가 수천 개 규모입니다

히트하면 번역은 사실상 공짜입니다. 명령 처리 과정에 묻혀서 시간이 따로 안 보입니다. 미스하면 위의 네 단계를 실제로 걸어야 합니다. 그 표들이 캐시에 남아 있으면 수십 사이클, 메모리까지 가야 하면 수백 사이클입니다.

여기서 중요한 숫자가 하나 나옵니다. TLB 가 덮는 범위입니다.

2000개 × 4KB = 약 8MB

지금 만지고 있는 데이터가 8MB 안에 모여 있으면 번역은 거의 공짜입니다. 그보다 넓게 흩어져 있으면 만질 때마다 표를 걸어 내려가야 합니다.

적중률 99% 와 95% 는 말로는 비슷해 보입니다. 그런데 미스 횟수는 다섯 배 차이입니다. 번역 비용은 적중률이 아니라 미스 횟수에 붙습니다.

큰 페이지가 왜 있나

TLB 를 키우는 것은 한계가 있습니다. 빨라야 하니까 작아야 합니다. 그래서 반대쪽을 건드립니다. 덮는 범위를 넓히는 것입니다.

페이지를 2MB 로 잡으면 TLB 한 줄이 2MB 를 덮습니다. 같은 TLB 로 512배를 덮는 셈입니다.

공짜는 아닙니다. 2MB 를 통째로 잡으니 조금만 쓰면 나머지가 낭비되고, 커널은 이어진 2MB 자리를 찾아야 합니다. 메모리가 조각나 있으면 그것부터 정리해야 합니다.

게임 클라이언트에서 이걸 우리가 직접 켜고 끄는 일은 거의 없습니다. OS 와 런타임이 알아서 씁니다. 다만 큰 배열 하나가 작은 객체 수천 개보다 유리한 이유가 여기에도 있다는 것은 알아 둘 값이 있습니다.

게임에서 보이는 자리

연속된 배열이 빠른 이유가 하나 더 있습니다. 흔히 캐시 때문이라고 말하는데, 같은 페이지 안을 계속 만지면 번역도 한 번만 하면 됩니다. 4KB 안에 값이 천 개 들어 있으면 그 천 개를 훑는 동안 TLB 는 한 줄만 씁니다.

반대쪽이 나쁜 이유도 같습니다.

• 포인터로 흩어진 객체를 따라다니면 한 번 만지고 다른 페이지로 건너뜁니다. 매번 새 번역입니다
• 대용량 자료구조를 통째로 훑는 작업은 TLB 가 덮는 범위를 금방 넘깁니다
• 주소 공간이 통째로 바뀌면 TLB 에 담긴 번역이 전부 쓸모없어집니다. 그때는 버리고 다시 채워야 합니다

프로파일러에서는 이게 아무 이름도 없이 나타납니다. 함수 이름이 붙는 것도 아니고 호출 스택에 남지도 않습니다. 그냥 같은 코드가 어떤 데이터에서는 느립니다. 원인을 코드에서 찾으면 안 나옵니다. 데이터가 주소 공간에 어떻게 흩어져 있는지를 봐야 합니다.

정리

• 페이지 테이블도 메모리에 있습니다. 표를 보는 것 자체가 메모리 접근입니다
• 48비트 주소 공간을 한 장짜리 표로 만들면 표가 램보다 커집니다. 그래서 9비트씩 네 단계로 쪼개고, 안 쓰는 가지는 만들지 않습니다
• 대신 번역 한 번에 표를 최대 네 번 읽습니다. 그 값을 없애는 것이 TLB 입니다
• TLB 가 덮는 범위는 4KB 페이지 기준 8MB 안팎입니다. 그 안에 모여 있으면 번역은 공짜고, 넘어가면 매번 표를 걸어 내려갑니다
• 그래서 연속된 배열이 유리합니다. 캐시 때문만이 아니라 번역을 한 번만 하기 때문입니다