16 ms·

FreeBSD replaces bubblesort with mergesort on SYSINTs

339 points by gslin 3y ago

chris_wot 3y ago
100x speed on what though? bootup time?
- dpwm 3y ago
  > 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.
  - torstenvl 3y ago
    EDIT: I misread—please disregard the below comment. 3.5% decrease. A 100% increase in speed is a 50% reduction in time. E.g., traveling 60km at 30km/h takes two hours, but at 60km/h takes one hour.
    - dharmab 3y ago
      A 100x increase is a 9900% increase, not a 100% increase.
    - loeg 3y ago
      You're misreading 100x as 100%. 100x is 10,000%.
    - deleted 3y ago
      [deleted]
    - Finn_ 3y ago
      100x not 100%. 3,000 km/h takes 1.2 minutes to go 60km.
    - chris_wot 3y ago
      Thank you, that's what I was interested in. Not sure why I got downvoted, it was a legitimate question as I didn't know what parts were adversely affected.
Blikkentrekker 3y ago
Okay, but what exactly is 100 times faster when measured? Simply the sorting algorithm? If it not be a bottleneck to something then it doesn't matter much. I assume the entire performance of FreeBSD hasn't improved a hundredfold by this small change.
- wkat4242 3y ago
  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.
- Crestwave 3y ago
  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.
- reanimus 3y ago
  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.
- paulddraper 3y ago
  100x faster on 7% of Firecracker boot So ~5ms speedup
eitland 3y ago
As two persons have already asked: > 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. > O(N^2) can bite hard when you're sorting over a thousand items. Time to replace the bubblesort with something faster.
_3u10 3y ago
Boot time was reduced by 2ms, from 28ms to 26ms. Hardly 100x speed.
- cperciva 3y ago
  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.)
  - dataflow 3y ago
    Why does any sorting anywhere use bubble sort at all? Aren't there sorts out there that are strictly better?
    - _3u10 3y ago
      Because 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 ago
        It'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 ago
        It'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.
ggm 3y ago
Small increments add up. Sure, its not 100x faster booting. its 100x less spent in one fragment of overall boot time. Do another 20, and you've made a LOT of difference.
- nucleardog 3y ago
  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_Improvements https://wiki.freebsd.org/BootTime#Past_Performance_Improveme...
  - 0xFF0123 3y ago
    How is time measured on things like this? Surely processors have also become faster as well.
    - maccard 3y ago
      From the link, > An Amazon EC2 c5.xlarge instance is being used as a reference platform and measuring the time between the instance entering "running" state and when it is possible to SSH into the instance.
- legulere 3y ago
  This is known as the hotspot or bottleneck model of optimization. It has its flaws: https://lemire.me/blog/2023/04/27/hotspot-performance-engineering-fails/ https://lemire.me/blog/2023/04/27/hotspot-performance-engine...
  - ggm 3y ago
    Nice article. I didn't see it say "don't do it" I saw it say "try not to have to"
  - IshKebab 3y ago
    That article is 100% right, but gmm said "do another 20" - that's not really what hotspot people expect to do. They think there's one or two hotspots that they need to optimise and then they'll get a 10x speedup. You can definitely do 20-100 small optimisations and get a 2-3x speedup. The best example I've seen of that is Nicholas Nethercote's work on speeding up the Rust compiler. A ton of tiny speed improvements that add up to 2x or 3x speed improvements overall. I've done similar work on optimising a compiler. You're never going to get 10x without architectural changes but you can get 3x with a lot of work. Of course the "we'll just optimise the hotspots" people have written their code so badly they need at least 10x.
asicsp 3y ago
Related discussion: "FreeBSD spends 7% of its boot time running a bubblesort on its SYSINITs" https://news.ycombinator.com/item?id=36002574 https://news.ycombinator.com/item?id=36002574 (381 points | 3 months ago | 358 comments)
upon_drumhead 3y ago
Why not sort this in a precompile step and not sort the static list every boot?
- loeg 3y ago
  No good reason. It would just require something fiddly with the linker / build process. This is good enough.
