Vor kurzem ein Vorschlag für den Linux-Kernel wurde veröffentlicht, in dem vorgeschlagen wird, eine Reihe von Patches mit a aufzunehmen optimierte Implementierung der Funktion memchr() Wird verwendet, um nach einem Zeichen in einem Array zu suchen.
Die Funktion memchr() durchsucht die führenden n Bytes des Speicherbereichs, auf den s zeigt, nach der ersten Instanz von c. Sowohl c als auch die Bytes im Speicherbereich, auf die s zeigt, werden als vorzeichenlose Zeichen interpretiert.
der Vorschlag verspricht sei schneller um ein Zeichen innerhalb eines Speicherblocks zu lokalisieren. In Entwicklertests kann die neue Implementierung bei großen Suchen fast viermal schneller sein
Im Gegensatz zur vorherigen Version, die einen Byte-für-Byte-Vergleich verwendete, wird die vorgeschlagene Implementierung unter Berücksichtigung der vollständigen Nutzung von 64-Bit- und 32-Bit-CPU-Registern erstellt. Anstelle von Bytes erfolgt der Vergleich mit Maschinenwörtern, wodurch mindestens 4 Bytes gleichzeitig verglichen werden können.
Diese Reihe von Patches hat "memchr()" optimiert und ein Makro für hinzugefügt
"memchr_inv()", damit beide Funktionen daraus eine Bitmaske generieren können.Die ursprüngliche Implementierung von "memchr()" basiert auf Byte-Vergleich,
die das 64- oder 32-Bit-Register in der CPU nicht vollständig nutzt. Wir implementieren a
wortweiser Vergleich, so dass mindestens 4 Bytes miteinander verglichen werden können
Wetter. Das optimierte memchr() ist fast viermal schneller als das Original
für lange Ketten. Im Linux-Kernel finden wir, dass die Länge der Zeichenfolge
Gesucht von "memchr()" sind bis zu 512 Bytes in drivers/misc/lkdtm/heap.c.
Bei der Suche nach langen Zeichenfolgen Die neue Version erwies sich als etwa 4-mal schneller als die alte (z. B. für Zeichenfolgen mit 1000 Zeichen). Für kleine Ketten ist die Effizienz der neuen Implementierung nicht so signifikant, aber sie ist immer noch höher als die ursprüngliche Version.
Das Interessante an dem neuen Vorschlag ist die Verbesserung für große Ketten, die die Zeiten erheblich verbessert. Es ist erwähnenswert, dass im Linux-Kernel die Größe der in memchr() verarbeiteten Strings erreicht 512 Bytes. In unseren Tests war der Leistungsgewinn für 512-Byte-Strings in einer Situation, in der das Suchzeichen am Ende der Saite liegt, sind es 20 %.
Es ist erwähnenswert, dass die ursprüngliche Version von memchr() mit der byteweisen Vergleichstechnik implementiert ist, die die Register auf der 64-Bit- oder 32-Bit-CPU nicht vollständig nutzt.
Wir verwenden Ganzwortvergleiche, damit 8 Zeichen gleichzeitig auf der CPU verglichen werden können. Dieser Code basiert auf der Implementierung von David Light.
Wir erstellen zwei Dateien, um die Leistung der ersten Datei zu messen die durchschnittlich 10 Zeichen vor dem Zielzeichen enthält. Die zweite Datei enthält mindestens 1000 Zeichen vor der Zielcharakter.
Unsere Implementierung von "memchr()" ist leicht besser beim ersten Test und fast 4 mal schneller als das Original Umsetzung im zweiten Test.
Kernel 5.18-Tests mit neuer "memchr()"-Variante für 32-Bit- und 64-Bit-Architekturen zeigte keine Probleme.
Was passiert, wenn p nicht 8 (oder 4 auf 32-Bit-Zielen) Byte ausgerichtet ist? Nicht alle Ziele unterstützen nicht ausgerichtete (effiziente) Lasten, richtig?
Ich denke, es funktioniert, wenn p nicht 8 oder 4 Byte ausgerichtet ist. Nehmen wir an, die Zeichenfolge ist 10 Byte lang. Die for-Schleife sucht hier nach den ersten 8 Bytes. Wenn sich das Zielzeichen in den letzten 2 Bytes befindet, wird es von der zweiten for-Schleife gefunden. Es funktioniert auch so auf 32-Bit-Rechnern.
Gesamtleistungsgewinn noch nicht ausgewertet der Kernel-Subsysteme bei Verwendung der optimierten "memchr()"-Variante, noch wurde diskutiert, ob die Implementierung überschrieben werden sollte (der memchr()-Funktionsaufruf kommt 129 Mal im Kernel-Code vor, einschließlich Treiber und Dateisysteme).
Schließlich Wenn Sie mehr darüber erfahren möchten, Sie können die Details überprüfen im folgenden link.