syarikat Facebook mengenai pelaksanaan sumber terbuka jadual cincang , dioptimumkan untuk penggunaan memori yang cekap. F14 digunakan dalam infrastruktur Facebook sebagai pengganti kebanyakan jenis jadual cincang dan boleh mengurangkan penggunaan memori tanpa mengorbankan prestasi. F14 nyata mengatasi jadual cincang google::sparse_hash_map, yang setakat ini dianggap paling cekap dari segi penggunaan memori. Kod projek ditulis dalam C++ dan disertakan dalam perpustakaan .
F14 merujuk kepada algoritma dengan sistem resolusi perlanggaran berdasarkan pencincangan berganda dengan 14 (rantaian 14 slot disimpan dalam satu sel jadual cincang, dan selang antara sel dikira menggunakan fungsi cincang tambahan). Untuk mempercepatkan operasi penapisan sel, pelaksanaan menggunakan arahan vektor SSE2 untuk sistem x86_64 dan NEON untuk Aarch64, yang membolehkan penyelarasan pelaksanaan operasi untuk memilih slot dengan rantai kunci dan menapis kekunci dalam rantai. Blok 14 slot diproses pada satu masa, iaitu keseimbangan optimum antara kecekapan penggunaan cache pemproses dan bilangan perlanggaran.
Ciri khas F14 ialah keupayaan untuk memilih strategi penyimpanan data yang berbeza:
- F14NodeMap - menggunakan paling sedikit memori untuk kekunci besar dan sederhana. Memastikan bahawa elemen disimpan secara tidak langsung dengan panggilan ke malloc pada setiap sisipan;
- F14ValueMap - menyediakan penggunaan memori yang minimum untuk kekunci kecil. Elemen disimpan dalam sel itu sendiri (sebaris). Untuk kekunci sederhana dan besar, pendekatan ini membawa kepada overhed memori yang ketara;
- F14VectorMap - berfungsi lebih pantas untuk jadual besar dan kekunci kompleks, tetapi lebih perlahan untuk kekunci ringkas dan jadual kecil. Unsur-unsur dibungkus ke dalam tatasusunan yang dihuni secara berterusan dan ditangani oleh penunjuk indeks 32-bit;
- F14FastMap ialah strategi gabungan. Jika kunci kurang daripada 24 bait, maka F14ValueMap dipilih dan jika lebih, F14VectorMap dipilih.
Sumber: opennet.ru