생물학자에게서 훔친 알고리즘으로 Haskell 컴파일러를 빠르게 만든 이야기

컴파일러와 DNA 분석이 만나면

제목이 좀 이상하죠? "생물학자에게서 훔쳤다"니. 한 개발자가 Haskell 컴파일러(GHC)의 빌드 속도를 개선하는 과정에서, 생물정보학(bioinformatics)에서 쓰이는 알고리즘을 가져와서 적용했다는 이야기예요. 분야를 넘나드는 알고리즘 차용 사례 중에서도 꽤 흥미로운 케이스라서, 컴파일러 내부에 관심 있는 분들이라면 재미있게 읽으실 만해요.

배경부터 짚어볼게요. Haskell은 함수형 프로그래밍 언어인데, 컴파일 시간이 느린 걸로 악명이 높아요. 큰 프로젝트는 처음 빌드하는 데 30분~1시간씩 걸리기도 하죠. 그래서 GHC 팀과 커뮤니티는 컴파일 속도를 줄이는 데 항상 신경을 쓰고 있어요. 이 글에서 다루는 최적화는 모듈 의존성 그래프를 처리하는 부분입니다.

문제가 뭐였냐면

Haskell 프로젝트는 여러 모듈(.hs 파일)로 나뉘어 있고, 모듈끼리 import로 서로 참조해요. 컴파일러는 일단 "누가 누구를 import하는지" 그래프를 만들어야 해요. 그래야 어떤 순서로 컴파일할지 결정할 수 있거든요. 의존성이 없는 것끼리는 병렬로 컴파일할 수도 있고요.

그런데 이 의존성 그래프를 분석하는 과정에서 사이클(순환 참조)을 찾고, 강한 연결 요소(SCC, Strongly Connected Components)를 계산해야 해요. 이게 뭐냐면, A가 B를 쓰고 B도 A를 쓰는 식으로 서로 얽혀 있는 모듈 그룹을 찾아내는 작업이에요. 이런 그룹은 한 덩어리로 같이 컴파일해야 하거든요.

기존 GHC는 이 작업을 위해 타잔(Tarjan) 알고리즘을 썼어요. 그래프 이론에서 SCC를 찾는 고전적인 방법인데, 시간 복잡도는 O(V+E)로 이론상 최적이에요. 그런데 글쓴이가 GHC를 프로파일링해보니까, 큰 프로젝트에서 이 SCC 계산이 전체 시간의 상당 부분을 잡아먹고 있더라는 거예요. 왜? 모듈 수가 수천 개 단위로 가면, 알고리즘의 점근적 복잡도보다 상수 인자(constant factor)가 중요해지기 시작합니다. 캐시 효율, 메모리 할당, 자료구조 선택 같은 실제 구현의 디테일이 큰 차이를 만든다는 거예요.

생물학에서 빌려온 아이디어

여기서 글쓴이는 생물정보학 분야의 그래프 알고리즘에 눈을 돌렸어요. 왜 생물학이냐고요? 유전체 분석(genome assembly)에서는 어마어마하게 큰 그래프를 다뤄야 하거든요. de Bruijn 그래프라는 게 있는데, 짧은 DNA 조각들을 이어붙여서 전체 게놈을 복원할 때 쓰는 자료구조예요. 노드가 수십억 개 단위가 되기도 합니다. 그러다 보니 생물정보학자들은 그래프 알고리즘의 "실전 효율"을 극한까지 짜내는 데 도가 텄어요.

그쪽 분야에서 자주 쓰는 기법 중 하나가 반복 작업을 줄이기 위한 캐시 친화적인 자료구조예요. 예를 들면 인접 리스트(adjacency list)를 단순히 포인터로 연결하는 게 아니라, 연속된 메모리 배열(CSR, Compressed Sparse Row 형식)로 저장해서 CPU 캐시가 잘 작동하도록 만드는 거죠. 또 SCC를 찾을 때도 재귀 호출 대신 명시적 스택을 쓰거나, 방문 표시를 비트맵으로 압축해서 메모리 접근을 줄이는 기법들이 있어요.

