FreeBSD spends 7% of its boot time running a bubblesort on its SYSINITs

Re:FreeBSD spends 7% of its boot time running a bubblesort o... by cperciva on Friday May 19, 2023 @11:47AM (#36003305)

Sure. In this case though the list doesn't change from boot to boot, or for that matter from system to system; if we hit a worst-case we would notice before the release shipped.

Also, the worst case would be "systems take 2 ms extra time to boot" so it's not exactly a disaster.

[ Parent | on HN ]

Re:FreeBSD spends 7% of its boot time running a bubblesort o... by whimsicalism on Friday May 19, 2023 @11:53AM (#36003390)

> though the list doesn't change from boot to boot, or for that matter from system to system; if we hit a worst-case we would notice before the release shipped.

Wait what - why don't you just sort it at build time then? I'm probably misunderstanding what you are saying or maybe just a premature optimization.

e: Nevermind, read further in the thread and saw you answered [0]

[0]: https://twitter.com/cperciva/status/1659561673278226432

[ Parent | on HN ]

Re:FreeBSD spends 7% of its boot time running a bubblesort o... by cperciva on Friday May 19, 2023 @11:59AM (#36003481)

We might end up doing that. A quicksort takes it from 2 ms down to 40 us though, and doing the sorting at build time would take a lot of linker magic.

(The SYSINITs are records in separate object files which are marked as going into a particular ELF section, so we don't actually have a complete list of them until we finish linking the kernel.)

[ Parent | on HN ]

Re:FreeBSD spends 7% of its boot time running a bubblesort o... by alberth on Friday May 19, 2023 @08:27PM (#36008279)

Any consideration to use Radix sort.

It’s typically the fastest. It’s also a stable sort algorithm.

https://youtu.be/BeoCbJPuvSE

[ Parent | on HN ]