GN⁺: 2GB/s 이상의 속도로 protobuf 파싱하기: C 언어에서 tail calls를 사랑하게 된 이유 (2021)

• Tail Call: 함수가 반환되기 직전에 호출되는 함수 호출. Tail Call 최적화가 발생하면 jmp 명령어가 사용되어 호출 스택을 줄임.
• 장점:
  • 스택 메모리 사용을 O(n)에서 O(1)로 줄임.
  • 함수 호출의 성능 오버헤드를 제거하여 효율적인 반복 제어 구조로 사용 가능.

인터프리터 루프의 문제점

• 문제점:
  • 함수가 커지고 제어 흐름이 복잡해질수록 중요한 데이터를 레지스터에 유지하기 어려움.
  • 빠른 경로와 느린 경로가 섞여 있으면 코드 품질이 저하됨.

Tail Call을 활용한 인터프리터 루프 개선

• 해결책: Tail Call을 사용하여 각 작업을 작은 함수로 분리하고, 각 함수가 다음 작업을 Tail Call로 호출.
• 장점:
  • 레지스터 할당을 제어할 수 있음.
  • 빠른 경로와 느린 경로를 분리하여 코드 품질을 유지.
  • 독립적인 명령어 시퀀스를 최적화 가능.

한계

• 비 Tail Call 존재 시 문제: 비 Tail Call이 존재하면 스택 프레임이 생성되고 데이터가 스택에 저장되어 성능 저하.
• 복잡한 예외 처리: 예외 처리가 복잡한 경우 코드 중복과 복잡성 증가.
• 이식성 문제: musttail 속성이 표준이 아니므로 모든 컴파일러에서 지원되지 않음.

GN⁺의 정리

• Tail Call 최적화는 성능 향상에 중요한 역할을 하며, 특히 Protobuf 파싱에서 큰 성과를 보임.
• 이 기술은 C로 작성된 주요 언어 인터프리터(Python, Ruby, PHP, Lua 등)에도 적용 가능.
• musttail 속성의 이식성 문제는 해결해야 할 과제.
• 비슷한 기능을 제공하는 프로젝트로는 LuaJIT, wasm3 WebAssembly 인터프리터 등이 있음.

[neo]

Hacker News 의견

• C 표준 제안서에는 "return goto (expression);" 형태로 꼬리 호출을 포함하고 있음

  • [[musttail]]을 표준화하는 것보다 로컬 객체의 수명이 보장되어 광범위한 탈출 분석이 필요하지 않음

• Rust 애호가들을 위해 "become" 키워드를 추가하는 오래된 RFC가 있었음

  • 2018년 에디션 목표에 집중하기 위해 연기되었으나 최근 다시 논의되고 있음
  • 다시 등장할 가능성이 있음

• C++에서 해석기가 속도를 높이는 방법은 주로 계산된 goto를 사용하는 것임

  • 호출 규약 문제를 피할 수 있음
  • 계산된 goto 스타일이나 꼬리 스타일을 사용하면 분기 예측기 압력을 줄일 수 있음

• 꼬리 호출을 사용하여 컨텍스트를 전환하는 문제는 호출 규약을 사용하는 함수가 필요함

  • 함수 종료 시 상태를 복원하기 위해 레지스터를 낭비함
  • luajit 리메이크 블로그에서 대안과 분석을 제공함

• [[musttail]] 속성이 GCC, Visual C++, 다른 인기 있는 컴파일러로 확산되기를 희망함

  • [[musttail]] 속성이 GCC에 추가되는 과정에 있음

• C++ 지원을 언급하며, C++에는 꼬리 호출이 거의 없음을 지적함

  • 예를 들어, 소멸자가 있는 클래스의 객체를 반환하는 경우 꼬리 호출이 아님

• C++ [[musttail]] 함수에서 예외를 던지면 어떻게 되는지 궁금해함

  • 예외 스택이 완전히 분리되는지 질문함

• 단순한 예제는 좋은 코드 생성을 위해 __attribute__((musttail))이 필요하지 않음을 언급함

  • 오류 처리 함수 호출 속도에 크게 신경 쓰지 않을 것임
  • 특정 구조가 신뢰할 수 있는 점프 테이블을 생성함

• 트램폴린을 사용하여 반환하는 함수 포인터를 외부 루프에서 호출하는 방식의 속도를 궁금해함

  • 이 방식은 이식 가능한 C의 장점을 가짐

• [[musttail]]로 래핑된 예외 경로의 예를 명확히 해달라는 요청이 있음

  • [[musttail]]이 스택 프레임 구성과 레지스터 스필링을 방지하는 이유를 설명함
  • 예외 경로가 실제로 호출될 때만 스택 프레임 구성과 레지스터 스필링이 발생함
  • 예외 경로가 드물게 호출되므로 성능에 큰 영향을 미치지 않음
  • 분기 예측 효과로 인해 추가 작업 가능성이 빠른 경로를 느리게 만들 수 있음