요약
순수 함수형 언어 Roc로 짠 압축 라이브러리가 고도로 최적화된 C 라이브러리보다 중앙값 기준 몇 퍼센트만 느렸습니다.
Roc 언어를 만든 리처드 펠드먼의 글입니다. Lean으로 짠 압축 라이브러리가 Rust 패키지는 이겼지만 C 라이브러리 libdeflate에는 크게 졌다는 소식을 보고, Roc로는 얼마나 따라잡을 수 있는지 직접 실험했습니다.
왜 중요한가
- 순수 함수형 언어는 느리다는 통념과 달리, 실제 격차는 한 자릿수 퍼센트까지 줄어들 수 있다는 사례입니다.
- 저자는 그만큼 느린 대가로 메모리 안전성, 부작용 없음, 공급망 보안을 얻는다며 값어치를 따져 보자고 했습니다.
- C에서 범위 검사를 건너뛴 위험의 예로, 글 전날 공개된 Node.js Brotli 원격 코드 실행 취약점을 들었습니다.
핵심 내용
- DEFLATE 압축 구현 roc-deflate는 144개 벤치마크의 중앙값 기준으로 AMD 라이젠에서 8.9%, M1 맥북 프로에서 2.6% 느렸습니다.
- 입력에 따라 약 18% 느리거나 18% 넘게 빠르기도 했지만, 저자는 이를 언어가 아닌 구현 차이로 봤습니다.
- 가장 효과가 큰 최적화는 값을 여러 곳에서 공유하지 않게 해서 제자리 수정(복사 없이 메모리를 바로 고치는 것)을 끌어내는 것이었습니다.
- 반복문 앞에서 길이를 한 번 검사해 안쪽 범위 검사를 없애고, 조회 표는 컴파일할 때 미리 만들었습니다.
- libdeflate가 앞서는 주된 이유는 Roc에서 쓸 수 없는 CPU별 SIMD(한 명령으로 여러 데이터를 처리하는 기능) 코드라고 했습니다.
HN 반응
- C는 멀리 떨어진 상태를 직접 고쳐 복사를 줄이고 메모리 배치도 통제할 수 있어 함수형 언어가 불리하다는 의견이 이어졌지만, 이번 격차는 SIMD 탓이 크다는 보충도 나왔습니다.
- Lean 쪽 비교 대상이던 miniz_oxide는 일부러 단순하게 만든 구현이라, C보다 빠르다는 zlib-rs와 비교해야 공정하다는 지적도 있었습니다.
최적화 가능성에서 차이가 나는 큰 이유는 C/C++가 꽤 극단적인 복사 생략(copy elision)을 허용한다는 점입니다. 메모리 대역폭이 성능의 주요 병목이 되기 쉬우니 이건 중요합니다.
C/C++ 코드는 멀리 떨어진 어떤 상태에 직접 손을 뻗어 바로 변경할 수 있습니다. 접근 방식이나 패턴이 아무리 지저분해도 컴파일러는 좀처럼 문제 삼지 않습니다. 불변 조건을 지키는 건 프로그래머의 몫이고, 컴파일러가 그 속을 항상 들여다볼 수 있는 것도 아닙니다. 이렇게 생략된 복사가 쌓이면 상당하지만, 대개 유지보수성과 안전성이 그 대가가 됩니다.
함수형 언어가 이론상으로는 대규모 병렬화에 좋은 성질을 갖고 있는데도 실제 슈퍼컴퓨팅에서는 평범한 수준에 머무르는 이유와도 관련이 있습니다.
클로저(Clojure)를 만든 리치 히키(Rich Hickey)는 클로저의 접근 방식이 특정 종류의 문제에 더 낫다고 설명하면서, 전통적인 명령형 프로그래밍을 "장소 지향 프로그래밍(PLace Oriented Programming, PLOP)"이라고 부릅니다.
저도 그 주장에 동의하고 클로저는 제가 가장 좋아하는 프로그래밍 언어이지만, 컴퓨터 자체는 장소 지향적입니다. 컴퓨터는 메모리의 특정 위치를 읽고 쓰는 방식으로 돌아가고, 거기서 최대 효율을 끌어내려면 그 메모리를 직접 제어해야 합니다.
현대 컴퓨터는 공간적, 시간적 지역성에 극도로 민감합니다. 코드를 (공짜로!) 빠르게 만들어 주는 하드웨어 기능 상당수가 서로 "가까이 있는" 데이터나 명령어를 활용하기 때문입니다. 함수형 프로그램에서는 이게 어려울 수 있습니다. 데이터가 어디에 놓이는지 제어할 수 있는 부분이 적을 뿐 아니라, 멋진 일을 가능하게 하는 추상화(예: 클로저나 지연 평가)가 자연스럽게 간접 참조를 끌어들여 지역성을 해치기 때문입니다.
상위 계층에서는 훌륭한 추상화를 쓰고, 그것이 빠른 기본 연산으로 내려가게 만들 수 있습니다. 더 자세한 내용은 [1] Push your "ifs" up and "fors' down 과 [2] Vectorized interpreters 글을 보세요.
[1] https://debasishg.github.io/blog/push-ifs-up-fors-down/ [2] https://venge.net/graydon/talks/VectorizedInterpretersTalk-2023-05-12.pdf
같은 식으로 컴퓨터가 사실은 근본적으로 함수형이라고 주장할 수도 있습니다. 핵심 명령어 사이클(인출-해독-실행)은 어떤 메모리도 수정하지 않으니까요.
이 시스템의 핵심 통찰은, 함수형 시스템을 명령형으로 만들어 주는 메커니즘 안에 심어 놓았다는 것입니다. 함수형 사이클은 더 많은 데이터를 가져오라는 명령을 내보낼 수 있고, 그 데이터를 다음 사이클에서 씁니다. 여기에 시간이 더해지면서 명령형이 되는데, 입력과 출력의 양이 한정되어 있어서 시간이 필요하기 때문입니다.
실행 단계는 상태를 아주 많이 수정합니다. 사실 항상 수정합니다. 메모리를 쓰지 않는 명령어는 레지스터를 수정하고, 메모리 명령어는 레지스터나 메모리에 씁니다. noop조차 명령어 포인터를 증가시키니까, 어떻든 항상 레지스터를 수정하는 셈입니다.
숲속에서 함수가 계산되었는데, 그 함수가 결과를 반환할까요?
결과를 놓을 장소가 있을 때만요.
스택 세 파운드!
좋은 설명 감사합니다.
이런 접근 방식과 패턴을 다루면서, 특히 소프트웨어와 하드웨어 사이의 간극을 메우는 걸 목표로 하는 자료가 혹시 널리 알려진 게 있나요? 제가 떠올릴 수 있는 가장 좋은 건 데니스 바흐발로프(Denis Bakhvalov)의 Performance Analysis and Tuning on Modern CPUs0입니다.
최근에 https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html 을 봤는데, 저자가 리눅스 코드베이스에 최적화를 적용한 경험을 바탕으로 쓴 책입니다.
함수형 언어에서 참조 카운팅 비용을 줄이는 방법을 다룬 https://xnning.github.io/papers/perceus.pdf 논문도 아주 읽기 쉬워서 좋았습니다.
이 경우에는 libdeflate가 miniz-oxide를 이기는 가장 큰 이유가 SIMD인 것 같네요. 그 단계가 되면 어셈블리를 쓰거나, 어셈블리에 대응하는 이름과 기능을 제공하는 함수 라이브러리를 쓰게 되죠. 그 점에서 C가 다른 언어보다 딱히 낫다고는 생각하지 않습니다. 자동 벡터화로 그 SIMD 지원을 얻는 것도 아니고요.
Miniz_oxide는 의도적으로 단순하게 만든 구현입니다. 더 최근에 나온 zlib-rs1와 비교하는 게 공정할 겁니다. zlib-rs는 (C로 만든 가장 빠른 구현인) zlib-ng보다도 빠릅니다2.
그러니까 lean-zip이 "crates.io 기준 10억 번 넘게 다운로드된 동급 Rust 패키지를 능가했다"는 거네요. 맞아요, zlib-rs는 다운로드가 2억 번밖에 안 됐죠. 하지만 훨씬 빠르잖아요!
zlib-rs는 몇 년 더 늦게 나왔으니 당연히 다운로드 수가 적죠. 최근 일일 다운로드 수를 보면 zlib-rs가 여유 있게 앞섭니다(250만 대 160만).
다운로드 수를 지표로 삼다니 참 이상하네요.
다운로드가 많다는 건 이 정도 성능이면 받아들일 만하다는 선호가 드러난 것입니다.
그렇긴 한데, 거기엔 조건이 많이 붙습니다. 예를 들면 이런 겁니다.
더 빠른 패키지가 공개된 기간이 짧아서, 다운로드 수가 아직 따라잡을 시간이 없었을 수 있습니다.
더 빠른 패키지가 있다는 걸 모르는 사람이 많을 수 있고, 알았다면 갈아탔을 겁니다.
더 빠른 패키지가 있다는 걸 알아도, 갈아타는 비용이 더 느린 패키지 때문에 치르는 비용보다 커서 당장은 못 옮길 수도 있습니다.
deflate를 쓰는 사용자 대부분은(전부는 아니지만) 그걸 핫 패스에 두지 않고, 아주 큰 파일을 압축하지도 않는다고 말해도 무리가 없을 것 같습니다.
최근 일일 다운로드 수는 반대 추세를 보여줍니다. 하루 250만 대 160만으로 zlib-rs가 앞서고 있어요. 문제는 zlib-rs가 훨씬 늦게 나왔다는 점이라서 누적 다운로드 수를 보는 건 말이 안 됩니다. 게다가 갈아타는 데에도 관성이 있고요.
D에는 함수에
pure를 붙이면 컴파일러가 그 함수가 순수한지 검사해 주는 좋은 기능이 있습니다.pure검사를 통과하도록 코드를 재구성하는 건 재미있습니다.D의 그 점은 좋다고 생각해요. 그런데 관례가 거꾸로 된 게 아닌가 싶을 때가 있거든요. Lua는 global이 아니라 local을 명시하게 하고, TS는 기본이 strict가 아니고, 대부분의 언어는 불변이 아니라 가변이 기본이잖아요.
저는 늘 제대로 돌아가는 프로그램이 옵트인이 아니라 옵트아웃이어야 한다고 생각했어요.
(예를 들어 제가 꿈꾸는 언어는 동적 타이핑을 지원하는데, 컴파일러 지시어로 #jammode를 쓰거나 아니면 #explodeinprod를 써야 해요)
아주 좋은 질문입니다. 답은
pure가 D가 이미 자리 잡고 기존 코드가 많이 쌓인 뒤에 나왔기 때문입니다. 이걸 기본값으로 바꾸면 그 코드 거의 전부가 깨집니다.문제의 일부는
pure가 전이적이라는 점입니다. 즉 순수 함수가 비순수 함수를 호출하는 건 허용되지 않습니다. 그래서 코드를 점진적으로 순수하게 만들기가 어렵습니다.하지만 성공하고 나면 아주 뿌듯합니다.
그래도 탈출구가 있습니다. 문장 앞에
debug를 붙이면 그 문장은 비순수해도 됩니다. 프로그램을 디버깅하려고 출력문을 몇 줄 넣어야 할 때 아주 편리합니다. (printf 호출은 비순수니까요!)그
debug방식 영리하네요! Roc에는 같은 일을 하는 전용 언어 키워드dbg를 넣었습니다. 말씀하신 대로 디버그 출력을 로깅하는 건 부작용인데도 순수 함수 안에서 쓸 수 있게 했습니다.그나저나 다시 인사드립니다! 2021년 Handmade Seattle 이후에 직접 잠깐 이야기를 나눴었죠. 혼자서 동작하는 C++ 컴파일러를 구현해 낸 몇 안 되는 사람(어쩌면 유일한 사람?)이라는 걸 알고 정말 감명받았던 기억이 납니다.
아무튼 잘 지내시길 바라고, 언제든 팟캐스트 에피소드를 녹음해 보고 싶으시면 알려주세요 - [email protected]
여러 기벽(지연 IO)과 결함(base의 부분 함수, 난립하는 언어 확장)이 있는데도, 이 부분만큼은 Haskell이 정말 잘합니다.
거의 10년 동안 프로덕션 Haskell을 써 온 게 정말 다행입니다.
그러면 순수 함수 안에 로컬 디버깅용 출력문을 몇 개 넣고 싶을 때, 호출 그래프 전체에서 pure를 떼어내야 한다는 뜻인가요? 아니면 그걸 경고로만 처리하는 방법이 있나요?
이런 최적화를 라이브러리로 공개해서, 프로그래머가 최적화 패스를 요청하고 컴파일러가 전제 조건을 검사하게 하는 방안은 생각해 보셨나요?
JS가 얼마나 빨라질 수 있는지 다루는 글을 준비 중인데 같은 걸 발견해서 묻습니다. V8을 충분히 괴롭히면 사실상 어떤 코드든 최적화된 C 코드의 10% 안쪽까지 갈 수 있습니다(SIMD는 예외인데, 누가 봐도 뻔한 경우에도 V8이 SIMD로 최적화하지 않는 버그가 있는 것 같습니다). 그걸 라이브러리로 뽑아서 더 매끄럽게 만들 수 있겠다고 생각했지만, 수동 변환이 얼마나 일반화될지는 확신이 없습니다.
그리고 roc-deflate 작업을 하시면서, 이런 모델에 들어맞을 만한 반복되는 변환을 발견하셨나요, 아니면 개선 대부분이 압축에만 해당하는 것이었나요?
제가 알기로는 특이한 구석 사례에서는 JS 코드가 wasm/C/C++보다 빠를 수 있습니다. JIT가 탈출 분석과 인라이닝으로 최적화하니까요.
네, 가끔은 -O3 C보다도 빠릅니다. 인터넷에 있는 여러 '언어 속도' 벤치마크에서 코드를 가져왔는데, -O3 C가 비슷해 보이는 JS를 이기게 하려면 코드를 재배치해야 했습니다(Node 25.8.1 w\ V8 14.1, clang 21, MBP3 기준).
말 그대로 이겁니다.
out[i] = a[i] * b[i] + 0.25; out[i + 1] = a[i + 1] * b[i + 1] + 0.25; out[i + 2] = a[i + 2] * b[i + 2] + 0.25; out[i + 3] = a[i + 3] * b[i + 3] + 0.25;
}
여러 형태를 시도해 봤는데, Firefox는
for (let i = n; i--;) out[i] = a[i] * b[i] + 0.25;를 선호합니다. 이미 최적화가 한계까지 되어 있어서, 어떤 형태도 눈에 띄게 더 낫지는 않습니다.