perusahaan Facebook tentang implementasi tabel hash open source , dioptimalkan untuk konsumsi memori yang efisien. F14 digunakan di infrastruktur Facebook sebagai pengganti sebagian besar jenis tabel hash dan dapat mengurangi konsumsi memori tanpa mengorbankan kinerja. F14 secara nyata mengungguli tabel hash google::sparse_hash_map, yang sejauh ini dianggap paling efisien dalam hal konsumsi memori. Kode proyek ditulis dalam C++ dan disertakan di perpustakaan .
F14 mengacu pada algoritma dengan sistem resolusi tabrakan berdasarkan hashing ganda dengan 14 (rantai 14 slot disimpan dalam satu sel tabel hash, dan interval antar sel dihitung menggunakan fungsi hash tambahan). Untuk mempercepat operasi pemfilteran sel, implementasinya menggunakan instruksi vektor SSE2 untuk sistem x86_64 dan NEON untuk Aarch64, yang memungkinkan paralelisasi eksekusi operasi untuk memilih slot dengan gantungan kunci dan menyaring kunci dalam rantai. Blok 14 slot diproses sekaligus, yang merupakan keseimbangan optimal antara efisiensi penggunaan cache prosesor dan jumlah tabrakan.
Fitur khusus F14 adalah kemampuan untuk memilih strategi penyimpanan data yang berbeda:
- F14NodeMap - menggunakan memori paling sedikit untuk kunci berukuran besar dan sedang. Memastikan bahwa elemen disimpan secara tidak langsung dengan panggilan ke malloc pada setiap penyisipan;
- F14ValueMap - menyediakan konsumsi memori minimal untuk kunci kecil. Elemen disimpan di dalam sel itu sendiri (inline). Untuk kunci sedang dan besar, pendekatan ini menyebabkan overhead memori yang nyata;
- F14VectorMap - bekerja lebih cepat untuk tabel besar dan kunci kompleks, tetapi lebih lambat untuk kunci sederhana dan tabel kecil. Elemen-elemen tersebut dikemas ke dalam array yang terus diisi dan dialamatkan oleh penunjuk indeks 32-bit;
- F14FastMap adalah strategi gabungan. Jika kuncinya kurang dari 24 byte, maka F14ValueMap dipilih, dan jika lebih, F14VectorMap dipilih.
Sumber: opennet.ru