10 ms·

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 pr

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.
    - GuB-42 3y ago
      The problem is that it is an issue in 1% of cases, and it is hard to know in advance which 1%. So either you do a proper analysis to see how many inputs you really need, or you use an algorithm that scale. 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.
  - masklinn 3y ago
    Here it took almost 30 years for it to stop being fine, which is a pretty good run. 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).
    - alkonaut 3y ago
      One should indeed be forgiven when getting 30 years out of a code base, any code base. It's hard to predict that you'd need to shave milliseconds of cloud/VM startups or from some embedded device, if you can't imagine Clouds, VMs or computers the size of watches.
  - toast0 3y ago
    > Yeah and it almost always stops being fine. 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.
- JonChesterfield 3y ago
  Old colleague had some wisdom on this which stuck with me. Thanks Ben! Spoken at separate times. - 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.
  - Sharlin 3y ago
    > - constant time means your best case is as slow as your worst case Which is in fact important in crypto code to prevent timing attacks.
kragen 3y ago
yes, it was stupid to use bubble sort to begin with; there is never a good reason to use bubble sort for (size_t i = 0; i < n; i++) { for (size_t j = 1; j < n - i; j++) { if (a[j-1] > a[j]) { item_t tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; } } } when you could use insertion sort for (size_t i = 1; i < n; i++) { for (size_t j = i; j > 0; j--) { item_t tmp = a[j]; if (tmp > a[j-1]) break; a[j] = a[j-1]; a[j-1] = tmp; } } which is no more complicated (both are 17 amd64 instructions with -Os), but twice as fast in the random case, and enormously faster in the sorted and almost-sorted cases (above code only minimally tested: https://godbolt.org/z/43dqz9Gq8 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)
- SomeoneFromCA 3y ago
  Neither of your code snippets are working, or are an actual implementation of bubble sort. Since what insertion sort is faster that bubble sort on sorted data?
  - kragen 3y ago
    i tested both of them on some input data and they both sorted it correctly, though of course they could contain bugs (if so i'd be grateful if you pointed them out) 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
    - SomeoneFromCA 3y ago
adam_oxla 3y ago
It is surprising how popular is using O(N^2) algorithms that are simple in implementation even in extremely popular libraries. E. g. ICU search method: https://github.com/unicode-org/icu/blob/a7a2fdbcf257fa22c7a24cfae838675dafd5e071/icu4c/source/common/stringpiece.cpp#L54 https://github.com/unicode-org/icu/blob/a7a2fdbcf257fa22c7a2... ICU is used by Python, Windows or OpenOffice.

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.
  - GuB-42 3y ago
    The problem is that it is an issue in 1% of cases, and it is hard to know in advance which 1%. So either you do a proper analysis to see how many inputs you really need, or you use an algorithm that scale. 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.
- masklinn 3y ago
  Here it took almost 30 years for it to stop being fine, which is a pretty good run. 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).
  - alkonaut 3y ago
    One should indeed be forgiven when getting 30 years out of a code base, any code base. It's hard to predict that you'd need to shave milliseconds of cloud/VM startups or from some embedded device, if you can't imagine Clouds, VMs or computers the size of watches.
- toast0 3y ago
  > Yeah and it almost always stops being fine. 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.
JonChesterfield 3y ago
Old colleague had some wisdom on this which stuck with me. Thanks Ben! Spoken at separate times. - 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.
- Sharlin 3y ago
  > - constant time means your best case is as slow as your worst case Which is in fact important in crypto code to prevent timing attacks.

kragen 3y ago

yes, it was stupid to use bubble sort to begin with; there is never a good reason to use bubble sort for (size_t i = 0; i < n; i++) { for (size_t j = 1; j < n - i; j++) { if (a[j-1] > a[j]) { item_t tmp = a[j]; a[j] = a[j-1]; a[j-1] = tmp; } } } when you could use insertion sort for (size_t i = 1; i < n; i++) { for (size_t j = i; j > 0; j--) { item_t tmp = a[j]; if (tmp > a[j-1]) break; a[j] = a[j-1]; a[j-1] = tmp; } } which is no more complicated (both are 17 amd64 instructions with -Os), but twice as fast in the random case, and enormously faster in the sorted and almost-sorted cases (above code only minimally tested: https://godbolt.org/z/43dqz9Gq8 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)

SomeoneFromCA 3y ago
Neither of your code snippets are working, or are an actual implementation of bubble sort. Since what insertion sort is faster that bubble sort on sorted data?
- kragen 3y ago
  i tested both of them on some input data and they both sorted it correctly, though of course they could contain bugs (if so i'd be grateful if you pointed them out) 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
  - SomeoneFromCA 3y ago

adam_oxla 3y ago

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