6 ms·

> above code only minimally tested There you have your problem: any programmer can write a bubble sort while half asleep and inebriated at the same time, but f

by gpvos 3y ago

> above code only minimally tested 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.

kragen 3y ago
i'm not sure; i made a few mistakes in each of them as i was writing them, but they were both working by the time i first tested them. i do feel like the insertion sort was maybe a little more challenging? edited to add: someonefromca spotted a bug in the insertion sort; where it says if (tmp > a[j-1]) break; it should say if (tmp >= a[j-1]) break; which is both a performance bug and also breaks the stability property the algorithm otherwise has 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?
- abecedarius 3y ago
  fwiw that comparison was where I went "wait, is that right?" in my reading. 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.
- aristophenes 3y ago
  You should edit the code in your original comment, someone is bound to copy paste the code somewhere…
  - kragen 3y ago
    it's only editable for two hours, for better or worse
moffkalast 3y ago
This has gotta be the most bullshit justification for writing bad kernel code that will be reviewed and tested by 200 people before it reaches production. Literally anything written as low level as this has the potential to crash the system on a dime and needs to be thoroughly tested.
- astrange 3y ago
  Old code in BSD wasn't thoroughly tested except by virtue of being old; there's no QA department and traditionally UNIX code was tested by thinking about it really hard rather than automated testing. (FreeBSD got a test suite in 10.1, which came out in 2014, not that long ago in UNIX terms.)
  - oblio 3y ago
    Not just in BSD... GNU wasn't much better. People would be shocked by how little the core tools we use were tested automatically. Some still aren't.
    - Quekid5 3y ago
      Quite. 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.
- Quekid5 3y ago
  If your testing infrastructure is so anemic that a sorting algorithm (of all things) is hard to subject to e.g. property-based/fuzzing tests then it'd probably be worth it to expand that before doing anything else. 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.
  - kragen 3y ago

by gpvos 3y ago

kragen 3y ago

i'm not sure; i made a few mistakes in each of them as i was writing them, but they were both working by the time i first tested them. i do feel like the insertion sort was maybe a little more challenging? edited to add: someonefromca spotted a bug in the insertion sort; where it says if (tmp > a[j-1]) break; it should say if (tmp >= a[j-1]) break; which is both a performance bug and also breaks the stability property the algorithm otherwise has 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?

abecedarius 3y ago
fwiw that comparison was where I went "wait, is that right?" in my reading. 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.
aristophenes 3y ago
You should edit the code in your original comment, someone is bound to copy paste the code somewhere…
- kragen 3y ago
  it's only editable for two hours, for better or worse

moffkalast 3y ago

This has gotta be the most bullshit justification for writing bad kernel code that will be reviewed and tested by 200 people before it reaches production. Literally anything written as low level as this has the potential to crash the system on a dime and needs to be thoroughly tested.

astrange 3y ago
Old code in BSD wasn't thoroughly tested except by virtue of being old; there's no QA department and traditionally UNIX code was tested by thinking about it really hard rather than automated testing. (FreeBSD got a test suite in 10.1, which came out in 2014, not that long ago in UNIX terms.)
- oblio 3y ago
  Not just in BSD... GNU wasn't much better. People would be shocked by how little the core tools we use were tested automatically. Some still aren't.
  - Quekid5 3y ago
    Quite. 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.
Quekid5 3y ago
If your testing infrastructure is so anemic that a sorting algorithm (of all things) is hard to subject to e.g. property-based/fuzzing tests then it'd probably be worth it to expand that before doing anything else. 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.
- kragen 3y ago