55 GiB/s 피즈버즈 (2021)

 (codegolf.stackexchange.com)
5P by GN⁺ | ★ favorite | 댓글 1개
  • Code Golf Stack Exchange의 High throughput Fizz Buzz는 FizzBuzz 출력을 얼마나 빠르게 생성해 pipe로 흘릴 수 있는지 겨루는 성능 실험이며, <program> | pv > /dev/null 처리량으로 점수를 매김
  • 유효 출력은 단순 ASCII, \n 줄바꿈, 정확한 Fizz/Buzz/FizzBuzz, 최소 2^58 이상 또는 사실상 무한 출력이 필요하며, pv에만 잡히는 널 바이트 트릭은 금지됨
  • 상위 구현들은 % 3, % 5, printf 루프를 버리고 15줄 패턴 언롤, 고정 폭 숫자 처리, 대형 버퍼, 병렬화, 무복사(zero-copy) 출력으로 병목을 줄임
  • 표시된 x86-64+AVX2 assembly 답변은 Linux와 AVX2를 전제로 vmsplice, L2 cache, huge page, FizzBuzz 바이트코드 인터프리터를 결합해 약 61GiB/s를 기록함
  • 결과는 CPU, pipe buffer, pv 버전, CPU affinity, mitigation 설정에 크게 흔들리며, 질문자 머신 기준 최고 점수는 David Frank의 C++ 구현 약 1.7Tb/s로 정리됨

FizzBuzz로 밀어붙인 처리량 한계

  • 핵심은 FizzBuzz 문제가 아니라, 아주 단순한 텍스트 생성에서 CPU 계산, 메모리 복사, pipe I/O, 커널 경계 중 어디가 먼저 병목이 되는지 확인하는 데 있음
  • 기준이 되는 순진한 C 구현은 % 3, % 5, printf를 사용하며, 평균적인 머신에서 약 170MiB/s 수준을 냄
  • 질문자는 같은 머신에서 3GiB/s 이상 구현을 본 적이 있었고, 커뮤니티가 더 높은 처리량 한계를 탐색하길 원함
  • 점수는 질문자의 데스크톱에서 측정됨
    • AMD 5950x, 16C/32T
    • 64GB 3200MHz RAM
    • CPU mitigations 비활성화
  • 언어별 표에는 asm 60.8GiB/s, C 20.9GiB/s, Julia 15.5GiB/s, Go 6.8GiB/s, Java 5.8GiB/s, Rust 3.4GiB/s, Ruby 1.7GiB/s, Python 0.5GiB/s 등이 포함됨
  • ais523의 x86-64+AVX2 assembly 답변은 단일 스레드 최대 성능을 노리며, 작성자 머신에서 약 31GiB/s, 질문자 집계에서 약 61GiB/s를 기록함
  • David Frank의 C++ 구현은 질문 본문 기준 현재 최고 점수로 약 1.7 Terrabit/s를 기록했으며, 별도 C++20 구현은 AMD Ryzen 9 7700X에서 283GB/s를 냈다고 밝힘

출력 규칙과 벤치마크 조건

  • 유효 출력 조건이 까다로움
    • 출력은 정확한 FizzBuzz여야 함
    • ASCII 문자당 1바이트여야 함
    • 줄바꿈은 \n만 허용됨
    • \r\n은 허용되지 않음
    • 출력은 최소 2^58 이상의 매우 큰 수까지 이어져야 함
  • 벤치마크 방식 자체도 처리량에 영향을 줌
    • pv와 Linux pipe buffer는 기본적으로 64K 버퍼를 쓰는 것으로 논의됨
    • CPU sibling core 배치에 따라 생성 프로그램과 소비 프로그램 사이의 L2 cache 경로가 달라질 수 있음
    • taskset으로 CPU 배치를 강제해 비교할 수 있음

