Facebook fyrirtæki um opinn uppspretta útfærslu á kjötkássatöflum , fínstillt fyrir skilvirka minnisnotkun. F14 er notað í Facebook innviðum sem staðgengill fyrir flestar gerðir af kjötkássatöflum og getur dregið úr minnisnotkun án þess að fórna frammistöðu. F14 er áberandi betri en google::sparse_hash_map kjötkássatöflur, sem hingað til hafa verið taldar þær hagkvæmustu hvað minnisnotkun varðar. Verkefnakóði er skrifaður í C++ og er innifalinn í safninu .
F14 vísar til reiknirita með árekstrarupplausnarkerfi sem byggir á tvöföldum kjötkássa með 14 (keðja af 14 rifum er geymd í einni kjötkássatöflureit og bilið á milli frumna er reiknað með því að nota hjálparkássaaðgerð). Til að flýta fyrir frumusíuaðgerðum notar útfærslan vektorleiðbeiningar SSE2 fyrir x86_64 kerfi og NEON fyrir Aarch64, sem leyfa samhliða framkvæmd aðgerða til að velja raufar með lyklakippum og sigta út lykla innan keðjunnar. Blokkir með 14 raufum eru unnar í einu, sem er besta jafnvægið á milli hagkvæmni þess að nota skyndiminni örgjörva og fjölda árekstra.
Sérstakur eiginleiki F14 er hæfileikinn til að velja mismunandi gagnageymsluaðferðir:
- F14NodeMap - eyðir minnstu minni fyrir stóra og meðalstóra lykla. Tryggir að þættir séu geymdir óbeint með kalli til malloc við hverja innsetningu;
- F14ValueMap - veitir lágmarks minnisnotkun fyrir litla lykla. Frumefni eru geymd í frumunum sjálfum (inline). Fyrir meðalstóra og stóra lykla leiðir þessi nálgun til áberandi minniskostnaðar;
- F14VectorMap - virkar hraðar fyrir stór töflur og flókna lykla, en hægar fyrir einfalda lykla og lítil töflur. Einingunum er pakkað inn í stöðugt fyllt fylki og beint með 32 bita vísitölubendil;
- F14FastMap er sameinuð stefna. Ef lykillinn er minni en 24 bæti, þá er F14ValueMap valið og ef meira er F14VectorMap valið.
Heimild: opennet.ru