Facebook 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