फेसबुकले F14 ह्यास टेबलको कार्यान्वयन खोल्छ

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

F14 ले 14 सँग डबल ह्यासिङमा आधारित टक्कर रिजोल्युसन प्रणाली भएको एल्गोरिदमलाई जनाउँछ। नमूनाहरूको अनुक्रम (१४ स्लटहरूको चेन एउटा ह्यास टेबल सेलमा भण्डार गरिएको छ, र कक्षहरू बीचको अन्तराल सहायक ह्यास प्रकार्य प्रयोग गरेर गणना गरिन्छ)। सेल फिल्टरिङ कार्यहरूलाई गति दिनको लागि, कार्यान्वयनले x14_2 प्रणालीहरूको लागि भेक्टर निर्देशन SSE86 र Aarch64 को लागि NEON प्रयोग गर्दछ, जसले कि चेनहरूसँग स्लटहरू छनोट गर्न र चेन भित्र कुञ्जीहरू बाहिर निकाल्नका लागि सञ्चालनको कार्यान्वयनलाई समानान्तर गर्न अनुमति दिन्छ। 64 स्लटहरूको ब्लकहरू एक पटकमा प्रशोधन गरिन्छ, जुन प्रोसेसर क्यास प्रयोग गर्ने क्षमता र टक्करहरूको संख्या बीचको इष्टतम सन्तुलन हो।

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

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

स्रोत: opennet.ru