फेसबुक ने F14 हैश टेबल का कार्यान्वयन शुरू किया

कंपनी फेसबुक की घोषणा की हैश तालिकाओं के ओपन सोर्स कार्यान्वयन के बारे में F14, कुशल मेमोरी खपत के लिए अनुकूलित। F14 का उपयोग फेसबुक के बुनियादी ढांचे में अधिकांश प्रकार की हैश तालिकाओं के प्रतिस्थापन के रूप में किया जाता है और यह प्रदर्शन से समझौता किए बिना मेमोरी की खपत को कम कर सकता है। F14 उल्लेखनीय रूप से google::sparse_hash_map हैश तालिकाओं से बेहतर प्रदर्शन करता है, जिन्हें अब तक मेमोरी खपत के मामले में सबसे कुशल माना जाता है। प्रोजेक्ट कोड C++ में लिखा गया है और लाइब्रेरी में शामिल है मूर्खता.

F14, 14 के साथ डबल हैशिंग पर आधारित टकराव समाधान प्रणाली वाले एल्गोरिदम को संदर्भित करता है नमूनों का क्रम (14 स्लॉट की एक श्रृंखला एक हैश टेबल सेल में संग्रहीत होती है, और कोशिकाओं के बीच के अंतराल की गणना एक सहायक हैश फ़ंक्शन का उपयोग करके की जाती है)। सेल फ़िल्टरिंग संचालन को गति देने के लिए, कार्यान्वयन x2_86 सिस्टम के लिए वेक्टर निर्देश SSE64 और Aarch64 के लिए NEON का उपयोग करता है, जो कुंजी श्रृंखला के साथ स्लॉट का चयन करने और श्रृंखला के भीतर कुंजी को बाहर निकालने के लिए संचालन के निष्पादन को समानांतर करने की अनुमति देता है। 14 स्लॉट के ब्लॉक को एक समय में संसाधित किया जाता है, जो प्रोसेसर कैश का उपयोग करने की दक्षता और टकराव की संख्या के बीच इष्टतम संतुलन है।

F14 की एक विशेष विशेषता विभिन्न डेटा भंडारण रणनीतियों का चयन करने की क्षमता है:

• F14NodeMap - बड़ी और मध्यम आकार की कुंजियों के लिए कम से कम मेमोरी की खपत करता है। यह सुनिश्चित करता है कि तत्वों को प्रत्येक प्रविष्टि पर मॉलोक पर कॉल के साथ अप्रत्यक्ष रूप से संग्रहीत किया जाता है;
• F14ValueMap - छोटी कुंजियों के लिए न्यूनतम मेमोरी खपत प्रदान करता है। तत्व स्वयं कोशिकाओं में (इनलाइन) संग्रहीत होते हैं। मध्यम और बड़ी कुंजियों के लिए, यह दृष्टिकोण ध्यान देने योग्य मेमोरी ओवरहेड की ओर ले जाता है;
• F14VectorMap - बड़ी तालिकाओं और जटिल कुंजियों के लिए तेज़ काम करता है, लेकिन सरल कुंजियों और छोटी तालिकाओं के लिए धीमा। तत्वों को लगातार पॉपुलेटेड सरणी में पैक किया जाता है और 32-बिट इंडेक्स पॉइंटर द्वारा संबोधित किया जाता है;
• F14FastMap एक संयुक्त रणनीति है। यदि कुंजी 24 बाइट्स से कम है, तो F14ValueMap चुना जाता है, और यदि अधिक है, तो F14VectorMap चुना जाता है।

स्रोत: opennet.ru