assembly 구현의 최적화 방식

  • assembly 구현의 핵심은 계산보다 출력 복사 비용을 줄이는 데 있음
    • write를 쓰면 사용자 공간에서 커널 공간으로 복사하는 비용이 커짐
    • 작성자는 write 기반으로 바꾸면 성능이 5분의 1로 떨어진다고 적음
    • vmsplice로 pipe가 프로그램의 버퍼를 참조하게 만들어 복사를 줄임
  • FizzBuzz 계산은 3단계로 나뉨
    • 첫 단계는 초기 문자열을 하드코딩함
    • 두 번째 단계는 2~5자리 숫자를 비교적 직접적인 AVX2 루틴으로 처리함
    • 세 번째 단계는 6~18자리 구간을 FizzBuzz 바이트코드 인터프리터로 처리함
  • 세 번째 단계의 주 루프는 4클록 사이클당 64바이트 출력을 목표로 함
    • 바이트코드 1바이트가 출력 1바이트를 생성함
    • 32바이트 바이트코드를 로드하고 vpshufb, vpsubb 등으로 출력 32바이트를 만듦
    • 줄 번호는 근사값과 바이트코드 보정으로 처리해 매 줄마다 일반적인 숫자 변환을 하지 않음
  • 이 구현은 플랫폼 의존성이 큼
    • 오래되지 않은 Linux가 필요함
    • AVX2를 지원하는 x86-64 프로세서가 필요함
    • 표준 출력이 pipe가 아니면 시작 시 에러를 냄
    • splice가 끼는 파이프 구성에서는 잘못된 출력을 낼 수 있는 경우가 있다고 밝힘

다른 언어 구현들이 택한 공통 전략

  • C, Go, Java, Rust, Python, Julia, Ruby, C# 구현들도 비슷한 최적화 방향을 반복함
    • 15줄 FizzBuzz 패턴을 언롤함
    • 숫자 문자열 변환 횟수를 줄임
    • 큰 버퍼에 모아 씀
    • 스레드나 goroutine으로 생성 작업을 병렬화함
    • 출력 순서를 유지하기 위해 barrier, channel, queue, mutex를 사용함
  • 이 결과는 단순한 “언어 성능” 비교로 보기 어려움
    • pv 버전, pipe 크기, vmsplice 사용 가능 여부, CPU affinity, huge page, compiler 최적화, memcpy 인라인 여부가 처리량을 크게 바꿈
    • 일부 답변은 특정 머신에서 빠르지만, 다른 환경에서는 같은 수치를 재현하지 못했다는 댓글이 있음

