Phoronix meldete am 24. Oktober, dass ein Patch mit binärer Suche als Teil eines memblock-Pull-Requests für Linux 7.4 eingereicht worden sei. Sein Autor Tarun Sahu beziffert den Abruf von KHO-Speicher in einem Fall mit rund 393.000 Seiten auf etwa 50 Millisekunden statt 268 Sekunden.
Was memblock beim frühen Linux-Start macht
memblock verwaltet physischen Speicher in der frühen Startphase des Linux-Kernels, bevor der vollständige Seitenallokator bereitsteht. Der vorgeschlagene Patch betrifft die Datei mm/memblock.c und damit die Suche nach Speicherbereichen in diesem frühen Abschnitt.
Wie der Patch die Suche in memblock ändert
Der Patch ersetzt wiederholte lineare Durchläufe durch eine binäre Suche in memblock_add_range() und memblock_isolate_range(). Eine lineare Suche prüft Einträge der Reihe nach; die binäre Suche grenzt den Bereich ein, in dem der passende Eintrag liegen kann. Sie sucht den ersten Speicherbereich, dessen Ende hinter der angefragten Basisadresse liegt.
Sahu beschreibt für die wiederholten linearen Durchläufe bei starker Fragmentierung eine Komplexität von O(N²). Mit der Änderung liege der ungünstigste Fall bei O(N log N); aufeinanderfolgende Ergänzungen kämen auf O(N). Für kleine Listen könne eine lineare Suche weiterhin effizient sein, erklärte Sahu. Als Schwerpunkt nannte er große Listen; die betroffenen Abläufe ordnete er der Initialisierung beim Systemstart zu, mit Memory Hotplug als Ausnahme.
Was der KHO-Zeitvergleich misst
Die von Sahu genannten Zeiten beziehen sich auf den Abruf im Rahmen von Kernel Handover (KHO), einem Einsatzfall mit vielen voneinander getrennten Speicherbereichen. Für den Fall mit rund 393.000 Seiten nennt er folgende Werte:
| Messung im KHO-Fall | Vor der Änderung | Nach der Änderung |
| Abrufzeit bei rund 393.000 Seiten | etwa 268 Sekunden | etwa 50 Millisekunden |
Diese Zahlen beschreiben den Speicherabruf in diesem konkreten Fall, nicht die Dauer des gesamten Systemstarts oder die Geschwindigkeit gewöhnlicher Anwendungen.
Was ein weiterer Testbericht erfasst
Dongli Zhang berichtete über einen eigenen Test auf einem Ein-Knoten-System mit 32 CPUs, 4K-Seiten und deaktivierten Transparent Huge Pages (THP). In seinen Boot-Logs sank der Abstand zwischen den Markern mem-auto-init und SLUB von 38,355755 auf 0,264273 Sekunden. Das sind Zeitabstände zwischen zwei Logmarkern in Zhangs Arbeitslast, keine isolierte Messung des Patches oder der gesamten Startzeit.
