شرکت فیس بوک درباره اجرای متن باز جداول هش ، برای مصرف کارآمد حافظه بهینه شده است. F14 در زیرساخت فیس بوک به عنوان جایگزینی برای اکثر انواع جداول هش استفاده می شود و می تواند مصرف حافظه را بدون کاهش عملکرد کاهش دهد. F14 به طور محسوسی از جدول های هش google::sparse_hash_map که تاکنون کارآمدترین آنها از نظر مصرف حافظه در نظر گرفته شده است، بهتر عمل می کند. کد پروژه به زبان C++ نوشته شده و در کتابخانه گنجانده شده است .
F14 به الگوریتم هایی با سیستم تفکیک تصادم بر اساس هش دوگانه با 14 اشاره دارد. (زنجیره ای از 14 اسلات در یک سلول جدول هش ذخیره می شود و فاصله بین سلول ها با استفاده از یک تابع هش کمکی محاسبه می شود). برای سرعت بخشیدن به عملیات فیلتر سلولی، پیاده سازی از دستورالعمل های برداری SSE2 برای سیستم های x86_64 و NEON برای Aarch64 استفاده می کند، که امکان موازی سازی اجرای عملیات برای انتخاب اسلات ها با زنجیره کلید و غربال کردن کلیدهای درون زنجیره را فراهم می کند. بلوک های 14 اسلات در یک زمان پردازش می شوند که تعادل بهینه بین کارایی استفاده از حافظه پنهان پردازنده و تعداد برخوردها است.
ویژگی خاص F14 امکان انتخاب استراتژی های مختلف ذخیره سازی داده ها است:
- F14NodeMap - کمترین حافظه را برای کلیدهای بزرگ و متوسط مصرف می کند. تضمین می کند که عناصر به طور غیر مستقیم با فراخوانی به malloc در هر درج ذخیره می شوند.
- F14ValueMap - حداقل مصرف حافظه را برای کلیدهای کوچک فراهم می کند. عناصر در خود سلول ها (در خط) ذخیره می شوند. برای کلیدهای متوسط و بزرگ، این رویکرد منجر به سربار حافظه قابل توجهی می شود.
- F14VectorMap - برای جداول بزرگ و کلیدهای پیچیده سریعتر کار می کند، اما برای کلیدهای ساده و جداول کوچک کندتر عمل می کند. عناصر در یک آرایه به طور مداوم پر شده و توسط یک نشانگر شاخص 32 بیتی آدرس دهی می شوند.
- F14FastMap یک استراتژی ترکیبی است. اگر کلید کمتر از 24 بایت باشد، F14ValueMap و اگر بیشتر باشد، F14VectorMap انتخاب می شود.
منبع: opennet.ru