다루지 않은 범위

  • 입력 노트에 일부 source chunk가 길이·비용 제한으로 생략됐다고 표시되어 있어, 전체 답변 46개와 모든 코드·댓글을 빠짐없이 다루지는 않음
  • 생략된 범위에는 일부 언어별 제출, 긴 코드 본문, 세부 튜닝 로그, 댓글 논의가 포함될 수 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • Linux가 한 프로그램에서 다른 프로그램으로 파이프된 데이터를 L2 캐시 안에만 머물게 하고 주 메모리를 건드리지 않을 수 있다는 점이 가장 인상적임
    평범한 Linux 커널의 여러 부분이 함께 맞물려 이런 빠른 경로가 가능해지는 건 놀라운 시스템 아키텍처 설계라고 봄
    Mac OSX의 Mach 포트나 Windows의 Named Pipes에서도 이런 일이 가능할지 궁금함

    • CPU 캐시가 물리 주소 태그를 쓰고, 두 프로세스의 페이지 테이블이 같은 물리 페이지를 공유한다면, 운영체제가 문맥 전환 때 캐시를 명시적으로 비우거나 무효화하지 않는 한 CPU는 어느 프로세스든 캐시 내용을 쓰게 해줌
    • 전체 고빈도 매매 업계가 Linux에서 돌아가는 많은 이유 중 하나임

  • “ais523 - high effort answers”라는 사용자명에 걸맞게, 프로그램을 실행하지 못한 사람에게도 상당히 공들인 댓글을 남겼고 결론은 이랬음
    “아마 프로그램이 어쩌다 ASLR이 켜진 상태로 컴파일된 것 같습니다. 이 경우 동적 링커가 BSS 세그먼트의 4MiB 정렬을 존중하지 않아 제 .align을 사실상 무시하고, 그게 버그의 원인이 되는 듯합니다”

    • 이 사람이 나와 같은 일자리에 지원하면 나는 승산이 없겠다는 것만은 알겠음. 궁극의 leet coder임

  • 이 글이 다시 올라올 때마다 이 댓글을 보고 웃게 됨
    “@chx: 저는 이미 석사 논문이 있습니다. 이게 더 어려웠습니다. – ais523 - high effort answers Oct 29, 2021 at 1:17”

  • Rust, Python3, C로 최적화 없이 단순 구현을 해봤음. 단순 if/else/while과 표준 출력 출력만 사용함
    Rust -> 23.2MiB/s
    Python3 -> 28.6MiB/s
    C -> 238MiB/s
    왜 Rust 성능이 Python3와 비슷한 범위인지 아는 사람이 있는지 궁금함. C에 더 가까울 줄 알았음

    • Rust의 print 함수는 기본적으로 잠금을 잡음. 안전성 때문이고, C는 그렇지 않음. 자세한 내용은 Rust 문서 참고: https://doc.rust-lang.org/std/macro.print.html
      C와 비슷한 성능을 내려면 이 잠금을 직접 다뤄야 할 가능성이 큼
      let mut lock = stdout().lock();
      write!(lock, "hello world").unwrap();
      그리고 표준 출력의 버퍼 크기도 C와 맞춰야 함
    • 오래전에 쓴 글인데 도움이 될 수 있음
      https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
    • C와 Python은 표준 출력에 적응형 버퍼링을 씀. 출력 대상이 터미널이면 줄바꿈마다 비우고, 아니면 내부 버퍼가 찰 때만 비움
      1ms 지연을 두고 숫자를 세는 C 프로그램에서 두 번째 열은 이전 read() 이후 경과 시간임
      $ ./out | rtss
      4.7ms 4.7ms | 1
      4.7ms | 2
      4.7ms | 3
      4.7ms | 4
      4.8ms exit status: 0
      한 번에 모두 기록된 걸 볼 수 있음. 터미널을 할당하면 줄마다 나옴
      $ rtss --pty ./out
      0.8ms 0.8ms | 1
      1.9ms 1.1ms | 2
      3.0ms 1.1ms | 3
      4.1ms 1.1ms | 4
      4.3ms exit status: 0
      Rust는 출력에 이런 적응형 동작이 없어서, 터미널 여부와 상관없이 항상 두 번째 결과처럼 동작함
      기술적으로는 표준 출력을 무조건 LineWriter(https://doc.rust-lang.org/std/io/struct.LineWriter.html)로 감싸며, 줄바꿈이 포함된 쓰기를 보면 항상 비움. 처리량을 최대화하려면 BufWriter로 감싸는 식으로 여러 줄을 묶어 써야 함
    • Rust는 --release로, C는 -O3로 컴파일해야 함
    • 거의 확실히 출력 때문에 제한이 걸린 것임. 아마 버퍼링이나 잠금 문제일 가능성이 큼

  • 모든 게 어셈블리로 작성됐다면 얼마나 빨랐을지 궁금해짐
    오디오 개발에서는 DSP 코드를 어셈블리로 작성하는 일이 매우 흔함

    • 이게 빠른 이유가 단순히 어셈블리라서인 건 아님. 이 해법에 필요하긴 하지만 결코 충분조건은 아님
      극단적인 알고리즘 연구, Linux 시스템 호출에 대한 깊은 지식, 플랫폼별 최적화가 결합되어야 이게 가능함. 작성자인 Alex Smith 본인의 말을 빌리면:
      “@chx: 저는 이미 석사 논문이 있습니다. 이게 더 어려웠습니다.”
      그냥 “어셈블리로 하면 됨”으로 만들 수 있는 것과는 전혀 다른 차원임
    • 전부 Java로만 작성됐어도, Python 인스턴스 안에 Chrome을 넣고 JavaScript 웹서버를 돌려 문서를 렌더링하는 지금 방식보다는 나았을 것임
    • 결국 Steve Yegge의 Geoworks 이야기처럼 될 것임
      “좋아요. 저는 University of Washington에 다니다가 Geoworks라는 회사에 취직해서 어셈블리 언어 프로그래밍을 5년 했습니다. 우리 Geoworker들은 운영체제 전체, 라이브러리, 드라이버, 앱, 그러니까 데스크톱 운영체제를 전부 어셈블리로 작성했습니다. 8086 어셈블리였죠! 심지어 좋은 어셈블리도 아니었습니다! 레지스터가 네 개뿐이었어요! 386까지 친다면 si 레지스터도 있었지만요. 끔찍했습니다.
      사실 우리는 꽤 좋아했습니다. 객체지향 어셈블리였거든요. 사람이 스스로를 설득해서 뭘 좋아하게 만들 수 있는지가 놀라운데, 이게 이 모든 일의 진짜 아이러니입니다. 우리에게 C++는 로마식 퇴폐의 극치였습니다. 더 먹으려고 토하러 가는 것과 같았죠. 그들은 IF가 있었습니다! 우리는 jump CX zero가 있었고요! 그들은 ‘객체’가 있었습니다. 우리도 있긴 했지만, 그들은 그걸 위한 문법이 있었죠. 정말 나약해 보였습니다. 그리고 당시에는 우리가 어떤 컴파일러보다도 빠른 코드를 만들 수 있다고 알았고, 실제로 그랬습니다!
      그래서 무슨 일이 있었을까요? 회사는 파산했습니다. 왜냐고요? 아마 저는 모든 Geoworker와 의견이 다를 겁니다. 실제로 제가 유일하게 이렇게 믿는다는 것도 압니다. 하지만 이유는 우리가 1,500만 줄의 8086 어셈블리 언어를 작성했기 때문입니다. 정말 좋은 도구, 세계적 수준의 도구가 있었고, 믿어도 됩니다. 그런 게 꼭 필요합니다. 하지만 어느 순간이 오면…
      문제는, 개미가 차고 바닥을 가로질러 직선으로 걸어가려는 모습을 상상해보라는 겁니다. 직선으로 못 갑니다. 우리는 시야가 넓으니 그걸 압니다. 개미가 돌아다니며 저 돌에 맞춰 국소 최적화하고, 이제 저쪽으로 가는 걸 볼 수 있죠.
      우리가 거대한 어셈블리 언어 시스템을 작성할 때 바로 그랬습니다. 결국 Microsoft가 우리 것보다 훨씬 빠른 모바일 기기 플랫폼을 냈습니다. 저는 디버거를 들고 들어가서, ‘뭐지? 왜 이러지? 렌더링이 정말 느린데, 버벅거리네’라고 했습니다. 들어가 보니 화면을 새로 고칠 때마다 어떤 제목 표시줄이 140번 렌더링되고 있었습니다. 제목 표시줄만 그런 것도 아니었습니다. 모든 것이 여러 번 호출되고 있었습니다.
      우리가 더 이상 시스템이 어떻게 동작하는지 볼 수 없었기 때문입니다!
      작은 시스템은 최적화하기 쉬울 뿐 아니라, 최적화가 가능합니다. 전역 최적화가 가능하다는 뜻입니다.”
      http://steve-yegge.blogspot.com/2008/05/dynamic-languages-st...
    • 어셈블리는 오늘날 작성되는 원본 코드와 너무 멀어져서 생각하기도 현실적이지 않음. 다만 소프트웨어를 만드는 회사들이 실제로 성능에 신경 쓴다면 모든 게 얼마나 빨라질지 상상해볼 만함
      오늘날 웹사이트와 소프트웨어의 99% 정도는 애플리케이션 성능에 조금만 신경 써도 기본적인 변경만으로 최소 50% 속도 향상을 달성할 수 있을 것 같음. 올바른 캐싱, 자산 최적화, 비대한 서드파티 라이브러리를 같은 일을 하는 기본 네이티브 호출로 대체, 서버와 데이터베이스의 적절한 설정 같은 것들임
      몇 년 안에 AI가 저장소에 원클릭 최적화를 제공해서 모범 사례를 적용하거나 원래 코드를 빠른 어셈블리로 다시 써줄 수 있을 것 같기도 함
    • 더 원시적인 언어가 더 빠른 프로그램을 낳는다는 얘기에서 자주 놓치는 세부점은, 코딩하면서 조금만 진전하기도 고통스러우면 최대한 적게 구현하려고 매우 애쓴다는 것임
      자원 제약은 초점의 명확함을 줄 수 있음

  • 이 실험은 재미있고 유익하긴 해도 약간 결함이 있어 보임. 복잡한 문제가 얼마나 빨리 해결되는지를 평가한다기보다, 한 프로세스에서 메모리를 꺼내 다른 프로세스로 넘기는 효율이라는 주변 문제를 주로 테스트함
    그래서 두 번째 프로세스가 계속 콘솔이나 파일에 쓰는 것처럼 보이지만, 기술적으로는 그렇지 않음. pv >/dev/null 실행은 본질적으로 아무 일도 안 하는 것에 가깝고, write 시스템 호출은 거의 즉시 반환됨
    vmsplice는 한 프로세스의 버퍼/메모리에 다른 프로세스가 접근하게 해주는 공유 메모리 상당의 기능임. 초기 대회 요구사항이 모호했을 가능성이 높아서 규칙상 괜찮은지는 불명확해 보임

    • 초기 요구사항이 모호했는지는 원래 질문으로 위쪽을 스크롤해 확인할 수 있고, 편집 이력을 보면 챌린지 시작 이후 바뀌지 않았다는 것도 확인할 수 있음
      “FizzBuzz 프로그램을 작성하세요. 실행하세요. 출력을 | pv > /dev/null로 파이프하세요. 처리량이 높을수록 잘한 겁니다.”
      “프로그램 출력은 정확히 유효한 fizzbuzz여야 합니다. 유효한 출력 사이에 null 바이트를 끼워 넣는 식의 속임수는 안 됩니다. 콘솔에는 보이지 않지만 pv 처리량에는 잡히는 null 바이트 같은 것 말입니다.”
      그리고 vmsplice(2)는 실제로 표준 출력 파이프에 바이트 스트림을 만들고, pv(1)가 그걸 /dev/null로 splice하거나 cat(1)이 터미널로 복사할 수 있음
      이 제출물만 vmsplice(2)를 쓴 것도 아님. 다른 제출자들도 이것이 결코 마법의 해결책이 아니라는 걸 알아냈음. 입출력 장벽을 넘고 나서도 출력 페이지를 최대한 빠르게 생성하는 작업이 많이 남아 있음
    • “한 프로세스에서 메모리를 꺼내 다른 프로세스로 넘기는 효율”이 거의 언제나 전체 문제 아닌가 싶음
      대부분의 코드는 메모리와 입출력에서 병목이 걸림. 복잡한 문제도 보통 데이터를 한 곳에서 다른 곳으로 옮기는 속도에 막히고, 데이터를 계산하는 데 막히는 경우는 드묾. GPU 어셈블리를 최적화하며 하루를 보내는 입장에서도, 드물게 계산이 병목인 경우조차 그걸 최적화하고 나면 메모리가 병목이 됨
    • 동의하지 않음. 먼저 상당한 FizzBuzz 특화 최적화를 하지 않고서는 병목이 “한 프로세스에서 메모리를 꺼내 다른 프로세스로 넘기는 효율”에 도달하지 못함
      예를 들어 10진수 자리올림이 자연스럽게 일어나도록 하는 영리한 비트 표현이 있음
      초기 대회 요구사항도 이 지점에서는 딱히 모호하지 않음. | pv > /dev/null로 처리량을 측정하라고 명시했고, 이렇게도 말함:
      “아키텍처별 최적화 / 어셈블리도 허용됩니다. 이건 진짜 대회가 아닙니다. 특수한 환경/플랫폼에서만 동작하더라도 사람들이 fizz buzz를 한계까지 밀어붙이는 걸 보고 싶을 뿐입니다.”
    • 입출력은 말 그대로 모든 프로그램이 해야 하는 일임. 현대 하드웨어에서 실행되는 코드의 99%가 여기서 병목이 걸리기도 함. 바이트를 한 곳에서 다른 곳으로 옮기는 일은 필수적이고 상대적으로 느림
      메모리 입출력과 파일 입출력을 성능 좋게 다루는 법을 이해하는 건 모든 프로그램과 프로그래머에게 관련 있는 기술임

  • fizzbuzz.S로 저장하라고 되어 있는데, 확장자 .S와 .s의 차이가 뭔지 궁금함

    • 대문자 S는 먼저 전처리기를 실행함
      매뉴얼 페이지 기준:
      file.s
      어셈블러 코드
      file.S
      file.sx
      전처리가 필요한 어셈블러 코드
    • 기억하기로는 전통적으로 입력을 전처리기에 통과시키는지(.S), 아닌지(.s)의 차이였음
      현대 도구 체인에서도 차이가 있는지는 잘 모르겠음
    • 내가 익숙한 관례에서는 .S를 사람이 직접 작성한 어셈블리 파일, 보통 git에 추적되는 파일로 쓰고, .s는 필요하면 덮어쓸 수 있는 기계 생성 어셈블리로 씀
    • GCC 등은 .S를 덮어쓰지 않지만, 어셈블리를 생성하라고 요청하면(예: gcc -S xyz.c) .s는 덮어씀

  • 이전 글:
    https://news.ycombinator.com/item?id=29031488
    https://news.ycombinator.com/item?id=29413656

  • 처음엔 55 GiB/s FritzBox라고 읽었음. FritzBox는 유럽 독일어권에서 인기 있는 라우터임
    내 ISP도 지난주에 곧 제공될 60 GiB/s 지원 OPNSense 박스[1]를 트윗했음
    [1] https://twitter.com/init7/status/1674920410889043973

    • 메모리를 16GB로 늘린 DEC750을 쓰고 있음. 10GbE 지원, WireGuard 2.3GbE 가능한 라우터가 조용하고 유휴 전력도 케이블 모뎀과 비슷한 8W라서 훌륭한 장비였고, 2030~2035년 전에는 교체할 생각이 없음
      USB WiFi 어댑터도 꽂아 두어서 케이블이 끊기면 특정 VLAN들이 장애 조치되고, 휴대폰을 써서 업무용 핵심 연결성을 유지함
      싸지는 않지만 OPNSense 프로젝트를 재정적으로 지원하면서 제대로 된 장비를 원한다면 Deciso 장비는 반박하기 어려움. 전력 효율이 좋고, 내구성 중심 부품을 쓰며, 그냥 잘 동작함
      상용 제품군이 더 강력해지는 걸 보니 좋음
답변달기