- cperciva 3y ago
  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.
  - JoshTriplett 3y ago
    > First, it's not worth screwing with the linker to save 20 microseconds. ...yet. Certainly not when boot is 28ms; might be worth it when boot is 1ms. > Second, you need to merge lists anyway because kernel modules. Does FreeBSD have the equivalent of a non-modular kernel build, for kernels where you know every piece of hardware it'll ever talk to?
    - cperciva 3y ago
      If I get the entire kernel boot down to 1 ms I might take another look at this. ;-) You absolutely can compile everything you need into the kernel -- in fact for Firecracker you have to since you don't have a boot loader handing you multiple kernel modules. But I needed to write the code to support more than just Firecracker.
      - JoshTriplett 3y ago
        > If I get the entire kernel boot down to 1 ms I might take another look at this. ;-) I look forward to the upcoming boot-time competitions between FreeBSD and Linux. :) > You absolutely can compile everything you need into the kernel -- in fact for Firecracker you have to since you don't have a boot loader handing you multiple kernel modules. But I needed to write the code to support more than just Firecracker. Absolutely. But it seems reasonable to have, for instance, link-time sorting support that only works when building a kernel that doesn't support kernel modules.
timmaxw 3y ago
For people (like me) who are wondering why a kernel needs to boot in under 28ms: It's for virtual machines that get launched on-demand in services like AWS Lambda. https://www.daemonology.net/blog/2022-10-18-FreeBSD-Firecracker.html https://www.daemonology.net/blog/2022-10-18-FreeBSD-Firecrac...
- atmosx 3y ago
  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.
  - mongol 3y ago
    Yes I remember being surprised that Linux containers were used for that purpose.
  - srcreigh 3y ago
    Very OT, but I concur. I need a DSP for my car audio system. I considered a rpi3 with a DAC attachment. I tried the raspbian OS with some moderate overclocking and removing unneeded startup processes. Couldn’t get it under 25 seconds for boot. Kind of a deal breaker (remote start unit could help, but…) Apparently somebody can start the rpi3 in <3 seconds. I’ll believe it when I try their image myself. Their setup disables USB and networking (maybe audio too who knows) which is a giant pain for configuring my system. Maybe I’ll try again with an RPi 4 and usb3 nvme. or maybe I’ll just pay hundreds of dollars for a dedicated DSP unit. In case anyone cares, my main use case is parametric EQ for phon adjusted low bass frequencies. 90dB 20Hz sounds as loud as 70dB 50Hz (give or take) and subwoofers are generally quieter at lower frequencies. Hence, audio processing unit to cut as you go higher than your lowest decently loud frequency. The lowest cost option for this is about $230USD plus some electrical components (miniDSP 2x4HD). I figure the rpi would cost around $100 including the DAC unit, open source audio software, just need some power source to link the battery to the rpi power cord. Edit: I don’t want to spam thanks comments for helpful replies, so I’ll just say it here (possibly in advance): thanks!!!
    - 3y ago
