18 ms·

FreeBSD spends 7% of its boot time running a bubblesort on its SYSINITs

381 points by gslin 3y ago

erdaniels 3y ago
But how long on average does it take to boot in wall clock time?
- Skunkleton 3y ago
  This is firecracker, so less than a second I guess?
- cwillu 3y ago
  This is from a year old tweet so it may not be correct anymore, but: “FreeBSD/Firecracker now boots to a login prompt in 782 ms. 170 ms of this is spent generating a self-signed TLS certificate for sendmail, because of course it is.”
  - yakubin 3y ago
    FreeBSD 14 is going to replace sendmail with DragonFlyBSD’s dma.
  - pjc50 3y ago
    It's 2023, I don't think any system calling itself "minimal" should have an MTA.
    - JdeBP 3y ago
      The notion that the system mails things to certain local accounts is still quite strong in FreeBSD. In fairness, it's a notion that has a long history in Unices in general; so it isn't FreeBSD Think. On the gripping hand, it's mad that it's still Sendmail, although that is going to change. It's 2023, and the fact that a FreeBSD system still has the traditional ~2000 lines of indistinguishable-from-line-noise "DO NOT EDIT THIS" stuff in /etc/mail/sendmail.cf, complete with whole bunches of rules for UUCP, is rather amazing. I wonder how many small FreeBSD systems out there are spending their time double-bouncing cron-job mail that cannot be delivered. (-:
    - stephan-cr 3y ago
      Recently, I tested FreeBSD and it seems one can disable sendmail. See https://docs.freebsd.org/en/books/handbook/bsdinstall/#bsdinstall-hardening https://docs.freebsd.org/en/books/handbook/bsdinstall/#bsdin....
- cperciva 3y ago
  In that particular case, 620 ms for the entire boot process. 28 ms for the kernel boot (of which 7% or 2 ms is the bubblesort).
  - senko 3y ago
    Looking from the outside, this is astonishing. I suspect Firecracker is set up to be as quick to initialize as possible, but still that a vanilla (ie not an optimized fork) can do that ... My phone takes a two orders of magnitude more! I hope your BSDCan talk is getting recorded.
    - cperciva 3y ago
      Yes, talks are being recorded, should be up on YouTube in a month or two depending on how busy the (volunteer) video editors are.
    - maccard 3y ago
      Your phone boots in 2.8 seconds? Mine is closer to 2.8 minutes.
      - senko 3y ago
        No, closer to 62 seconds (which is 100x the total boot time, not just the kernel)
- throw0101c 3y ago
  > The kernel boot (of which 7% is bubblesort) is 28 ms. * https://twitter.com/cperciva/status/1659577625289928705 https://twitter.com/cperciva/status/1659577625289928705
Tade0 3y ago
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.
- arnsholt 3y ago
  At a previous job, I debugged a close relative of that exact problem: sorting list views was very slow when you wanted to sort on a column with very few distinct values in a large table. The culprit was of course a quick sort degenerating to n squared performance.
  - kzrdude 3y ago
    And pattern-defeating quicksort is one example of a solution to that
  - epx 3y ago
    Had this problem in xBase (Clipper with NTX indexes): sorting by date but there were many null (empty) dates in that particular column. Added another date column (that was never null) to the index just to provide entropy.
bombcar 3y ago
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?
- secondcoming 3y ago
  initialising hardware mostly.
- EscapeFromNY 3y ago
  On linux you can use systemd-analyze and get a nice svg waterfall chart of the boot-time dependency chains.
  - yjftsjthsd-h 3y ago
    On the subset of Linux distros that use systemd, rather. Thankfully, there are other options (https://elinux.org/Bootchart https://elinux.org/Bootchart seems a decent overview)
    - freedomben 3y ago
      > On the subset of Linux distros that use systemd, rather. Worth noting that Fedora, RHEL/CentOS/et al, Debian, Ubuntu, Arch and derivatives use systemd, so odds are pretty high if you use "Linux" you also get systemd
      - yjftsjthsd-h 3y ago
        That's true; I think the only major user-facing Linux distros without systemd (or with non-systemd versions) these days are Gentoo, Void, Alpine, and Android (which may or may not count). Embedded stuff is probably more of a mixture (openwrt doesn't use systemd, yocto and buildroot can use it but optionally), and firecracker feels closer to embedded than desktop but both ends are interesting. I dunno, I mostly just object to conflating "Linux" with systemd even if it is the most popular option (but bear in mind that I have strong opinions about "Linux" vs "GNU/Linux", so YYMV;]).
