동적 타입 체크의 두 가지 메커니즘

wingolog에서 흥미로운 글을 읽었다. 가상 머신에서 동적 타입 체크를 구현하는 두 가지 방법에 대한 기술적 분석이다. DFS 넘버링과 디스플레이 해킹. 둘 다 단일 상속 시스템에서의 타입 체크를 다룬다.

DFS 넘버링: 타입이 고정된 경우

첫 번째 방법은 타입 집합이 컴파일 타임에 고정된 경우에 사용한다. 타입 계층을 깊이 우선 탐색하면서 각 타입에 pre-order와 post-order 번호를 매긴다. 런타임에는 간단한 범위 체크로 서브타입 여부를 판단할 수 있다.

WebAssembly 정적 컴파일이나 JIT 컴파일러 내부의 타입 모델링에서 이 방식을 쓴다고 한다. 타입 시스템이 폐쇄적인 경우에 효율적이다.

디스플레이 해킹: 타입이 동적인 경우

두 번째 방법은 런타임에 타입이 추가될 수 있는 경우다. 각 타입이 자신의 상위 타입 배열을 가지고, 깊이 정보와 함께 관리한다. 1991년 Norman H. Cohen의 논문에서 상수 시간 타입 체크가 가능함이 증명되었다.

마흔이 넘어 이런 low-level 최적화 논문을 읽을 일이 많지 않다. 하지만 가끔 읽으면 기본기가 되살아나는 느낌이다. 우리가 쓰는 언어의 런타임이 내부적으로 어떻게 동작하는지 알면 더 나은 코드를 짤 수 있다.

왜 이게 중요한가

대부분의 개발자에게 타입 체크는 그냥 되는 것이다. instanceof 쓰면 알아서 체크된다. 하지만 언어를 만드는 사람들, VM을 구현하는 사람들에게 이건 성능에 직접적인 영향을 미치는 결정이다.

Java의 instanceof가 왜 그렇게 빠른가. Python의 isinstance()는 어떻게 구현되어 있나. 이런 질문들의 답이 이 두 메커니즘에 있다. 언젠가 직접 언어를 만들 일이 생긴다면 기억해야 할 내용이다.

결론

기술의 발전은 추상화의 역사다. 어셈블리에서 C로, C에서 고급 언어로. 우리는 점점 더 높은 수준에서 생각하게 된다. 하지만 가끔은 추상화 아래를 들여다보는 것도 좋다. 그 아래서 누군가는 상수 시간 타입 체크를 고민하고 있다.