bongobingo1 3y ago
non xitter mirror: https://nitter.net/cperciva/status/1693127769901969772 https://nitter.net/cperciva/status/1693127769901969772
xyzelement 3y ago
To sum up what I learned from the comments: Is FreeBSD stupid for having used bubblesort to begin with? NO. It worked well for decades before surfacing as a problem in this extreme and unanticipated use case. Is optimizing this a waste of time? NO. The use case revolves around super frequent bootups to power lambda and for this type of thing every ms matters.
- Sharlin 3y ago
  As is often said, O(n^2) (or even 3) is fine until it stops being fine.
  - alkonaut 3y ago
    Yeah and it almost always stops being fine. The problem with an O(N^2) solution is that you rarely put in an assert that N < 100 or something like that to guard your assumption that big N "doesn't happen". Because after all it's better that the process eventually completes than that the process crashes. And if you don't dare to put that in, you perhaps shouldn't use O(N^2). N^2 or N^3 is fine for things that are fixed size and very unlikely to stop being fixed size, or at least unlikely to grow a lot. But any time you think "oh it's just a few files" when there is nothing to stop it from being 1000 files in ten years, or at one rare user: don't use an O(N^2) solution.
    - kortilla 3y ago
      > Yeah and it almost always stops being fine. No, it’s just a non-issue in the 99% of cases where it really does stay at small inputs. I come across configuration code all of the time that is stupidly inefficient like this and it’s almost always irrelevant. Tons of stuff works on inputs of <10.
      - alkonaut 3y ago
        It's an observation with heavy selection bias: in 100% of the cases where you had to deal with a perf problem it had stopped being fine... Since it also almost invariably is accidentally quadratic and not deliberately quadratic as with BubbleSort, you also have a hard time estimating how many quadratic algorithms you have that haven't caused problems, and perhaps never will. Adding complexity because of an anticipation that some input will grow to an unreasonable size (at the time of writing) may or may not be a good idea. But using a different off the shelf function or data structure is usually not a high cost for making sure it's not a problem down the line. Of course, that also assumes that there is a good and efficient standard lib of methods and data structures so that "making a more clever choice" isn't also a burden or risk in terms of code size, complexity, risk of bugs.
rf15 3y ago
Does anyone know why they used bubblesort in the first place? It is known for its bad performance, so what other factors came into play? Number of ops, maybe?
- phoenixreader 3y ago
  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.
  - professoretc 3y ago
    For 30 items bubblesort might very well have been faster than mergesort.
    - harry8 3y ago
      Bubble/selection sort with early exit can win outright on big lists if they're already almost in order. Textbook example years ago was cheque numbers which mostly are presented in order. Know your data. (Which in this case, i don't).
    - jeltz 3y ago
      But it always loses to insertion sort.
benreesman 3y ago
For everyone challenging Colin on this, by all means, but do remember that it’s Colin. If anyone misses less I can’t think of them.
im3w1l 3y ago
Why do you boot the system anyway? Wouldn't it be faster dump the memory of an already booted system and just read that in?
- hakfoo 3y ago
  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.
- RetroTechie 3y ago
  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.
  - im3w1l 3y ago
    The context here is starting a vm really fast on aws firecracker, so those concerns about hardware don't apply.
- 3y ago
Attummm 3y ago
Well, it's a bit of a embarrassing moment. Bubblesort has been controversial in many cs programs. That memo even reached the President ten years ago. [0]https://youtu.be/koMpGeZpu4Q https://youtu.be/koMpGeZpu4Q
kunley 3y ago
I wonder since 25 years or so why bubblesort is considered a viable sort at all. Putting aside its terrible complexity and thus performance, it is not even intuitive. For example, if you look at it, it is not how we humans sort things manually. It is IMO an example of a "following the herd" confusion: some scientist wrote a paper (they must do it to survive, don't they), others mentioned it in a textbook (doesn't hurt to have more pages, huh), others put it in their other textbooks because, well, it was mentioned in the past, and this is how this abomination survives decades..
- bradley13 3y ago
  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.
  - kunley 3y ago
    Yeah, great points about insertion and selection sort. Thank you for the story and for keeping up the quality of education.
- Delk 3y ago
  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.)
ilyt 3y ago
You'd think some algorithms would be considered near always wrong solution for the problem and so never used aside for very specific use case (like tiny microcontroller) but here we are.
deleted 3y ago
[deleted]
chaxor 3y ago
"This is good for LLMs"
tiffanyh 3y ago
"1 files changed, 86 insertions, 91 deletions" Net reduce of 5 LOCs and it's "100x faster". Nice commit.
tiffanyh 3y ago
iOS ~13 seconds to boot FreeBSD ~10 seconds to boot As a comparison point, my iPhone 14 Pro (latest phone) running iOS 16.6 (latest OS) boots in 12.7 second from when the Apple logo is displayed when you can see the wallpaper.