klyrs 3y ago
> 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)
- pimbrah 3y ago
  he means quicksort will be enough to make further boot time improvements due to precomputing and storing the sorted list insignificants
- whimsicalism 3y ago
  What freshman complexity class would teach you to conflate how fast an algorithm is in practice with the asymptotic complexity?
  - CaptainNegative 3y ago
    Not to mention that QuickSort isn't a single algorithm but rather a class of algorithms (as the choice of pivot is left unspecified), and there are methods to choose the pivot that give O(n log n) worst case or O(n log n) expected running time (e.g. median of medians or soft heaps for the former, random choice for the latter).
  - yjftsjthsd-h 3y ago
    Most of them? If the instructor doesn't call out the difference and point out that all terms of a O() expression have invisible but important constants tacked on, it's easy to accidentally conflate scaling complexity with actual total speed.
    - bee_rider 3y ago
      Why would the instructor skip that part of the the definition? Giving out wrong definitions as a prank or something?
RcouF1uZ4gsC 3y ago
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).
- thomasmg 3y ago
  Why do you think qsort is not nice? I could imagine that qsort is not an option in FreeBSD for example because it is recursive and there is no stack at that level, or there is a risk of stack overflow. If that's the case, shell sort should be fine I guess.
- BearOso 3y ago
  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".
  - floxy 3y ago
    Seems like we are due for the cyclic interest in microkernels. I wonder what's the latest research on that front.
  - tczMUFlmoNk 3y ago
    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.sort_unstable 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.)
    - steveklabnik 3y ago
      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/2d1bcbc6cd703e64caf8df314e3669b4786e008a/rust/alloc/slice.rs#L274 https://github.com/torvalds/linux/blob/2d1bcbc6cd703e64caf8d...
chaxor 3y ago
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.
- pkaler 3y ago
  This is for FreeBSD Firecracker. This means this is used for AWS Lambda and Fargate. A whole bunch of 2ms wins is how one would improve cold start time.
- noisy_boy 3y ago
  This is talking about Firecracker[0] which is for microvm deployments so I would think it is the aggregate effect of losing that 7% across a large number of spin-ups that would make a difference. Occasional reboot on your personal machines obviously doesn't make a dent. [0]: https://firecracker-microvm.github.io/ https://firecracker-microvm.github.io/
  - ilyt 3y ago
    I'd imagine if you wanted absolute boot time you'd just use a container
    - insanitybit 3y ago
      Containers are inappropriate for many workloads, such as any workload that relies on multitenancy.
  - vidarh 3y ago
    The lower the boot time, the more aggressively you can also afford to shut them down when not in use, freeing up capacity.
- operator-name 3y ago
  I wanted to figure out the cost to all users. BSD is sometimes used in some iot-like devices, of which there are 3 billion. If I randomly assume 0.5% of those are running a fork of FreeBSD, that's 15 million devices. I'm also going to randomly assume that devices reboot once a month on average. That all comes out to 4.2 days/year saved! Wow! https://www.wolframalpha.com/input/?i=2ms+*+3+billion+*+0.5%25+*+1+%2F+month+to+days+per+year https://www.wolframalpha.com/input/?i=2ms+*+3+billion+*+0.5%...
gkbrk 3y ago
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".
- cperciva 3y ago
  2.031 ms, I rounded down.
- lkbm 3y ago
  Probably true. My question was "how often is this run?" I assume it's not just once when I first turn on my laptop from fully off. Is it once every time I restart a Docker container? (Assuming FreeBSD images.) Is it something that runs a couple times a day, a dozen times a day, a thousand times a day? Fifty times every time I open an Electron app? I suspect this doesn't matter and is more a curiosity, but I wouldn't be shocked to learn otherwise.
- rwmj 3y ago
  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 ..?)
  - cperciva 3y ago
    AWS Lambda does not support FreeBSD. It would be great if that changed though...
- MrDOS 3y ago
  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. [0]: https://firecracker-microvm.github.io/ https://firecracker-microvm.github.io/
tonetheman 3y ago
[dead]
daniel-thompson 3y ago
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-invisible-icons-in-quadratic-time/ https://randomascii.wordpress.com/2021/02/16/arranging-invis...
- 908B64B197 3y ago
  Discoveries and analysis like this blog post and the parent show the difference between programmers and engineers.
