GN⁺: 가장 빠른 브랜치리스 바이너리 검색

• 이 기사는 표준 std::lower_bound 함수보다 두 배 빠르고 짧은 일반 이진 검색 C++ 구현에 대해 논의합니다.
• 새로운 구현은 분기/조건부 점프보다 조건부 이동 명령어로 컴파일되기 때문에 "분기 없음"입니다.
• 이진 검색은 정렬된 목록을 중간 항목에서 두 부분으로 나누고, 중간 값을 주어진 값과 비교하는 방식으로 작동합니다. 비교 결과에 따라 어느 두 목록 중에서 계속 찾을지 결정합니다.
• 이 기사는 또한 분기 예측이라는 개념에 대해 논의합니다. 이는 프로세서가 명령어를 병렬로 실행하여 속도를 높이는 기술입니다. 그러나 이진 검색은 예측할 수 없기 때문에 분기 예측은 이상적이지 않습니다.
• 저자는 표준 구현과 branchless_lower_bound 버전보다 빠른 새로운 이진 검색 구현, sb_lower_bound를 소개합니다. 이는 루프 내의 명령어가 훨씬 적기 때문에 더 빠릅니다.
• 저자는 또한 검색 목록을 분할하는 다른 방법을 사용하는 더 빠른 버전, bb_lower_bound를 제시합니다.
• 이 기사는 프로그램의 가장 느린 부분이 프로세서가 예측할 수 없는 검색 및/또는 비교를 포함한다면, clang을 -mllvm -x86-cmov-converter=false와 함께 사용해 보라고 제안으로 마무리합니다. 더 빠른 이진 검색이 필요하다면 sb_lower_bound를 시도해 보세요.
• 저자는 또한 새로운 이진 검색 구현에 대한 코드를 제공하고 각각의 성능에 대해 자세히 논의합니다.
• 이 기사는 핫 루프에서 어셈블리 명령어 수를 9에서 8로 줄이는 sb_lower_bound의 리팩토링 버전으로 업데이트되었으며, 이로 인해 속도가 약간 향상되었습니다.
• 저자는 또한 프리페칭이라는 개념에 대해 논의합니다. 이는 특정 메모리 부분을 캐시로 끌어들여 프리페치된 데이터가 실제로 필요할 때 L1/L2 캐시 지연만 발생하도록 합니다. 256KB+에 프리페칭이 추가된 sb_lower_bound 버전도 제공됩니다.
• 이 기사는 Mihail Dumitrescu가 작성하였으며 2023년 6월 24일에 발행되었습니다.

[neo]

Hacker News 의견

• 기사는 브랜치 없는 이진 검색의 개념과 잠재적 이점에 대해 논의합니다.
• 한 댓글에서는 브랜치 제거의 필요성을 의문시하며, 브랜치 예측 실패로 인한 파이프라인 정체가 아키텍처의 본질적인 부분이 아니라고 제안합니다.
• 댓글에서는 모든 작업이 본질적으로 브랜치라고 더 설명하며, 이러한 브랜치가 성능에 해를 끼치지 않는 이유는 주 파이프라인에서의 브랜치가 아니기 때문이라고 합니다.
• 또 다른 댓글에서는 lowerBound를 구현하기 위해 "bare-metal" 언어로 컴파일되는 Nim 언어의 사용을 제안합니다.
• 코드가 가장 먼저 일치하는 것을 반환하는지 아니면 어떤 일치하는 것을 반환하는지에 대한 논의가 있으며, 코드의 기능을 이해하는 것의 중요성을 강조합니다.
• 한 댓글에서는 블로그 게시물의 직관적인 소개를 칭찬하며, 이는 가장 빠른 일반 이진 검색 C++ 구현을 빠르게 제시합니다.
• 댓글에서는 Zig stdlib이 이진 검색을 위해 C++를 호출하지 않는다고 지적하며, Zig stdlib의 이진 검색에 대한 링크를 제공합니다.
• 이진 검색과 브랜치의 문제에 대한 논의가 있으며, 문제는 브랜치 자체가 아니라 비교가 완료될 때까지 다음에 가져올 메모리 위치를 모르는 데이터 의존성에서 발생한다고 제안합니다.
• 댓글에서는 Cascade Lake 프로세서에서의 이진 검색 성능 결과를 공유하며, clang이 이 특정 코드를 최적화하는 데 gcc보다 더 나쁘다고 제안합니다.
• 한 댓글에서는 "BUT RUST" 링크의 목적지에 대해 의문을 제기하며, 이 링크가 오래된 것으로 보인다고 합니다.
• 댓글에서는 결과가 더 복잡한 비교 함수로는 유지되지 않는다고 지적하며, 최상의 성능은 기본 유형에 대해 sb_lower_bound를 사용하고 그 외의 경우에는 std::lower_bound를 사용함으로써 달성될 수 있다고 제안합니다.
• 마지막 댓글에서는 예측할 수 없는 속성이 이제 cmov 변환 패스에 영향을 미친다고 언급하며, 추가 정보를 위한 링크를 제공합니다.