फेसबुकने F14 हॅश टेबलची अंमलबजावणी उघडली

फेसबुक कंपनी घोषणा केली हॅश टेबलच्या ओपन सोर्स अंमलबजावणीबद्दल F14, कार्यक्षम मेमरी वापरासाठी अनुकूलित. F14 फेसबुक इन्फ्रास्ट्रक्चरमध्ये बर्‍याच प्रकारच्या हॅश टेबल्ससाठी बदली म्हणून वापरले जाते आणि कार्यक्षमतेचा त्याग न करता मेमरी वापर कमी करू शकते. F14 लक्षणीयपणे google::sparse_hash_map हॅश टेबल्सला मागे टाकते, जे आतापर्यंत मेमरी वापराच्या दृष्टीने सर्वात कार्यक्षम मानले गेले आहे. प्रकल्प कोड C++ मध्ये लिहिलेला आहे आणि लायब्ररीमध्ये समाविष्ट आहे मूर्खपणा.

F14 14 सह दुहेरी हॅशिंगवर आधारित टक्कर रिझोल्यूशन सिस्टमसह अल्गोरिदमचा संदर्भ देते नमुन्यांचा क्रम (14 स्लॉटची साखळी एका हॅश टेबल सेलमध्ये संग्रहित केली जाते आणि सेलमधील मध्यांतर सहायक हॅश फंक्शन वापरून मोजले जाते). सेल फिल्टरिंग ऑपरेशन्सची गती वाढवण्यासाठी, अंमलबजावणीमध्ये x2_86 सिस्टीमसाठी SSE64 आणि Aarch64 साठी NEON वेक्टर निर्देशांचा वापर केला जातो, जे की चेनसह स्लॉट्स निवडण्यासाठी आणि साखळीतील चाव्या बाहेर काढण्यासाठी ऑपरेशन्सच्या समांतरपणे अंमलबजावणी करण्यास अनुमती देतात. एका वेळी 14 स्लॉट्सच्या ब्लॉक्सवर प्रक्रिया केली जाते, जी प्रोसेसर कॅशे वापरण्याची कार्यक्षमता आणि टक्करांची संख्या यांच्यातील इष्टतम संतुलन आहे.

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

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

स्त्रोत: opennet.ru