마인크래프트 구조물 탐색기에서 배우는 최적화의 기술: 무식한 브루트 포스에 우아함 한 스푼 더하기

엔지니어로 15년 넘게 일하면서 가장 짜릿한 순간 중 하나는, 도저히 끝날 것 같지 않던 대규모 데이터 처리 작업의 실행 시간을 몇 달에서 몇 시간으로, 다시 몇 초로 줄여냈을 때입니다. 최근 Hacker News에서 제 눈길을 끈 흥미로운 아티클이 하나 있었습니다. 겉보기엔 그저 ‘마인크래프트 맵 구조물 탐색기’를 만든 이야기 같지만, 그 속을 들여다보면 고성능 컴퓨팅(HPC)과 백엔드 시스템 최적화에 그대로 적용할 수 있는 보석 같은 기법들이 가득합니다.

이 글은 단순히 코드를 빠르게 만들었다는 뻔한 무용담이 아닙니다. 알고리즘의 복잡도를 낮추는 휴리스틱부터, 메모리 Locality, SIMD를 활용한 벡터화, 그리고 부동소수점 연산 제거까지. 시니어 엔지니어라면 반드시 숙지해야 할 최적화의 정석을 보여줍니다.

완벽함을 버리고 Throughput을 취하다

마인크래프트 세계는 무한에 가깝습니다. 목표는 ‘베드락 감옥(Bedrock prison)‘이라 불리는 탈출 불가능한 지형을 찾는 것입니다. 3D 공간을 전부 탐색하는 것은 컴퓨팅 리소스 낭비입니다. 저자는 이를 2D 문제로 치환하고, DFS(깊이 우선 탐색)를 활용해 닫힌 공간을 찾습니다.

여기서 첫 번째 통찰이 나옵니다. 저자는 복잡한 형태의 감옥을 완벽하게 찾아내는 대신, 탐색하기 쉬운 단순한 형태만 필터링하는 방식을 택합니다.

탐색 공간은 무한하므로, 계산하기 어려운 후보군을 건너뛰어도 상관없습니다. 중요한 것은 초당 얼마나 많은 감옥을 찾아낼 수 있는가 하는 Throughput 입니다.

솔직히 이 대목에서 박수를 쳤습니다. 주니어 시절에는 엣지 케이스를 모두 커버하는 완벽한 알고리즘을 짜느라 병목을 만드는 경우가 많습니다. 하지만 대규모 분산 시스템에서는 100%의 정확도보다 99%의 정확도를 10배 빠르게 처리하는 Trade-off 가 훨씬 가치 있는 경우가 많습니다.

상태 관리와 메모리 최적화: Broken Profile 기법

기본적인 DFS는 visited 라는 HashSet에 방문한 노드를 기록합니다. 하지만 맵이 거대해지면 메모리는 순식간에 고갈됩니다. 저자는 전체 맵의 상태를 유지하는 대신, 탐색 중인 현재 행과 이전 행의 데이터만 유지하는 방식을 사용합니다.

for z in -WORLD_BORDER..=WORLD_BORDER {
    for x in -WORLD_BORDER..=WORLD_BORDER {
        if !visited.contains(&(x, z)) {
            region_size = 0;
            if dfs((x, z)).is_ok() {
                // 성공!
            }
        }
        visited.remove(&(x, z - 1)); // 이전 행의 데이터를 즉시 삭제
    }
}

이러한 Broken profile 기법은 동적 계획법(DP) 최적화에서 종종 쓰이는 패턴입니다. 불필요한 과거 상태를 즉시 메모리에서 해제하여 Cache locality를 극대화하는 훌륭한 접근입니다.

부동소수점 연산 걷어내기

비디오 게임이나 절차적 생성 로직에서는 Float 연산이 난무합니다. 마인크래프트의 베드락 생성 로직도 예외는 아닙니다. 하지만 Float는 느리고, 정밀도 문제를 일으킵니다.

저자는 이 로직을 수학적으로 분석하여, 런타임에 Float 연산을 수행하는 대신 컴파일 타임에 확률을 상수로 계산하고 정수 비트 연산으로 치환해 버립니다.

// 최적화된 Integer 연산 로직
prng.next_bits(24) < (probability * 2f64.powi(24)).ceil() as u64

