Bug 150828 – B3/Air should use bubble sort for their insertion sets, because it's faster than std::stable_sort

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Filip Pizlo]

std::stable_sort really sucks.  We should use bubble sort instead.

[Filip Pizlo]

Created attachment 264651 [details]
the patch

[WebKit Commit Bot]

Attachment 264651 [details] did not pass style-queue:


ERROR: Source/WTF/wtf/BubbleSort.h:42:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
ERROR: Source/WTF/wtf/BubbleSort.h:44:  Should have only a single space after a punctuation in a comment.  [whitespace/comments] [5]
Total errors found: 2 in 8 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Alex Christensen]

Comment on attachment 264651 [details]
the patch

Would it be as fast if you added something to eliminate the possibility of the worst case, such as when the number of swaps reaches 5 times the number of elements fall back to std::stable_sort? 5 is arbitrary

[Geoffrey Garen]

Comment on attachment 264651 [details]
the patch

Why not insertion sort? Equally easy, fewer writes because it doesn't swap.

[Filip Pizlo]

(In reply to comment #4)
> Comment on attachment 264651 [details]
> the patch
> 
> Why not insertion sort? Equally easy, fewer writes because it doesn't swap.

Style points!

[Geoffrey Garen]

:(

[Filip Pizlo]

(In reply to comment #6)
> :(

In all seriousness, I just wanted a quick fix to undo the perf regression caused by using std::stable_sort.

I filed a bug to fix this: https://bugs.webkit.org/show_bug.cgi?id=150843

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/191960