Facebook yritys hash-taulukoiden avoimen lähdekoodin toteutuksesta , optimoitu tehokkaaseen muistinkulutukseen. F14:ää käytetään Facebookin infrastruktuurissa useimpien hash-taulukoiden korvikkeena, ja se voi vähentää muistin kulutusta suorituskyvystä tinkimättä. F14 ylittää selvästi google::sparse_hash_map hash-taulukot, joita on pidetty tähän mennessä tehokkaimpana muistinkulutuksen suhteen. Projektikoodi on kirjoitettu C++:lla ja se sisältyy kirjastoon .
F14 viittaa algoritmeihin, joissa on kaksoishajautusjärjestelmä 14:n kanssa (14 paikan ketju on tallennettu yhteen hajautustaulukon soluun ja solujen välinen aika lasketaan apuhajautusfunktiolla). Solusuodatustoimintojen nopeuttamiseksi toteutuksessa käytetään vektorikäskyjä SSE2 x86_64-järjestelmille ja NEON Aarch64:lle, jotka mahdollistavat toimintojen suorittamisen rinnakkaiseksi paikkojen valitsemiseksi avainketjuilla ja avainten seulomiseksi ketjun sisällä. 14 paikan lohkoja käsitellään kerrallaan, mikä on optimaalinen tasapaino prosessorin välimuistin käytön tehokkuuden ja törmäysten määrän välillä.
F14:n erikoisominaisuus on kyky valita erilaisia tiedon tallennusstrategioita:
- F14NodeMap - kuluttaa vähiten muistia suurille ja keskikokoisille avaimille. Varmistaa, että elementit tallennetaan epäsuorasti malloc-kutsulla jokaisen lisäyksen yhteydessä;
- F14ValueMap - tarjoaa minimaalisen muistinkulutuksen pienille avaimille. Elementit tallennetaan itse soluihin (inline). Keskikokoisille ja suurille näppäimille tämä lähestymistapa johtaa huomattavaan muistiin;
- F14VectorMap - toimii nopeammin suurille taulukoille ja monimutkaisille avaimille, mutta hitaammin yksinkertaisille avaimille ja pienille taulukoille. Elementit pakataan jatkuvasti täytettyyn taulukkoon ja osoitetaan 32-bittisellä indeksiosoittimella;
- F14FastMap on yhdistetty strategia. Jos avain on alle 24 tavua, valitaan F14ValueMap, ja jos enemmän, F14VectorMap.
Lähde: opennet.ru