Facebook eröffnet die Implementierung von F14-Hash-Tabellen

Facebook-Unternehmen kündigte die über die Open-Source-Implementierung von Hash-Tabellen F14, optimiert für effizienten Speicherverbrauch. F14 wird in der Facebook-Infrastruktur als Ersatz für die meisten Arten von Hash-Tabellen verwendet und kann den Speicherverbrauch reduzieren, ohne die Leistung zu beeinträchtigen. F14 übertrifft die Hash-Tabellen google::sparse_hash_map deutlich, die bisher als die effizientesten hinsichtlich des Speicherverbrauchs galten. Der Projektcode ist in C++ geschrieben und in der Bibliothek enthalten Torheit.

F14 bezieht sich auf Algorithmen mit einem Kollisionsauflösungssystem, das auf doppeltem Hashing mit 14 basiert Sequenzen von Proben (Eine Kette von 14 Slots wird in einer Hash-Tabellenzelle gespeichert und das Intervall zwischen den Zellen wird mithilfe einer Hilfs-Hash-Funktion berechnet.) Um Zellfilterungsvorgänge zu beschleunigen, verwendet die Implementierung die Vektoranweisungen SSE2 für x86_64-Systeme und NEON für Aarch64, die eine Parallelisierung der Ausführung von Vorgängen zur Auswahl von Slots mit Schlüsselketten und zum Aussortieren von Schlüsseln innerhalb der Kette ermöglichen. Blöcke mit jeweils 14 Slots werden gleichzeitig verarbeitet, was das optimale Gleichgewicht zwischen der Effizienz der Nutzung des Prozessorcaches und der Anzahl der Kollisionen darstellt.

Eine Besonderheit von F14 ist die Möglichkeit, verschiedene Datenspeicherstrategien auszuwählen:

• F14NodeMap – verbraucht am wenigsten Speicher für große und mittelgroße Schlüssel. Stellt sicher, dass Elemente indirekt mit einem Aufruf von malloc bei jeder Einfügung gespeichert werden;
• F14ValueMap – sorgt für minimalen Speicherverbrauch für kleine Schlüssel. Elemente werden in den Zellen selbst gespeichert (inline). Bei mittleren und großen Schlüsseln führt dieser Ansatz zu einem spürbaren Speicheraufwand;
• F14VectorMap – arbeitet schneller bei großen Tabellen und komplexen Schlüsseln, aber langsamer bei einfachen Schlüsseln und kleinen Tabellen. Die Elemente werden in ein kontinuierlich gefülltes Array gepackt und durch einen 32-Bit-Indexzeiger adressiert;
• F14FastMap ist eine kombinierte Strategie. Wenn der Schlüssel weniger als 24 Bytes lang ist, wird F14ValueMap ausgewählt, und wenn er größer ist, wird F14VectorMap ausgewählt.

Source: opennet.ru