32비트 모든 소수 구하기: 알고리즘 최적화와 엔지니어링의 함정

주말에 재미삼아 시작한 토이 프로젝트가 어느새 극한의 성능 최적화 챌린지로 변모하는 경험, 시니어 엔지니어라면 누구나 한 번쯤 있을 겁니다. 이번에 Hacker News에서 흥미로운 글을 하나 발견했습니다. 32비트 unsigned int 범위 내의 모든 소수(Prime number)를 찾아내어 바이너리 파일로 저장하는 C 프로그램 작성기입니다.

단순해 보이지만 32비트 최대값은 약 42억 9천만이고, 그 안에는 약 2억 3백만 개의 소수가 존재합니다. 이를 어떻게 가장 빨리 찾을 것인가는 컴퓨팅 역사상 가장 클래식한 문제 중 하나죠. 원작자의 접근 방식과 삽질, 그리고 HN 커뮤니티의 피드백을 보면서 우리가 실무에서 겪는 최적화의 함정과 해결책에 대해 이야기해 볼까 합니다.

1. Trial Division: 순진한 접근법

가장 무식하고 직관적인 방법은 Trial Division(시험 나눗셈)입니다. 어떤 수 n이 소수인지 확인하기 위해 루트 n 이하의 모든 소수로 나누어 보는 것이죠.

bool is_prime(uint32_t n, uint32_t* primes) {
    for (size_t i=0; ; i++) {
        uint32_t p = primes[i];
        if (n % p == 0) return false;
        if (p >= 0xFFFF || p*p >= n) return true;
    }
}

원작자의 환경(Framework Laptop 13)에서 이 방식은 약 24분 20초가 걸렸습니다. 알고리즘 시간 복잡도는 최악의 경우 O(N√N/log N) 수준입니다. 실무에서 이런 코드를 대용량 데이터 처리 PR로 올린다면 바로 반려될 수준의 성능입니다.

2. Wheel Factorization의 함정

성능을 개선하기 위해 원작자는 Wheel Factorization(바퀴 인수분해)을 도입합니다. 2, 3, 5의 배수처럼 뻔히 소수가 아닌 수들을 미리 걸러내는 기법입니다. 이를 통해 검사해야 할 후보군을 전체 자연수의 20% 수준으로 줄일 수 있습니다.

결과가 어땠을까요? 23분 30초. 고작 50초 줄었습니다.

솔직히 이 부분에서 약간 헛웃음이 났습니다. 제가 주니어 시절에 자주 하던 실수와 정확히 일치하기 때문입니다. 후보군을 80%나 줄였는데 왜 성능 향상은 미미할까요? 우리가 스킵한 80%의 숫자들은 어차피 2, 3, 5로 한 번만 나누어보면 바로 Composite(합성수) 판정이 나는, 연산 비용이 극도로 저렴한 케이스들이기 때문입니다. 복잡한 Wheel 자료구조를 메모리에 올리고 분기를 태우는 오버헤드가, 값싼 연산을 스킵해서 얻는 이득을 다 잡아먹은 겁니다. 전형적인 마이크로 최적화의 함정입니다.

3. Sieve of Eratosthenes와 메모리 트레이드오프

결국 연산 위주의 접근을 버리고 메모리를 활용하는 에라토스테네스의 체(Sieve of Eratosthenes)로 넘어갑니다. 42억 개의 boolean 배열이 필요하니 1바이트씩 쓰면 4.3GB라는 엄청난 메모리를 먹게 됩니다. 이를 해결하기 위해 Bit Array를 구현하여 메모리 사용량을 537MB로 압축합니다.

struct BitArray list = bitarray_init( (size_t) 0xFFFFFFFF );
bitarray_set(&list, 0, true);
bitarray_set(&list, 1, true);

for (uint32_t p = 2; p <= 0xFFFF && p*p <= 0xFFFFFFFF; p++) {
    if (bitarray_get(list, p)) continue;
    for (size_t i=2; i <= 0xFFFFFFFF / p; i++) {
        bitarray_set(&list, i*p, true);
    }
}

이 방식의 실행 시간은 무려 32초입니다. 이전 대비 40배 이상의 성능 향상입니다. CPU가 일일이 나누기 연산을 하는 대신, 메모리에 순차적으로 접근하며 비트 플립만 수행하기 때문에 압도적으로 빠릅니다.

하지만 제 기준에서 이 코드도 완벽한 프로덕션 레벨은 아닙니다. 537MB의 비트 배열과 815MB의 소수 저장용 배열이 동시에 메모리에 올라가 총 1.3GB를 점유합니다. L1/L2 Cache 크기를 아득히 벗어나는 거대한 메모리 접근은 필연적으로 Cache Miss를 유발하여 성능을 깎아먹게 됩니다.

4. Hacker News의 통찰: 진짜 고수들의 방식

HN 스레드에서도 이 점을 정확히 지적하는 고수들이 많았습니다. 커뮤니티에서 언급된 몇 가지 핵심 대안들을 살펴보겠습니다.

  • Segmented Sieve: 메모리 사용량을 획기적으로 줄이는 기법입니다. 전체 범위를 CPU 캐시에 쏙 들어가는 작은 Chunk로 나누어 처리하면, 메모리 풋프린트도 줄고 Cache Hit Ratio가 극대화되어 Throughput이 비약적으로 상승합니다.
  • Miller-Rabin Test: 기본적으로는 확률론적 소수 판별법이지만, 특정 Base 집합을 사용하면 64비트 이하의 수에 대해서는 100% 결정론적으로 동작함이 증명되어 있습니다. 굳이 전체 소수를 체로 거를 필요 없이 단일 숫자의 소수 여부를 확인할 때 압도적으로 유리합니다.
  • IO Bottleneck: 결국 이 프로그램의 최종 목적은 파일에 쓰는 것입니다. 계산이 아무리 빨라져도 800MB가 넘는 데이터를 Disk에 쓰는 IO 시간이 전체 Latency의 병목이 될 수밖에 없습니다. 누군가 지적했듯 파일 쓰기 대신 표준 출력(stdout)을 파이프라인으로 넘기는 구조가 시스템 최적화 관점에서는 훨씬 유연합니다.

결론 (Verdict)

원작자의 글은 알고리즘 최적화의 단계를 밟아가는 훌륭한 튜토리얼입니다. 하지만 진짜 극한의 성능을 원한다면, 단순히 알고리즘의 시간 복잡도(Big-O)를 줄이는 것을 넘어 하드웨어의 특성 즉 Cache Line, Branch Prediction, Memory Bandwidth를 뼈저리게 이해해야 합니다.

가장 빠른 코드는 가장 적은 명령어를 실행하는 코드가 아니라, CPU가 가장 좋아하는 방식으로 데이터에 접근하는 코드입니다. 여러분의 다음 시스템 최적화 작업에서도 이 점을 꼭 기억하시길 바랍니다.

References