▲ 381 points
back
358 comments
Dawson's law strikes again!
> O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there.
https://randomascii.wordpress.com/2021/02/16/arranging-invis...
GTA online was struck too
How I cut GTA Online loading times by 70% https://nee.lv/2021/02/28/How-I-cut-GTA-Online-loading-times...
For a collection of similar stories:
Probably because it's MUCH easier to code bubblesort without making mistakes that cause it to not terminate or some such. Especially if they are writing the bootloader in assembly.
For something mission critical like a bootloader that's more valuable than turning O(n^2) into O(n log n). People running systems like BSD largely don't care how long the system takes to boot, once it's booted the system runs for years.
O(n^2) algorithms often cause performance issues. The main cases I have seen in business logic are: (A) offset pagination (select ... offset n) and then paginate over all entries, and (B) read a text value, append something, store, repeat.
Off Topic: "Laying out icons on a grid should be an inherently linear operation"
it doesn't seem mentioned in the HN thread the cause here is probably the same thing O(n^2): sorting. laying out icons is only linear if the icons are read in the order that they're placed. It's been a long time since I used windows regularly but my memory is the default placement is by creation time. So if they're read off disk by filename (or some sort of hash) they'd need to be sorted by timestamp.
This made me recall modern AI and the issue with quadratic complexity in its transformers. Ooof! A breakthrough here would be a true Breakthrough™ with remarkably larger context sizes. Like it would barely even be a limit anymore and be transformative (har har) to what they can be used for.
Thanks, that's a fun read although I don't understand much of it. I do understand the gist.
Discoveries and analysis like this blog post and the parent show the difference between programmers and engineers.
True but I think the real cause of this is surely that C makes it too hard to use a sorting library that someone competent has written. I would not be surprised if the author was fully aware of the N^2 complexity but opted for a simpler implementation anyway.
So a few milliseconds in total. Big whoop. OpenBSD's ahci(4) driver stalls 5-6 seconds for each SATA device on the bus, just to make sure the device really is there and that the link speed is correct...or something. My two OpenBSD machines, which incidentally have 3 SATA drives each, spend almost 20 seconds on that one segment alone during kernel startup.
Colin (and others?) have been working to reduce the boot time of FreeBSD for a while now. At this point shaving off a few milliseconds is probably a nice win for them.
https://twitter.com/cperciva/status/1659391725427720195?t=0y...
Colin's focus has been on speeding up EC2 boot time. You pay per second from time on EC2. A few milliseconds at scale probably ads up to a decent amount of savings - easily imaginable it's enough to cover the work it took to find the time savings.
If you boot OpenBSD thousands of times per day it adds up. I can imagine this being the case for people running big server farms or doing virtualization stuff.
Well, FreeBSD has other issues too. I had re-cable all of my USB devices because it was taking forever (linux and windows booted a lot faster).
...wat? How something that bad could linger for so long?
How do the other OS's get around this?
OS should save all serial numbers of devices and after they are all found continue.
we should make it declarative or how do you want to call it.
also why cant freaking boot process be optimized after first boot? bsd is essentialy sorting SAME thing every boot, THAT is ridiculous. sort once, save order ( list, sysinit000000000000 ), boot fast next time. hardware or other change or failed boot, can trigger start sorting bull for safety.
you know what youre booting into, so sort it once then run it from saved order next time. how many times you change hardware on computer ? and if you do, you can just restart with grub flag, toggle switch in control panel before restart, etc
Based on the kernel boot time (28 ms) given by the author, this process takes 1.97 milliseconds.
I'd consider this less "haha dum code is slow" and more "you are booting the kernel way too much, even a 1.97 millisecond delay is noticable".
I think the “Firecracker” referenced in this Tweet is Amazon's “microVM” environment[0]. VMs running in this environment are sometimes booted to service scheduled/batch jobs, but are, I think, more often launched in direct response to (and with the intent of serving) an incoming HTTP request (and then stick around for a few minutes afterwards in case there are any subsequent requests). Network latency from the continental US to the nearest AWS datacentre is typically <30ms, so even after you add the response time of the application running in the VM, an extra 2ms boot time still probably makes up >2% of the total cold response time.
Yeah, and Ahmdal's law comes directly into play here. At 7% of the total boot time, this bubble sort may be the slowest part of the kernel boot. But, even if you optimized away the sort entirely somehow, you could still only save 1.97 ms. And once you do that, the next slowest thing probably doesn't take more than ~1ms to run. Eventually, you get to a state that resists these kinds of targeted optimizations, where there are no bottlenecks, and the only improvements can come from new algorithms and data structures, i.e. "uniformly slow code."
Of course, calling anything that takes place in less than a blink of an eye "slow" is overstating things... lol :-)
If only I could get my desktop environment to come up in less than 28ms :-)
Sure but Firecracker is used for AWS lambdas, so you're going to be booting those extremely frequently. (Now I wonder if Amazon is using FreeBSD for AWS lambda ..?)
We now boot so often kernels this is important.
My tv boots a kernel, Alexa's, laptops, cars etc.
And this might be not specifically critical but it's a sign of people just doing something less optimal
2.031 ms, I rounded down.
You lack the imagination to come up with a use for some improvement off the cuff, that doesn't mean everyone else (some of whom are more motivated) does as well.
Why do we even need to waste any consciousness-seconds on watching electric circuits initialize? Computers should just start working
So you might be shocked that 7% is so high, but the reason it is so high is that cperciva has been driving down the overall boot time to the tune of ~99%+ faster than two major releases ago. Bubblesort used to be <1% of total boot time because the rest of boot was so slow. Now that many of the gratuitous sleeps are gone, the next thing to look at is stupid algorithms like this.
I've seen this referred to as the "BBBB problem", as in: "nobody types BBBB into the search box, so it makes no sense to optimize the algorithm so it doesn't have worst-case complexity with repeated characters".
That is, until someone searches for e.g. git conflict markers.
Funny that this is what trends, and not the flame chart of the different boot times of different FBSD versions: https://twitter.com/cperciva/status/1659059445685420032
At a glance looks like 13.1-RELEASE booted 3x faster than 11.1-RELEASE, and 14.0-CURRENT on Firecracker boots 45x faster than 11.1-RELEASE on a c5.xlarge
When I was doing my PhD in hydrology modeling, I found a bubble sort in one of our pre-processing programs, which calculated the topographic flow network. This worked okay when the watersheds being modeled were small or the grid resolution was coarse. I however, was modeling at much finer resolution (3m^2) resulting in runtimes of more than an hour. I replaced the bubble sort with merge sort from libc and my runtimes fell to less than 5 minutes. Fun times.
I would love to see a detailed analysis of various OS boot sequences and times, it is kind of insane that modern computers and phones can take minutes to boot; what ever are they doing?
Makes me realize how spoiled I am by standard libraries nowadays.
Outside of toy projects, interviews, and teaching them, I've never actually written a sort function. I never saw the point; the sort function built into the standard library of whatever language I'm using is probably faster and/or more space efficient than whatever thing I whip up in a few seconds.
Of course, that's a privileged opinion that I am afforded by the fact that my entire career has been "Java and higher" languages.
> O(N^2) can bite hard when you're sorting over a thousand items. Time to replace the bubblesort with something faster.
... downthread ...
> I suspect quicksort will be enough though.
Somebody hasn't taken a freshman complexity theory class in a while...
(Note, this is tongue in cheek. Worst case is not average case and all that. I'm sure quicksort will do fine)
Back in the 1980s, my compiler (Datalight C) won file I/O benchmark after benchmark, year after year.
My trick was stupid simple. The usual file I/O buffer size was 512 bytes, I made it 16K.
Man that's crazy. Think of all that extra time you'll have if timsort was used! An extra 2ms to go on that walk while your system is booting.
Many years ago I worked on a piece of software that simulated networks. As networks got bigger it would run out of memory. Turned out it did something like
CONNECTION *c = malloc(num_nodes * num_nodes * sizeof(CONNECT_STRUCT));
But how long on average does it take to boot in wall clock time?
This is one of the cases where C’s low-level nature bites.
Both C++ and Rust have pretty nice sorting algorithms in the standard library. C does not (qsort doesn’t really count as a nice sorting algorithm which is why so many C programmers took their own).
I see a lot of discussion here about quicksort as an alternative.
If I'm understanding correctly, we're talking about sorting integers. Would something like radix sort not be more appropriate? Or is there a reason to still prefer a more generic sorting algorithm?
One of the replies:
https://twitter.com/cperciva/status/1659577625289928705
So this bubble sort is just under 2ms.
I think it's cool to find and optimize that, he says he'll put in a qsort and that's great. But 2ms? Probably not a huge deal.
At the risk of tempting the systemd flame wars back to life, is there data on how systemd performs? I know faster boot time was a major goal of the project[1].
Naïve question here: Sorting algorithms aside, is there a reason why the ordering of these even needs to be (re)determined at runtime every boot as opposed to the order being recomputed when the kernel is updated, and written to a file?
Gah! I was just looking at this code last night because RTEMS borrows parts of the FreeBSD codebase for drivers and networking. The sorting happens in mi_startup, in case anyone wants to look.
The story behind this: “how long do you think until they find this?”
-somebody who accepted a bet
The real story
"The kernel boot (of which 7% is bubblesort) is 28 ms."
Is there no link for the actual code?