FreeBSD remplace le tri à bulles de SYSINIT par un tri fusion

 (twitter.com/cperciva)
10 points par GN⁺ 2023-08-22 | 3 commentaires | Partager sur WhatsApp
  • Un signalement indiquait que FreeBSD utilisait 7 % de son temps de démarrage à trier les SYSINIT avec un tri à bulles
  • Le code datait de 1996 et, à l’époque, il n’y avait qu’environ 30 SYSINIT à trier ; aujourd’hui, il y en a plus d’un millier, ce qui rallonge l’opération
  • Un commit récent a remplacé les tableaux de SYSINIT par des SLIST, ce qui permet d’utiliser un tri fusion et accélère aussi l’ajout de nouveaux SYSINIT
    • Le tri fusion est jusqu’à environ 100 fois plus rapide
  • Dans le cas de Firecracker, cela permet d’économiser 2 ms sur un démarrage total de 28 ms

À lire aussi

3 commentaires

 
rousseau 2023-08-23

Pour des jeux de données en dessous d’une certaine taille, il était sans doute pertinent d’utiliser un code petit et facile à comprendre.
Il doit encore rester pas mal de cas d’usage d’algorithmes lents à cause de ce genre de décision.
(C’est un préjugé, mais) j’ai fortement tendance à penser que, s’il y a des gens pour chipoter là-dessus, ce seront surtout des gens qui se plaignent beaucoup sans être d’une grande aide.
 
GN⁺ 2023-08-22
Commentaire Hacker News
  • FreeBSD a remplacé bubblesort par mergesort dans les SYSINIT, ce qui a considérablement amélioré le temps de démarrage.
  • L’utilisation de bubblesort n’était pas une erreur et a bien fonctionné pendant de nombreuses années, jusqu’à ce qu’un cas d’usage particulier mette en évidence son inefficacité.
  • C’était une optimisation nécessaire pour les cas où les démarrages sont fréquents, comme avec AWS Lambda.
  • Le noyau FreeBSD passait 7 % de son temps à exécuter bubblesort dans les SYSINIT lors du démarrage sur Firecracker.
  • Le passage à mergesort s’est traduit par une réduction nette de 5 lignes de code et un temps de démarrage « 100 fois plus rapide ».
  • La décision initiale d’utiliser bubblesort a peut-être été influencée par des facteurs comme le nombre de tâches.
  • Le passage à mergesort montre comment une petite amélioration peut faire une différence importante sur les performances globales.
  • Certains utilisateurs s’interrogent sur l’usage initial de bubblesort, compte tenu de son inefficacité connue et de son manque d’évidence intuitive.
  • Ce changement a déclenché des discussions connexes sur le temps de démarrage de FreeBSD et sur l’utilisation de bubblesort dans les SYSINIT.