GN⁺: FreeBSD, SYSINIT의 버블소트를 머지소트로 변경
(twitter.com/cperciva)- FreeBSD는 부팅시에 7%의 시간을 SYSINIT들을 버블소트하는데 사용한다는 제보가 있었음
- 1996년에 만들어진 코드고, 그 시절에는 정렬할 SYSINIT이 약 30개 정도 였지만, 현재는 천개 이상이 되면서 오래 걸리게 됨
- 최근 커밋에서 SYSINIT Array들을 SLIST로 변경해서 머지소트가 가능해지고, 새로운 SYSINIT 들을 추가하는 것도 빨라짐
- 머지소트는 약 ~100배까지 빠름
- Firecracker 기준 전체 부팅 28ms 중 2ms 를 절약할수 있게 됨
일정 규모 이하의 데이터셋에 대해서는, 작고 이해하기 쉬운 코드를 사용하는 것이 유효했을 것입니다.
그런 결정으로 잔존하는 느린 알고리즘 용례는 여전히 많을 거구요.
(편견입니다만) 이런 데에 딴지를 거는 사람이 있다면, 도움은 안되면서 불평만 많은 사람일 거라는 생각이 강하게 드네요.
Hacker News 의견
- FreeBSD가 SYSINTs에서 bubblesort를 mergesort로 교체하여 부팅 시간이 크게 개선되었습니다.
- bubblesort의 사용은 실수가 아니었으며, 특정 사용 사례가 그 비효율성을 부각시킬 때까지 많은 년 동안 잘 작동했습니다.
- AWS Lambda와 같이 자주 부팅하는 경우에 필요한 최적화였습니다.
- FreeBSD 커널은 Firecracker에서 부팅할 때 SYSINTs에서 bubblesort를 실행하는 데 7%의 시간을 소비했습니다.
- mergesort로의 변경은 코드 5줄의 순감소와 "100배 빠른" 부팅 시간을 가져왔습니다.
- 처음에 bubblesort를 사용하기로 한 결정은 작업 수와 같은 요소에 의해 영향을 받았을 수 있습니다.
- mergesort로의 변경은 작은 증가가 전체 성능에 중요한 차이를 만들 수 있음을 보여주는 예입니다.
- 일부 사용자들은 bubblesort의 알려진 비효율성과 직관성 부족을 고려할 때 초기 사용에 의문을 제기합니다.
- 이 변경은 FreeBSD의 부팅 시간과 SYSINTs에서의 bubblesort 사용에 대한 관련 토론을 촉발시켰습니다.