Our great sponsors
-
freebsd-src
The FreeBSD src tree publish-only repository. Experimenting with 'simple' pull requests....
-
WorkOS
The modern identity platform for B2B SaaS. The APIs are flexible and easy-to-use, supporting authentication, user identity, and complex enterprise features like SSO and SCIM provisioning.
Looks like the code to bubble-sort the SYSINIT objects was committed a few months BEFORE this kernel qsort code was committed. So that's why the code didn't use qsort.
see ~line 150 of sys/kern/init_main.c in https://github.com/freebsd/freebsd-src/commit/2b14f991e64ebe...
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...
Here is 9 year old bug that is still not fixed:
https://github.com/systemd/systemd/issues/2460
Long story short: there is no useful indexing in journald DB format which means looking for say "last message app emitted" means looking thru every file.
As long as it is mmaped in or on tmpfs it is reasonably fast, but if you say have last 1GB of logs stored on spinning rust on NAS.... you either have 3-4 second wait till it finds those few log lines, or buffer cache littered with that GB of logs, pushing out actually useful stuff.
It literally have worse performance than grepping entire /var/log last time I checked.
And it seems in its entirety it was "Lennart wanted to make a binary log format" vs something actually useful... just having SQLite DB instead would on top of being faster far more useful (ability to SQL query logs on local node with no extra fuss would be awesome)
Did a bit of digging and found that there used to be a comment for why it was done, but it got removed [0] when they switched to the implementation from Bentley & McIlroy's "engineering a sort function" [1] around 1992.
[0]: https://github.com/weiss/original-bsd/commit/d3fcf71e0db57cb...
[1]: https://cs.fit.edu/~pkc/classes/writing/papers/bentley93engi...