Το Facebook ανοίγει την υλοποίηση πινάκων κατακερματισμού F14

εταιρεία Facebook ανακοινώθηκε σχετικά με την εφαρμογή ανοιχτού κώδικα των πινάκων κατακερματισμού F14, βελτιστοποιημένο για αποτελεσματική κατανάλωση μνήμης. Το F14 χρησιμοποιείται στην υποδομή του Facebook ως αντικατάσταση των περισσότερων τύπων πινάκων κατακερματισμού και μπορεί να μειώσει την κατανάλωση μνήμης χωρίς να θυσιάζει την απόδοση. Το F14 ξεπερνά αισθητά τους πίνακες κατακερματισμού του google::sparse_hash_map, οι οποίοι μέχρι στιγμής θεωρούνταν οι πιο αποδοτικοί όσον αφορά την κατανάλωση μνήμης. Ο κώδικας του έργου είναι γραμμένος σε C++ και περιλαμβάνεται στη βιβλιοθήκη Τρέλα.

Το F14 αναφέρεται σε αλγόριθμους με σύστημα ανάλυσης σύγκρουσης που βασίζεται σε διπλό κατακερματισμό με 14 αλληλουχίες δειγμάτων (μια αλυσίδα 14 υποδοχών αποθηκεύεται σε ένα κελί κατακερματισμού και το διάστημα μεταξύ των κελιών υπολογίζεται χρησιμοποιώντας μια βοηθητική συνάρτηση κατακερματισμού). Για να επιταχύνει τις λειτουργίες φιλτραρίσματος κυψελών, η υλοποίηση χρησιμοποιεί διανυσματικές οδηγίες SSE2 για συστήματα x86_64 και NEON για Aarch64, οι οποίες επιτρέπουν τον παραλληλισμό της εκτέλεσης λειτουργιών για την επιλογή υποδοχών με αλυσίδες κλειδιών και το κοσκίνισμα των κλειδιών εντός της αλυσίδας. Επεξεργάζονται μπλοκ 14 θυρίδων τη φορά, που είναι η βέλτιστη ισορροπία μεταξύ της αποτελεσματικότητας της χρήσης της κρυφής μνήμης του επεξεργαστή και του αριθμού των συγκρούσεων.

Ένα ιδιαίτερο χαρακτηριστικό του F14 είναι η δυνατότητα επιλογής διαφορετικών στρατηγικών αποθήκευσης δεδομένων:

• F14NodeMap - καταναλώνει τη λιγότερη μνήμη για μεγάλα και μεσαίου μεγέθους κλειδιά. Διασφαλίζει ότι τα στοιχεία αποθηκεύονται έμμεσα με μια κλήση στο malloc σε κάθε εισαγωγή.
• F14ValueMap - παρέχει ελάχιστη κατανάλωση μνήμης για μικρά πλήκτρα. Τα στοιχεία αποθηκεύονται στα ίδια τα κελιά (inline). Για μεσαία και μεγάλα πλήκτρα, αυτή η προσέγγιση οδηγεί σε αξιοσημείωτη επιβάρυνση μνήμης.
• F14VectorMap - λειτουργεί πιο γρήγορα για μεγάλα τραπέζια και σύνθετα πλήκτρα, αλλά πιο αργά για απλά πλήκτρα και μικρά τραπέζια. Τα στοιχεία συσκευάζονται σε μια συστοιχία που συμπληρώνεται συνεχώς και διευθύνονται από έναν δείκτη ευρετηρίου 32 bit.
• Το F14FastMap είναι μια συνδυασμένη στρατηγική. Εάν το κλειδί είναι μικρότερο από 24 byte, τότε επιλέγεται το F14ValueMap και εάν είναι μεγαλύτερο, επιλέγεται το F14VectorMap.

Πηγή: opennet.ru