FreeBSD: Bubble Sort in SYSINIT auf Merge Sort umgestellt

 (twitter.com/cperciva)
10 Punkte von GN⁺ 2023-08-22 | 3 Kommentare | Auf WhatsApp teilen
  • Es gab einen Bericht, dass FreeBSD beim Booten 7 % der Zeit dafür verwendet, die SYSINITs per Bubble Sort zu sortieren
  • Der Code stammt aus dem Jahr 1996; damals gab es nur etwa 30 zu sortierende SYSINITs, inzwischen sind es mehr als tausend, wodurch der Vorgang deutlich länger dauert
  • In einem aktuellen Commit wurden die SYSINIT-Arrays in SLISTs umgewandelt, sodass Merge Sort möglich wird und sich neue SYSINITs auch schneller hinzufügen lassen
    • Merge Sort ist bis zu etwa 100-mal schneller
  • Auf Firecracker-Basis lassen sich so von insgesamt 28 ms Bootzeit 2 ms einsparen

Verwandte Beiträge

3 Kommentare

 
rousseau 2023-08-23

Bei Datensätzen unterhalb einer gewissen Größenordnung war es vermutlich sinnvoll, kleinen und leicht verständlichen Code zu verwenden.
Darum gibt es wohl auch heute noch viele verbliebene Anwendungsfälle langsamer Algorithmen.
(Das ist vielleicht ein Vorurteil, aber) wenn sich daran jemand stößt, habe ich stark den Eindruck, dass es sich um jemanden handelt, der nicht hilft, sondern nur viel meckert.
 
GN⁺ 2023-08-22
Hacker-News-Kommentar
  • FreeBSD hat in den SYSINITs bubblesort durch mergesort ersetzt, was die Bootzeit deutlich verbessert hat.
  • Die Verwendung von bubblesort war kein Versehen und funktionierte viele Jahre lang gut, bis ein bestimmter Anwendungsfall seine Ineffizienz deutlich machte.
  • Es war eine notwendige Optimierung für Umgebungen, die häufig booten, wie etwa AWS Lambda.
  • Der FreeBSD-Kernel verbrachte beim Booten in Firecracker 7 % seiner Zeit damit, in den SYSINITs bubblesort auszuführen.
  • Die Umstellung auf mergesort brachte netto 5 Zeilen weniger Code und eine „100-mal schnellere“ Bootzeit.
  • Die ursprüngliche Entscheidung für bubblesort könnte von Faktoren wie der Anzahl der Aufgaben beeinflusst worden sein.
  • Die Umstellung auf mergesort ist ein Beispiel dafür, dass kleine Änderungen für die Gesamtleistung einen wichtigen Unterschied machen können.
  • Einige Nutzer stellen die ursprüngliche Verwendung angesichts der bekannten Ineffizienz und der mangelnden Intuitivität von bubblesort infrage.
  • Diese Änderung hat eine relevante Diskussion über die Bootzeit von FreeBSD und die Verwendung von bubblesort in den SYSINITs ausgelöst.