Does this open Webkit up for a denial of service Javascript fragment that triggers O(n^2) behaviour in their compiler? Then again, if you want to use up CPU resources with Javascript a simple while loop will do...
"Bug 150843 - Consider something better than bubble sort for insertion sets
achristiansen suggested falling back on stable sort if we do too many passes. ggaren suggested insertion sort.
There's also the possibility that we could make merge sort a lot faster, if we didn't use system malloc as the temp buffer allocator."
Apparently a really slow merge sort implementation caused a major performance slowdown. Since bubble sort is always taught as a bad sort it's kind of funny that he is using it to fix a performance regression. Hence the link and upvotes.
> Since bubble sort is always taught as a bad sort...
I was taught about bubble sort in three different situations. In each one, bubble sort was not taught as a "bad" sort. The instructor always focused on the difference between worst-case performance and best-case performance. It always forced me to learn how much context matters.
Bubble sort should not be used as teaching tool for "bad algorithms" but a teaching tool for understanding your data and how much you really know about it.
It might indeed be the best algorithm for common cases of this specific problem, but there needs to be a fallback when either the input is large or a lot of swaps are being done since otherwise it's O(n^2).
Interesting that other people pointed this out, yet he apparently committed the code anyway.
This touches on an interesting topic: how robust implementations of most algorithms go well beyond what you're taught in an algorithms course. There are tons of optimizations that matter when dealing with real world data that don't matter for algorithmic complexity.
(Sadly, I can't find a free PDF. I've sen this in Selected Papers on the Analysis of Algorithms--you can get a used copy from Amazon for a few dollars.)
"Is there any area (outside of numerical analysis) where mathematical theory has actually helped computer programmers?"
Ironically enough, he mentions bubblesort's performance as better in theory than practice for the most part. :P
Nice little speech, and his conclusion is much less inflammatory than your quote suggests (it would be strange if Knuth was really against mathematical theory).
Reading his examples, I feel as if time has been kind to mathematical theory. n has gotten a lot larger these days, and random access memory also simplifies some analyses. That's not always true, and the gap he identifies is still real, but maybe it's not always as important as it was.
14 comments
[ 2.9 ms ] story [ 40.2 ms ] threadDoes this open Webkit up for a denial of service Javascript fragment that triggers O(n^2) behaviour in their compiler? Then again, if you want to use up CPU resources with Javascript a simple while loop will do...
I filed a bug to fix this: https://bugs.webkit.org/show_bug.cgi?id=150843"
From that link
"Bug 150843 - Consider something better than bubble sort for insertion sets achristiansen suggested falling back on stable sort if we do too many passes. ggaren suggested insertion sort.
There's also the possibility that we could make merge sort a lot faster, if we didn't use system malloc as the temp buffer allocator."
Apparently a really slow merge sort implementation caused a major performance slowdown. Since bubble sort is always taught as a bad sort it's kind of funny that he is using it to fix a performance regression. Hence the link and upvotes.
Thanks for the explanation!
https://bugs.webkit.org/show_bug.cgi?id=150843
I was taught about bubble sort in three different situations. In each one, bubble sort was not taught as a "bad" sort. The instructor always focused on the difference between worst-case performance and best-case performance. It always forced me to learn how much context matters.
Bubble sort should not be used as teaching tool for "bad algorithms" but a teaching tool for understanding your data and how much you really know about it.
Interesting that other people pointed this out, yet he apparently committed the code anyway.
Two links on the subject:
Bentley and McIlroy on Engineering a Sort Function: http://cs.fit.edu/~pkc/classes/writing/samples/bentley93engi...
Tim Peters' Timsort: https://en.wikipedia.org/wiki/Timsort
https://mail.python.org/pipermail/python-dev/2002-July/02683...
(Sadly, I can't find a free PDF. I've sen this in Selected Papers on the Analysis of Algorithms--you can get a used copy from Amazon for a few dollars.)
"Is there any area (outside of numerical analysis) where mathematical theory has actually helped computer programmers?"
Ironically enough, he mentions bubblesort's performance as better in theory than practice for the most part. :P
Reading his examples, I feel as if time has been kind to mathematical theory. n has gotten a lot larger these days, and random access memory also simplifies some analyses. That's not always true, and the gap he identifies is still real, but maybe it's not always as important as it was.