페이스북, F14 해시 테이블 구현 개시

페이스북 회사 발표했다. 해시 테이블의 오픈 소스 구현에 대해 F14, 효율적인 메모리 소비를 위해 최적화되었습니다. F14는 대부분의 해시 테이블 유형을 대체하기 위해 Facebook 인프라에서 사용되며 성능 저하 없이 메모리 소비를 줄일 수 있습니다. F14는 지금까지 메모리 소비 측면에서 가장 효율적인 것으로 간주되었던 google::sparse_hash_map 해시 테이블보다 눈에 띄게 성능이 뛰어납니다. 프로젝트 코드는 C++로 작성되었으며 라이브러리에 포함되어 있습니다. 어리석은 행동.

F14는 14의 이중 해싱을 기반으로 하는 충돌 해결 시스템을 갖춘 알고리즘을 나타냅니다. 샘플 시퀀스 (하나의 해시 테이블 셀에는 14개의 슬롯으로 구성된 체인이 저장되며, 보조 해시 함수를 사용하여 셀 간의 간격을 계산합니다.) 셀 필터링 작업 속도를 높이기 위해 구현에서는 x2_86 시스템용 벡터 명령어 SSE64와 Aarch64용 NEON을 사용합니다. 이를 통해 키 체인이 있는 슬롯을 선택하고 체인 내에서 키를 선별하는 작업 실행을 병렬화할 수 있습니다. 14개 슬롯의 블록이 한 번에 처리됩니다. 이는 프로세서 캐시 사용 효율성과 충돌 횟수 간의 최적 균형입니다.

F14의 특별한 기능은 다양한 데이터 저장 전략을 선택할 수 있다는 것입니다.

• F14NodeMap - 대형 및 중간 크기 키에 대해 최소한의 메모리를 소비합니다. 삽입할 때마다 malloc을 호출하여 요소가 간접적으로 저장되도록 합니다.
• F14ValueMap - 작은 키에 대해 최소한의 메모리 소비를 제공합니다. 요소는 셀 자체(인라인)에 저장됩니다. 중간 및 큰 키의 경우 이 접근 방식을 사용하면 상당한 메모리 오버헤드가 발생합니다.
• F14VectorMap - 큰 테이블과 복잡한 키에서는 더 빠르게 작동하지만 간단한 키와 작은 테이블에서는 더 느립니다. 요소는 연속적으로 채워진 배열로 압축되고 32비트 인덱스 포인터로 주소가 지정됩니다.
• F14FastMap은 결합된 전략입니다. 키가 24바이트 미만이면 F14ValueMap이 선택되고, 그보다 크면 F14VectorMap이 선택됩니다.

출처 : opennet.ru