자료구조 이론과 라이브러리 사이의 격차

최근 두 해의 자료구조 이론 결과 대부분은 라이브러리를 바꾸지 못했습니다. 구현자의 관성이 아니라, 이론이 세는 비용과 하드웨어가 치르는 비용이 다르기 때문입니다.

확정된 이론과 그대로인 코드

지난 두 해 사이 자료구조 이론에서 수십 년간 열려 있던 질문 여러 개가 닫혔습니다. 같은 기간 표준 라이브러리와 주요 오픈소스의 자료구조 구현은 거의 바뀌지 않았습니다. 이 격차를 정보 지연으로 설명하면 틀립니다. 논문이 최적화하는 양과 실행 시간을 지배하는 양이 애초에 다르기 때문입니다.

무엇이 확정됐는지부터 정리합니다. 개별 자료구조의 동작 원리는 자료구조에 따로 정리해 두었습니다.

여섯 건 중 코드에 닿은 것은 마지막 하나입니다. 나머지가 왜 멈춰 섰는지를 세 갈래로 나눠 보면 각각 다른 이유가 나옵니다.

현실 밖에 놓인 교차점

Duan 등(2025)은 단일 출발점 최단경로(Single-Source Shortest Path, SSSP)를 푸는 새 알고리즘을 냈습니다. 비교-가산 모델에서 $O(m\log^{2/3}n)$ 시간에 도는 결정론적 알고리즘입니다. 여기서 n은 정점 수, m은 간선 수입니다. 다익스트라의 $O(m+n\log n)$이 이 문제의 하한이 아니라는 것이 이 결과로 처음 증명됐습니다. 2026년 2월 후속 논문은 같은 전제에서 희소 그래프 기준 $O(m\sqrt{\log n\log\log n})$까지 줄였습니다.

Castro, Clementino, de Freitas는 2025년 알고리즘을 C++로 구현해 다익스트라와 비교했습니다(arXiv:2511.03007, 2026-09 기준). 희소 무작위 그래프, 격자, 미국 도로망에서 정점 1000만 개까지 측정한 결과 다익스트라가 모든 경우에 3~4배 빨랐습니다. 논문은 최악 시간 보장을 지키는 구현이 다익스트라를 앞서려면 정점 수가 $10^{67}$을 크게 넘어야 한다고 추정합니다.

여기서 읽어야 할 것은 두 알고리즘의 우열이 아니라 교차점의 위치입니다. 점근 우위는 n이 충분히 클 때만 나타나는데, 그 충분히가 어디인지를 빅오 표기는 감춥니다. 상수 인자가 크면 교차점이 물리적으로 도달할 수 없는 크기로 밀려나고, 그러면 이론적 우위는 코드 선택에 아무 정보도 주지 않습니다.

이론이 세는 비용과 하드웨어가 치르는 비용

Farach-Colton, Krapivin, Kuszmaul(2025)은 원소를 재배치하지 않는 개방 주소법에서 일래스틱 해싱을 제시했습니다. 삽입 프로브가 분할상환 $O(1)$, 최악 기대 $O(\log\delta^{-1})$입니다. δ는 남은 여유 공간의 비율입니다. 같은 논문이 하한도 함께 증명해 두 값이 맞물리고, 그 과정에서 균등 해싱이 최적이라는 Yao의 추측이 반증됐습니다.

그런데 널리 쓰이는 해시 테이블 구현은 여전히 선형 탐사와 이차 탐사에 머물러 있습니다. 프로브 수가 비용 자체가 아니라 비용의 대리 지표이기 때문입니다. 선형 탐사에서 연속한 프로브는 대개 같은 캐시 라인 안에 떨어지므로, 프로브를 몇 번 더 해도 메모리 접근은 한 번으로 끝납니다.

Guo, Pettie, Wan(2026)은 이 사정을 논문 첫머리에서 그대로 인정합니다. 이차 탐사가 매력적인 이유는 참조 지역성이 높으면서 탐색당 프로브 수가 적다는 데 있는데, 이것이 경험적 관찰일 뿐 이론적 보장은 아니었다고 적습니다. 이들은 프로브 충돌의 연쇄를 트리로 기록하는 증거 포레스트 기법을 도입했습니다. 임의의 고정 오프셋 수열은 로드팩터 35.74%까지, 이차 탐사는 37.61%까지 삽입당 상수 기대 비용을 가진다는 것이 결론입니다.

일래스틱 해싱은 배열을 여러 구간으로 나누고 구간마다 다른 삽입 규칙을 적용합니다. 프로브가 어느 구간으로 떨어질지 미리 알 수 없어 연속 프로브의 지역성을 기대하기 어렵습니다. 프로브 수 지표에서 이긴 구조가 캐시 라인 지표에서는 질 수 있다는 뜻인데, 두 논문 모두 캐시 미스를 측정하지 않았으므로 이 대목은 추정입니다.

순차 모델에 없는 락 대기

캐시 교체 알고리즘은 오랫동안 미스율 하나로 평가됐습니다. 그 기준에서 LRU는 FIFO보다 낫고, 이 비교는 단일 스레드 모델 안에서 성립합니다. 문제는 LRU가 히트마다 공유 순서 리스트의 머리로 객체를 옮긴다는 점입니다. 읽기 경로에 쓰기 잠금이 걸리므로 스레드를 늘려도 처리량이 비례해 늘지 않습니다.

S3-FIFO 저자들의 보고에 따르면 16스레드에서 S3-FIFO는 최적화된 LRU 구현 대비 약 6배 높은 처리량을 냈습니다. SIEVE는 큐 하나와 손가락 포인터만으로 같은 효과를 내면서 16스레드에서 LRU와 TwoQ 대비 두 배 넘는 처리량을 기록했습니다. 이 차이는 미스율 계산 어디에도 등장하지 않습니다. 구조의 세부는 LRU를 대체하는 FIFO 캐시 축출에 정리해 두었습니다.

