Facebook-ek F14 hash-taulen ezarpena ireki du

Facebook konpainia iragarri hash-taulen kode irekiko ezarpenari buruz F14, memoria eraginkorra kontsumitzeko optimizatua. F14 Facebook azpiegituran erabiltzen da hash-taula mota gehienen ordezko gisa eta memoria-kontsumoa murriztu dezake errendimenduari uko egin gabe. F14-k google::sparse_hash_map hash taulak nabarmen gainditzen ditu, orain arte memoria-kontsumoari dagokionez eraginkorrenak izan direnak. Proiektuaren kodea C++-n idatzita dago eta liburutegian sartuta dago Folly.

F14 14-rekin hashing bikoitzean oinarritutako talkak ebazteko sistema duten algoritmoei egiten die erreferentzia lagin-sekuentziak (14 zirrikitu kate bat hash taulako gelaxka batean gordetzen da, eta gelaxken arteko tartea hash funtzio laguntzaile bat erabiliz kalkulatzen da). Zelula iragazteko eragiketak bizkortzeko, inplementazioak SSE2 instrukzio bektorialak x86_64 sistemetarako eta NEON Aarch64rako erabiltzen ditu, giltza-kateekin zirrikituak aukeratzeko eta katearen barruan gakoak bahetzeko eragiketen exekuzioa paralelizatzeko aukera ematen dutenak. 14 zirrikituen blokeak aldi berean prozesatzen dira, hau da, prozesadorearen cachea erabiltzearen eraginkortasunaren eta talka kopuruaren arteko oreka optimoa.

F14-ren ezaugarri berezi bat datuak biltegiratzeko estrategia desberdinak hautatzeko gaitasuna da:

• F14NodeMap - gako handi eta ertaineko memoria gutxien kontsumitzen du. Elementuak zeharka gordetzen direla ziurtatzen du txertatze bakoitzean malloc dei batekin;
• F14ValueMap - tekla txikientzako memoria gutxieneko kontsumoa eskaintzen du. Elementuak gelaxketan bertan gordetzen dira (lerroan). Tekla ertainetarako eta handietarako, ikuspegi honek memoria gainkostu nabaria dakar;
• F14VectorMap - azkarrago funtzionatzen du mahai handietarako eta tekla konplexuetarako, baina motelagoa gako sinpleetarako eta taula txikietarako. Elementuak etengabe betetako array batean biltzen dira eta 32 biteko indize-erakusle baten bidez zuzentzen dira;
• F14FastMap estrategia konbinatua da. Gakoa 24 byte baino txikiagoa bada, F14ValueMap hautatzen da, eta gehiago bada, F14VectorMap hautatzen da.

Iturria: opennet.ru