FreeBSD replaces bubblesort with mergesort on SYSINTs

yes, it was stupid to use bubble sort to begin with; there is never a good reason to use bubble sort

    for (size_t i = 0; i < n; i++) {
        for (size_t j = 1; j < n - i; j++) {
            if (a[j-1] > a[j]) {
                item_t tmp = a[j];
                a[j] = a[j-1];
                a[j-1] = tmp;
            }
        }
    }

when you could use insertion sort

    for (size_t i = 1; i < n; i++) {
        for (size_t j = i; j > 0; j--) {
            item_t tmp = a[j];
            if (tmp > a[j-1]) break;
            a[j] = a[j-1];
            a[j-1] = tmp;
        }
    }

which is no more complicated (both are 17 amd64 instructions with -Os), but twice as fast in the random case, and enormously faster in the sorted and almost-sorted cases

(above code only minimally tested: https://godbolt.org/z/43dqz9Gq8)

this is not much of a criticism of freebsd; if you polished your codebase until there was nothing stupid in it, you'd never ship anything. freebsd's code quality is quite high, but probably we can all agree that this was stupid

of course it wouldn't be nearly as fast as mergesort on large inputs, but mergesort is more complicated

(also mergesort is slower on small inputs than insertion sort or bubble sort, but in the case where you're only sorting something once at startup time, that probably isn't important. it might matter if you were sorting a million lists of ten items or something)

As is often said, O(n^2) (or even 3) is fine until it stops being fine.

It is surprising how popular is using O(N^2) algorithms that are simple in implementation even in extremely popular libraries. E. g. ICU search method: https://github.com/unicode-org/icu/blob/a7a2fdbcf257fa22c7a2... ICU is used by Python, Windows or OpenOffice.

There was an article about a Linux embedded system handling a car back-camera that had to boot within 3-5 seconds or something along those lines.

Very naiive question... But why can't you "just" memcopy and exec an image of an already booted system?

meanwhile our new dishwasher takes between two and four SECONDS from pressing the power button to showing something on the display

Yep. When work started working on boot time, FreeBSD took 30 seconds to boot. It’s now down under 10 seconds. Many have contributed, but Colin’s done a lot of it [0].

[0]: https://wiki.freebsd.org/BootTime#Past_Performance_Improveme...

People, including me, used to think I knew some special sauce about optimization. It's true that I have a bit more mechanical sympathy than most people, due to not only the curriculum at my school but which parts fascinated me.

The big thing is that I'm willing to sit down and earn a 50% improvement in performance by doing 10x 4% improvements in perf time. That's perseverance and foresight. Most of what I know about optimization tricks vs optimization process wouldn't quite fill up the first Gems book.

It's all about budget. If you're trying to double, quadruple the performance of something, you can't look at what the 5 slowest things are. You have to look at the thing taking 5% of the time and ask, "Does this deserve 20% of the CPU?" Because if you get 4x without touching this code, that 5% becomes 20%.

Then you don't work on the tall tent poles first, you work on the hot spots that relate to each other, and the ones you have the time and attention to do well. Because if you get a 20% improvement where a 25% improvement is possible, most bosses will not let you go back for the 2 x 2.5% later if you don't get it the first time. So then you are forever stuck with 50 x 1.5% slowdowns. Which is not a problem if you're profitable, but definitely is if you're bleeding money on hosting. Or if your main competitor is consistently 50% faster than yours.

This is known as the hotspot or bottleneck model of optimization. It has its flaws:

https://lemire.me/blog/2023/04/27/hotspot-performance-engine...

FWIW: As an instructor, I used to include bubblesort when talking about sorting algorithms.. I stopped, because too many students saw it presented as an algorithm, and thought it was therefore a valid choice. It is not. As others have pointed out, insertion sort and selection sort are just as simple, but significantly faster.

As long as the quantity of data is small, there is nothing wrong with using an n^2 algorithms for sorting. They are simple, robust, stable, and easy to implement correctly.

Sure, things may change. In 25 years, you may have 1000 elements instead of 10. If that happens, your successors can change the algorithm to meet the new requirements. That's what software maintenance is all about.

To me, bubble sort is intuitive, as far as sorting algorithms or their detailed implementations go.

I absolutely wouldn't sort that way if I were to sort something as a human, but in that case I wouldn't be even trying to figure out an exact systematic logic with its minute details that always gets it right. I'd be thinking in terms of ad hoc problem solving, and possibly some heuristics for speeding it up. When thinking of algorithms in a programming (or CS) sense, getting the exact logic right down to the detail is exactly what you'll need to do. So, to me, those aren't the same kind of intuitive.

As is probably common, a bunch of simple sorting algorithms were given as some kinds of introductory examples of algorithms during my first university programming courses. I think those included selection sort, bubble sort and insertion sort. I don't think I initially considered bubble sort the more intuitive one (I think selection sort was it for me). But for some reason, over the years the basic logic of bubble sort became more obvious to me than those other options. So, at least personally, maybe there's something else to it than following the herd.

Of course I've never actually written bubble sort in any kind of real code, but it's still perhaps the most intuitive one to me, in terms of detailed algorithms rather than in terms of heuristics for human problem solving. (Merge sort is also about as intuitive to me at least as a general idea.)

According to the Twitter thread linked, at the beginning there were only 30 items, so using bubblesort didn't matter. The number of items has since grown to a thousand.

Two reasons: First, it's not worth screwing with the linker to save 20 microseconds. Second, you need to merge lists anyway because kernel modules.

Why not boot as a compilation step, and save a memory instance to be loaded on actual boots.

No good reason. It would just require something fiddly with the linker / build process. This is good enough.

That paradigm used to be a thing for things like home-computer games-- the game might take 5 minutes for an anemic Commodore 1541 drive to load, so you'd use a "freeze" cartridge that snapshotted RAM after the load finished and produced something smaller; I suspect a major side appeal was that you bypassed copy-protection that involved the loading process.

On a more complex system, with external devices active at all times, this gets a lot harder. It would be easy to take a snapshot at the "wrong" time when something is deadlocked on a timer or external device that won't be in an appropriate state at the next power on. A "boot" process ensures everything attached has been roused from their slumber and get them back to a known state.

OTOH, I could imagine if you were designing to a specific enough use case, you could design a system that relied on a minimal support devices and a CPU that bit-banged almost everything, so you knew if you were in the idle loop, everything was safe to snapshot.

Would it?

Read in small amount of code (or execute directly from flash) & use that to initialize hardware, might just be faster than read memory dump of already-initialized system.

Also the "read memory dump" method would include code & data structures which were used on a previous run, but may not be needed for the next run (or only much later). And not re-initialize hardware which may have gone flaky, or changed configuration in the meanwhile (like USB port with different device plugged vs. state that memory dump reflects).

Rebooting is just an all around cleaner method to return system to a known state. But of course it all depends on hardware specifics & what type(s) of initialization is done.

That's what windows fast startup does, it starts from a post-boot hibernated state of RAM. Linux mint on the same laptop boots fully in less time.

Would be insecure because nothing would be randomized, all your systems would have the same ASLR slide, etc.

> When the FreeBSD kernel boots in Firecracker (1 CPU, 128 MB RAM), it now spends 7% of its time running a bubblesort on its SYSINITs.

It’s a 100x speed increase on 7% of the boot time, so it should be approximately a 7% decrease in boot time.

The 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.)

welcome to amdahl's law

They explain this further on in the Twitter thread. It's the portion of time spent sorting the array of system calls during boot. This didn't used to matter when it took longer than a second to boot up, but now that the boot times are in the sub-second range, the amount of time spent sorting the array of system calls ended up taking up a notable chunk of the time spent booting.

Might not matter for the things you care about, but some people certainly do care about boot performance.

The author mentions in the thread that the boot time they measured on the device was 28 ms and 7% of it (2 ms) was spent sorting.

On the sorting of SYSINIT (not sysint as the title says) calls during bootup. The actual speedup is only a couple milliseconds but that means the old method was in the order of hundreds of milliseconds. Which is indeed a lot for a sorting operation.

100x faster on 7% of Firecracker boot

So ~5ms speedup