pausahaan Facebook ngeunaan palaksanaan open source tabel hash , dioptimalkeun pikeun konsumsi memori efisien. F14 dianggo dina infrastruktur Facebook salaku gaganti pikeun kalolobaan jinis tabel hash sareng tiasa ngirangan konsumsi mémori tanpa ngorbankeun kinerja. F14 noticeably outperforms google :: tabel Hash sparse_hash_map, nu geus jadi jauh dianggap pang éfisiénna dina watesan konsumsi memori. Kodeu proyék ditulis dina C ++ sarta kaasup kana perpustakaan .
F14 nujul kana algoritma sareng sistem résolusi tabrakan dumasar kana hashing ganda sareng 14 (Ranté 14 slot disimpen dina hiji sél tabel hash, sarta interval antara sél diitung ngagunakeun fungsi hash bantu). Pikeun nyepetkeun operasi panyaring sél, palaksanaan ngagunakeun petunjuk vektor SSE2 pikeun sistem x86_64 sareng NEON pikeun Aarch64, anu ngamungkinkeun parallelizing palaksanaan operasi pikeun milih slot sareng ranté konci sareng nyaring konci dina ranté. Blok 14 slot diolah dina hiji waktu, nu kasaimbangan optimal antara efisiensi ngagunakeun cache processor jeung Jumlah tabrakan.
Fitur khusus F14 nyaéta kamampuan pikeun milih strategi panyimpen data anu béda:
- F14NodeMap - meakeun memori pangsaeutikna pikeun kenop badag tur sedeng-ukuran. Mastikeun yén elemen disimpen sacara henteu langsung kalayan nelepon ka malloc dina unggal sisipan;
- F14ValueMap - nyadiakeun konsumsi memori minimal keur kenop leutik. Unsur disimpen dina sél sorangan (inline). Pikeun kenop sedeng sarta badag, pendekatan ieu ngabalukarkeun overhead memori noticeable;
- F14VectorMap - jalan gancang pikeun tabel badag sarta konci kompléks, tapi laun pikeun kenop basajan tur tabel leutik. Unsur-unsurna dipak kana susunan anu terus-terusan dieusi sareng ditunjuk ku pointer indéks 32-bit;
- F14FastMap mangrupikeun strategi gabungan. Upami koncina kirang ti 24 bait, teras F14ValueMap dipilih, sareng upami langkung, F14VectorMap dipilih.
sumber: opennet.ru