TL;DR

  • rayon의 성능을 따라잡기 어려운 한계를 넘기 위해 API를 재구성하고 stackful, stackless, scoped 세 가지 실행 모델을 도입함.
  • scoped는 continuation을 분리하지 않고 병렬로 실행할 계산을 클로저로 전달하는 모델이며, 작업 설명자와 힙 할당이 필요 없는 가장 가벼운 방식임.
  • stackless는 Future 폴링 방식으로 스택 할당이 없고, stackful은 일반적인 사용자 수준 스레드로 뮤텍스와 배리어에서 블로킹할 수 있음.
  • 로컬 마이크로벤치마크에서 scoped가 rayon의 join보다 빠르고, stackless가 stackful보다 다소 빠르며, 두 모델을 지원하는 dual은 더 느린 결과임.
  • TLS 없이 워커를 식별하는 실험은 구현에 성공했지만, 로컬 macOS 환경에서는 계산 비용이 TLS 비용보다 커 성능 향상으로 이어지지 않음.

API 재구성 배경

  • 이전 글에서 Rust용 ComposableThreads를 공개하고 crates.io에도 배포한 뒤, 구현을 계속 개선함.
  • 벤치마크 과정에서 rayon의 join()이 예상보다 빨랐으며, 처음에는 stackless 비동기 구현을 조정하면 성능을 따라잡을 수 있다고 판단함.
  • 그러나 비동기 구현만 조정하는 데는 한계가 있음. 작업을 동기적으로 중단하는 메커니즘은 작업 상태 추적에 필요한 기록 작업과, 스케줄러로 한 번 돌아갈 때 발생하는 분기 비용을 피할 수 없음.
  • 비동기는 ‘오버헤드가 없다’고 홍보되지만, continuation을 분리하는 데 드는 비용은 피할 수 없음. 따라서 rayon 성능에 도달하려면 API 자체를 바꿔야 한다고 판단함.
  • 이에 구현을 재구성해 rayon의 API를 또 다른 실행 모델로 추가함.

세 가지 실행 모델

  • stackful: 일반적인 스택 기반 사용자 수준 스레드이며, 뮤텍스나 배리어에서 블로킹할 수 있음.
  • stackless: async/await 기반이며, Future로 폴링해 실행하므로 스택 할당이 없음.
  • scoped: 병렬 실행할 계산을 클로저로 넘기는 이항 전용 모델이며, continuation을 분리하지 않음. 작업 설명자와 힙 할당이 없어 세 모델 중 가장 가벼움.
  • HPC(고성능 컴퓨팅) 및 Cilk 계열의 fork/join 연구 문헌에서는 scoped 모델에 해당하는 별도의 이름이 없는 것으로 보임. continuation을 분리하지 않는 fork/join 방식은 TBB의 parallel_invoke와 OpenMP의 parallel for처럼 이미 널리 존재하지만, 독립된 프로그래밍 모델로 부르는 명칭은 찾지 못함.
  • continuation에 해당하는 작업이 클로저의 스코프 안에 머무는 특성을 바탕으로 ComposableThreads에서는 임시 명칭인 scoped를 사용함.

TLS 없는 워커 식별 실험

  • 스레드 로컬 저장소(TLS)를 사용하지 않고 현재 워커를 식별하는 방법도 실험함. 스택 포인터가 특수한 영역에 있다는 점을 이용해 해당 위치에서 역으로 워커를 찾아가는 방식임.
  • 구현 자체는 동작했지만, 실제로 TLS 비용은 크지 않았고 역산 비용이 더 컸음. 적어도 로컬 macOS 환경에서는 성능 향상으로 이어지지 않음.

벤치마크 결과

  • 로컬에서 마이크로벤치마크를 다시 실행해 독립 실행형 stackful, stackless, 둘 다 지원하는 dual, scoped 시스템을 rayon의 join과 비교함.
  • stackless 구현은 AI와 함께 어셈블리를 살펴보며 조정했으며, 성능 한계에 상당히 가까워진 상태임. 그럼에도 stackless와 scoped 사이에는 뚜렷한 성능 차이가 있음.
  • scoped는 rayon보다 빠른 결과를 냈지만, 구현은 거의 그대로 AI가 작성한 상태이며 세부 동작을 추적하지 않아 원인은 확실하지 않음. rayon이 사용하는 일부 추상화 작업을 건너뛰었을 가능성은 있음.
  • continuation을 절대 분리하지 않는다는 제약만으로도 프로그래밍 모델의 성능이 크게 달라질 수 있음을 보여주는 결과임.
  • stackless는 stackful에 필요한 컨텍스트 전환을 생략하고 호출 스택을 관리하지 않아 stackful보다 다소 빠름.
  • dual은 stackful과 stackless 사이에서 분기해야 하므로 더 느리며, stackless와 stackful의 성능 차이를 포함해 두 결과 모두 예상에 대체로 부합함.

현재 상태

  • 구현 상당 부분은 여전히 프로토타입에 가깝고 인터페이스도 아직 확정되지 않은 상태임.
  • 성능을 조정하고 더 사용하기 편한 형태로 다듬는 작업을 이어갈 계획임.