Inline Caching (인라인 캐싱)

원본 출처: http://en.wikipedia.org/wiki/Inline_caching

메세지, 메세지 셀렉터, 리시버 부분에서는 나도 무슨 말인지 잘 모르겠지만 대략의 개념만 파악했다. 어쨌든 함수 호출하는 부분에다가 함수 위치를 알 수 있게 저장해서 룩업 생략하겠다는 거 아닌가?

잘못 옮긴 부분 있다면 지적 부탁드립니다.

Inline caching

최적화 테크닉의 한 종류로, 랭귀지 실행시간에 사용이 되며 Smalltalk을 위해서 처음으로 개발되었다. 인라인 캐싱의 목표는 호출 지점¹에서 직접적으로 이전의 메소드 검색의 결과를 기억해서 런타임 메소드 바인딩의 성능을 높이는 것이다. 인라인 캐싱은 대부분의 메소드 바인딩이 런타임에 일어나고 가상 메소드 테이블을 사용할 수 없는 동적 언어에서 특히 유용하다.

Runtime method binding

동적언어에서는 오브젝트의 타입이 명시되지 않고 메소드 오버로딩의 가능성이 존재하기 때문에, 메소드를 호출할 때 구체적으로 어떤 구현 함수가 적용될지 미리 결정할 수 없다. 캐싱을 사용하지 않는 런타임에, 이러한 검색은 하나의 메소드가 불릴 때마다 매번 실행된다. 메소드들이 상속 체인을 따라내려가서 여러 단계로 정의될 수도 있기 때문에, 동적 검색은 시간이 많이 소모될 수 있다.

퍼포먼스를 향상시키기 위해, 많은 언어들은 연관 데이터 구조 안에 제한된 숫자의 메소드 검색 결과를 저장해놓은 모종의 non-inline 캐싱을 사용한다. 이것은 실행되는 프로그램들이 "cache friendly" 할 때(제한된 숫자의 메소드가 자주 불릴 때) 성능을 크게 향상시킬 수 있다. 이러한 데이터 구조는 일반적으로 first-level method lookup cache라고 불린다.

Inline caching

인라인 캐싱의 개념은 특정 호출지점에서 발생하는 오브젝트들은 주로 같은 타입이라는 경험적 관찰에 기반한다. 그런 경우에 메소드 검색의 결과를 "inline"으로, 즉 호출 지점에 직접 저장해놓으면 성능이 크게 증가할 수 있다. 이 과정을 가능하게 하려고, 호출 지점들에 서로 다른 상태를 부여한다. 처음에는 각 호출지점은 "uninitialized" 상태이다. 일단 런타임이 특정한 uninitialized 호출 지점에 도달하면, 동적 검색을 수행하고, 호출 지점에 결과를 저장하고 호출 지점의 상태를 "monomorphic"(단형성)으로 바꾼다. 언어 런타임이 똑같은 호출 지점에 다시 도달한다면, callee를 (inline cache로부터) 다시 가져와서 더이상의 검색을 수행하지 않고 곧바로 불러온다. 같은 호출 지점에서 서로 다른 타입의 오브젝트가 존재할 수도 있기 때문에, 언어 런타임은 코드 안에 gaurd condition도 삽입을 해야만 한다. 흔히 garud condition들을 호출 지점보다는 callee의 프리앰블에 삽입한다. 브랜치 프리딕션을 더 잘 이용할 수 있고, 프리앰블에 하나의 카피만 있는 것이 각 호출 지점마다 여러 카피가 있는 것에 비해 공간을 절약할 수 있기 때문이다. "monomorphic" 상태에 있는 호출 지점이 예상치 못했던 다른 타입을 만나게되면 호출 지점은 "uninitialized" 상태로 돌아가서 완전한 동적 검색을 다시 수행해야 한다.

고전적인 구현방법은 레지스터에 상수를 불러온 뒤에 콜 명령어가 오는 것이다. "uninitialized" 상태는 "unlinked"로 불리는 것이 낫다. 레지스터에 message selector(주로 어떤 오브젝트의 주소)를 채우고, (함수의) 호출은 위에서 말한 first-level method lookup cache를 사용해서 현재 리시버의 클래스(분류?) 안에 있는 메세지를 탐색하는 런타임 루틴이 된다. 그렇게 되면 런타임 루틴은 로드 명령어를 레지스터에 현재 리시버의 타입을 채우는 것으로 바꾸고, call 명령어를 바꿔서 타겟 메소드의 프리앰블을 부르도록 바꿔서 명령어를 다시 쓴다. 그러면 호출 지점과 타겟 메소드를 "연결(linking)"하는 것이다. (함수의) 실행은 이제 프리앰블을 곧장 따라가면서 이어진다. 다음 번의 실행에서는 (linking 없이) 프리앰블을 직접적으로 호출할 수 있을 것이다. 그러면 프리앰블은 현재 리시버의 타입을 가져와서 레지스터 안에 있는 값과 비교할 것이다. 만약 맞아떨어진다면 리시버는 같은 타입이므로 메소드를 계속해서 실행한다. 다르다면 프리앰블은 다양한 전략들을 시도해볼 수 있다. 호출 지점과 새로운 리시버 타입을 재연결하는 것이 한 방법이 될 수 있다.

성능의 이득은 최소 한번의 타입 비교와 셀렉터 비교를 하는 first-level method lookup cache에 비해 한번의 타입 비교만 하는 것과, method-lookup이나 vtable 방식을 썼을 때의 간접 호출에 대비되는 직접 호출(명령어 prefetch와 pipelining으로 이득을 얻을 수 있다)을 통해서 얻게 된다.

요약

• 어떤 함수를 호출할 때 같은 call site에서는 계속해서 같은 함수를 불러올 가능성이 높다는 관찰에 기반한다.
• 최초로 call site에 도달했을 때는 어떤 함수를 불러와야 할 지 알 수 없으므로 완전한 메소드 검색을 해야만 한다.
• 불러올 함수가 결정이 되었으면 다음번에 call site에 도달했을 때는 방금 전에 찾아온 메소드를 바로 찾아갈 수 있도록 call site에 찾아갈 대상이 되는 위치를 기록해둠.
• 함수 오버로딩 같은 경우가 있을 수 있으므로, 불러올 함수의 유형이 달라질 것에 대비해 guard instruction을 삽입해야 한다. (맞는지 틀린지 확인하기 위해)
  • 만약 call site마다 guard instruction을 삽입하게 되면 여러 call site에서 똑같은 함수를 불러올 때 여러 번 guard instruction 삽입해야 하므로 낭비가 생긴다.
  • 따라서 불러올 대상이 되는 함수의 맨 앞에 guard instruction을 삽입해서 중복삽입을 피한다.
• 만약 guard instruction을 실행했을 때 원래 예측했던 타입과 다르다면 다시 돌아가서 메소드 검색부터 다시 실행한다.

* http://jayconrod.com/posts/44/polymorphic-inline-caches-explained 이쪽의 내용을 참고해도 좋을 것 같다.

---

1. call site: 함수나 서브루틴이 호출되는 위치(코드의 라인). 호출 지점은 0개 이상의 argument가 함수에 넘겨지고, 0개 이상의 리턴값을 넘겨받는 위치이다. ↩