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

최근 두 해의 자료구조 이론 결과 대부분은 라이브러리를 바꾸지 못했습니다. 이론이 계산하는 비용과 하드웨어의 실제 비용이 다르기 때문입니다.

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

지난 두 해 동안 자료구조 이론에서 수십 년간 풀리지 않았던 질문 여러 개가 해결됐습니다. 같은 기간 표준 라이브러리와 주요 오픈소스의 자료구조 구현은 거의 바뀌지 않았습니다. 이 차이를 정보 전달의 지연으로 설명할 수는 없습니다.

논문이 최적화하는 지표와 실행 시간을 결정하는 지표가 다르기 때문입니다.

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

여섯 결과 중 코드에 반영된 것은 마지막 하나입니다. 나머지 결과가 반영되지 않은 이유는 세 가지로 나눌 수 있습니다.

현실 밖에 놓인 교차점

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 안팎보다 낮습니다. 그 사이 구간의 안전성은 여전히 경험적 근거에 의존합니다. 이차 탐사 구현은 이론적으로 증명되지 않은 범위에서도 잘 동작하고 있습니다.

채택 전에 확인할 것

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

flowchart TD
    A[새 이론 결과] --> B{교차점 n이<br/>내 데이터 크기 안인가}
    B -->|아니다| X[보류<br/>SSSP, 정점 10의 67제곱]
    B -->|그렇다| C{개선한 지표가<br/>내 병목인가}
    C -->|아니다| Y[보류<br/>프로브 수 대 캐시 라인]
    C -->|그렇다| D{동시 접근이 있는가}
    D -->|있다| E{순차 모델 밖 비용을<br/>측정했는가}
    D -->|없다| F{늘어난 비용이<br/>어느 단계에 붙는가}
    E -->|아니다| Y
    E -->|그렇다| F
    F -->|백그라운드 구성| G[채택<br/>Ribbon 필터]
    F -->|질의 경로| H[절감분과 상쇄되는지 재측정]

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

앞의 세 항목은 이론 결과의 성질이고, 뒤의 두 항목은 적용할 코드베이스의 성질입니다. 앞의 항목을 충족하지 못하면 추가 연구 결과를 기다려야 합니다. 뒤의 항목을 충족하지 못하면 도입 방식을 다시 설계하는 편이 빠릅니다.

정리

2025년 이후 자료구조 이론은 개방 주소법의 최적 경계, 동적 필터의 공간 하한, 정렬 장벽 돌파까지 오래 열려 있던 질문을 연달아 닫았습니다. 그 결과가 라이브러리로 넘어오지 못한 이유는 세 가지입니다. 교차점이 현실적인 데이터 크기 밖에 있거나, 개선한 지표가 실행 시간을 지배하는 지표와 다르거나, 순차 복잡도 모델에 락 대기가 아예 없기 때문입니다.

반대로 Ribbon filter와 SNG 파라미터 규칙처럼 인터페이스를 유지하고 늘어난 비용을 백그라운드 단계에 몰아넣은 결과는 실제로 코드에 들어갔습니다. 새 결과를 볼 때는 개선폭보다 교차점의 위치와 비용이 붙는 단계를 먼저 확인하면 됩니다.