글쓴이는 이런 아이디어들을 GHC의 모듈 그래프 처리에 적용했어요. Haskell이라는 게 "우아한 자료구조"를 좋아하는 언어지만, 정작 컴파일러 내부의 핫 패스(hot path)에서는 좀 더 저수준으로 내려가서 메모리 레이아웃을 신경 써야 한다는 거였죠. 결과적으로 SCC 계산 시간이 의미 있게 줄었고, 큰 Haskell 프로젝트의 전체 컴파일 시간도 체감할 만큼 개선됐다는 보고예요.

다른 분야의 알고리즘이 컴파일러에 들어온 사례들

사실 이런 "분야 횡단" 알고리즘 차용은 컴파일러 역사에서 종종 있어왔어요. 레지스터 할당(register allocation) 문제는 그래프 채색 문제로 환원되는데, 이건 원래 지도 채색 같은 조합론 문제에서 나온 거였죠. 링커의 심볼 해석 알고리즘은 데이터베이스의 해시 조인 기법을 차용한 경우가 많고요. LLVM의 별칭 분석(alias analysis)은 한때 정적 프로그램 분석 학계의 포인터 분석 연구를 통째로 흡수했어요.

생물정보학 쪽에서는 또 다른 흥미로운 사례가 있어요. suffix array라는 자료구조는 원래 DNA 서열 검색을 위해 발전했는데, 이게 정규표현식 엔진과 컴파일러의 문자열 처리에 도입돼서 큰 성능 향상을 가져왔어요. 또 BLAST 같은 서열 정렬 알고리즘의 아이디어가 코드 클론 탐지(code clone detection)에 적용되기도 했고요.

반대로 컴파일러에서 생물학으로 간 사례도 있어요. LLVM의 SSA(Static Single Assignment) 폼이 유전자 발현 분석에 응용되거나, 추상 해석(abstract interpretation)이 생화학 반응 네트워크 분석에 쓰이는 식이에요. 결국 "그래프 위에서 정보를 전파한다"는 기본 문제는 분야가 달라도 같으니까요.

한국 개발자에게 주는 시사점

이 글의 직접적인 실용성은 Haskell을 쓰는 분들에게만 해당될 수 있어요. 한국에 Haskell로 프로덕션 코드 작성하는 회사가 많진 않으니까요. 그런데 이 글이 던지는 더 큰 교훈이 있어요.

첫째, 점근적 복잡도가 같다고 끝이 아니다라는 점이에요. O(N) 알고리즘 두 개가 있어도, 캐시 효율이나 분기 예측, 메모리 할당 패턴 같은 "숨겨진 상수"에 따라 실제 성능은 10배 이상 차이가 날 수 있어요. 빅오 표기법에만 의존하지 말고 실제 프로파일링을 해봐야 한다는 교훈이죠.

둘째, 다른 분야의 솔루션을 의도적으로 찾아볼 가치가 있다는 거예요. 우리가 다루는 문제가 정말 새로운 경우는 드물어요. 누군가가, 다른 분야에서, 비슷한 문제를 이미 풀어놨을 가능성이 높아요. 그래프 문제는 운영 연구(operations research)나 사회 네트워크 분석, 생물정보학 같은 곳에서 미친 듯이 연구돼 있고, 그쪽 논문 한두 편만 읽어도 새로운 아이디어를 얻을 때가 많습니다.

셋째, 본인이 쓰는 도구의 내부를 한 번씩 들여다보는 경험이 정말 도움이 돼요. 컴파일러, 런타임, 데이터베이스, 브라우저 엔진 — 이런 "블랙박스"를 한 번이라도 열어보고 "아, 여기는 이렇게 동작하는구나"를 체감하면, 평소에 코드 짤 때 직관이 달라져요. Haskell 컴파일러까지는 아니더라도, 본인이 좋아하는 오픈소스 프로젝트의 소스를 한 번 둘러보세요.

마무리

결국 이 글은 "알고리즘은 분야의 경계를 넘는다"는 오래된 진실을 다시 한번 보여주는 사례예요. 30년 전 생물학자들이 짠 그래프 알고리즘이 오늘날 함수형 언어 컴파일러를 빠르게 만들고 있다니, 좀 낭만적이지 않나요?

여러분은 어떠세요? 본인 분야가 아닌 곳에서 아이디어를 빌려와 문제를 해결해본 경험이 있으세요? 혹은 평소에 "이건 다른 곳에서도 풀고 있는 문제 같은데"라고 느낄 때, 어디서 답을 찾으시나요?