(But since you mention it, when I started working on speeding up the boot process, the kernel took about 10 seconds to boot, so I have a kernel booting about 400x faster now than I did a few years ago.)
The real reason is because this is an early boot environment with exact constraints that are unusual if not unique to FreeBSD where the facilities to support your general language / runtime environment is not up yet.
Rust's [T].sort_unstable() is part of core, that is, the code to sort a slice of arbitrary type T doesn't need the allocator, operating system etc.
Only if you want a fast stable sort do you need to wait for such an environment because their fast stable sort needs an allocator, I doubt that FreeBSD needs a stable sort here.
If you had a kernel written in Rust, you would have to bring up the rust runtime environment as part of the boot process. You don't just magically get it because that's the language you used, whether it is "core" or not. You can't even execute simple functions before you have set up stack, and in this case apparently there is a constraint on stack usage. And evidently they do need a stable sort.
In any case my main point is that it's not anything to do with dependency management, not quibbling about whether or not some language could support this function at this exact point of the boot.
Like the existing C runtime environment, this just isn't a big deal by the time we've got here. If you're the code for initialising the DRAM controller then sure, that's pretty intimidating. But this is all happening much later, we're part of an operating system, we were already loaded from disk.
> And evidently they do need a stable sort.
How so? They appear to even have a deliberate tie-breaking mechanism in their data structure, which suggests if order actually matters you're expected to specify when creating the data, not rely on stability to do what you expected.
> Like the existing C runtime environment, this just isn't a big deal by the time we've got here. If you're the code for initialising the DRAM controller then sure, that's pretty intimidating. But this is all happening much later, we're part of an operating system, we were already loaded from disk.
I don't know what you're trying to say. The code which is written here that we are discussing is in a constrained environment where the regular kernel runtime facilities are not all available. This was cited as one of the reasons cited for open coding a very simple algorithm.
> > And evidently they do need a stable sort.
> How so?
From reading comments from patch author here.
The SYSINITs need to bring up the system in a particular order. I dunno why there are both explicit ordering (the sort keys) and implicit ordering (the stability requirement), perhaps cperciva can chime in.
Based on when I last looked at this code, I guess the explicit ordering is to do with startup phases, and the implicit ordering is because of the way SYSINITs are (or were?) implemented using linker sets, which have more guarantees about ordering than __attribute__((constructor)) and other similar functionality.
In the event Colin is looking at this sub-thread now I'm intrigued too.
What we need isn't actually "stable" so much as "consistent from one boot to the next" to make sure that ordering bugs don't end up being heisenbugs.
This may be impractical, but I think my reaction would be to re-design it so that the ordering was mechanically a full order, even if culturally the people writing these things don't need to specify if they don't want to.
e.g. maybe a macro can turn your existing explicit order into high bits of a value, and then a "noise" factor into low bits, where that "noise" is derived from a date integer like 20230822 or filenames or whatever, and truly order on the entire value.
The idea is, this means any hidden order is the same for everyone, Intel laptop test rig, ARM WiFi cameras at customer site, last week's build, this week's build, Colin's build, the CI system's build, they're all using the same order, because while heisenbugs are strictly worse, "It only happens with my setup" is also extremely frustrating.
When people discover a hidden ordering requirement they can adjust the "real" ordering accordingly, just now there's a deliberate systemic consistency.
Probably not worth all the bother, but I think I couldn't live with the "stable sort to avoid heisenbugs" situation.
What facilities does Rust's sort require? It probably just needs a bit of stack but that's it.
That qsort implementation doesn't look like it needs anything either tbh, though I only skimmed it.
Maybe they could permit some of their sort library functions to be used in such a constrained environment, sure. Don't need rust to do that, just need to be happy that the implementation is suitable for purpose. Which they would have to do regardless of what language and runtime they were using.
(The first two limitations are because this happens very early in the boot process.)
In this case however I'm putting all of the SYSINITs onto a linked list; mergesorting a linked list is easy.
grabbed the source and git blamed the file before the patch to see when the original code was from.
94e9d7c12 (Peter Wemm 1998-10-09 23:42:47 +0000 157) * The sysinit table itself. Items are checked off as the are run.
94e9d7c12 (Peter Wemm 1998-10-09 23:42:47 +0000 158) * If we want to register new sysinit types, add them to newsysinit.
The time wasted during boot here was probably irrelevant next to a hundred other things the project has worked on since.
the bubble sort was good enough that 25 years later they replaced it to save only 2ms during boot.
seems reasonable to me.
I just coarsely checked TAOCP volume 3, and didn’t see bubble sort mentioned in the chapter on external sorting.
Do you know how fast Linux starts up? I found the number 125ms but that’s a 4 year old number.
Just curious how similar they are. This is the first I’ve heard of Firecracker.
The overall speedups are still quite impressive - but for “thousands” of data items a simple O(n^2) algorithm seems fine, doesn’t it?