- IshKebab 3y ago
  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.
  - pjc50 3y ago
    qsort() not good enough for you? (More realistically, below people are discussing that in the kernel environment the set of standard or third party library available may be unavoidably limited)
    - jart 3y ago
      qsort() is pretty slow if you're sorting something like long[]. In that case, radix sort goes 5x faster and vectorized quicksort goes 10x faster. If you're sorting int[] then vectorized quicksort goes 25x faster than qsort(). Nothing goes faster. The issue is it's a big ugly c++ monstrosity that's a huge pain to compile.
      - rcxdude 3y ago
        That's fair if the constant factor is relevant, but if bubble sort is terminating in any reasonable timescale then the difference between qsort, C++ std::sort, and a custom implementation is really not a factor.
deleted 3y ago
[deleted]
0xbadcafebee 3y ago
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 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
asveikau 3y ago
One of the replies: https://twitter.com/cperciva/status/1659577625289928705 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.
avidphantasm 3y ago
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.
- tombert 3y ago
  Tangential, but in my Java class recently I was teaching teaching the students some basic Big O stuff. I wrote a few versions of a program that found the "biggest delta" of two numbers in a list. The first version was O(n^2) time, the next version was just O(n). I showed them how long it took to run the O(n^2) on 100000 elements, about two minutes on my beefy server. Then I showed them the O(n) version running on my comparatively weaker laptop, and it took about ten seconds to run a million elements. The students were genuinely kind of impressed, and I stressed the point to say that "these are the kind of numbers that make it important to take theory seriously."
  - saagarjha 3y ago
    O(n) for 1 million elements taking ten seconds is pretty long. What’s the constant factor?
deleted 3y ago
[deleted]
daneel_w 3y ago
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.
- jhalstead 3y ago
  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_F1T03dyGuBb8PjECm7Q&s=19 https://twitter.com/cperciva/status/1659391725427720195?t=0y...
  - taeric 3y ago
    I mean, I get it. But shaving 4.5ms does seem to fall into the realm of not most peoples problems? Note that I want to stress that that is no reason for some folks to stop focusing on it. And kudos on the improvement. Criticism, if any, here is that statistics once again rears its head to make something feel bigger by using a percent.
    - nextaccountic 3y ago
      > I mean, I get it. But shaving 4.5ms does seem to fall into the realm of not most peoples problems? If whoever is fixing this depend on quickly launching instances in Firecracker, it's their problem. And that's how open source is usually done
      - taeric 3y ago
        Sorta. They have to rely on this on a repeated basis such that it matters. And there, if startup time is still 10x this, roughly, why push for solutions that require that many kernel startups?
jgrahamc 3y ago
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)); And almost the entire matrix was empty because most things in a network aren't connected to each other. I spent a a few minutes replacing that with a hash table on the (i, j) node pair.
loeg 3y ago
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.
- deleted 3y ago
  [deleted]
tombert 3y ago
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.
- repiret 3y ago
  In my first computer science class in college, after finishing the unit on Red-Black Trees, the professor said something like "Now you should never implement a Red-Black Tree again. If you need a balanced binary tree, use std::map or whatever your standard library provides. Same goes for all the other sorting and data structures we've done in this class." Relatedly: Q: When is Python faster than C? A: When the C programmer used a linked list or some O(n^2) algorithm because they didn't have a standard library full of easy to use well implemented data structures and algorithms.
  - tombert 3y ago
    That's actually something I've been saying for quite awhile when people bring up microbenchmarks complaining about how a language like Haskell is slow. Like, yes, no question, if you try and implement a tightloop in Haskell vs C, C is going to come out a lot faster. However, no one writes Haskell like that! People rely pretty heavily on standard libraries (or even third party libraries), and on the optimizations afforded to them by the "rich" language of Haskell. C might be capable of being faster, but that doesn't imply that a C program will inherently be faster than a similar Haskell program, especially if the programs are relatively large.
  - norir 3y ago
    Even though I kind of mostly agree that you almost never should implement your own rb tree, this advice is also kind of disempowering and I worry that it is part of a mindset that accepts the status quo when it is so often the case that we could have better things if we just got our hands a little dirty.
