perusahaan Facebook babagan implementasine open source saka tabel hash , optimized kanggo konsumsi memori efisien. F14 digunakake ing infrastruktur Facebook minangka panggantos kanggo paling jinis tabel hash lan bisa nyuda konsumsi memori tanpa ngorbanake kinerja. F14 noticeably outperforms google :: tabel hash sparse_hash_map, kang nganti saiki wis dianggep paling efisien ing syarat-syarat konsumsi memori. Kode proyek ditulis ing C ++ lan kalebu ing perpustakaan .
F14 nuduhake algoritma kanthi sistem resolusi tabrakan adhedhasar hashing ganda kanthi 14 (chain 14 slot disimpen ing siji sel tabel hash, lan interval antarane sel diwilang nggunakake fungsi hash tambahan). Kanggo nyepetake operasi nyaring sel, implementasine nggunakake instruksi vektor SSE2 kanggo sistem x86_64 lan NEON kanggo Aarch64, sing ngidini parallelizing eksekusi operasi kanggo milih slot karo rante tombol lan sifting metu tombol ing chain. Pamblokiran 14 slot diproses ing wektu, kang imbangan optimal antarane efficiency nggunakake cache prosesor lan nomer tabrakan.
Fitur khusus F14 yaiku kemampuan kanggo milih strategi panyimpenan data sing beda:
- F14NodeMap - nggunakake memori paling sethithik kanggo tombol gedhe lan medium. Mesthekake yen unsur disimpen kanthi ora langsung karo telpon kanggo malloc ing saben sisipan;
- F14ValueMap - nyedhiyakake konsumsi memori minimal kanggo tombol cilik. Unsur disimpen ing sel dhewe (inline). Kanggo tombol medium lan gedhe, pendekatan iki ndadékaké kanggo overhead memori ngelingke;
- F14VectorMap - dianggo luwih cepet kanggo tabel gedhe lan tombol Komplek, nanging luwih alon kanggo tombol prasaja lan tabel cilik. Unsur-unsur kasebut dikempalken menyang array sing terus diisi lan ditangani kanthi penunjuk indeks 32-bit;
- F14FastMap minangka strategi gabungan. Yen tombol kurang saka 24 bita, banjur F14ValueMap dipilih, lan yen luwih, F14VectorMap dipilih.
Source: opennet.ru