이건 정말 클래식하면서도 우아한 최적화입니다. 금융 시스템이나 코어 백엔드 시스템에서도 Float 대신 Decimal이나 Integer로 단위를 변환해 처리하는 것이 국룰이죠. CPU 사이클을 아끼는 것은 물론, 아키텍처 간 비결정적(Non-deterministic) 버그를 원천 차단할 수 있습니다.

AVX-512와 벡터화

이 프로젝트의 백미는 단연 SIMD 활용입니다. 저자는 단순히 반복문을 돌리는 대신, 8개의 셀을 한 번에 검사하도록 로직을 벡터화했습니다. 이 과정에서 is_interior 검사를 일괄 수행하고, 유효한 비트만 추출하기 위해 x &= x - 1 이라는 고전적인 비트 트릭을 사용합니다.

for coords in diagonals() {
    // is_interior는 이제 비트마스크를 반환합니다.
    for coords_index in BitIter::from(is_interior(coords)) {
        let coords = coords[coords_index];
        visited.clear();
        // DFS 수행...
    }
}

보통 백엔드 개발을 하다 보면 SIMD 영역까지 내려갈 일이 많지 않다고 생각하지만, 대용량 JSON 파싱이나 데이터베이스 엔진 내부에서는 이미 광범위하게 쓰이고 있는 기술입니다. Rust의 Portable SIMD를 활용해 Unsafe 코드 없이 깔끔하게 구현해 낸 점이 매우 인상적입니다.

Coarse Filtering과 로컬 Bitset

모든 후보군에 대해 무거운 DFS를 돌리는 대신, 저자는 빠른 경로(Fast path)를 도입합니다. 위험 요소를 벽으로 간주하고 대략적인 크기를 먼저 잰 뒤, 일정 크기 이상일 때만 정밀 검사를 수행하는 방식입니다. 또한, 무거운 범용 HashSet 대신 [u32; 32] 형태의 고정 크기 로컬 Bitset을 스택에 올려 사용했습니다.

  • Cache Locality: 힙 할당을 피하고 스택 메모리를 사용하여 L1 캐시 히트율을 극대화합니다.
  • Bounds Checking: 비트 마스킹을 통해 배열 인덱스 초과로 인한 패닉을 방지하고, 오버플로우 발생 시에만 HashSet으로 Fallback 하는 전략을 취했습니다.

이러한 낙관적 락(Optimistic Lock)과 유사한 접근 방식은, 시스템 최적화에서 90%의 일반적인 케이스를 압도적으로 빠르게 처리하고 10%의 예외 케이스만 무겁게 처리하는 전형적이고 효과적인 패턴입니다.

Principal Engineer의 시선: 결론 및 평가

Hacker News 커뮤니티는 이런 류의 하드코어한 바닥부터의 최적화 이야기에 열광합니다. 최근 AI가 짜준 뻔한 보일러플레이트 코드와 튜토리얼이 범람하는 가운데, 이런 장인정신이 깃든 엔지니어링 블로그 글은 가뭄에 단비 같습니다.

개인적으로 이 글에서 가장 높게 평가하는 부분은 최적화의 순서 입니다. 저자는 무턱대고 어셈블리를 뜯어보거나 SIMD를 적용하지 않았습니다. 먼저 문제의 정의를 비틀어 알고리즘 복잡도를 낮추고, 자료구조를 캐시 친화적으로 변경한 뒤, 마지막으로 CPU 아키텍처의 이점을 쥐어짜 냈습니다.

이 프로젝트는 장난감 맵 탐색기일지 모르지만, 여기서 사용된 기법들은 초당 수백만 건의 트래픽을 처리하는 Ad-Tech 시스템이나 고빈도 매매 엔진을 구축할 때 제가 직접 사용했던 기법들과 정확히 일치합니다.

당장 내일 회사에 가서 느려터진 레거시 시스템에 더 큰 AWS EC2 인스턴스를 갖다 붙이기 전에, 한 번쯤 자문해 보시길 바랍니다. 과연 우리는 데이터의 특성을 제대로 이해하고 자료구조를 최적화했는가? 아니면 그냥 프레임워크가 제공하는 기본 자료구조에 의존하고 있는가? 최상의 코드는 더 빠른 코드가 아니라, 실행할 필요가 없는 코드를 없애는 것에서 시작합니다.