freedomben 3y ago
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]. [1]: http://0pointer.de/blog/projects/systemd.html http://0pointer.de/blog/projects/systemd.html
- ilyt 3y ago
  My personal/corporate, n=~500 experience is that it boots faster, shuts down slower (technically because it is doing it "properly"), and if you have any problem during shutdown it is absolute PITA to debug why. We did managed to throw away few thousand lines of code of fixed init scripts after moving to systemd and get rid of few other stuff so it has been positive but definitely some of the bad with a lot of good. Journald logging format is also kinda fucked that causes some nasty edge cases Except of systemd-resolved, this utterly radioactive piece of shit can go fuck itself.
  - taneliv 3y ago
    Do you have more details on the journald issues?
    - ilyt 3y ago
      Here is 9 year old bug that is still not fixed: https://github.com/systemd/systemd/issues/2460 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)
aflag 3y ago
Is there no link for the actual code?
- JdeBP 3y ago
  It's FreeBSD. The source for base comes with the operating system, in this particular case in /usr/src/sys/kern/init_main.c .
  - canucker2016 3y ago
    Starting around line 255 in init_main.c (or search for bubble). see https://github.com/freebsd/freebsd-src/blob/40b287054521f0a92e5ae9a26e6a87d17ee85eea/sys/kern/init_main.c https://github.com/freebsd/freebsd-src/blob/40b287054521f0a9...
    - jodrellblank 3y ago
      (btw If you click on the line numbers in Github, you get a three-dots popup, click that and you can "Copy Permalink" to get a link directly to the line which has #L255 on the end, e.g. https://github.com/freebsd/freebsd-src/blob/40b287054521f0a92e5ae9a26e6a87d17ee85eea/sys/kern/init_main.c#L255 https://github.com/freebsd/freebsd-src/blob/40b287054521f0a9... )
    - aflag 3y ago
      Fascinating. It’s just plain old bubble sort. Why did they choose to do that? I don’t get the benefits of it. If they are going for simplicity, why not selection or insertion sort?
xp84 3y ago
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?
sn9 3y ago
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?
deleted 3y ago
[deleted]
kgbcia 3y ago
The real story "The kernel boot (of which 7% is bubblesort) is 28 ms."
inamberclad 3y ago
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.
barbariangrunge 3y ago
The story behind this: “how long do you think until they find this?” -somebody who accepted a bet
WalterBright 3y ago
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.
- WalterBright 3y ago
  P.S. I learned that trick from Shal Farley, who dramatically speeded up DECUS' Runoff program (an ancestor of Markdown) by doubling the buffer size.

381 points by gslin 3y ago

erdaniels 3y ago

But how long on average does it take to boot in wall clock time?

Skunkleton 3y ago
This is firecracker, so less than a second I guess?
cwillu 3y ago
This is from a year old tweet so it may not be correct anymore, but: “FreeBSD/Firecracker now boots to a login prompt in 782 ms. 170 ms of this is spent generating a self-signed TLS certificate for sendmail, because of course it is.”
- yakubin 3y ago
  FreeBSD 14 is going to replace sendmail with DragonFlyBSD’s dma.
- pjc50 3y ago
  It's 2023, I don't think any system calling itself "minimal" should have an MTA.
  - JdeBP 3y ago
    The notion that the system mails things to certain local accounts is still quite strong in FreeBSD. In fairness, it's a notion that has a long history in Unices in general; so it isn't FreeBSD Think. On the gripping hand, it's mad that it's still Sendmail, although that is going to change. It's 2023, and the fact that a FreeBSD system still has the traditional ~2000 lines of indistinguishable-from-line-noise "DO NOT EDIT THIS" stuff in /etc/mail/sendmail.cf, complete with whole bunches of rules for UUCP, is rather amazing. I wonder how many small FreeBSD systems out there are spending their time double-bouncing cron-job mail that cannot be delivered. (-:
  - stephan-cr 3y ago
    Recently, I tested FreeBSD and it seems one can disable sendmail. See https://docs.freebsd.org/en/books/handbook/bsdinstall/#bsdinstall-hardening https://docs.freebsd.org/en/books/handbook/bsdinstall/#bsdin....
cperciva 3y ago
In that particular case, 620 ms for the entire boot process. 28 ms for the kernel boot (of which 7% or 2 ms is the bubblesort).
- senko 3y ago
  Looking from the outside, this is astonishing. I suspect Firecracker is set up to be as quick to initialize as possible, but still that a vanilla (ie not an optimized fork) can do that ... My phone takes a two orders of magnitude more! I hope your BSDCan talk is getting recorded.
  - cperciva 3y ago
    Yes, talks are being recorded, should be up on YouTube in a month or two depending on how busy the (volunteer) video editors are.
  - maccard 3y ago
    Your phone boots in 2.8 seconds? Mine is closer to 2.8 minutes.
    - senko 3y ago
      No, closer to 62 seconds (which is 100x the total boot time, not just the kernel)
throw0101c 3y ago
> The kernel boot (of which 7% is bubblesort) is 28 ms. * https://twitter.com/cperciva/status/1659577625289928705 https://twitter.com/cperciva/status/1659577625289928705

Tade0 3y ago

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.

arnsholt 3y ago
At a previous job, I debugged a close relative of that exact problem: sorting list views was very slow when you wanted to sort on a column with very few distinct values in a large table. The culprit was of course a quick sort degenerating to n squared performance.
- kzrdude 3y ago
  And pattern-defeating quicksort is one example of a solution to that
- epx 3y ago
  Had this problem in xBase (Clipper with NTX indexes): sorting by date but there were many null (empty) dates in that particular column. Added another date column (that was never null) to the index just to provide entropy.

bombcar 3y ago

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?

secondcoming 3y ago
initialising hardware mostly.
EscapeFromNY 3y ago
On linux you can use systemd-analyze and get a nice svg waterfall chart of the boot-time dependency chains.
- yjftsjthsd-h 3y ago
  On the subset of Linux distros that use systemd, rather. Thankfully, there are other options (https://elinux.org/Bootchart https://elinux.org/Bootchart seems a decent overview)
  - freedomben 3y ago
    > On the subset of Linux distros that use systemd, rather. Worth noting that Fedora, RHEL/CentOS/et al, Debian, Ubuntu, Arch and derivatives use systemd, so odds are pretty high if you use "Linux" you also get systemd
    - yjftsjthsd-h 3y ago
      That's true; I think the only major user-facing Linux distros without systemd (or with non-systemd versions) these days are Gentoo, Void, Alpine, and Android (which may or may not count). Embedded stuff is probably more of a mixture (openwrt doesn't use systemd, yocto and buildroot can use it but optionally), and firecracker feels closer to embedded than desktop but both ends are interesting. I dunno, I mostly just object to conflating "Linux" with systemd even if it is the most popular option (but bear in mind that I have strong opinions about "Linux" vs "GNU/Linux", so YYMV;]).