339 points by gslin 3y ago

chris_wot 3y ago

100x speed on what though? bootup time?

dpwm 3y ago
> 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.
- torstenvl 3y ago
  EDIT: I misread—please disregard the below comment. 3.5% decrease. A 100% increase in speed is a 50% reduction in time. E.g., traveling 60km at 30km/h takes two hours, but at 60km/h takes one hour.
  - dharmab 3y ago
    A 100x increase is a 9900% increase, not a 100% increase.
  - loeg 3y ago
    You're misreading 100x as 100%. 100x is 10,000%.
  - deleted 3y ago
    [deleted]
  - Finn_ 3y ago
    100x not 100%. 3,000 km/h takes 1.2 minutes to go 60km.
  - chris_wot 3y ago
    Thank you, that's what I was interested in. Not sure why I got downvoted, it was a legitimate question as I didn't know what parts were adversely affected.

Blikkentrekker 3y ago

Okay, but what exactly is 100 times faster when measured? Simply the sorting algorithm? If it not be a bottleneck to something then it doesn't matter much. I assume the entire performance of FreeBSD hasn't improved a hundredfold by this small change.

wkat4242 3y ago
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.
Crestwave 3y ago
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.
reanimus 3y ago
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.
paulddraper 3y ago
100x faster on 7% of Firecracker boot So ~5ms speedup

eitland 3y ago

As two persons have already asked: > 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. > O(N^2) can bite hard when you're sorting over a thousand items. Time to replace the bubblesort with something faster.

_3u10 3y ago

Boot time was reduced by 2ms, from 28ms to 26ms. Hardly 100x speed.

cperciva 3y ago
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.)
- dataflow 3y ago
  Why does any sorting anywhere use bubble sort at all? Aren't there sorts out there that are strictly better?
  - _3u10 3y ago
    Because 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 ago
      It'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 ago
        It'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.

ggm 3y ago

Small increments add up. Sure, its not 100x faster booting. its 100x less spent in one fragment of overall boot time. Do another 20, and you've made a LOT of difference.

nucleardog 3y ago
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_Improvements https://wiki.freebsd.org/BootTime#Past_Performance_Improveme...
- 0xFF0123 3y ago
  How is time measured on things like this? Surely processors have also become faster as well.
  - maccard 3y ago
    From the link, > An Amazon EC2 c5.xlarge instance is being used as a reference platform and measuring the time between the instance entering "running" state and when it is possible to SSH into the instance.
legulere 3y ago
This is known as the hotspot or bottleneck model of optimization. It has its flaws: https://lemire.me/blog/2023/04/27/hotspot-performance-engineering-fails/ https://lemire.me/blog/2023/04/27/hotspot-performance-engine...
- ggm 3y ago
  Nice article. I didn't see it say "don't do it" I saw it say "try not to have to"
- IshKebab 3y ago
  That article is 100% right, but gmm said "do another 20" - that's not really what hotspot people expect to do. They think there's one or two hotspots that they need to optimise and then they'll get a 10x speedup. You can definitely do 20-100 small optimisations and get a 2-3x speedup. The best example I've seen of that is Nicholas Nethercote's work on speeding up the Rust compiler. A ton of tiny speed improvements that add up to 2x or 3x speed improvements overall. I've done similar work on optimising a compiler. You're never going to get 10x without architectural changes but you can get 3x with a lot of work. Of course the "we'll just optimise the hotspots" people have written their code so badly they need at least 10x.

asicsp 3y ago

Related discussion: "FreeBSD spends 7% of its boot time running a bubblesort on its SYSINITs" https://news.ycombinator.com/item?id=36002574 https://news.ycombinator.com/item?id=36002574 (381 points | 3 months ago | 358 comments)

upon_drumhead 3y ago

Why not sort this in a precompile step and not sort the static list every boot?

