FreeBSD replaces bubblesort with mergesort on SYSINTs
twitter.com
twitter.com
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.
for (size_t i = 0; i < n; i++) {
for (size_t j = 1; j < n - i; j++) {
if (a[j-1] > a[j]) {
item_t tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
}
}
}
for (size_t i = 1; i < n; i++) {
for (size_t j = i; j > 0; j--) {
item_t tmp = a[j];
if (tmp > a[j-1]) break;
a[j] = a[j-1];
a[j-1] = tmp;
}
}
(above code only minimally tested: https://godbolt.org/z/43dqz9Gq8)
this is not much of a criticism of freebsd; if you polished your codebase until there was nothing stupid in it, you'd never ship anything. freebsd's code quality is quite high, but probably we can all agree that this was stupid
of course it wouldn't be nearly as fast as mergesort on large inputs, but mergesort is more complicated
(also mergesort is slower on small inputs than insertion sort or bubble sort, but in the case where you're only sorting something once at startup time, that probably isn't important. it might matter if you were sorting a million lists of ten items or something)
I used to believe this but then a friend pointed out a real use case for bubble sort: when you have an array that is always mostly sorted, and real-time performance is more important than perfectly correct ordering. Then running one pass of bubble sort each cycle around the main loop is somewhat satisfyingly ideal.
One pass of insertion sort would be too expensive, and bubble sort is guaranteed to make incremental progress each pass.
This is sort of like how a linked list is never the right solution... unless it's one of those cases where intrusive linked lists are ideal. Except while intrusive linked lists intrude in space, intrusive bubble sort kind of intrudes in time.
Most sorts are designed to "really sort something", however I'm very interested in eg: ranking preferences of movies, and in cases like that there may never be "the one true ordering" ... however the mechanism for getting things "closer to sorted" is incredibly close to the mechanism you mentioned: multiple passes, and continual, incremental progress.
My imaginary GUI for interactive sorting in this manner is something like starting with a few "A vs. B" of a generally accepted "top 10/100 vs generic v pretty bad", and then morph to a "drag this new movie in between a few other movies either above, between, or below"
There are sorting algorithms for computers (eg: compare + swap), but fewer sorting algorithms for humans (eg: bucket sort / postman's sort - https://en.wikipedia.org/wiki/Bucket_sort#Postman's_sort ) which can take advantage of "not just compare and swap" to get things "close to correct" quicker.
Abstract-This paper considers the reduction in algorithmic complexity that can be achieved by permitting approximate answers to computational problems. It is shown that Shannon’s rate-distortion function could, under quite general conditions, provide lower bounds on the mean complexity of inexact computations. As practical examples of this approach, we show that partial sorting of N items, insisting on matching any non zero fraction of the terms with their correct successors, requires 0 (N log N) comparisons. On the other hand, partial sorting in linear time is feasible (and necessary) if one permits any finite fraction of pairs to remain out of order. It is also shown that any error tolerance below 50 percent can neither reduce the state complexity of binary N-sequences from the zero-error value of O(N) nor reduce the combinational complexity of N-variable Boolean functions from the zero-error level of 0(2N/N).
When humans are tasked with the comparison, it doesn't have to be strictly pair-wise and instead can devolve (kindof) into the various kinds of "sorting networks" that minimize the cmp-swap given a limited subset of the list.
Thanks for the reference!
i feel like one pass of insertion sort (inserting one item into the sorted run) or selection sort (selecting one minimum or maximum from the unsorted run) would work tho
If I suspected at all that the algorithms would have to sort a decent number of items, I wouldn't consider using an O(n^2) sort at all and would take the time to find a good implementation of (or implement) one of the O(n log(n)) algorithms.
One iteration of bubble sort is: find two elements in the wrong order and swap them.
One iteration of insertion sort is: find an element out of order, then find the location in the array where it should've been, then move all the items between those two slots one slot ahead, then insert the out-of-order element into the now free slot where it belongs.
Admittedly, insertion sort is pretty intuitive, since it reflects more or less how a human would instinctively try to sort a list; take an out-of-order element and move it to where it belongs. But when translated to code, I think it's very hard to beat "find two items in the wrong order and swap them".
Once you admit superscalar execution (multiple loadstore pipes), out of order execution and caches into the picture ( as well as the possibility of almost sorted arrays as input) the picture is never as simple.
That said, I’m curious whether insertion sort is categorically better than bubble sort. I thought they might have been equivalent for the almost sorted case. I’ve heard both sides argued on this thread.
even if insertion sort reliably beats bubble sort on your ssd ftl chip and your wristwatch, though, it seems like there are cases on modern high-performance hardware where insertion sort is worse than bubble sort (cf. https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubb...) which is very surprising to me
> Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position
In fact it’s often a sub-sort of hybrid sorts, like timsort:
> If a run is smaller than this minimum run size, insertion sort is used to add more elements to the run until the minimum run size is reached.
I can never remember the loop bounds of bubble sort, always have to look it up.
That said a lot of time I have small arrays of objects. Instead of keeping them sorted I just grind through them to find the next largest value. That tends to be hard to get wrong.
commonly (as in wellons's post about the two-sum problem) there's a variation on the standard algorithm that can help significantly, but which the standard library function doesn't have an option for
also i think the cost of reimplementing simple 'algorithms from the book' like insertion sort or even quicksort is pretty low; as you saw in my comment above, insertion sort is six lines of code and only moderately bug-prone. we aren't talking about fibonacci heaps or red-black trees or fm-indexes or rader's algorithm or something. the cost is low enough that it's easy to justify in a lot of cases
And given that C's stdlib has a quicksort function, how would using a different language have helped?
Eg Rust has no-std crates that you can use even if you can't use the standard library.
And maybe it wasn't 'no additional effort' because they were more confident with quickly writing a bubble sort.
Not if it was already written.
I don't know anything about this particular codebase, but one thing I have learned over the years is that when you are tempted to say "such and such decision was stupid" in a production codebase, you are almost always missing something.
It also could have been apathy: knowing there was a better solution and just not caring what was implemented. I feel like this is more common than incompetence, especially in larger projects or organizations. Nature tends to take the path of least resistance.
even the best of us do stupid things sometimes
Of course there are valid values below that...
If they were designing to a collection size of N -> ∞ then they shouldn't have used Insertion Sort either then, because it is O(n²) in the worst case.
It's trivial to start with something that gets human input and someone, somewhere, decides to plug the thing into something else that generates that input.
And we all know that if computers are good at something, it's doing a lot of small things millions of times.
Besides there's little reason for any codebase of any kind of ever contain bubble sort (except for an academic one, showing it as an example of a bad one). We're talking 20 years ago, not 2000 years ago, the basic sorting algorithms were pretty well researched and established by then.
/*
* Perform a bubble sort of the system initialization objects by
* their subsystem (primary key) and order (secondary key).
*
* Since some things care about execution order, this is the
* operation which ensures continued function.
*/
for( sipp = (struct sysinit **)sysinit_set.ls_items; *sipp; sipp++) {
for( xipp = sipp + 1; *xipp; xipp++) {
if( (*sipp)->subsystem < (*xipp)->subsystem ||
( (*sipp)->subsystem == (*xipp)->subsystem &&
(*sipp)->order < (*xipp)->order))
continue; /* skip*/
save = *sipp;
*sipp = *xipp;
*xipp = save;
}
}
selection sort has the potential advantage for things that are larger than your key that it can avoid copying the entire item, just doing a single swap at the end of the inner loop, but it's not implemented that way here. that would have looked like this
size_t m = 0;
register unsigned int subsystem = (*sipp)->subsystem;
register unsigned int order = (*sipp)->order;
for( xipp = sipp + 1; *xipp; xipp++) {
register unsigned int newsubsystem = (*xipp)->subsystem;
register unsigned int neworder = (*xipp)->order;
if( subsystem < newsubsystem ||
(subsystem == newsubsystem && order < neworder))
continue; /* skip*/
m = xipp - sipp;
subsystem = newsubsystem;
order = neworder; /* enjoy the sorting */
}
save = sipp[0];
sipp[0] = sipp[m];
sipp[m] = save;
Not true. Bubble sort is excellent for sorting very small arrays.
See "Hoare’s Rebuttal and Bubble Sort’s Comeback (2020)" under "Fallback for sorting short arrays" and the performance results presented therein [0]. Discussion [1].
[0]: https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubb...
all of the bubble sorts i tried compiling in this thread ended up being compiled to code with either conditional branches or (on arm thumb-2) a couple of conditionalized stores. but conditional stores don't require a pipeline flush, and it is of course perfectly correct that insertion sort depends on its inner loop having an unpredictable branch to get better performance on almost-sorted data, which bubble sort does not
python version of the inner loop
max_ = arr[0]
for j in range(1, i):
y = arr[j]
arr[j - 1] = min(max_, y)
max_ = max(max_, y)
arr[i - 1] = max_Since what insertion sort is faster that bubble sort on sorted data?
admittedly i probably added the godbolt link showing this after you wrote your comment
perhaps you can elaborate; i couldn't understand your last sentence or why you think the bubblesort function above doesn't bubble-sort
You should probably check wikipedia page. Here: https://en.wikipedia.org/wiki/Bubble_sort.
it's true that, if your data is exactly sorted, or has a small number of items that are far too early (e.g., 43 3 4 5 6 7 8 9 10), you can modify bubble sort to notice this and exit early, at the expense of making it more complicated and even slower in the average case
however, this doesn't help if instead you have a small number of items that are far too late (e.g., 4 5 6 7 8 9 10 43 3), in which case bubble sort takes the same number of passes as it normally would, while insertion sort takes linear time. of course you can complicate bubble sort further into "shaker sort" to handle this, which makes it even more complicated but at least doesn't slow it down any further
but all of this is sort of futile because it's still half as fast as insertion sort in the case of unsorted input, and even without the tweaks, no simpler
someone else might have written the original version, i can't remember any more, but i think it was probably me
bubble sort with early exit is
for (size_t i = 0; i < n; i++) {
bool sorted = 1;
for (size_t j = 1; j < n - i; j++) {
if (a[j-1] > a[j]) {
item_t tmp = a[j];
a[j] = a[j-1];
a[j-1] = tmp;
sorted = 0;
}
}
if (sorted) break;
}
if you compile it https://godbolt.org/z/jdzov8cPn you can see that the inner loop goes from 10 instructions to 11. that doesn't guarantee that it's 9% slower (that depends a lot on the platform, and in particular on a big superscalar cpu it probably just uses a little more power but the same number of clocks) but it does tend in that direction. of course occasionally it will save you a pass or two over the array, which will tend to compensate, but it won't usually save you 9% of the passes
if some item is in position n and needs to be in position m, where m < n, it will require n - m passes of bubble sort to get there. a little thought suffices to show that, for randomly shuffled input, where m = 0 the item has to move about half the size of the array, where m = 1 it has to move about half the size of the array minus one half, where m = 2 it has to move about half the size of the array minus one; but it's the maximum of these three numbers which determines the number of passes after which all three of those positions will have the correct item, and that maximum is heavily skewed to be almost the entire size of the array. the chance that none of those three items is in the last 25% of the array originally is only .75*3 = 42%. and as the value of three increases, it gets worse. so in general early exit doesn't buy you much
as for modern implementations of bubble sort, they're all either didactic classroom exercises like this one or careless mistakes like the original freebsd code; because insertion sort always beats it, there aren't like a community of bubble sort implementors who have annual bubble sort conferences. so you can expect some variation in precise terminology and shouldn't worry about it
(fwiw clrs 3ed. gives bubblesort without an early termination test, as i did; their definition is in exercise 2-2 on p. 40. but they're counting in the opposite direction, so everything i said above about items moving forward quickly and backward slowly is reversed for the clrs version of bubblesort)
Although I certainly agree that Bubble Sort is almost always a bad choice, it still is used in computer graphics, or other situations when you have only one or two misplaced pairs of elements. In this case it will outperform the other algorithms, in average case while maintainig functionally in the less than ideal situation.
Besides it is entirely irrelevant what are the purposes the algorithm is used today, didactic, deliberate or poor judgement, the de facto standard way of doing it today is to check for the early exit. Your argument about poor performance on the already sorted data is a straw man argument, your are stubbornly defending. Well ok, if you believe so...
it might help your intuition to think of it this way:
1. with random input, the first ten positions of output are pretty likely (65%) to have an item that was originally in the last 10% of the input, and almost certain (97%) to have an item that was originally in the last 30% of the input. so those ten items alone account for needing 95% of the passes you'd need without an early exit, minus about five, in 65% of cases.
2. the first 20 positions are pretty likely (64%) to have an item that was originally in the last 5% of the input, and almost certain (96%) to have an item that was originally in the last 15% of the input. so those 20 items account for needing 97% of the passes you'd need without an early exit, minus about ten, in 64% of cases.
3. the first 30 positions are pretty likely (64%) to have an item that was originally in the last 3.3% of the input, and almost certain (96%) to have an item that was originally in the last 10% of the input. so those 30 items account for needing 98.5% of the passes you'd need without an early exit, minus about 15, in 64% of cases.
of course, if you're only sorting 30 items, the first ten positions of output are actually a third of all the positions, so "minus five" is pretty significant. and probably if you're sorting more than about 30 items at a time you ought to use a linearithmic sort or a linear-time radix sort instead of a quadratic sort
similarly, it's reasonable to argue that complexity (in the sense of containing many parts, not in the sense of asymptotic computational work required) is subjective, and to disagree about it
but i think these are sort of moot points
insertion sort still beats bubble sort in the situations where you have only one or two misplaced pairs of elements, and generally replaces it as soon as somebody notices
as for 'the de facto standard way of doing it today', i suggest you argue with clrs, not with me
the wikipedia article has a cleverer early-exit version of bubble sort that keeps track of the last pair it had to swap; it will do 1.5n-1 comparisons in that case on average (because the swapped pair is on average in the middle of the array)
above i linked to working code on godbolt (modulo the extra unnecessary swaps on duplicate keys that you were kind enough to point out earlier); edit a comparison counter and a swap counter into it and you'll see
/*
*
* Perform a bubble sort of the system initialization objects by
* their subsystem (primary key) and order (secondary key).
*/
TSENTER2("bubblesort");
for (sipp = sysinit; sipp < sysinit_end; sipp++) {
for (xipp = sipp + 1; xipp < sysinit_end; xipp++) {
if ((*sipp)->subsystem < (*xipp)->subsystem ||
((*sipp)->subsystem == (*xipp)->subsystem &&
(*sipp)->order <= (*xipp)->order))
continue; /* skip*/
save = *sipp;
*sipp = *xipp;
*xipp = save;
}
}
TSEXIT2("bubblesort");It's also not an improvement over the insertion sort. If you look at kragen's code, you'll see that running it on a list of e.g. 6 elements in ascending order will mean that you make 5 comparisons, swap 0 elements, and exit. (You do have to count from 1 to 6 as you do this.)
The insertion sort is implemented as a bubble sort, interestingly enough, but one that doesn't consider the entire array at every iteration. Given that it's equally correct, it's not difficult to understand why it will always be faster than a bubble sort that does consider the entire array at every iteration.
oh yeah, you're right, thanks, it does do useless extra work if there are equal values in the list
it should say
if (tmp >= a[j-1]) break;
There you have your problem: any programmer can write a bubble sort while half asleep and inebriated at the same time, but for an insertion sort you actually have to think a little. There's much more chance of errors.
edited to add: someonefromca spotted a bug in the insertion sort; where it says
if (tmp > a[j-1]) break;
if (tmp >= a[j-1]) break;
this is some evidence in favor of your point that insertion sort is more error-prone; even if i could have made the same error in the bubble sort, i didn't, and possibly that was because the rest of the algorithm required less mental effort?
Maybe a fair judge of mental difficulty would say "you gotta write at least the loop invariant" (termination being too pedantically obvious) -- though admittedly I leave it out more than I used to.
When I was introduced to sorting as a new programmer, via bubblesort, I thought "why that way?" and came up with selection sort as a method that made more obvious sense. It seems to me like bubblesort's alleged intuitiveness is post hoc from the shortness of the code in terms of all-ascending for-next loops -- the intuitive reason it worked was just that the inner loop did move the next max into place just like selection sort, but with extra swaps along the way.
(FreeBSD got a test suite in 10.1, which came out in 2014, not that long ago in UNIX terms.)
People would be shocked by how little the core tools we use were tested automatically. Some still aren't.
Thankfully the practice of just randomly shelling out to 'random' programs (like the core tools) has been stemmed somewhat, so perhaps we're mostly safe from RCE via that vector. Downloaded files might still be a vector, tho. Maybe I'm an optimist even though I sound very pessimistic.
I dunno what FreeBSD's test infrastructure is, but I'm just saying that "it needs testing" is not a good reason not to change to a better sort algorithm in this case.
if your interests run the other way, that's great, and hopefully you will succeed in improving freebsd's testing infrastructure, but it's hardly a reason for colin not to speed up booting
but i don't think i saw anyone claiming that the change should not be made because it wouldn't be adequately tested?
Quote:
> will be reviewed and tested by 200 people before it reaches production
I was only saying that this is a bad argument for changing to any simple-ish sorting algorithm. (Because: add tests if you need assurance)
Granted, if you're doing super-complicated sorting algos with fallbacks for different sizes, heuristics for detecting semi-sorted input, etc. you might want something more sophisticated than trivial property-based checking.
There _could_ be arguments against some sorts, e.g. less predictable memory or performance. But qsort is pretty well behaved.
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.
And it was a blatant O(n^2) algorithm, easily swapped out, it’s not like they were calling sscanf in a loop and whoopsie turns out C strings are shit so now parsing a 4 characters decimal number is O(buflen^2).
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.
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.
For sorting, getting a n.log(N) algorithm that doesn't break down is usually just a matter of calling a library, or writing <100 lines of code if you really can't use a library. It usually doesn't have much of a negative impact when the number of inputs is small, and it is often simpler than making a proper analysis. So, when in doubt, never use a n^2 sorting algorithm.
Properly predicting if it will be fine or not is a sign of wisdom. But something like this is a fine place to use something where the complexity blows up. The sort happens in a clear place; early boot is a little hard to debug, but still. It's much worse when you put something N^3 in where when it blows up, the time spent is diffuse.
- it's constant time or it's crap
- constant time means your best case is as slow as your worst case
In this case, constant time would be sorting it before the program runs.
Which is in fact important in crypto code to prevent timing attacks.
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!!!
I've worked with similarly underpowered boards (licheepi zero, only has 64mb ram and uses the cpu from a dashcam!) and those will still boot and start an SDL app in under five seconds.
If you can identify the bare minimum that you need for your EQ solution, you can probably get similar boot times.
Check this thing out, it‘s a programmable audio DSP:
I suppose I'm more sensitive to downtime than most - I recently (unsuccessfully) tried to add a ton of capacitance into my head unit's power supply and acc-signal lines to keep it from turning off for a few seconds when starting the engine.
https://en.wiktionary.org/wiki/Chesterton%27s_fence
It's for safety in case of roll-over and for better aerodynamics due to increased emissions standards and in the case of EVs, increasing the range.
Dismissing it as "design with poor usability" is very facile. It's trade-offs between different goals, all the way down.
Those pillars that hold the roof up are safer if they're sturdy, but sturdy means wider and that obstructs the driver's field of vision a bit, and weighs more. "strong and slender" is possible, but it costs more. It all inter-relates.
(strong, narrow, cheap), pick any 2.
There does come a point where you start to appreciate what Polestar is doing on one of next years models (the Polestar 4): give up on the idea and change direction; no rear window at all, just a camera.
And I'm not only thinking about damaged camera. Humidity, weather etc. often makes these cameras completely useless.
You'd have to have wipers for your camera-lens and probably heating or something as well to even approach the utility of a window - short term.
Because none of that is ever going to fail, and it isn't cheap either.
It is IMHO a bold move, which will attract fans and haters. Neither of us know for sure how it will play out; if the potential issues outweigh the rest. The implementation details clearly matter. In a couple of years we will see if it's a genius innovation, a terrible misstep or somewhere in-between. Until the vehicle ships and is on the road for some time in some volume, we won't know for sure.
After all, on a high-end vehicle a back-camera that hasn't sorted this is just a gimmick.
Maybe they have, all my experiences indicate otherwise though I don't have much experience with new expensive cars.
You don't see lots of truck parking in parallel unassisted on streets with pedestrians and cyclists, but I do this all the time.
Even the Mini Cooper is huge now.
In the EU, it’s similar. https://ec.europa.eu/info/law/better-regulation/have-your-sa...:
All new vehicles sold from May 2022 must be fitted with advanced safety features, including:
- monitors that detect when a driver has become drowsy or distracted
- emergency stop signal to help prevent rear-end collisions
- rear-view camera or parking sensors
- alcohol interlock system to prevent drunk driving.
These systems will help reduce serious accidents on Europe’s roads.
Wait, what? _All_ new vehicles need to have this? Or do they just need to be constructed such that one can be installed easily?
Also, see:
https://road-safety.transport.ec.europa.eu/statistics-and-an...
Edit:
The actual text:
> Article 6 of Regulation (EU) 2019/2144 of the European Parliament and of the Council requires motor vehicles of categories M and N to be equipped with certain advanced vehicle systems, including driver drowsiness and attention warning systems. It lays down in its Annex II basic requirements for the type-approval of motor vehicles with regard to the driver drowsiness and attention warning systems.
Disclaimer: Not a joke. I've never owned a car.
Also, if you live in a sparsely populated area, public transport with good coverage often isn't really economically (or ecologically) feasible, even in countries that have good public transport in cities. A bicycle might be an option if distances aren't too great but relying on it exclusively probably takes more than an average person is willing to take on. Weather conditions could be poor, you might regularly need to transport groceries for an entire family, etc. All of that is entirely doable within a few miles in a bikeable city but it's potentially a lot less so if distances are greater.
I've never owned a car, I bicycle some thousands of kilometres per year (probably more than I drive most years), and I wish people didn't automatically consider owning a car a necessity even when it actually isn't. But I can definitely see reasons for owning one.
Convenience :-)
The delay that I notice the most is the time it takes to connect to my phone via Bluetooth (usually so I can play music from it). I’m often already pulling out of my parking space before it connects.
I can change gears in well under a second when moving. My car requires the clutch to be depressed when the car starts, meaning that I can actually ahve the car started in reverse in under a second. Waiting another 4 seconds is crazy.
And if you’re reversing within 3 seconds of turning your engine on then you’re either driving recklessly or on an open and safe space where you don’t even need your cameras.
To be clear, I’m not suggesting that a 4 second boot time for an embedded device is great. But I do think your claim that waiting 4 seconds “is crazy” is rather hyperbolic.
If I've parked my car, I have to have my foot on the clutch to turn it back on agian. My foot is already on the clutch, and I can very easily (and often do) put my car in gear _immediately_.
> then you’re either driving recklessly or on an open and safe space where you don’t even need your cameras.
Or I've looked in my mirror and put my seatbelt on before I turned the engine on. This is the equivalent of "you're holding it wrong".
My point being, 5 seconds might sound like an eternity on paper but I’d wager it’s not nearly as impactful once you start factoring real world scenarios.
Personally, I never look at my camera. I just listen to the beeps and watch my blind spot. Not because it’s safer not because of any delay in the camera coming on, but simply out of habit. So I’ve never noticed a delay in the camera coming on. Maybe there isn’t even a delay in my particular car — but if there was, I wouldn’t know.
Also my usual sequence is "start the engine, set up on phone (music, GPS), leave", so it would've booted before I need it.
I think it works better now than before, but it's hard to be sure because I neglected to measure the downtime before/after the modifications. Essentially I had a cap/diode to keep the acc line high during startup for the head unit, but it would still cut off due to the power supply voltage dropping to ~10-11V on the engine turning over (4.8L V8). So then I added a cap/diode to the power supply line, and it works "better...ish...maybe..." now: there are some times when it will stay on across startup, but not always. Perhaps with a larger cap on the PS line (I'm using ~2500uF), but it seemed to be discharging much faster than I'd expect, as if the diode wasn't doing it's thing and the line was effectively just at the system's general "+12V". I wondered if there was perhaps some way the power was escaping the diode/cap isolation and making it back into the main system, but I didn't have a good way to test or fix that (I previously diagnosed a similar issue to a bad diode, but this one seemed to measure fine).
And besides all that, the amp is on a separate line in the way back of the car that I didn't bother to tear into because the head unit turns off in the critical stage anyways. So the head unit does stay on for a couple seconds after I turn if off completely, but since the amp is off it doesn't matter.
So delayed startups aren't some new issue.
If you believe your idea is true, can you tell me what I can expect to see if I don't do this? IE, I've never done this and I have cars that last 10+ years without any engine trouble.
But these virtual machines can all be exactly the same, except for the network MAC and IP.
It could even be possible to compile executables that bypass the need for a kernel, just have some libraries with the required stuff, and boot to the program, MS-DOS style.
Or consider: https://github.com/uniqernel/awesome-unikernels
Some virtual machine environments do have facilities to snapshot the entire state of a machine and resume it (potentially on another machine), but if you look at what is involved with snapshot metadata it's more than just the state of memory, you have CPU and device state as well.
On virtual machines there probably isn't nearly so much real hardware to set up, and hypervisors can optimize virtual device setup. The machine image could also be provided via COW snapshot of memory. So I don't know, possibly at some corners it could be faster to do a resume type operation than a full boot. I haven't played with hypervisor guest boot at these kinds of speeds before.
So it’s difficult and dangerous for not a lot of gain. Perhaps an easier approach would be to boot a few spare systems in advance and hibernate them so they can be booted quickly.
Plus, as the sibling poster says, you usually don't know this before you first start to use it, which means it's already been delivered, connected, and everything.
I already paid $100 more for 2dB less, according to the spec. No regrets.
> which I believe is required by some regulation to be the default
Huh. This must be recent-ish. My parents' dishwasher has a rotary button to choose the program, which stays put as long as the little grandchildren don't mess with it..
> From 1 March 2021, household dishwashers shall provide an eco programme meeting the following requirements:
> (a) this programme shall be: [...] set as the default programme for household dishwashers equipped with automatic programme selection or any function maintaining the selection of a programme, or, if there is no automatic programme selection, available for direct selection without the need for any other selection such as a specific temperature or load;
Ours was bought in late 2020, but manufacturers probably take a head start with implementation whenever they renew their models.
it's inferior to our old one, which was from the 90s and still worked, in other aspects too, most annoyingly cleaning performance. i guess it uses less water thou
> 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.
https://news.ycombinator.com/item?id=36002574 (381 points | 3 months ago | 358 comments)
[0]: https://wiki.freebsd.org/BootTime#Past_Performance_Improveme...
> 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.
The big thing is that I'm willing to sit down and earn a 50% improvement in performance by doing 10x 4% improvements in perf time. That's perseverance and foresight. Most of what I know about optimization tricks vs optimization process wouldn't quite fill up the first Gems book.
It's all about budget. If you're trying to double, quadruple the performance of something, you can't look at what the 5 slowest things are. You have to look at the thing taking 5% of the time and ask, "Does this deserve 20% of the CPU?" Because if you get 4x without touching this code, that 5% becomes 20%.
Then you don't work on the tall tent poles first, you work on the hot spots that relate to each other, and the ones you have the time and attention to do well. Because if you get a 20% improvement where a 25% improvement is possible, most bosses will not let you go back for the 2 x 2.5% later if you don't get it the first time. So then you are forever stuck with 50 x 1.5% slowdowns. Which is not a problem if you're profitable, but definitely is if you're bleeding money on hosting. Or if your main competitor is consistently 50% faster than yours.
https://lemire.me/blog/2023/04/27/hotspot-performance-engine...
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.
By looking at a module or concern as a whole, you get to do small-to-medium architectural improvements instead of none-to-small improvements. You get a broader picture, and can pull in more small areas of improvement in the process. The fastest code is code that doesn't run, and 'tall tent-pole' optimizations miss at least half of those opportunities. In some cases they just push them around, like broccoli on a child's plate.
Many teams get to the end of this road and then have absolutely no idea what to do next. I find it infuriating for a bunch of my 'betters' to listen to someone on the business side say, "Our customers are complaining about our speed/leaving for a competitor with a faster app" and then pull up a rectangular flame chart to 'prove' "We've done all we can". You have only done the easy parts, probably not even the best parts. You might have actually broken the best parts.
These apps are 'death by a thousand cuts'. No one part of the app is particularly slow, it's just uniformly mediocre coding and an architecture that squeaks by with 'adequate' (to them, but not the business) attention to capacity planning. Either a force of nature shows up and fixes it, or the company fades away.
The only boss I ever followed to a new job had two sayings that I stole. 1) "If you want to complete a meeting in an hour you need to complete half the meeting in half an hour" and the other was about scaling:
The first order of magnitude is simple. The second is difficult. The third requires talent (sometimes tacking on "which not all teams have.")
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..
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.
Thank you for the story and for keeping up the quality of education.
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.)
Know your data. (Which in this case, i don't).
If anyone misses less I can’t think of them.
...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?
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.
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.
Another possibility: always use link-time sorting for the kernel, and for individual modules, and then do runtime merging if and only if you have kernel modules. That way, the link-time sorting path is always tested, and the runtime merging is tested anytime you have kernel modules (which sounds like the more common case).
(All of this, though, is gated under "is it worth saving the microseconds yet".)
Net reduce of 5 LOCs and it's "100x faster".
Nice commit.
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.
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.
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.
It’s a 100x speed increase on 7% of the boot time, so it should be approximately a 7% decrease in boot time.
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.
(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.)
(The first two limitations are because this happens very early in the boot process.)
In this case however I'm putting all of the SYSINITs onto a linked list; mergesorting a linked list is easy.
grabbed the source and git blamed the file before the patch to see when the original code was from.
94e9d7c12 (Peter Wemm 1998-10-09 23:42:47 +0000 157) * The sysinit table itself. Items are checked off as the are run.
94e9d7c12 (Peter Wemm 1998-10-09 23:42:47 +0000 158) * If we want to register new sysinit types, add them to newsysinit.
The time wasted during boot here was probably irrelevant next to a hundred other things the project has worked on since.
the bubble sort was good enough that 25 years later they replaced it to save only 2ms during boot.
seems reasonable to me.
I just coarsely checked TAOCP volume 3, and didn’t see bubble sort mentioned in the chapter on external sorting.
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.
Rust's [T].sort_unstable() is part of core, that is, the code to sort a slice of arbitrary type T doesn't need the allocator, operating system etc.
Only if you want a fast stable sort do you need to wait for such an environment because their fast stable sort needs an allocator, I doubt that FreeBSD needs a stable sort here.
The SYSINITs need to bring up the system in a particular order. I dunno why there are both explicit ordering (the sort keys) and implicit ordering (the stability requirement), perhaps cperciva can chime in.
Based on when I last looked at this code, I guess the explicit ordering is to do with startup phases, and the implicit ordering is because of the way SYSINITs are (or were?) implemented using linker sets, which have more guarantees about ordering than __attribute__((constructor)) and other similar functionality.
In the event Colin is looking at this sub-thread now I'm intrigued too.
What we need isn't actually "stable" so much as "consistent from one boot to the next" to make sure that ordering bugs don't end up being heisenbugs.
This may be impractical, but I think my reaction would be to re-design it so that the ordering was mechanically a full order, even if culturally the people writing these things don't need to specify if they don't want to.
e.g. maybe a macro can turn your existing explicit order into high bits of a value, and then a "noise" factor into low bits, where that "noise" is derived from a date integer like 20230822 or filenames or whatever, and truly order on the entire value.
The idea is, this means any hidden order is the same for everyone, Intel laptop test rig, ARM WiFi cameras at customer site, last week's build, this week's build, Colin's build, the CI system's build, they're all using the same order, because while heisenbugs are strictly worse, "It only happens with my setup" is also extremely frustrating.
When people discover a hidden ordering requirement they can adjust the "real" ordering accordingly, just now there's a deliberate systemic consistency.
Probably not worth all the bother, but I think I couldn't live with the "stable sort to avoid heisenbugs" situation.
If you had a kernel written in Rust, you would have to bring up the rust runtime environment as part of the boot process. You don't just magically get it because that's the language you used, whether it is "core" or not. You can't even execute simple functions before you have set up stack, and in this case apparently there is a constraint on stack usage. And evidently they do need a stable sort.
In any case my main point is that it's not anything to do with dependency management, not quibbling about whether or not some language could support this function at this exact point of the boot.
Like the existing C runtime environment, this just isn't a big deal by the time we've got here. If you're the code for initialising the DRAM controller then sure, that's pretty intimidating. But this is all happening much later, we're part of an operating system, we were already loaded from disk.
> And evidently they do need a stable sort.
How so? They appear to even have a deliberate tie-breaking mechanism in their data structure, which suggests if order actually matters you're expected to specify when creating the data, not rely on stability to do what you expected.
> Like the existing C runtime environment, this just isn't a big deal by the time we've got here. If you're the code for initialising the DRAM controller then sure, that's pretty intimidating. But this is all happening much later, we're part of an operating system, we were already loaded from disk.
I don't know what you're trying to say. The code which is written here that we are discussing is in a constrained environment where the regular kernel runtime facilities are not all available. This was cited as one of the reasons cited for open coding a very simple algorithm.
> > And evidently they do need a stable sort.
> How so?
From reading comments from patch author here.
What facilities does Rust's sort require? It probably just needs a bit of stack but that's it.
That qsort implementation doesn't look like it needs anything either tbh, though I only skimmed it.
Maybe they could permit some of their sort library functions to be used in such a constrained environment, sure. Don't need rust to do that, just need to be happy that the implementation is suitable for purpose. Which they would have to do regardless of what language and runtime they were using.
Do you know how fast Linux starts up? I found the number 125ms but that’s a 4 year old number.
Just curious how similar they are. This is the first I’ve heard of Firecracker.
The overall speedups are still quite impressive - but for “thousands” of data items a simple O(n^2) algorithm seems fine, doesn’t it?
A small speedup on the longest (by time) part of the program is usually better than infinite speedup on a short part of the program.
https://en.wikipedia.org/wiki/Amdahl%27s_law
Usually used in the parallel computing context, but works here too.
I assume the entire performance of FreeBSD hasn't improved a hundredfold by this small change.
Might not matter for the things you care about, but some people certainly do care about boot performance.
So ~5ms speedup
Bubblesort has been controversial in many cs programs. That memo even reached the President ten years ago.