klyrs 3y ago

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

pimbrah 3y ago
he means quicksort will be enough to make further boot time improvements due to precomputing and storing the sorted list insignificants
whimsicalism 3y ago
What freshman complexity class would teach you to conflate how fast an algorithm is in practice with the asymptotic complexity?
- CaptainNegative 3y ago
  Not to mention that QuickSort isn't a single algorithm but rather a class of algorithms (as the choice of pivot is left unspecified), and there are methods to choose the pivot that give O(n log n) worst case or O(n log n) expected running time (e.g. median of medians or soft heaps for the former, random choice for the latter).
- yjftsjthsd-h 3y ago
  Most of them? If the instructor doesn't call out the difference and point out that all terms of a O() expression have invisible but important constants tacked on, it's easy to accidentally conflate scaling complexity with actual total speed.
  - bee_rider 3y ago
    Why would the instructor skip that part of the the definition? Giving out wrong definitions as a prank or something?

RcouF1uZ4gsC 3y ago

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

thomasmg 3y ago
Why do you think qsort is not nice? I could imagine that qsort is not an option in FreeBSD for example because it is recursive and there is no stack at that level, or there is a risk of stack overflow. If that's the case, shell sort should be fine I guess.
BearOso 3y ago
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".
- floxy 3y ago
  Seems like we are due for the cyclic interest in microkernels. I wonder what's the latest research on that front.
- tczMUFlmoNk 3y ago
  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.sort_unstable 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.)
  - steveklabnik 3y ago
    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/2d1bcbc6cd703e64caf8df314e3669b4786e008a/rust/alloc/slice.rs#L274 https://github.com/torvalds/linux/blob/2d1bcbc6cd703e64caf8d...

chaxor 3y ago

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.