loeg 3y ago
No good reason. It would just require something fiddly with the linker / build process. This is good enough.
cperciva 3y ago
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.
- JoshTriplett 3y ago
  > First, it's not worth screwing with the linker to save 20 microseconds. ...yet. Certainly not when boot is 28ms; might be worth it when boot is 1ms. > Second, you need to merge lists anyway because kernel modules. Does FreeBSD have the equivalent of a non-modular kernel build, for kernels where you know every piece of hardware it'll ever talk to?
  - cperciva 3y ago
    If I get the entire kernel boot down to 1 ms I might take another look at this. ;-) You absolutely can compile everything you need into the kernel -- in fact for Firecracker you have to since you don't have a boot loader handing you multiple kernel modules. But I needed to write the code to support more than just Firecracker.
    - JoshTriplett 3y ago
      > If I get the entire kernel boot down to 1 ms I might take another look at this. ;-) I look forward to the upcoming boot-time competitions between FreeBSD and Linux. :) > You absolutely can compile everything you need into the kernel -- in fact for Firecracker you have to since you don't have a boot loader handing you multiple kernel modules. But I needed to write the code to support more than just Firecracker. Absolutely. But it seems reasonable to have, for instance, link-time sorting support that only works when building a kernel that doesn't support kernel modules.

timmaxw 3y ago

For people (like me) who are wondering why a kernel needs to boot in under 28ms: It's for virtual machines that get launched on-demand in services like AWS Lambda. https://www.daemonology.net/blog/2022-10-18-FreeBSD-Firecracker.html https://www.daemonology.net/blog/2022-10-18-FreeBSD-Firecrac...

atmosx 3y ago
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.
- mongol 3y ago
  Yes I remember being surprised that Linux containers were used for that purpose.
- srcreigh 3y ago
  Very OT, but I concur. I need a DSP for my car audio system. I considered a rpi3 with a DAC attachment. I tried the raspbian OS with some moderate overclocking and removing unneeded startup processes. Couldn’t get it under 25 seconds for boot. Kind of a deal breaker (remote start unit could help, but…) Apparently somebody can start the rpi3 in <3 seconds. I’ll believe it when I try their image myself. Their setup disables USB and networking (maybe audio too who knows) which is a giant pain for configuring my system. Maybe I’ll try again with an RPi 4 and usb3 nvme. or maybe I’ll just pay hundreds of dollars for a dedicated DSP unit. In case anyone cares, my main use case is parametric EQ for phon adjusted low bass frequencies. 90dB 20Hz sounds as loud as 70dB 50Hz (give or take) and subwoofers are generally quieter at lower frequencies. Hence, audio processing unit to cut as you go higher than your lowest decently loud frequency. The lowest cost option for this is about $230USD plus some electrical components (miniDSP 2x4HD). I figure the rpi would cost around $100 including the DAC unit, open source audio software, just need some power source to link the battery to the rpi power cord. Edit: I don’t want to spam thanks comments for helpful replies, so I’ll just say it here (possibly in advance): thanks!!!
  - 3y ago

bongobingo1 3y ago

non xitter mirror: https://nitter.net/cperciva/status/1693127769901969772 https://nitter.net/cperciva/status/1693127769901969772

xyzelement 3y ago

To sum up what I learned from the comments: Is FreeBSD stupid for having used bubblesort to begin with? NO. It worked well for decades before surfacing as a problem in this extreme and unanticipated use case. Is optimizing this a waste of time? NO. The use case revolves around super frequent bootups to power lambda and for this type of thing every ms matters.

