News for hackers. Stuff that matters.
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by kortilla on Monday August 21, 2023 @04:14AM (#37206699)
> 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.

Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by alkonaut on Monday August 21, 2023 @04:25AM (#37206781)
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.

Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re... by GuB-42 on Tuesday August 22, 2023 @05:15PM (#37228619)
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.