Daniel Lemire가 말한 저수준 하드웨어 최적화와는 별개로, 이진 탐색이나 그 구현 변형이 최선인 경우는 데이터가 정렬/단조라는 사실 외에 아무것도 모를 때뿐임
데이터 분포에 대한 사전 정보가 있으면 그 정보를 써서 훨씬 더 빠른 알고리즘을 만들 수 있음. 종이 사전에서 사람이 순수한 이진 탐색보다 더 빨리 적당한 페이지 묶음으로 이동하는 것이 예시임
수학적으로 정렬 리스트 검색은 닫힌 루프 제어 알고리즘으로 단조 함수의 역함수를 찾는 일에 가깝고, 비용 함수를 만들어 경사 하강법이나 가속 변형을 쓸 수도 있음. 더 일반적으로는 지나치게 추상화된 표현의 해법을 가져오기보다, 풀려는 특정 문제에 대한 정보를 더 쓰는 편이 항상 더 효율적이며, 하드웨어를 더 잘 써서 얻는 상수배 개선보다 훨씬 큰 확장 가능한 속도 향상을 줄 수 있음
반복 횟수가 고정된 이진 탐색
고정 반복 횟수는 분기 예측기에 좋고, 핵심 루프도 대상 하드웨어에 맞게 곱셈을 피하며 꽤 빡빡하게 최적화돼 있음. 더 영리하게 만들려는 시도는 루프를 악화시켰고 이득을 못 냈음. 구조체 배열 형식에 크기가 12이고, 대체로 N이 작아서 어렵기도 함
트립(treap)에 관한 글을 읽은 기억이 있는데, 트리 균형을 맞추는 대신 가중치를 써서 허프만 인코딩처럼 탐색 깊이를 조정하고, 접근 빈도가 다른 경우 평균 접근 시간을 줄이는 방식이었음
북마크를 안 해둬서 1년에 두 번쯤 다시 찾고 있음. 전설에 따르면 아직도 찾는 중임
맞지만, 핵심은 데이터를 더 알 수 없는 경우가 많다는 것임
그래서 데이터베이스에서는 B-트리가 표준임. 데이터는 무엇이든 될 수 있고, 새 행을 대량으로 가져오면 특성이 언제든 크게 바뀔 수 있음
경사 하강법 같은 방식으로 조회를 가속하는 알고리즘을 만들 수는 있지만, B-트리는 이미 매우 빠르고 최악 성능과 I/O 요구량 예측 가능성, 범위 스캔, 정렬 순회, 접두 조건 지원 같은 장점도 많음
특정 데이터 분포에 더 효율적인 조회 알고리즘은 만들 수 있지만, 중요한 속성을 잃는 경우가 많음. 다른 알고리즘이 더 가까운 초기 추정을 내더라도 마지막 항목을 찾는 데 느릴 수 있고, 평균은 빨라도 최악 성능이 너무 나빠서 못 쓸 수도 있음
종이 사전에서도 첫 추정 이후에는 거의 이진 탐색을 썼고, 그 초기 추정으로 줄어드는 단계는 몇 번뿐임. 적당한 페이지 묶음에 도달한 뒤에는 필요한 것보다 선형적으로 훑는 편인데, 엄격한 이진 탐색을 하면 더 빠를 수도 있지만 페이지 넘기는 시간과도 균형을 맞춰야 함
“풀려는 특정 문제에 대한 정보를 더 쓰는 것이 더 효율적”이라는 말은 뻔하면서도 깊음. 이미 가진 정보가 많을수록, 이미 가진 정보가 많은 셈임
“4분 탐색”은 결국 이진 탐색 루프를 한 단계 펼친 것 아닌가? 항목이 있는 구간을 찾으려면 비교 횟수는 대략 비슷하고, 한 번에 2개가 아니라 4개씩 처리하는 것처럼 보임. 루프 펼치기로도 같은 효과가 날 것 같음
그보다 더 까다로움. 현대 프로세서는 추측 실행을 해서 비교 결과를 예측하고, 틀렸다는 걸 알거나 내부 한계에 닿을 때까지 한쪽 분기를 계속 진행함. 틀리면 추측 작업을 버리고 몇 사이클 페널티를 낸 뒤 다른 시작점에서 다시 함
사실상 프로세서 관점에서는 모든 루프가 이미 어느 정도 펼쳐져 있고, 루프 자체의 작은 오버헤드만 남음. 이진 탐색에서 주된 비용은 메모리나 캐시에서 데이터를 가져오는 것이므로, 실제 싸움은 나중에 필요할 데이터를 최대한 일찍 요청하게 만들어 도착을 덜 기다리는 것임
4분 탐색 같은 알고리즘의 차이는 각 분기의 한쪽만 깊게 미리 가져오는 대신, 가능한 모든 경우를 얕게 프리페치한다는 데 있음. 결국 필요할 프리페치는 반드시 발행되고, 실제 실행 경로에서 쓰지 않을 데이터에 대역폭을 조금 덜 쓰게 됨
검색 알고리즘의 실제 성능을 예측하려면 “비교 횟수”는 거의 쓸모없는 지표임. 병목은 비교를 얼마나 많이 할 수 있느냐가 아니라 메모리와 캐시 대역폭을 최대한 활용하느냐에 달려 있음. 현대 프로세서의 분기 동작을 내부까지 고려한다면 루프 펼치기로 볼 수도 있음
이건 루프를 조금 펼친 것으로 볼 수 있음. 성능이 좋아지는 이유는 명령 수나 메모리 읽기를 크게 줄여서가 아니라, 연산 간 의존성을 완화해 순수 직렬 실행을 피하기 때문임. 분기의 양쪽을 추측 실행하는 것과 비슷하게 볼 수도 있음
4분 탐색은 사실상 현재 반복의 비교와 동시에 다음 반복에서 가능할 두 비교를 함께 수행함. 단순한 루프 펼치기보다는 조금 더 복잡함
어쨌든 두 탐색 모두 상수가 다른 O(log N)임. 알고리즘 수업에서는 상수가 별로 중요하지 않지만 현실에서는 꽤 크게 작용할 수 있음
지수 탐색은 순차 ID로 리소스를 주소 지정하는 REST API에서 마지막 ID가 필요하지만 전용 엔드포인트가 없을 때 유용함
HEAD /users/1 -> 200 OK
HEAD /users/2 -> 200 OK
HEAD /users/4 -> 200 OK
...
HEAD /users/2048 -> 200 OK
HEAD /users/4096 -> 404 Not Found
그런 다음 2048과 4096 사이를 이진 탐색하면 가장 최근 사용자와 부수적으로 사용자 수를 찾을 수 있음. 경쟁 SaaS 회사를 조사할 때 알면 좋은 정보임
CPU는 항상 캐시 라인 전체, 보통 64바이트를 한 번에 접근하니 캐시 라인 전체를 검색하는 편이 낫겠음. 데이터가 CPU 안에 올라온 뒤에는 사실상 공짜에 가까움
그래서 “이진” 탐색에서 가운데 캐시 라인의 모든 값을 검사하고, 일치하는 값이 없으면 왼쪽/오른쪽으로 가는 방식을 시도해보고 싶음. 캐시 라인 검색은 512비트 SIMD 명령 하나로 가능함. 캐시 라인 64바이트는 16비트 정수 32개이므로, 단순 이진 탐색보다 거의 32배 빠를 수도 있고, 적어도 메모리 접근은 32배 줄어들어 현실적인 프로그램 대부분에서 지배적일 것임
이진 탐색 트리, 즉 정렬 벡터의 위쪽 캐시 라인에서 목표값을 찾을 가능성은 낮음. 대신 라인 안의 추가 데이터를 이용해 탐색 범위를 줄이는 편이 좋고, 그러면 B-트리나 B+트리로 이어짐
4바이트 키와 4바이트 자식 포인터, 또는 배열 인덱스를 쓰면 내부 노드는 키 7개, 자식 포인터 8개, 다음 포인터 1개로 64바이트 캐시 라인을 꽉 채울 수 있음. 100만 항목에서 트리 깊이는 약 20에서 약 7로 줄고, 위쪽 몇 단계는 캐시에 남아 있을 가능성이 큼
조금 고민하면 SIMD로 B-트리 노드 내부 검색을 빠르게 할 수 있지만, 데이터 의존성이 매우 큼
더 작은 배열이라면 끝에 센티널 값을 둔 선형 탐색은 이미 이기기 어려움. 다만 이 주장이 애매한 이유는 “작다”가 너무 흐릿한 조건이라 체감하기 어렵다는 데 있음
그건 사실이 아님. 이 글의 훌륭한 벤치마크를 보면 선형 탐색은 대략 200~400개 원소 부근에서 뒤처짐
전반적으로 이 글은 마음에 듦. 평소 궁금했던 점을 유용한 제거 실험까지 곁들여 완벽하게 탐구했음
이 글이 다루는 내용은 그게 아님
작은 배열, 16~32개 항목에서 검색 실험을 조금 해봤는데 이진 탐색은 분기가 많아서 최악의 방법 중 하나였음. 작은 배열에서 가장 빠른 방법은 분기 없는 선형 탐색이었음
루프를 중간에 끊지 않고 모든 원소를 훑는 방식임. 예를 들어 배열에 어떤 수가 있는지 알고 싶다면 모든 항목의 검사 결과를 논리 OR로 합침. SIMD는 쓰지 않았지만, 작은 배열에서는 분기가 매우 비싸서 분기 없이 모든 원소를 그냥 검사하는 편이 더 빠름
프리페처가 좋아하는 접근 패턴이라 더 빠른 건지 궁금함
알고리즘 설명이 조금 헷갈렸음 SIMD 부분은 마지막 단계, 즉 마지막 16개 원소를 검색할 때만 쓰임
4분 탐색 부분은 3개 지점을 검사해서 4개 경로를 만드는 것이지만, 단순히 올바른 키가 아니라 올바른 블록을 찾고 있음
세부가 흥미로운데, 작성자는 각 블록의 마지막 원소를 4분 탐색에 사용함. 첫 원소를 쓰거나 임의의 원소를 쓰면 알고리즘이 어떻게 바뀔지 궁금함
여기의 핵심 직관인 SIMD 다중 비교는 마지막 단계보다 더 큰 규모에도 쓸 수 있어 보임
개요는 이렇다: a) gather로 균등 간격 16곳에서 여러 원소를 가져옴 b) SIMD 명령으로 병렬 비교 c) 올바른 블록에 집중 d) 블록이 작으면 선형 탐색으로 전환하고, 아니면 gather/비교 주기를 반복함
gather 명령은 비연속 메모리에서 읽고, 이진 탐색이라면 필요하지 않을 만큼 더 많이 읽긴 함. 그래도 다방향 비교가 가능해지고 이진 탐색 4단계를 접을 수 있다면 큰 테이블에서는 이길 수 있을 듯함
모든 자료형에서 완전한 16방향 비교가 가능한 것도 아님. float64 검색은 AVX-512에서도 8방향 비교로 제한되지만, int32와 float32는 16방향 비교가 가능함
gather는 극도로 느림. 효율을 노리는 사람이라면 gather를 피할 것임
gather 기반 방식보다 이진 탐색이 실제로 더 빠를 가능성이 높다고 봄
고전적인 컴퓨터 과학 알고리즘은 사실상 병렬성이 없는 CPU를 대상으로 “설계”된 셈임. 여러 코어, Hyper-threading, SIMD 명령 같은 병렬성이 없고, 모든 메모리 접근 시간이 같아서 L1/L2/L3 캐시 지연 같은 개념도 없으며, 일반적/무작위 데이터를 다룬다는 가정임
이 가정 중 하나라도 벗어나면 성능을 높일 수 있는 조정이 많이 생김
고전 알고리즘은 특정 데이터 형태나 특정 CPU의 특성/기능을 더 알게 된 뒤 더 최적화된 해법을 개발하기 위한 매우 좋은 출발점을 제공함
최적화의 뾰족한 끝까지 가면 보통 데이터가 메모리에 어떻게 저장되고 접근되는지, 그리고 이를 개선하는 변경이 이후 단계에 해를 끼치지 않는지를 보게 됨. 오래전 직장에서 누군가 코드의 특정 부분을 너무 오래 최적화했는데, 그 최적화 때문에 나중에 필요한 많은 정보가 캐시에서 밀려나 전체 애플리케이션은 더 느려진 일이 있었음
이는 아마 Rob Pike의 프로그래밍 5번째 규칙, 다시 말해 _The Mythical Man Month_에서 Fred Brooks가 한 말을 재진술한 것에 가까움. 참고: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
십대 때 주말 내내, 이진 탐색이 매 단계 탐색 공간을 절반으로 줄여서 좋다면 삼진 탐색은 3분의 1씩 줄이니 더 낫지 않을까 생각했음
가운데 값 하나만 비교하는 대신 1/3 지점 값을 비교하고, 너무 낮으면 2/3 지점 값을 비교하는 방식임
하지만 각 단계에서 이진 탐색의 1/2 대신 1/3로 줄이는 반면, 비교는 평균 3/2배 한다고 생각해서 결국 같다고 봤음
수정: zamadatix 답변을 보니 실제로는 2/3의 경우 비교를 2번 해야 하므로 평균 5/3배임
이 삼진 접근은 실제로 단계당 평균 비교 횟수가 3/2가 아님
첫 1/3: 비교 1번
둘째 1/3: 비교 2번
셋째 1/3: 비교 2번
(1+2+2)/3 = 평균 5/3번 비교임. “비교를 1번 하거나 2번 한다”는 느낌 때문에 50%로 착각하기 쉽지만, 실제로는 첫 비교에서 걸릴 확률이 1/3이고, 2번 비교할 확률이 2/3임
그래서 총 평균 비교 횟수에서 삼진 탐색이 아주 조금 더 나쁨을 보일 수 있음: 5/3*Log_3[n] = 1.052... * Log_2[n]
즉 단계 수는 줄지만 끝까지 가기 위해 평균적으로 더 많은 비교를 하게 됨. 이건 이런 유형의 모든 탐색, 즉 분할 수가 2보다 큰 경우에 대체로 성립함. 물론 찾는 값이 균등 분포하고 연산 비용이 이상화돼 있다는 몇 가지 가정이 있고, 바로 이 지점에서 본문 글의 논의가 들어옴
알고 보니 십대 시절의 그 생각에도 뭔가가 있었음
이진 탐색 알고리즘의 삼진 버전으로서는 아님. 그건 실제 삼진 탐색이 아니라 치우친 이진 탐색에 가깝기 때문임. 비교는 본질적으로 이진이므로, 비교를 포함하는 탐색 알고리즘은 모두 일종의 이진 탐색이고, 가운데 원소가 아닌 선택은 알고리즘 복잡도 측면에서 덜 효율적임. 다만 실제 하드웨어에서는 어떤 조건에서 더 나을 수도 있음. 진짜 삼진 탐색을 하려면 기본 연산으로 3방향 비교가 필요함
흥미로워지는 지점은 “기수 효율”[1]을 고려할 때임. 최선의 선택은 e에 가장 가까운 자연수인 3임. 트리 탐색과도 관련이 있어서, 삼진 트리가 이진 트리보다 나을 수 있음
[1] https://en.wikipedia.org/wiki/Optimal_radix_choice
빠른 탐색이 불가능한 디스크 같은 곳에서는 예를 들어 128방향 B-트리를 쓸 수 있음. 키 128개를 가져오는 비용은 1개를 가져오는 것보다 크게 비싸지 않지만, 추가로 7번의 가져오기를 줄여줌
그 다음에는 삼진 비교기를 포함한 CPU를 상상했나?
십대 시절 이후 CPU는 실행 폭과 벡터 기능 양쪽에서 극적으로 넓어졌음. 처리량이 늘면서, 의존성 사슬을 줄이기 위해 연산을 더 태우는 쪽으로 균형이 이동함
그래서 그 아이디어가 당시 CPU에서는 실현성이 없었지만 지금 CPU에서는 더 가능성이 높아졌을 수 있음
Hacker News 의견들
Daniel Lemire가 말한 저수준 하드웨어 최적화와는 별개로, 이진 탐색이나 그 구현 변형이 최선인 경우는 데이터가 정렬/단조라는 사실 외에 아무것도 모를 때뿐임
데이터 분포에 대한 사전 정보가 있으면 그 정보를 써서 훨씬 더 빠른 알고리즘을 만들 수 있음. 종이 사전에서 사람이 순수한 이진 탐색보다 더 빨리 적당한 페이지 묶음으로 이동하는 것이 예시임
수학적으로 정렬 리스트 검색은 닫힌 루프 제어 알고리즘으로 단조 함수의 역함수를 찾는 일에 가깝고, 비용 함수를 만들어 경사 하강법이나 가속 변형을 쓸 수도 있음. 더 일반적으로는 지나치게 추상화된 표현의 해법을 가져오기보다, 풀려는 특정 문제에 대한 정보를 더 쓰는 편이 항상 더 효율적이며, 하드웨어를 더 잘 써서 얻는 상수배 개선보다 훨씬 큰 확장 가능한 속도 향상을 줄 수 있음
고정 반복 횟수는 분기 예측기에 좋고, 핵심 루프도 대상 하드웨어에 맞게 곱셈을 피하며 꽤 빡빡하게 최적화돼 있음. 더 영리하게 만들려는 시도는 루프를 악화시켰고 이득을 못 냈음. 구조체 배열 형식에 크기가 12이고, 대체로 N이 작아서 어렵기도 함
북마크를 안 해둬서 1년에 두 번쯤 다시 찾고 있음. 전설에 따르면 아직도 찾는 중임
그래서 데이터베이스에서는 B-트리가 표준임. 데이터는 무엇이든 될 수 있고, 새 행을 대량으로 가져오면 특성이 언제든 크게 바뀔 수 있음
경사 하강법 같은 방식으로 조회를 가속하는 알고리즘을 만들 수는 있지만, B-트리는 이미 매우 빠르고 최악 성능과 I/O 요구량 예측 가능성, 범위 스캔, 정렬 순회, 접두 조건 지원 같은 장점도 많음
특정 데이터 분포에 더 효율적인 조회 알고리즘은 만들 수 있지만, 중요한 속성을 잃는 경우가 많음. 다른 알고리즘이 더 가까운 초기 추정을 내더라도 마지막 항목을 찾는 데 느릴 수 있고, 평균은 빨라도 최악 성능이 너무 나빠서 못 쓸 수도 있음
종이 사전에서도 첫 추정 이후에는 거의 이진 탐색을 썼고, 그 초기 추정으로 줄어드는 단계는 몇 번뿐임. 적당한 페이지 묶음에 도달한 뒤에는 필요한 것보다 선형적으로 훑는 편인데, 엄격한 이진 탐색을 하면 더 빠를 수도 있지만 페이지 넘기는 시간과도 균형을 맞춰야 함
Ed Kmett은 그 아이디어를 Haskell용 discrimination[2] 라이브러리로 다듬었고, 관련 기술 발표[3]도 매우 흥미로움
[1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
[2]: https://hackage.haskell.org/package/discrimination
[3]: https://www.youtube.com/watch?v=cB8DapKQz-I
“4분 탐색”은 결국 이진 탐색 루프를 한 단계 펼친 것 아닌가? 항목이 있는 구간을 찾으려면 비교 횟수는 대략 비슷하고, 한 번에 2개가 아니라 4개씩 처리하는 것처럼 보임. 루프 펼치기로도 같은 효과가 날 것 같음
사실상 프로세서 관점에서는 모든 루프가 이미 어느 정도 펼쳐져 있고, 루프 자체의 작은 오버헤드만 남음. 이진 탐색에서 주된 비용은 메모리나 캐시에서 데이터를 가져오는 것이므로, 실제 싸움은 나중에 필요할 데이터를 최대한 일찍 요청하게 만들어 도착을 덜 기다리는 것임
4분 탐색 같은 알고리즘의 차이는 각 분기의 한쪽만 깊게 미리 가져오는 대신, 가능한 모든 경우를 얕게 프리페치한다는 데 있음. 결국 필요할 프리페치는 반드시 발행되고, 실제 실행 경로에서 쓰지 않을 데이터에 대역폭을 조금 덜 쓰게 됨
검색 알고리즘의 실제 성능을 예측하려면 “비교 횟수”는 거의 쓸모없는 지표임. 병목은 비교를 얼마나 많이 할 수 있느냐가 아니라 메모리와 캐시 대역폭을 최대한 활용하느냐에 달려 있음. 현대 프로세서의 분기 동작을 내부까지 고려한다면 루프 펼치기로 볼 수도 있음
어쨌든 두 탐색 모두 상수가 다른 O(log N)임. 알고리즘 수업에서는 상수가 별로 중요하지 않지만 현실에서는 꽤 크게 작용할 수 있음
최근에 지수 탐색[2]에 대해서도 글[1]을 썼음. 찾는 원소들 자체가 정렬된 상태로 배열에서 반복적으로 이진 탐색해야 할 때 쓸 수 있는 알고리즘이고, 우리 작업 부하에서는 8배 속도 향상이 나왔음
[1] https://lalitm.com/post/exponential-search/
[2] https://en.wikipedia.org/wiki/Exponential_search
HEAD /users/1 -> 200 OK
HEAD /users/2 -> 200 OK
HEAD /users/4 -> 200 OK
...
HEAD /users/2048 -> 200 OK
HEAD /users/4096 -> 404 Not Found
그런 다음 2048과 4096 사이를 이진 탐색하면 가장 최근 사용자와 부수적으로 사용자 수를 찾을 수 있음. 경쟁 SaaS 회사를 조사할 때 알면 좋은 정보임
CPU는 항상 캐시 라인 전체, 보통 64바이트를 한 번에 접근하니 캐시 라인 전체를 검색하는 편이 낫겠음. 데이터가 CPU 안에 올라온 뒤에는 사실상 공짜에 가까움
그래서 “이진” 탐색에서 가운데 캐시 라인의 모든 값을 검사하고, 일치하는 값이 없으면 왼쪽/오른쪽으로 가는 방식을 시도해보고 싶음. 캐시 라인 검색은 512비트 SIMD 명령 하나로 가능함. 캐시 라인 64바이트는 16비트 정수 32개이므로, 단순 이진 탐색보다 거의 32배 빠를 수도 있고, 적어도 메모리 접근은 32배 줄어들어 현실적인 프로그램 대부분에서 지배적일 것임
4바이트 키와 4바이트 자식 포인터, 또는 배열 인덱스를 쓰면 내부 노드는 키 7개, 자식 포인터 8개, 다음 포인터 1개로 64바이트 캐시 라인을 꽉 채울 수 있음. 100만 항목에서 트리 깊이는 약 20에서 약 7로 줄고, 위쪽 몇 단계는 캐시에 남아 있을 가능성이 큼
조금 고민하면 SIMD로 B-트리 노드 내부 검색을 빠르게 할 수 있지만, 데이터 의존성이 매우 큼
더 작은 배열이라면 끝에 센티널 값을 둔 선형 탐색은 이미 이기기 어려움. 다만 이 주장이 애매한 이유는 “작다”가 너무 흐릿한 조건이라 체감하기 어렵다는 데 있음
전반적으로 이 글은 마음에 듦. 평소 궁금했던 점을 유용한 제거 실험까지 곁들여 완벽하게 탐구했음
작은 배열, 16~32개 항목에서 검색 실험을 조금 해봤는데 이진 탐색은 분기가 많아서 최악의 방법 중 하나였음. 작은 배열에서 가장 빠른 방법은 분기 없는 선형 탐색이었음
루프를 중간에 끊지 않고 모든 원소를 훑는 방식임. 예를 들어 배열에 어떤 수가 있는지 알고 싶다면 모든 항목의 검사 결과를 논리 OR로 합침. SIMD는 쓰지 않았지만, 작은 배열에서는 분기가 매우 비싸서 분기 없이 모든 원소를 그냥 검사하는 편이 더 빠름
알고리즘 설명이 조금 헷갈렸음
SIMD 부분은 마지막 단계, 즉 마지막 16개 원소를 검색할 때만 쓰임
4분 탐색 부분은 3개 지점을 검사해서 4개 경로를 만드는 것이지만, 단순히 올바른 키가 아니라 올바른 블록을 찾고 있음
세부가 흥미로운데, 작성자는 각 블록의 마지막 원소를 4분 탐색에 사용함. 첫 원소를 쓰거나 임의의 원소를 쓰면 알고리즘이 어떻게 바뀔지 궁금함
여기의 핵심 직관인 SIMD 다중 비교는 마지막 단계보다 더 큰 규모에도 쓸 수 있어 보임
개요는 이렇다: a) gather로 균등 간격 16곳에서 여러 원소를 가져옴 b) SIMD 명령으로 병렬 비교 c) 올바른 블록에 집중 d) 블록이 작으면 선형 탐색으로 전환하고, 아니면 gather/비교 주기를 반복함
gather 명령은 비연속 메모리에서 읽고, 이진 탐색이라면 필요하지 않을 만큼 더 많이 읽긴 함. 그래도 다방향 비교가 가능해지고 이진 탐색 4단계를 접을 수 있다면 큰 테이블에서는 이길 수 있을 듯함
모든 자료형에서 완전한 16방향 비교가 가능한 것도 아님. float64 검색은 AVX-512에서도 8방향 비교로 제한되지만, int32와 float32는 16방향 비교가 가능함
gather 기반 방식보다 이진 탐색이 실제로 더 빠를 가능성이 높다고 봄
고전적인 컴퓨터 과학 알고리즘은 사실상 병렬성이 없는 CPU를 대상으로 “설계”된 셈임. 여러 코어, Hyper-threading, SIMD 명령 같은 병렬성이 없고, 모든 메모리 접근 시간이 같아서 L1/L2/L3 캐시 지연 같은 개념도 없으며, 일반적/무작위 데이터를 다룬다는 가정임
이 가정 중 하나라도 벗어나면 성능을 높일 수 있는 조정이 많이 생김
고전 알고리즘은 특정 데이터 형태나 특정 CPU의 특성/기능을 더 알게 된 뒤 더 최적화된 해법을 개발하기 위한 매우 좋은 출발점을 제공함
최적화의 뾰족한 끝까지 가면 보통 데이터가 메모리에 어떻게 저장되고 접근되는지, 그리고 이를 개선하는 변경이 이후 단계에 해를 끼치지 않는지를 보게 됨. 오래전 직장에서 누군가 코드의 특정 부분을 너무 오래 최적화했는데, 그 최적화 때문에 나중에 필요한 많은 정보가 캐시에서 밀려나 전체 애플리케이션은 더 느려진 일이 있었음
이는 아마 Rob Pike의 프로그래밍 5번째 규칙, 다시 말해 _The Mythical Man Month_에서 Fred Brooks가 한 말을 재진술한 것에 가까움. 참고: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
십대 때 주말 내내, 이진 탐색이 매 단계 탐색 공간을 절반으로 줄여서 좋다면 삼진 탐색은 3분의 1씩 줄이니 더 낫지 않을까 생각했음
가운데 값 하나만 비교하는 대신 1/3 지점 값을 비교하고, 너무 낮으면 2/3 지점 값을 비교하는 방식임
하지만 각 단계에서 이진 탐색의 1/2 대신 1/3로 줄이는 반면, 비교는 평균 3/2배 한다고 생각해서 결국 같다고 봤음
수정: zamadatix 답변을 보니 실제로는 2/3의 경우 비교를 2번 해야 하므로 평균 5/3배임
첫 1/3: 비교 1번
둘째 1/3: 비교 2번
셋째 1/3: 비교 2번
(1+2+2)/3 = 평균 5/3번 비교임. “비교를 1번 하거나 2번 한다”는 느낌 때문에 50%로 착각하기 쉽지만, 실제로는 첫 비교에서 걸릴 확률이 1/3이고, 2번 비교할 확률이 2/3임
그래서 총 평균 비교 횟수에서 삼진 탐색이 아주 조금 더 나쁨을 보일 수 있음: 5/3*Log_3[n] = 1.052... * Log_2[n]
즉 단계 수는 줄지만 끝까지 가기 위해 평균적으로 더 많은 비교를 하게 됨. 이건 이런 유형의 모든 탐색, 즉 분할 수가 2보다 큰 경우에 대체로 성립함. 물론 찾는 값이 균등 분포하고 연산 비용이 이상화돼 있다는 몇 가지 가정이 있고, 바로 이 지점에서 본문 글의 논의가 들어옴
이진 탐색 알고리즘의 삼진 버전으로서는 아님. 그건 실제 삼진 탐색이 아니라 치우친 이진 탐색에 가깝기 때문임. 비교는 본질적으로 이진이므로, 비교를 포함하는 탐색 알고리즘은 모두 일종의 이진 탐색이고, 가운데 원소가 아닌 선택은 알고리즘 복잡도 측면에서 덜 효율적임. 다만 실제 하드웨어에서는 어떤 조건에서 더 나을 수도 있음. 진짜 삼진 탐색을 하려면 기본 연산으로 3방향 비교가 필요함
흥미로워지는 지점은 “기수 효율”[1]을 고려할 때임. 최선의 선택은 e에 가장 가까운 자연수인 3임. 트리 탐색과도 관련이 있어서, 삼진 트리가 이진 트리보다 나을 수 있음
[1] https://en.wikipedia.org/wiki/Optimal_radix_choice
그래서 그 아이디어가 당시 CPU에서는 실현성이 없었지만 지금 CPU에서는 더 가능성이 높아졌을 수 있음