Sharlin 3y ago
As is often said, O(n^2) (or even 3) is fine until it stops being fine.
- alkonaut 3y ago
  Yeah and it almost always stops being fine. The problem with an O(N^2) solution is that you rarely put in an assert that N < 100 or something like that to guard your assumption that big N "doesn't happen". Because after all it's better that the process eventually completes than that the process crashes. And if you don't dare to put that in, you perhaps shouldn't use O(N^2). N^2 or N^3 is fine for things that are fixed size and very unlikely to stop being fixed size, or at least unlikely to grow a lot. But any time you think "oh it's just a few files" when there is nothing to stop it from being 1000 files in ten years, or at one rare user: don't use an O(N^2) solution.
  - kortilla 3y ago
    > Yeah and it almost always stops being fine. No, it’s just a non-issue in the 99% of cases where it really does stay at small inputs. I come across configuration code all of the time that is stupidly inefficient like this and it’s almost always irrelevant. Tons of stuff works on inputs of <10.
    - alkonaut 3y ago
      It's an observation with heavy selection bias: in 100% of the cases where you had to deal with a perf problem it had stopped being fine... Since it also almost invariably is accidentally quadratic and not deliberately quadratic as with BubbleSort, you also have a hard time estimating how many quadratic algorithms you have that haven't caused problems, and perhaps never will. Adding complexity because of an anticipation that some input will grow to an unreasonable size (at the time of writing) may or may not be a good idea. But using a different off the shelf function or data structure is usually not a high cost for making sure it's not a problem down the line. Of course, that also assumes that there is a good and efficient standard lib of methods and data structures so that "making a more clever choice" isn't also a burden or risk in terms of code size, complexity, risk of bugs.

rf15 3y ago

Does anyone know why they used bubblesort in the first place? It is known for its bad performance, so what other factors came into play? Number of ops, maybe?

phoenixreader 3y ago
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.
- professoretc 3y ago
  For 30 items bubblesort might very well have been faster than mergesort.
  - harry8 3y ago
    Bubble/selection sort with early exit can win outright on big lists if they're already almost in order. Textbook example years ago was cheque numbers which mostly are presented in order. Know your data. (Which in this case, i don't).
  - jeltz 3y ago
    But it always loses to insertion sort.

benreesman 3y ago

For everyone challenging Colin on this, by all means, but do remember that it’s Colin. If anyone misses less I can’t think of them.

im3w1l 3y ago

Why do you boot the system anyway? Wouldn't it be faster dump the memory of an already booted system and just read that in?

hakfoo 3y ago
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.
RetroTechie 3y ago
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.
- im3w1l 3y ago
  The context here is starting a vm really fast on aws firecracker, so those concerns about hardware don't apply.
3y ago

Attummm 3y ago

Well, it's a bit of a embarrassing moment. Bubblesort has been controversial in many cs programs. That memo even reached the President ten years ago. [0]https://youtu.be/koMpGeZpu4Q https://youtu.be/koMpGeZpu4Q

kunley 3y ago

I wonder since 25 years or so why bubblesort is considered a viable sort at all. Putting aside its terrible complexity and thus performance, it is not even intuitive. For example, if you look at it, it is not how we humans sort things manually. It is IMO an example of a "following the herd" confusion: some scientist wrote a paper (they must do it to survive, don't they), others mentioned it in a textbook (doesn't hurt to have more pages, huh), others put it in their other textbooks because, well, it was mentioned in the past, and this is how this abomination survives decades..

bradley13 3y ago
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.
- kunley 3y ago
  Yeah, great points about insertion and selection sort. Thank you for the story and for keeping up the quality of education.
Delk 3y ago
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.)

ilyt 3y ago

You'd think some algorithms would be considered near always wrong solution for the problem and so never used aside for very specific use case (like tiny microcontroller) but here we are.

deleted 3y ago

[deleted]

chaxor 3y ago

"This is good for LLMs"

tiffanyh 3y ago

"1 files changed, 86 insertions, 91 deletions" Net reduce of 5 LOCs and it's "100x faster". Nice commit.

tiffanyh 3y ago

iOS ~13 seconds to boot FreeBSD ~10 seconds to boot As a comparison point, my iPhone 14 Pro (latest phone) running iOS 16.6 (latest OS) boots in 12.7 second from when the Apple logo is displayed when you can see the wallpaper.