News for hackers. Stuff that matters.

A comment on 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 klyrs on Friday May 19, 2023 @11:16AM (#36002960)
> O(N^2) can bite hard when you're sorting over a thousand items. Time to replace the bubblesort with something faster.

... downthread ...

> I suspect quicksort will be enough though.

Somebody hasn't taken a freshman complexity theory class in a while...

(Note, this is tongue in cheek. Worst case is not average case and all that. I'm sure quicksort will do fine)

[ Parent | on HN ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by cperciva on Friday May 19, 2023 @11:26AM (#36003073)
Somebody hasn't taken a freshman complexity theory class in a while...

Last time I was in a freshman complexity theory class I was teaching it.

We're not exactly talking about adversarial inputs here.

[ Parent | on HN ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by cpp_frog on Friday May 19, 2023 @11:30AM (#36003120)
Not even noon and Colin is already roasting. Reminds me of [0], also by him.

[0] https://news.ycombinator.com/item?id=35079

[ Parent | on HN ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by cperciva on Friday May 19, 2023 @11:44AM (#36003268)
I haven't recovered from jetlag yet. Sorry, my snark went overboard.
[ Parent | on HN ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by klyrs on Friday May 19, 2023 @11:33AM (#36003154)
I was mostly joking, but worst-cases include sorted and reverse-sorted lists. I've seen those happen accidentally, in practice, resulting in accidentally-quadratic runtime. This is why, when I taught that class, I made students compare sorting algorithms on real world data sets.
[ Parent | on HN ]
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 ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by sn9 on Friday May 19, 2023 @03:12PM (#36005736)
Isn't the point of quicksort that the randomization of the pivot selection means that you're extremely unlikely to run into a pathological case for the specific pivot chosen?

And perhaps even more unlikely if you permute the input sequence before sorting it.

I'm basing this off of my understanding of Skiena's discussion of quicksort in The Algorithm Design Manual.

[ Parent | on HN ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by whimsicalism on Friday May 19, 2023 @11:25AM (#36003058)
What freshman complexity class would teach you to conflate how fast an algorithm is in practice with the asymptotic complexity?
[ Parent | on HN ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by CaptainNegative on Friday May 19, 2023 @12:05PM (#36003537)
Not to mention that QuickSort isn't a single algorithm but rather a class of algorithms (as the choice of pivot is left unspecified), and there are methods to choose the pivot that give O(n log n) worst case or O(n log n) expected running time (e.g. median of medians or soft heaps for the former, random choice for the latter).
[ Parent | on HN ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by yjftsjthsd-h on Friday May 19, 2023 @12:05PM (#36003542)
Most of them? If the instructor doesn't call out the difference and point out that all terms of a O() expression have invisible but important constants tacked on, it's easy to accidentally conflate scaling complexity with actual total speed.
[ Parent | on HN ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by bee_rider on Friday May 19, 2023 @01:59PM (#36004949)
Why would the instructor skip that part of the the definition? Giving out wrong definitions as a prank or something?
[ Parent | on HN ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by yjftsjthsd-h on Friday May 19, 2023 @02:12PM (#36005080)
They're not intentionally avoiding it, they just get caught up in the mathematical angle and only mention its (dis)connection to real execution time in a passing comment if at all. Or they might even mention that there are constants in play... and then say that of course since they're constants we can ignore them for the purposes of O() notation. It's the difference between learning from PHDs and engineers, I suppose.
[ Parent | on HN ]
Re:FreeBSD spends 7% of its boot time running a bubblesort o... by pimbrah on Friday May 19, 2023 @11:25AM (#36003056)
he means quicksort will be enough to make further boot time improvements due to precomputing and storing the sorted list insignificants
[ Parent | on HN ]