Bug 150828

Summary:

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

Product:

WebKit

Reporter:

Filip Pizlo <fpizlo>

Component:

JavaScriptCore

Assignee:

Filip Pizlo <fpizlo>

Status:

RESOLVED FIXED

Severity:

Normal

CC:

benjamin, commit-queue, ggaren

Priority:

Version:

WebKit Nightly Build

Hardware:

All

OS:

All

Bug Depends on:

Bug Blocks:

150279

Attachments:

Description	Flags
the patch	ggaren: review+

Filip Pizlo

Reported 2015-11-02 17:36:23 PST

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

Attachments
the patch (12.93 KB, patch) 2015-11-02 17:43 PST, Filip Pizlo	ggaren: review+	Details Formatted Diff Diff
View All Add attachment proposed patch, testcase, etc.

Filip Pizlo

Comment 1 2015-11-02 17:43:20 PST

Created attachment 264651 [details] the patch

WebKit Commit Bot

Comment 2 2015-11-02 17:46:13 PST

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 3 2015-11-02 20:41:15 PST

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 4 2015-11-02 21:19:25 PST

Comment on attachment 264651 [details] the patch Why not insertion sort? Equally easy, fewer writes because it doesn't swap.

Filip Pizlo

Comment 5 2015-11-03 10:41:32 PST

(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

Comment 6 2015-11-03 10:43:01 PST

Filip Pizlo

Comment 7 2015-11-03 10:50:41 PST

(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

Comment 8 2015-11-03 12:27:55 PST

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

Note You need to log in before you can comment on or make changes to this bug.