FreeBSD cambia el bubble sort de SYSINIT por merge sort

• Se reportó que FreeBSD usa el 7% del tiempo de arranque para ordenar los SYSINIT con bubble sort
• Es un código creado en 1996, y en esa época había alrededor de 30 SYSINIT para ordenar, pero ahora ya son más de mil, por lo que tardaba bastante
• En un commit reciente, los arreglos de SYSINIT se cambiaron a SLIST, lo que permite usar merge sort y también acelera la incorporación de nuevos SYSINIT
  • El merge sort es hasta ~100 veces más rápido
• En Firecracker, esto permite ahorrar 2 ms de un arranque total de 28 ms

[rousseau]

Para conjuntos de datos de cierto tamaño o menores, probablemente haya sido válido usar código pequeño y fácil de entender.
Y seguramente todavía queden muchos casos de uso de algoritmos lentos por decisiones así.
(Aunque es un prejuicio mío) también me da fuertemente la impresión de que, si alguien se pone a objetar algo como esto, sería de esas personas que no ayudan y solo se quejan.

[xguru]

FreeBSD usa el 7% del tiempo de arranque para ordenar los SYSINIT con bubble sort

[GN⁺]

Opinión de Hacker News

• FreeBSD reemplazó bubblesort por mergesort en los SYSINIT, lo que mejoró significativamente el tiempo de arranque.
• El uso de bubblesort no fue un error y funcionó bien durante muchos años, hasta que un caso de uso específico puso en evidencia su ineficiencia.
• Era una optimización necesaria para casos como AWS Lambda, donde se arranca con frecuencia.
• El kernel de FreeBSD gastaba el 7% de su tiempo ejecutando bubblesort en los SYSINIT al arrancar en Firecracker.
• El cambio a mergesort redujo el código en 5 líneas netas y trajo tiempos de arranque "100 veces más rápidos".
• La decisión original de usar bubblesort pudo haber estado influida por factores como la cantidad de tareas.
• El cambio a mergesort es un ejemplo de cómo una mejora pequeña puede marcar una diferencia importante en el rendimiento general.
• Algunos usuarios cuestionan el uso inicial, considerando la ineficiencia ya conocida de bubblesort y lo poco intuitivo que resulta.
• Este cambio provocó debates relacionados con el tiempo de arranque de FreeBSD y el uso de bubblesort en los SYSINIT.