8 ms·
Boot time was reduced by 2ms, from 28ms to 26ms. Hardly 100x speed.
by _3u10 3y ago
Boot time was reduced by 2ms, from 28ms to 26ms. Hardly 100x speed.
- cperciva 3y agoThe mergesort is roughly 100x faster than the bubblesort was. I made no claim in that tweet about the overall speedup. (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.)
- dataflow 3y agoWhy does any sorting anywhere use bubble sort at all? Aren't there sorts out there that are strictly better?
- _3u10 3y agoBecause bubble sort is often faster for small sorts and it’s easy to write. This is the kernel, there’s no libc you have to write the sort algo yourself.
- IshKebab 3y agoIt's really because C doesn't have a proper dependency management system like modern languages do. If it did there's no reason you couldn't import a third party sorting algorithm in the kernel. You can do that in Rust for example, although you would just use the built in sort in this case.
- throwawaylinux 3y agoIt's not because of that. There exist countless BSD compatible code out there, and many are taken and used in projects like this. CRC codes being an obvious example. There is no reason sort code could not have been grabbed from somewhere, no "dependency management system" required. The FreeBSD kernel has its own existing sort libraries already in the code too -- https://cgit.freebsd.org/src/tree/sys/libkern/qsort.c?id=9a7add6d01f3c5f7eba811e794cf860d2bce131d https://cgit.freebsd.org/src/tree/sys/libkern/qsort.c?id=9a7... 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.
- tialaramex 3y ago> 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.
- throwawaylinux 3y agoI'm not sure what part of my post you are addressing. 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.
- tialaramex 3y ago> you would have to bring up the rust runtime environment as part of the boot process 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.
- throwawaylinux 3y ago> > you would have to bring up the rust runtime environment as part of the boot process > 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.
- cperciva 3y agoOptions for sorting algorithms are severely limited when (a) you can't use malloc, (b) you don't have enough stack to recurse, and (c) you want a stable sort. (The first two limitations are because this happens very early in the boot process.)
- dataflow 3y agoThanks! I completely forgot about the malloc/in-place aspect.
- magicalhippo 3y agoWhy the hash stack limit? I assume this precludes a fixed-size array.
- ahoka 3y agoI'm not sure when this sort happens, but early boot may not have a proper virtual memory implementation yet, so the kernel has to use a fixed stack size allocated by the boot loader.
- kevans91 3y agoRight, in this case specifically we're running off a limited bootstack allocated in the kernel's .bss (somewhere between 2 to 6 pages, generally); we won't finish initializing VM until shortly after this sort is done (in some of the SYSINITs that we're sorting).
- aidenn0 3y agoDoesn't mergesort require malloc?
- cperciva 3y agoThere are in-place array mergesorts. (Nobody uses them because they're horribly complicated, though.) In this case however I'm putting all of the SYSINITs onto a linked list; mergesorting a linked list is easy.
- knome 3y agosure, but bubble sort is trivial to write. they may have figured they'd replace it when they needed to. they may have figured the particular usage was so trivial they would never need to. 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. So the section was written in 98 and had some bits modified in 2001. 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.
- naniwaduni 3y agoYou'd still think it'd be easier to write an insertion sort though, even accidentally! It's almost the same algorithm conceptually, except cutting out an odd pessimization.
- ynik 3y agoBubble sort is optimal for sorting data stored on tapes (no random access possible). If you have RAM, insertion sort is strictly superior (both simpler code + better performance).
- _3u10 3y agoTotally agree but the title makes it sound like it’s 100x at init. I know you didn’t write the title…
- MBCook 3y agoWay to go. 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.
- cperciva 3y agoI believe Linux is at 75-80 ms for the same environment where I have FreeBSD booting in 25 ms. That comes from a Firecracker benchmark which I think is an apples-to-apples comparison with what I'm measuring in FreeBSD, but I'm not 100% certain. Once FreeBSD support is merged into mainline Firecracker (it's currently in a feature branch) I'm going to see if I can apply their performance tests to FreeBSD.
- butterisgood 3y agoI’d purchase a simpler, easier to debug algorithm over a complicated one for 2ms. But that’s me… The overall speedups are still quite impressive - but for “thousands” of data items a simple O(n^2) algorithm seems fine, doesn’t it?
- joshu 3y agowelcome to amdahl's law
- ashishgautam0 3y agoHey what's amdahl's law. Can you explain
- trostaft 3y agoThe Wikipedia article is pretty good, but tldr: "the overall performance improvement gained by optimizing a single part of a system is limited by the fraction of time that the improved part is actually used." https://en.wikipedia.org/wiki/Amdahl%27s_law https://en.wikipedia.org/wiki/Amdahl%27s_law Usually used in the parallel computing context, but works here too.
- bombcar 3y agoSo if you have something that takes 1 second out of 10 seconds, you can't improve the overall system more than 1 second (by removing it entirely).
- astrange 3y agoThat's not true, because in addition to taking 1 second it could be emptying all your caches. Performance isn't just adding up wallclock times.
- robocat 3y agoSame thing happens when driving - your trip duration usually depends on the slow bits not the faster parts e.g. in NZ driving through small towns will often be the longest part of your trip time.
- _3u10 3y agoSomething about 5% of things can’t be parallelized which then ends up dominating performance after the 95% of things that can be parallelized are.