Hacker News Reader

Comment by BearOso | Hacker News Reader

Can't use the standard library in the kernel, though. That's why there's special implementations of a lot of things you take for granted in kernel source, things like "print".

View on HN

Rust's `sort_unstable` is available in `core` and does not require the standard library or the `alloc` crate, so, if my understanding is correct, even `no_std` programs like the kernel could use it?

https://doc.rust-lang.org/core/primitive.slice.html#method.s...

(It's interesting that the stable `sort`, by contrast, is only available in `std` because it uses an allocating timsort-variant.)

So you're not wrong, but also, the Linux kernel uses a modified variant of alloc, so not only can it use sort_unstable, it also has access to sort https://github.com/torvalds/linux/blob/2d1bcbc6cd703e64caf8d...

Most relevant element of what's going on here is that Rust's standard library is deliberately split three ways: Core has stuff that should "just work" on your target platform, Alloc adds stuff that further requires a Memory Allocator, which is something target hardware doesn't come with, but any non-trivial system is likely to build, then Std adds stuff which requires an Operating System, such as Files, and Threading

C is technically also split, so called "freestanding" C implementations don't provide features like stdio but they do have e.g. math functions. C++ attempts something similar but it's a bit hit-and-miss as a truly "free standing" C++ doesn't entirely make sense, as systems that try to use C++ for very low level work often discover.

The next less relevant observation is that Rust chooses to call these sort and sort_unstable - the one that's guaranteed to be available doesn't get the easier name, that's reserved for the one that definitely doesn't have unexpected behaviour. If you don't know what an "unstable" sort is, then sort_unstable's behaviour might in some cases be astonishing. Some languages make the opposite choice, which means programmers may use sort, not realising it's actually an unstable sort because the entire concept was never explained to them.

This is one of many examples of Rust's safety achieved not via some sophisticated technology but just by thinking about why people screw up. Every Rust programmer who without thinking writes sort gets a stable sort, if that was too slow, they can choose sort_unstable, but doing so prompts them to consider, wait, is an unstable sort correct here?

Finally the least relevant but hopefully still interesting observation is that it is quite possible to have a stable sort which doesn't require allocation, but the performance is not so hot. It seems pretty unlikely that you must have a stable sort and you can't afford an allocator and yet you don't mind the performance hit. As I understand it though some C++ libraries do offer this.

As PHK points out [0] qsort was imported [1] into the kernel in 1995, it was simply never used for the boot process, but it is availible.

[0]: https://twitter.com/bsdphk/status/1659568675899228163

[1]: https://github.com/freebsd/freebsd-src/commit/d89a1b600fc071...

Looks like the code to bubble-sort the SYSINIT objects was committed a few months BEFORE this kernel qsort code was committed (late Aug 1995 vs early Nov 1995).

So that's why the sort-SYSINIT objects code didn't use qsort.

I'd also guess that there were fewer SYSINIT objects to sort back in 1995 than today.

see ~line 150 of sys/kern/init_main.c in https://github.com/freebsd/freebsd-src/commit/2b14f991e64ebe...

Seems like we are due for the cyclic interest in microkernels. I wonder what's the latest research on that front.

Reply on news.ycombinator.com