F14 ഹാഷ് ടേബിളുകൾ ഫേസ്ബുക്ക് തുറന്ന് നടപ്പിലാക്കുന്നു

കമ്പനി ഫേസ്ബുക്ക് പ്രഖ്യാപിച്ചു ഹാഷ് ടേബിളുകളുടെ ഓപ്പൺ സോഴ്സ് നടപ്പിലാക്കുന്നതിനെക്കുറിച്ച് F14, കാര്യക്ഷമമായ മെമ്മറി ഉപഭോഗത്തിനായി ഒപ്റ്റിമൈസ് ചെയ്തു. മിക്ക തരത്തിലുള്ള ഹാഷ് ടേബിളുകൾക്കും പകരമായി Facebook ഇൻഫ്രാസ്ട്രക്ചറിൽ F14 ഉപയോഗിക്കുന്നു, കൂടാതെ പ്രകടനം നഷ്ടപ്പെടുത്താതെ മെമ്മറി ഉപഭോഗം കുറയ്ക്കാനും കഴിയും. മെമ്മറി ഉപഭോഗത്തിൻ്റെ കാര്യത്തിൽ ഇതുവരെ ഏറ്റവും കാര്യക്ഷമമായി കണക്കാക്കപ്പെട്ടിരുന്ന google::sparse_hash_map ഹാഷ് ടേബിളുകളെ F14 ശ്രദ്ധേയമായി മറികടക്കുന്നു. പ്രോജക്റ്റ് കോഡ് C++ ൽ എഴുതിയിരിക്കുന്നു കൂടാതെ ലൈബ്രറിയിൽ ഉൾപ്പെടുത്തിയിട്ടുണ്ട് വണ്ണം.

14 ഉപയോഗിച്ചുള്ള ഇരട്ട ഹാഷിംഗിനെ അടിസ്ഥാനമാക്കിയുള്ള കൂട്ടിയിടി റെസലൂഷൻ സംവിധാനമുള്ള അൽഗോരിതങ്ങളെയാണ് F14 സൂചിപ്പിക്കുന്നത്. സാമ്പിളുകളുടെ ക്രമങ്ങൾ (14 സ്ലോട്ടുകളുടെ ഒരു ശൃംഖല ഒരു ഹാഷ് ടേബിൾ സെല്ലിൽ സംഭരിച്ചിരിക്കുന്നു, കൂടാതെ സെല്ലുകൾ തമ്മിലുള്ള ഇടവേള ഒരു സഹായ ഹാഷ് ഫംഗ്ഷൻ ഉപയോഗിച്ച് കണക്കാക്കുന്നു). സെൽ ഫിൽട്ടറിംഗ് പ്രവർത്തനങ്ങൾ വേഗത്തിലാക്കാൻ, നടപ്പിലാക്കൽ x2_86 സിസ്റ്റങ്ങൾക്കായി SSE64 വെക്റ്റർ നിർദ്ദേശങ്ങളും Aarch64-ന് NEON ഉം ഉപയോഗിക്കുന്നു, ഇത് കീ ചെയിനുകളുള്ള സ്ലോട്ടുകൾ തിരഞ്ഞെടുക്കുന്നതിനും ചെയിനിനുള്ളിലെ കീകൾ വേർതിരിച്ചെടുക്കുന്നതിനുമുള്ള പ്രവർത്തനങ്ങളുടെ നിർവ്വഹണത്തിന് സമാന്തരമായി അനുവദിക്കുന്നു. 14 സ്ലോട്ടുകളുടെ ബ്ലോക്കുകൾ ഒരു സമയം പ്രോസസ്സ് ചെയ്യുന്നു, ഇത് പ്രോസസർ കാഷെ ഉപയോഗിക്കുന്നതിൻ്റെ കാര്യക്ഷമതയും കൂട്ടിയിടികളുടെ എണ്ണവും തമ്മിലുള്ള ഒപ്റ്റിമൽ ബാലൻസ് ആണ്.

വ്യത്യസ്ത ഡാറ്റ സംഭരണ ​​തന്ത്രങ്ങൾ തിരഞ്ഞെടുക്കാനുള്ള കഴിവാണ് F14-ൻ്റെ ഒരു പ്രത്യേക സവിശേഷത:

• F14NodeMap - വലുതും ഇടത്തരവുമായ കീകൾക്കായി ഏറ്റവും കുറഞ്ഞ മെമ്മറി ഉപയോഗിക്കുന്നു. ഓരോ ഇൻസെർഷനിലും malloc-ലേക്കുള്ള കോളിനൊപ്പം ഘടകങ്ങൾ പരോക്ഷമായി സംഭരിച്ചിട്ടുണ്ടെന്ന് ഉറപ്പാക്കുന്നു;
• F14ValueMap - ചെറിയ കീകൾക്ക് കുറഞ്ഞ മെമ്മറി ഉപഭോഗം നൽകുന്നു. മൂലകങ്ങൾ സെല്ലുകളിൽ തന്നെ സൂക്ഷിക്കുന്നു (ഇൻലൈൻ). ഇടത്തരം, വലിയ കീകൾക്കായി, ഈ സമീപനം ശ്രദ്ധേയമായ മെമ്മറി ഓവർഹെഡിലേക്ക് നയിക്കുന്നു;
• F14VectorMap - വലിയ ടേബിളുകൾക്കും സങ്കീർണ്ണമായ കീകൾക്കും വേഗത്തിൽ പ്രവർത്തിക്കുന്നു, എന്നാൽ ലളിതമായ കീകൾക്കും ചെറിയ ടേബിളുകൾക്കും വേഗത കുറവാണ്. മൂലകങ്ങൾ തുടർച്ചയായി ജനസാന്ദ്രതയുള്ള ഒരു അറേയിൽ പായ്ക്ക് ചെയ്യുകയും 32-ബിറ്റ് സൂചിക പോയിൻ്റർ ഉപയോഗിച്ച് അഭിസംബോധന ചെയ്യുകയും ചെയ്യുന്നു;
• F14FastMap ഒരു സംയുക്ത തന്ത്രമാണ്. കീ 24 ബൈറ്റുകളിൽ കുറവാണെങ്കിൽ, F14ValueMap തിരഞ്ഞെടുത്തു, കൂടുതൽ ആണെങ്കിൽ, F14VectorMap തിരഞ്ഞെടുക്കും.

അവലംബം: opennet.ru