פייסבוק פותחת יישום של טבלאות Hash F14

חברת פייסבוק הוכרז על הטמעת קוד פתוח של טבלאות hash F14, מותאם לצריכת זיכרון יעילה. F14 משמש בתשתית פייסבוק כתחליף לרוב סוגי טבלאות ה-hash ויכול להפחית את צריכת הזיכרון מבלי להקריב את הביצועים. F14 עולה בהרבה על טבלאות hash של google::sparse_hash_map, שנחשבו עד כה ליעילות ביותר מבחינת צריכת זיכרון. קוד הפרויקט כתוב ב-C++ והוא כלול בספריה האיוולת.

F14 מתייחס לאלגוריתמים עם מערכת רזולוציית התנגשות המבוססת על גיבוב כפול עם 14 רצפים של דוגמאות (שרשרת של 14 משבצות מאוחסנת בתא טבלת גיבוב אחד, והמרווח בין התאים מחושב באמצעות פונקציית גיבוב עזר). כדי להאיץ את פעולות סינון התאים, ההטמעה משתמשת בהוראות וקטוריות SSE2 עבור מערכות x86_64 ו-NEON עבור Aarch64, המאפשרות במקביל ביצוע פעולות לבחירת חריצים עם מחזיקי מפתחות וניפוי מפתחות בתוך השרשרת. בלוקים של 14 חריצים מעובדים בכל פעם, וזה האיזון האופטימלי בין יעילות השימוש במטמון המעבד לבין מספר ההתנגשויות.

תכונה מיוחדת של F14 היא היכולת לבחור אסטרטגיות אחסון נתונים שונות:

• F14NodeMap - צורך הכי פחות זיכרון עבור מפתחות גדולים ובינוניים. מבטיח שאלמנטים מאוחסנים בעקיפין עם קריאה ל-malloc בכל הכנסה;
• F14ValueMap - מספק צריכת זיכרון מינימלית למקשים קטנים. אלמנטים מאוחסנים בתאים עצמם (inline). עבור מפתחות בינוניים וגדולים, גישה זו מובילה לתקורת זיכרון ניכרת;
• F14VectorMap - עובד מהר יותר עבור טבלאות גדולות ומפתחות מורכבים, אך איטי יותר עבור מקשים פשוטים וטבלאות קטנות. האלמנטים נארזים במערך מאוכלס ברציפות ומטופלים באמצעות מצביע אינדקס של 32 סיביות;
• F14FastMap היא אסטרטגיה משולבת. אם המפתח קטן מ-24 בתים, אזי נבחר F14ValueMap, ואם יותר, נבחר F14VectorMap.

מקור: OpenNet.ru