Kampuni ya Facebook kuhusu utekelezaji wa chanzo wazi cha meza za hashi , iliyoboreshwa kwa matumizi bora ya kumbukumbu. F14 inatumika katika miundombinu ya Facebook kama mbadala wa aina nyingi za jedwali la hashi na inaweza kupunguza matumizi ya kumbukumbu bila kughairi utendakazi. F14 inazidi ubora wa jedwali za google::sparse_hash_map, ambazo hadi sasa zimezingatiwa kuwa bora zaidi katika suala la utumiaji wa kumbukumbu. Nambari ya mradi imeandikwa katika C++ na imejumuishwa kwenye maktaba .
F14 inarejelea algoriti zilizo na mfumo wa utatuzi wa mgongano kulingana na hashing mara mbili na 14 (mlolongo wa nafasi 14 huhifadhiwa kwenye seli moja ya jedwali la hashi, na muda kati ya seli huhesabiwa kwa kutumia kazi ya hashi msaidizi). Ili kuharakisha shughuli za kuchuja seli, utekelezaji hutumia maagizo ya vekta SSE2 kwa mifumo ya x86_64 na NEON ya Aarch64, ambayo inaruhusu kusawazisha utekelezaji wa shughuli za kuchagua nafasi na minyororo muhimu na kuchuja funguo ndani ya mnyororo. Vitalu vya nafasi 14 vinachakatwa kwa wakati mmoja, ambayo ni uwiano bora kati ya ufanisi wa kutumia cache ya processor na idadi ya migongano.
Kipengele maalum cha F14 ni uwezo wa kuchagua mikakati tofauti ya kuhifadhi data:
- F14NodeMap - hutumia kumbukumbu ndogo zaidi kwa funguo kubwa na za kati. Inahakikisha kwamba vipengele vimehifadhiwa kwa njia isiyo ya moja kwa moja na wito kwa malloc kwenye kila uwekaji;
- F14ValueMap - hutoa matumizi madogo ya kumbukumbu kwa funguo ndogo. Vipengele vinahifadhiwa kwenye seli zenyewe (inline). Kwa funguo za kati na kubwa, njia hii inaongoza kwa kumbukumbu inayoonekana;
- F14VectorMap - inafanya kazi kwa kasi kwa meza kubwa na funguo ngumu, lakini polepole kwa funguo rahisi na meza ndogo. Vipengele vimefungwa kwenye safu inayoendelea ya watu wengi na kushughulikiwa na kiashiria cha index cha 32-bit;
- F14FastMap ni mkakati wa pamoja. Ikiwa ufunguo ni chini ya baiti 24, basi F14ValueMap imechaguliwa, na ikiwa zaidi, F14VectorMap imechaguliwa.
Chanzo: opennet.ru