방향이 앞의 두 사례와 반대라는 점이 중요합니다. 이론이 앞서고 실무가 따라가지 않은 것이 아니라, 실무가 쓰던 단순한 구조가 이론적으로 열등해 보였고 나중에 평가 기준 쪽이 틀렸다는 것이 드러났습니다. 격차는 이론이 실무를 앞설 때만 생기지 않습니다.

이론이 코드로 넘어온 경우

격차가 항상 남지는 않습니다. Ribbon filter는 정적 필터의 공간 오버헤드를 정보이론적 하한 근처까지 줄인 결과입니다. RocksDB는 버전 6.15부터 이를 Bloom filter 대신 고를 수 있는 정책으로 제공합니다.

RocksDB 팀은 두 필터의 비용을 직접 계산해 공개했습니다. 오탐률 1% 기준으로 Bloom은 키당 약 10비트, Ribbon은 약 7비트를 씁니다. 대신 구성 비용이 키당 32ns에서 140ns로, 조회가 500ns에서 600ns로 늘어납니다. 팀은 하드웨어 가격과 전력 단가를 대입해 손익분기를 계산했고, 필터가 메모리에 한 시간 넘게 남으면 Ribbon이 싸다는 결론을 냈습니다.

넘어올 수 있었던 조건은 세 가지로 읽힙니다. 인터페이스가 같아서 정책 객체만 교체하면 되고, 늘어난 비용이 컴팩션이라는 백그라운드 단계에 몰리며, 절감분은 상시 상주하는 메모리에서 발생합니다. SIEVE가 다섯 개 오픈소스 캐시 라이브러리에 평균 20줄 미만의 변경으로 이식된 것도 같은 성질 덕분입니다.

세 번째 사례는 알고리즘이 아니라 파라미터를 바꾼 경우입니다. Ma 등(2025)은 Sparse Neighborhood Graph(SNG) 구성 과정을 마팅게일로 모델링했습니다. 이 모델로 최대 차수 $O(n^{2/3+\epsilon})$과 기대 탐색 경로 길이 $O(\log n)$을 증명했습니다.

이어서 그래프 희소화를 제어하는 절단 파라미터의 닫힌 형태 선택 규칙을 유도했고, 파라미터 sweep이 사라지면서 인덱스 구축이 평균 5.9배, 최대 15.4배 빨라졌습니다. 그래프 구조는 그대로 두고 튜닝 절차만 대체했기 때문에 적용 비용이 낮았습니다. 배경은 그래프 기반 근사 최근접 탐색의 복잡도에 있습니다.

이 주장이 서지 않는 곳

이 글의 근거는 논문 여섯 편과 구현 보고 두 건입니다. 라이브러리 채택률을 조사한 것이 아니므로 거의 바뀌지 않았다는 표현은 사례 관찰이지 통계가 아닙니다.

SSSP 실측도 독립 구현 하나에 기댄 결과입니다. 논문 스스로 상수 인자를 실질적으로 줄여야 이 결과가 기존 기법을 대체할 수 있다고 적었고, 이는 알고리즘이 영영 쓸모없다는 뜻이 아닙니다.

애초에 격차를 물으면 안 되는 결과도 있습니다. 지문 필터 최적성 증명(FOCS 2025)은 코드를 바꾸라는 결과가 아니라 바꿀 이유가 없다는 결과입니다. Kuszmaul, Liang, Zhou는 ε이 0으로 갈 때의 동적 필터 하한을 $n\log\varepsilon^{-1}+n\log e-o(n)$ 비트로 확정했습니다. 1978년 Carter 등이 도입한 지문 기법이 이 하한을 그대로 달성합니다. 이 계보는 쿠쿠 해싱과 지문 필터에 정리해 두었습니다.

이론 쪽에 격차가 남은 경우도 있습니다. 증명된 로드팩터 37.61%는 실무에서 흔히 쓰는 0.7 안팎에 한참 못 미치고, 그 사이 구간은 여전히 경험적으로만 안전합니다. 이차 탐사를 쓰는 코드는 증명이 닿지 않는 영역에서 잘 돌고 있는 셈입니다.

채택 전에 확인할 것

새 이론 결과를 코드에 넣을지 정할 때는 순서가 있습니다. 앞의 사례들을 조건으로 바꾸면 다음 흐름이 됩니다.

각 분기에서 무엇을 보는지 표로 옮기면 이렇습니다.

다섯 항목 중 앞 세 개는 이론 결과 자체의 성질이고, 뒤 두 개는 내 코드베이스의 성질입니다. 앞쪽에서 걸리면 결과를 기다리는 것이 맞고, 뒤쪽에서 걸리면 도입 방식을 다시 설계하는 편이 빠릅니다.

정리

2025년 이후 자료구조 이론은 개방 주소법의 최적 경계, 동적 필터의 공간 하한, 정렬 장벽 돌파까지 오래 열려 있던 질문을 연달아 닫았습니다. 그 결과가 라이브러리로 넘어오지 못한 이유는 세 가지입니다. 교차점이 현실적인 데이터 크기 밖에 있거나, 개선한 지표가 실행 시간을 지배하는 지표와 다르거나, 순차 복잡도 모델에 락 대기가 아예 없기 때문입니다. 반대로 Ribbon filter와 SNG 파라미터 규칙처럼 인터페이스를 유지하고 늘어난 비용을 백그라운드 단계에 몰아넣은 결과는 실제로 코드에 들어갔습니다. 새 결과를 볼 때는 개선폭보다 교차점의 위치와 비용이 붙는 단계를 먼저 확인하면 됩니다.