Facebook F14 xesh-jadvallarini joriy qilishni ochadi

Facebook kompaniyasi e'lon qildi xesh-jadvallarning ochiq kodli amalga oshirilishi haqida F14, samarali xotira sarfi uchun optimallashtirilgan. F14 Facebook infratuzilmasida xesh-jadvallarning ko'p turlarini almashtirish sifatida ishlatiladi va unumdorlikni yo'qotmasdan xotira sarfini kamaytirishi mumkin. F14 google::sparse_hash_map xesh-jadvallaridan sezilarli darajada ustundir, ular hozirgacha xotira sarfi bo'yicha eng samarali hisoblanadi. Loyiha kodi C++ da yozilgan va kutubxonaga kiritilgan Folly.

F14 14 bilan ikki marta xeshingga asoslangan to'qnashuvni hal qilish tizimiga ega algoritmlarga ishora qiladi. namunalar ketma-ketligi (14 slotdan iborat zanjir bitta xesh-jadval yacheykasida saqlanadi va hujayralar orasidagi interval yordamchi xesh funktsiyasi yordamida hisoblanadi). Hujayralarni filtrlash operatsiyalarini tezlashtirish uchun dastur x2_86 tizimlari uchun SSE64 vektor ko'rsatmalaridan va Aarch64 uchun NEONdan foydalanadi, bu kalit zanjirlar bilan slotlarni tanlash va zanjir ichidagi kalitlarni saralash operatsiyalarini parallellashtirishga imkon beradi. Bir vaqtning o'zida 14 slot bloklari qayta ishlanadi, bu protsessor keshini ishlatish samaradorligi va to'qnashuvlar soni o'rtasidagi optimal muvozanatdir.

F14 ning o'ziga xos xususiyati turli xil ma'lumotlarni saqlash strategiyalarini tanlash qobiliyatidir:

• F14NodeMap - katta va o'rta o'lchamli kalitlar uchun eng kam xotirani iste'mol qiladi. Har bir qo'shishda malloc ga qo'ng'iroq bilan elementlarning bilvosita saqlanishini ta'minlaydi;
• F14ValueMap - kichik tugmalar uchun minimal xotira sarfini ta'minlaydi. Elementlar hujayralarning o'zida saqlanadi (inline). O'rta va katta kalitlar uchun bu yondashuv sezilarli xotira yukiga olib keladi;
• F14VectorMap - katta jadvallar va murakkab kalitlar uchun tezroq ishlaydi, lekin oddiy tugmalar va kichik jadvallar uchun sekinroq ishlaydi. Elementlar doimiy ravishda to'ldiriladigan massivga to'planadi va 32-bitli indeks ko'rsatkichi orqali manzillanadi;
• F14FastMap - bu birlashtirilgan strategiya. Agar kalit 24 baytdan kam bo'lsa, u holda F14ValueMap, ko'proq bo'lsa, F14VectorMap tanlanadi.

Manba: opennet.ru