지루함 + 새로운 PC가 Rust에서 64배 빠른 Prime Sieve를 만들게 된 이야기 ('Dopamine optimization' 스토리)

Source: Dev.to

기원 이야기: “새 장난감”으로 시작되다

약 반년 전, 나는 책상에 앉아 코더의 블록에 심각하게 빠져 있었다. 기존 버그들을 파고들고 싶지 않았다; 승리가 필요했다. 도파민이 터지는 순간이 필요했다.

우연히도 나는 새로운(내게는) 거대한 워크스테이션을 바라보고 있었다: 4.3 GHz i7, 64 GB RAM, Quadro GPU. 그건 진짜 짐승이었고, 나는 아직 한 번도 제대로 활용해 본 적이 없다는 걸 깨달았다. 금속이 달궈지는 모습을 보고 싶었다. 팬이 돌게 만들고 싶었다.

그래서 도전을 설정했다: C++로 가능한 한 가장 빠르고, CPU를 가장 많이 쓰게 하는 코드를 작성하라. 수학이 무거우니 소수 생성에 착수했다. 에라토스테네스 체 최적화에 관한 논문을 찾고, SIMD 인트린식(AVX2/512)을 파고들며, 캐시 라인과 사이클 수에 미친 주말을 보냈다. 표준 라이브러리 구현을 이겨냈고, CPU 사용량이 100 %에 도달하는 모습을 지켜봤다… 그리고 그 순간, 도파민이 사라졌다.

“멋지다. 다음.”

코드를 선반에 올려두고 잊어버렸다.

회상

3일 전으로 돌아가 보자. 나는 Rust 프로젝트를 컴파일하면서 의존성 리스트가 스크롤되는 것을 보고 있었다:

Compiling rand...
Compiling primes...

그때 벽돌처럼 머리에 박혔다. 나는 먼지 쌓인 C++ 레포에 고도로 최적화되고 전투 테스트를 거친 소수 생성 로직 전체가 있다는 것을 깨달았다. 비트 트위들링, 캐시 지역성, 메모리 레이아웃 같은 어려운 부분은 이미 해결돼 있었다.

왜 Rust에서 사용하지 않았을까?

열광: Rust로 포팅

아이디어를 구현하기 전에 잃어버릴까 두려워서 12시간 코딩 광기에 빠졌다.

목표는 단순히 포팅이 아니라 재구상이었다. C++에서는 포인터를 날것대로 다루었다. Rust에서는 같은 성능을 유지하면서 안전성과 더 나은 인체공학을 원했다.

결과적으로 Primer라는 크레이트가 탄생했다. 이 크레이트는:

• 비트‑패킹: 홀수 하나당 1 비트 사용(실제로는 숫자당 0.5 비트).
• 홀수‑전용: 2는 하드코딩하고 짝수는 완전히 무시.
• 인트린식‑구동: trailing_zeros를 사용( x86에서는 tzcnt로 컴파일)해 체를 즉시 스캔.
• Kernighan‑반복: 하드웨어 수준에서 0을 건너뛴다.

결과: 64배 빠르고 95배 작다

Rust 컴파일러가 이렇게 친절하게 동작할 줄은 몰랐지만, 결과는 나를 놀라게 했다.

벤치마크 (n = 50,000,000)

• 표준 Vec 구현: 약 47 MB RAM
• Primer (세그먼트 버퍼): 약 32 KB RAM
• 속도: primes 크레이트의 대량 생성보다 최대 64배 빠름.

왜 중요한가 (속도 그 이상)

이 프로젝트는 소수가 필요해서 시작된 것이 아니다. 지루함과 컴퓨터가 작동하는 모습을 보고 싶다는 욕구에서 시작되었다.

때때로 최고의 코드는 티켓이나 명세서에서 나오지 않는다. 새벽 2시 깜빡이는 커서를 바라보며 “이걸 더 빠르게 만들 수 있을까?”라고 생각하고, 우연히 방 안에서 가장 빠른 것을 만들게 될 때 나온다.

GitHub에서 코드(및 벤치마크)를 확인해 보세요:

👉

(또한, 여러분이 임베디드 Rust 개발자—ESP32/Raspberry Pi—라면 이 32 KB 풋프린트는 바로 여러분을 위한 것이다. 마음껏 활용해 보라.)