pkaler 3y ago
This is for FreeBSD Firecracker. This means this is used for AWS Lambda and Fargate. A whole bunch of 2ms wins is how one would improve cold start time.
noisy_boy 3y ago
This is talking about Firecracker[0] which is for microvm deployments so I would think it is the aggregate effect of losing that 7% across a large number of spin-ups that would make a difference. Occasional reboot on your personal machines obviously doesn't make a dent. [0]: https://firecracker-microvm.github.io/ https://firecracker-microvm.github.io/
- ilyt 3y ago
  I'd imagine if you wanted absolute boot time you'd just use a container
  - insanitybit 3y ago
    Containers are inappropriate for many workloads, such as any workload that relies on multitenancy.
- vidarh 3y ago
  The lower the boot time, the more aggressively you can also afford to shut them down when not in use, freeing up capacity.
operator-name 3y ago
I wanted to figure out the cost to all users. BSD is sometimes used in some iot-like devices, of which there are 3 billion. If I randomly assume 0.5% of those are running a fork of FreeBSD, that's 15 million devices. I'm also going to randomly assume that devices reboot once a month on average. That all comes out to 4.2 days/year saved! Wow! https://www.wolframalpha.com/input/?i=2ms+*+3+billion+*+0.5%25+*+1+%2F+month+to+days+per+year https://www.wolframalpha.com/input/?i=2ms+*+3+billion+*+0.5%...

gkbrk 3y ago

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".

cperciva 3y ago
2.031 ms, I rounded down.
lkbm 3y ago
Probably true. My question was "how often is this run?" I assume it's not just once when I first turn on my laptop from fully off. Is it once every time I restart a Docker container? (Assuming FreeBSD images.) Is it something that runs a couple times a day, a dozen times a day, a thousand times a day? Fifty times every time I open an Electron app? I suspect this doesn't matter and is more a curiosity, but I wouldn't be shocked to learn otherwise.
rwmj 3y ago
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 ..?)
- cperciva 3y ago
  AWS Lambda does not support FreeBSD. It would be great if that changed though...
MrDOS 3y ago
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. [0]: https://firecracker-microvm.github.io/ https://firecracker-microvm.github.io/

tonetheman 3y ago

[dead]

daniel-thompson 3y ago

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-invisible-icons-in-quadratic-time/ https://randomascii.wordpress.com/2021/02/16/arranging-invis...

908B64B197 3y ago
Discoveries and analysis like this blog post and the parent show the difference between programmers and engineers.
IshKebab 3y ago
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.
- pjc50 3y ago
  qsort() not good enough for you? (More realistically, below people are discussing that in the kernel environment the set of standard or third party library available may be unavoidably limited)
  - jart 3y ago
    qsort() is pretty slow if you're sorting something like long[]. In that case, radix sort goes 5x faster and vectorized quicksort goes 10x faster. If you're sorting int[] then vectorized quicksort goes 25x faster than qsort(). Nothing goes faster. The issue is it's a big ugly c++ monstrosity that's a huge pain to compile.
    - rcxdude 3y ago
      That's fair if the constant factor is relevant, but if bubble sort is terminating in any reasonable timescale then the difference between qsort, C++ std::sort, and a custom implementation is really not a factor.

deleted 3y ago

[deleted]

0xbadcafebee 3y ago

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 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

asveikau 3y ago

One of the replies: https://twitter.com/cperciva/status/1659577625289928705 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.

avidphantasm 3y ago

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.

tombert 3y ago
Tangential, but in my Java class recently I was teaching teaching the students some basic Big O stuff. I wrote a few versions of a program that found the "biggest delta" of two numbers in a list. The first version was O(n^2) time, the next version was just O(n). I showed them how long it took to run the O(n^2) on 100000 elements, about two minutes on my beefy server. Then I showed them the O(n) version running on my comparatively weaker laptop, and it took about ten seconds to run a million elements. The students were genuinely kind of impressed, and I stressed the point to say that "these are the kind of numbers that make it important to take theory seriously."
- saagarjha 3y ago
  O(n) for 1 million elements taking ten seconds is pretty long. What’s the constant factor?

deleted 3y ago

[deleted]

daneel_w 3y ago

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.

jhalstead 3y ago
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_F1T03dyGuBb8PjECm7Q&s=19 https://twitter.com/cperciva/status/1659391725427720195?t=0y...
- taeric 3y ago
  I mean, I get it. But shaving 4.5ms does seem to fall into the realm of not most peoples problems? Note that I want to stress that that is no reason for some folks to stop focusing on it. And kudos on the improvement. Criticism, if any, here is that statistics once again rears its head to make something feel bigger by using a percent.
  - nextaccountic 3y ago
    > I mean, I get it. But shaving 4.5ms does seem to fall into the realm of not most peoples problems? If whoever is fixing this depend on quickly launching instances in Firecracker, it's their problem. And that's how open source is usually done
    - taeric 3y ago
      Sorta. They have to rely on this on a repeated basis such that it matters. And there, if startup time is still 10x this, roughly, why push for solutions that require that many kernel startups?

