FreeBSD altera o bubble sort do SYSINIT para merge sort

 (twitter.com/cperciva)
10 pontos por GN⁺ 2023-08-22 | 3 comentários | Compartilhar no WhatsApp
  • Houve um relato de que o FreeBSD usa 7% do tempo de boot para fazer bubble sort dos SYSINITs
  • O código foi criado em 1996 e, naquela época, havia cerca de 30 SYSINITs para ordenar, mas hoje já são mais de mil, o que passou a consumir bastante tempo
  • Em um commit recente, os arrays de SYSINIT foram alterados para SLIST, permitindo usar merge sort e também tornando mais rápida a adição de novos SYSINITs
    • O merge sort é cerca de ~100 vezes mais rápido
  • No Firecracker, isso permite economizar 2 ms de um boot total de 28 ms

Leituras relacionadas

3 comentários

 
rousseau 2023-08-23

Para conjuntos de dados abaixo de um certo tamanho, provavelmente fazia sentido usar um código pequeno e fácil de entender.
Por causa desse tipo de decisão, ainda devem existir muitos casos remanescentes de uso de algoritmos lentos.
(Talvez seja preconceito meu, mas) tenho a forte impressão de que, se alguém implicar com isso, será o tipo de pessoa que não ajuda em nada e só reclama.
 
GN⁺ 2023-08-22
Comentários do Hacker News
  • O FreeBSD substituiu o bubblesort por mergesort nos SYSINITs, melhorando significativamente o tempo de boot.
  • O uso de bubblesort não foi um erro e funcionou bem por muitos anos, até que um caso de uso específico destacou sua ineficiência.
  • Era uma otimização necessária para casos com boots frequentes, como o AWS Lambda.
  • O kernel do FreeBSD, ao iniciar no Firecracker, gastava 7% do tempo executando bubblesort nos SYSINITs.
  • A mudança para mergesort trouxe uma redução líquida de 5 linhas de código e um tempo de boot "100 vezes mais rápido".
  • A decisão inicial de usar bubblesort pode ter sido influenciada por fatores como a quantidade de tarefas.
  • A mudança para mergesort é um exemplo de como um pequeno incremento pode fazer uma diferença importante no desempenho geral.
  • Alguns usuários questionam o uso inicial, considerando a conhecida ineficiência do bubblesort e a falta de intuitividade dessa escolha.
  • Essa mudança gerou discussões relacionadas ao tempo de boot do FreeBSD e ao uso de bubblesort nos SYSINITs.