Công ty Facebook về việc triển khai bảng băm nguồn mở , được tối ưu hóa để tiêu thụ bộ nhớ hiệu quả. F14 được sử dụng trong cơ sở hạ tầng của Facebook để thay thế cho hầu hết các loại bảng băm và có thể giảm mức tiêu thụ bộ nhớ mà không làm giảm hiệu suất. F14 vượt trội đáng kể so với các bảng băm google::sparse_hash_map, cho đến nay được coi là hiệu quả nhất về mức tiêu thụ bộ nhớ. Mã dự án được viết bằng C++ và được đưa vào thư viện .
F14 đề cập đến các thuật toán có hệ thống giải quyết xung đột dựa trên hàm băm kép với 14 (một chuỗi gồm 14 vị trí được lưu trữ trong một ô của bảng băm và khoảng cách giữa các ô được tính bằng hàm băm phụ trợ). Để tăng tốc các hoạt động lọc ô, việc triển khai sử dụng các hướng dẫn vectơ SSE2 cho hệ thống x86_64 và NEON cho Aarch64, cho phép thực hiện song song các hoạt động chọn vị trí bằng chuỗi khóa và chọn lọc các khóa trong chuỗi. Các khối gồm 14 khe được xử lý cùng một lúc, đây là sự cân bằng tối ưu giữa hiệu quả sử dụng bộ nhớ đệm của bộ xử lý và số lần va chạm.
Điểm đặc biệt của F14 là khả năng lựa chọn các chiến lược lưu trữ dữ liệu khác nhau:
- F14NodeMap - tiêu tốn ít bộ nhớ nhất cho các phím cỡ lớn và trung bình. Đảm bảo rằng các phần tử được lưu trữ gián tiếp bằng lệnh gọi malloc trên mỗi lần chèn;
- F14ValueMap - cung cấp mức tiêu thụ bộ nhớ tối thiểu cho các phím nhỏ. Các phần tử được lưu trữ trong chính các ô (nội tuyến). Đối với các khóa trung bình và lớn, cách tiếp cận này dẫn đến tiêu tốn bộ nhớ đáng kể;
- F14VectorMap - hoạt động nhanh hơn đối với các bảng lớn và các khóa phức tạp, nhưng chậm hơn đối với các khóa đơn giản và các bảng nhỏ. Các phần tử được đóng gói thành một mảng được điền liên tục và được xử lý bằng con trỏ chỉ mục 32 bit;
- F14FastMap là một chiến lược kết hợp. Nếu khóa nhỏ hơn 24 byte thì F14ValueMap sẽ được chọn và nếu nhiều hơn thì F14VectorMap sẽ được chọn.
Nguồn: opennet.ru