jgrahamc 3y ago

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)); And almost the entire matrix was empty because most things in a network aren't connected to each other. I spent a a few minutes replacing that with a hash table on the (i, j) node pair.

loeg 3y ago

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.

deleted 3y ago
[deleted]

tombert 3y ago

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.

repiret 3y ago
In my first computer science class in college, after finishing the unit on Red-Black Trees, the professor said something like "Now you should never implement a Red-Black Tree again. If you need a balanced binary tree, use std::map or whatever your standard library provides. Same goes for all the other sorting and data structures we've done in this class." Relatedly: Q: When is Python faster than C? A: When the C programmer used a linked list or some O(n^2) algorithm because they didn't have a standard library full of easy to use well implemented data structures and algorithms.
- tombert 3y ago
  That's actually something I've been saying for quite awhile when people bring up microbenchmarks complaining about how a language like Haskell is slow. Like, yes, no question, if you try and implement a tightloop in Haskell vs C, C is going to come out a lot faster. However, no one writes Haskell like that! People rely pretty heavily on standard libraries (or even third party libraries), and on the optimizations afforded to them by the "rich" language of Haskell. C might be capable of being faster, but that doesn't imply that a C program will inherently be faster than a similar Haskell program, especially if the programs are relatively large.
- norir 3y ago
  Even though I kind of mostly agree that you almost never should implement your own rb tree, this advice is also kind of disempowering and I worry that it is part of a mindset that accepts the status quo when it is so often the case that we could have better things if we just got our hands a little dirty.

freedomben 3y ago

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]. [1]: http://0pointer.de/blog/projects/systemd.html http://0pointer.de/blog/projects/systemd.html

ilyt 3y ago
My personal/corporate, n=~500 experience is that it boots faster, shuts down slower (technically because it is doing it "properly"), and if you have any problem during shutdown it is absolute PITA to debug why. We did managed to throw away few thousand lines of code of fixed init scripts after moving to systemd and get rid of few other stuff so it has been positive but definitely some of the bad with a lot of good. Journald logging format is also kinda fucked that causes some nasty edge cases Except of systemd-resolved, this utterly radioactive piece of shit can go fuck itself.
- taneliv 3y ago
  Do you have more details on the journald issues?
  - ilyt 3y ago
    Here is 9 year old bug that is still not fixed: https://github.com/systemd/systemd/issues/2460 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)

aflag 3y ago

Is there no link for the actual code?

JdeBP 3y ago
It's FreeBSD. The source for base comes with the operating system, in this particular case in /usr/src/sys/kern/init_main.c .
- canucker2016 3y ago
  Starting around line 255 in init_main.c (or search for bubble). see https://github.com/freebsd/freebsd-src/blob/40b287054521f0a92e5ae9a26e6a87d17ee85eea/sys/kern/init_main.c https://github.com/freebsd/freebsd-src/blob/40b287054521f0a9...
  - jodrellblank 3y ago
    (btw If you click on the line numbers in Github, you get a three-dots popup, click that and you can "Copy Permalink" to get a link directly to the line which has #L255 on the end, e.g. https://github.com/freebsd/freebsd-src/blob/40b287054521f0a92e5ae9a26e6a87d17ee85eea/sys/kern/init_main.c#L255 https://github.com/freebsd/freebsd-src/blob/40b287054521f0a9... )
  - aflag 3y ago
    Fascinating. It’s just plain old bubble sort. Why did they choose to do that? I don’t get the benefits of it. If they are going for simplicity, why not selection or insertion sort?

xp84 3y ago

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?

sn9 3y ago

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?

deleted 3y ago

[deleted]

kgbcia 3y ago

The real story "The kernel boot (of which 7% is bubblesort) is 28 ms."

inamberclad 3y ago

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.

barbariangrunge 3y ago

The story behind this: “how long do you think until they find this?” -somebody who accepted a bet

WalterBright 3y ago

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.

WalterBright 3y ago
P.S. I learned that trick from Shal Farley, who dramatically speeded up DECUS' Runoff program (an ancestor of Markdown) by doubling the buffer size.