Speed Up GC by Prefetching During Marking
요 PR에서 진행된 토론을 정리 및 번역해본다.
해당 PR은 프리페칭을 이용해서 프로세서의 메모리 병렬화를 이용하여 메이저 GC의 마킹 루프를 최적화한다. 이를 통해 마킹 페이즈에서 일어나는 거의 모든 캐시 미스를 없애서 GC 속도를 높인다.
800MB 힙의 마이크로 벤치마크에서 Gc.full_major에 걸리는 시간이
1.8초에서 0.5초로 줄었다.
물론 대부분의 프로그램은 GC에 100%의 시간을 쓰는게 아니기 때문에, 보통 이정도로 개선이 드라마틱하진 않다. 다른 테스트 프로그램에서는 마킹 시간이 1/3~2/3 정도로 줄어서 GC를 얼마나 쓰느냐에 따라서 전체적으로 5-20% 정도의 성능 개선이 있었다. 더 많은 벤치마킹이 필요하다.
캐시보다 힙이 훨씬 더 큰 프로그램에서만 성능 개선이 보일 것 같다. 수십 메가바이트보다 적게 쓰는 프로그램은 이 패치로 개선이 크게 되진 않겠지만, 더 느려지지도 않을 것이다.
알고리즘
현재의 마킹 알고리즘은 순수한 DFS다. 마킹은 항상 마크 스택 위에 있는 오브젝트를 진행하고, 찾아낸 새로운 블록은 스택에 푸시된다. 이 오브젝트들은 보통 캐시에 있지 않기 때문에 GC는 대부분의 시간을 캐시 미스 때문에 새 오브젝트의 헤더가 로딩되는 걸 기다리는 데 쓴다 (스톨링).
이 PR의 알고리즘은 작은(현재는 256 엔트리) 원형 큐 버퍼를 마크 스택
앞에다 붙여서 이른바 프리페치 버퍼로 사용한다. 마킹 페이즈 동안, 그
다음 오브젝트는 프리페치 버퍼에서 뽑거나 (최소 Pb_min 원소 이상일
때), 프리페치 버퍼가 비어있거나 거의 비어있으면 마크 스택에서 팝해서
스캔한다. 마킹하는 동안 새로운 포인터를 발견하면, 얘네는 곧장
따라가는게 아니라 프리페치해서 프리페치 버퍼에 넣는다. 블록은
프리페치 버퍼가 오버플로우 날 때에만 마크 스택에 푸시된다.
이러면 스캔할 새로운 오브젝트는 일반적으로 적어도 Pb_min 스텝
이전에 프리페치되고, 이 말은 곧 얘네는 캐시에 있을 확률이 아주아주
높아진다.
마크 스택 변경 사항
이 PR은 또한 마크 스택에 작은 구조적인 변경 사항을 포함한다. 마크
스택에는 이미 인터벌이 있고, 부분적으로 스캔된 오브젝트를 나타내기
위해 쓰이지만 이 인터벌은 (value, offset) 쌍으로 표현되고 있다. 이
패치는 이거를 (start, end) 쌍으로 바꾸는데, start = value +
osffet이고 end = value + Wosize_val(value) 이다. 이러면 긴 배열의
뒷부분을 탐색할 때 Wosize_val(value)를 정할 때 일어나는 캐시 미스를
세이브할 수 있다.
@stedolan
프리페치는 TLB 성능에도 도움이 된다. 프리페치는 프로세서가 더 많은 메모리 요청을 병렬적으로 처리할 수 있게 해줘서 필요한 경우에는 페이지도 훑는다.
페이지 사이즈가 더 커지면 TLB를 잘 활용할 수 있어서 성능을 더 많이 개선하겠지만, 이 PR과는 독립적인 이슈다.
뭔가 오해가 있는 것 같다. 메모리 병렬성을 더 많이 얻으면 이 코드는 더 빨리지고 다른 파라미터 수정이 필요없다. 이유를 설명하자면 다음과 같다.
프로세서의 메모리 서브시스템은 메모리를 읽는 요청을 받아들이는데, 약간의 딜레이 후에 읽은 내용물을 만든다. 이 딜레이는 3-4 싸이클(L1 캐시 히트 시)부터 수백 싸이클(메인 메모리 접근)까지 갈 수 있다. 아주 극단적인 경우에, 이것보다 길 수도 있는데, 만약 TLB 미스가 있어서 메인 메모리 접근 뿐만 아니라 메인 메모리의 페이지를 전부 훑어야할 수도 있다.
메모리 서브시스템은 동시에 여러 개의 요청에 대해서 유용한 발전을 만들 수 있는데, 이게 바로 “메모리 레벨 병렬성” 또는 MLP 이다. 대부분의 모던 x86 프로세서는 최대 MLP가 약 10정도 되는데, 최신은 더 많기도 하다. 사실 MLP는 단순히 숫자만 가지고 보기에는 좀 복잡하다. 최대 MLP는 어떤 캐시가 관여하는지, 코어 사이에 어떤 리소스를 공유하는지에 따라 다르다. 하지만 여기서는 이 숫자 하나만 봐도 충분하다.
예를 들어, 만약 20개의 로드 명령어를 1-20싸이클에 걸쳐서 발행하면, 최대 MLP가 10이고 메인 메모리 접근까지 300 싸이클이 걸리는 머신에서는 모든 로드가 600싸이클 정도에 완료될 것으로 기대할 수 있다. 메모리 서브시스템은 첫번째 10개의 로드를 아주 빠르게 받아들여서 로드를 시작하지만 나머지 11-20 명령어는 큐에 쌓인다.
하지만, 대부분으 피르고르매은 각 싸이클 마다 로드 명령어를 발행하지 않는데, 그래서 가용 MLP가 대부분 사용되지 않는다. 프로세서는 더 많은 MLP를 사용하기 위한 다양한 트릭을 갖고 있다. 예를 들어, 브랜치를 투기적으로 실행해서 실제로 어떤 브랜치로 갈지 정해지기 전에 로드를 수행하는데, 순차적인 접근을 발견해서 미리 프로그램을 읽는다. 안타깝게도 이런 트릭은 전부 GC의 마킹 페이즈에 특별히 효과적이지 않은데, 마킹 페이즈에서는 예측 불가능한 포인터 추적이 엄청 많이 일어난다. 포인터 추적은 특히 MLP에 안좋다. 검사할 다음 워드의 주소는 이전 로드가 완료되어야만 알 수 있어서, 강제로 순차적이다.
이 PR의 GC 프리페치는 다르게 작동한다. 얘는 소프트웨어 프리페치 명령어를 통해 곧바로 수백개 정도의 로드 명령어를 발행한다. 여기서 “수백”은 다를 수 있다. 버퍼 사이즈는 256이지만, 이게 항상 꽉 차진 않고, 꽉 차 있더라도 많은 값이 포인터가 아니다. 발행된 요청 수는 프로세서의 가용 최대 MLP를 엄청나게 초과하는데, 그래서 대부분의 이 요청은 큐에 쌓인다. 이 시도는 메모리 서브시스템이 항상 최대의 용량(capacity)로 수행되도록 보장하기 위함이다. 로드 명령어가 데이터를 리턴할 때마다, 항상 준비된 그 다음 데이터가 큐에 있다.
이것은 다른 프로세서에서 가용한 더 큰 MLP도 투명하게 활용할 수 있다. 몇 년쯤 뒤에 MLP가 수백이 되면 그때는 프리페치 버퍼 사이즈를 더 크게 잡는게 좋겠지만 지금은 256이면 충분해 보인다.
근본적으로, 마킹 페이즈는 아주 많은 메모리 접근을 하는데, 대부분 캐시 미스가 난다. 건드린 메모리의 각 워드에 대해서 아주 적은 양의 계산만 수행하는데, 그래서 CPU가 아닌 메모리 성능에 의해서 제한된다. 어떤식으로든 CPU는 메모리를 기다리면서 정체된다(스톨링).
스톨이 발생하면, 일반적으로 다른 오브젝트 B를 가리키는 오브젝트
A의 필드 i를 스캐닝하면서 스톨되는데, B의 헤더는 캐시에
없다. 하드웨어는 계속해서 투기적으로 계산해서 스톨을 피하려고 하는데,
보통 A의 i+1 필드를 다음에 읽도록 예측해서 이걸 페치하려고
한다. 하지만, 이는 같은 오브젝트의 필드에만 제한된다. 스캔할 그 다음
오브젝트의 주소는 B의 헤더에 의해서 결정되는데, B의 로드가 끝나기
전까지는 프로세서가 알지도 못하고 추측(투기)할 시도도 못한다. 그래서,
스톨되는 동안, 실제 일어나는 메모리 로드는 필드 i, i+1 등 몇 개
안된다. 따라서 10개 정도의 메모리 로드만 일어나기 때문에 메모리
서브시스템이 덜 활용된다.
GC 프리페치가 스톨되면, 이는 보통 로드 동안 일어나는게 아니다. 왜냐면 이미 프리페치가 이뤄져서 L1 캐시 히트가 일어난다. 하지만, 계속해서 나중에 필요할 메모리 로드 프리페치를 발행하고, 그래서 때때로 최대 MLP에 도달한 다음 스톨된다. 이런 종류의 스톨 동안에는 가능한 한 많은 수의 메모리 로드가 일어나기 때문에, 메모리 서브시스템이 최대한 활용될 때에만 이 스톨이 발생한다.
즉, 최대 MLP를 때려서 발생한 스톨은 마킹 루프를 위한 가장 이상적인 상태이다. 이 말은 메모리 접근이 아주 잘 스케쥴링 되어서 메모리 서브시스템을 최대한으로 활용하고 있다는 뜻이고, CPU가 결과를 기다리는 일 외에는 할 일이 없을 정도로 충분히 낮은 오버헤드가 일어난다는 뜻이다.