Faster sorting of numeric arrays

• Component: JavaScriptCore
• Status: RESOLVED CONFIGURATION CHANGED

[Cosmin Truta]

Currently, dense arrays are sorted with qsort(), although std::sort offers a better performance. The two main reasons are the better algorithm (Introsort vs. Quicksort) and the inlining of the comparator (see Item 46 "Consider function objects instead of functions as algorithm parameters" in Scott Meyers' "Effective STL").

In addition, I noticed that sorting is highly asymmetric: descending numeric sorting is much slower than ascending numeric sorting, because the former lacks a specialized comparator.

The upcoming patch will address these issues.

[Cosmin Truta]

Created attachment 171443 [details]
Patch

Here is the patch.

I tested the sorting of 1 million elements on x86-64. The performance results are as follows:
- Ascending-numeric sorting is faster by ~170%.
- Descending-numeric sorting is faster by ~6x.

[Yong Li]

Comment on attachment 171443 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=171443&action=review

> Source/JavaScriptCore/ChangeLog:14
> +        Add a specialized comparator for descending-numeric sorting.
> +        This improves its performance by several orders of magnitude.

any numbers?

> Source/JavaScriptCore/bytecode/CodeBlock.h:455
> +        ComparatorKind comparatorKind() { return m_comparatorKind; }

the function should be const

> Source/JavaScriptCore/runtime/JSArray.cpp:781
> +    bool operator()(const WriteBarrier<Unknown>& a, const WriteBarrier<Unknown>& b)

operator() can be either static or const. I would use static

> Source/JavaScriptCore/runtime/JSArray.cpp:870
> +static int compareByStringPairForQSort(const void* a, const void* b)
> +{
> +    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
> +    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
> +    return codePointCompare(va->second, vb->second);
> +}

Is this function still being used?

[Cosmin Truta]

Created attachment 171462 [details]
Patch

(In reply to comment #2)
> any numbers?

Added to ChangeLog.

> > Source/JavaScriptCore/bytecode/CodeBlock.h:455
> > +        ComparatorKind comparatorKind() { return m_comparatorKind; }
> 
> the function should be const

Done.

> > Source/JavaScriptCore/runtime/JSArray.cpp:781
> > +    bool operator()(const WriteBarrier<Unknown>& a, const WriteBarrier<Unknown>& b)
> 
> operator() can be either static or const. I would use static

I made it const. It can't be static, because it needs to be applied to the comparator object Less<WriteBarrier<Unknown>>().

> > Source/JavaScriptCore/runtime/JSArray.cpp:870
> > +static int compareByStringPairForQSort(const void* a, const void* b)
> 
> Is this function still being used?

Yes. String sorting is still done via qsort, because it needs a 3-way comparator. Unfortunately, std::sort requires a 2-way comparator, and because of that, strings get compared twice (1st time as a<b, 2nd time as b<a), and that wastes precious time.

An introspective sorting routine for strings, that uses a 3-way inlined comparator, is a possibility for future improvement.
Radix sorting is another possible alternative (currently marked as a FIXME in JSArray.cpp).

[Filip Pizlo]

Comment on attachment 171462 [details]
Patch

I think this change is right.  But this is tricky code - so can you add a new test case?  I want to see a test for descending-order sort, and a few tests where your descending/ascending order compare function detection code would have to fall back.

[Cosmin Truta]

(In reply to comment #4)
> But this is tricky code - so can you add a new test case?

Will do.

[Sam Weinig]

Can you also provide the micro-benchmark you used?

[Cosmin Truta]

Created attachment 171895 [details]
Micro-benchmark

(In reply to comment #6)
> Can you also provide the micro-benchmark you used?

Done. See the attached file sort_ubench.js

[Cosmin Truta]

Created attachment 171896 [details]
Patch and tests

[Darin Adler]

Comment on attachment 171896 [details]
Patch and tests

View in context: https://bugs.webkit.org/attachment.cgi?id=171896&action=review

Thanks for taking this on. Nice work and this seems like a tidy, small improvement.

At the time we originally chose qsort, I believe it was faster than std::sort on at least one platform. You are talking about std::sort and “STL’s algorithm” as if the standard library guaranteed a particular algorithm, but this can differ from platform to platform. It would be good to know what platform you did performance testing on, and what the results are on the other most-dissimilar platforms. I’m interested in what this does on Mac, for example.

review- because I think the class template and static member issues, at least, should be fixed. Please consider my other comments as well.

> Source/JavaScriptCore/ChangeLog:17
> +        * JavaScriptCore.order:

No need to touch order files. They are programmatically generated from time to time and don’t need to be hand-updated. At some point maybe we should just remove them from the project.

> Source/JavaScriptCore/ChangeLog:19
> +        (JSC::CodeBlock::CodeBlock):

Please leave out bogus lines like this, even if the change log script adds them. For extra credit, fix the script or convince someone else to do so.

> Source/JavaScriptCore/ChangeLog:23
> +        (CodeBlock):

Please leave out bogus lines like this, even if the change log script adds them. For extra credit, fix the script or convince someone else to do so.

> Source/JavaScriptCore/ChangeLog:27
> +        (BytecodeGenerator):

Please leave out bogus lines like this, even if the change log script adds them. For extra credit, fix the script or convince someone else to do so.

> Source/JavaScriptCore/ChangeLog:32
> +        (JSC::comparatorKind):
> +        (JSC::arrayProtoFuncSort):

No comments for these?

> Source/JavaScriptCore/ChangeLog:35
> +        (JSC):

Please leave out bogus lines like this, even if the change log script adds them. For extra credit, fix the script or convince someone else to do so.

> Source/JavaScriptCore/ChangeLog:38
> +        (JSC::compareByStringPairForQSort):

Given this function didn’t change, I suggest removing this from the change log. The change log script was just confused because of the diff output.

> Source/JavaScriptCore/ChangeLog:40
> +        (JSArray):

Please leave out bogus lines like this, even if the change log script adds them. For extra credit, fix the script or convince someone else to do so.

> Source/JavaScriptCore/bytecode/CodeBlock.h:454
> +        void setComparatorKind(ComparatorKind comparatorKind) { m_comparatorKind = comparatorKind; }

I’d name the argument just “kind”.

> Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp:2104
> +                else if (generator.isArgumentNumber(lhsIdentifier, 1) && generator.isArgumentNumber(rhsIdentifier, 0))
> +                    generator.setComparatorKind(NumericDescendingComparator);

How common is this particular form on actual websites? Are there other ways of writing the descending numeric comparator function that are common?

> Source/JavaScriptCore/runtime/JSArray.cpp:776
> +// Ascending-order comparator for the numeric sort

We put periods on comments even when they aren’t really full sentences. I think the word “the” here should be omitted.

> Source/JavaScriptCore/runtime/JSArray.cpp:778
> +template<typename ArgType> class Less;
> +template<> class Less<WriteBarrier<Unknown> >

As far as I can tell, there is no advantage in using a class template here instead of a struct or class. Please make this a struct instead of a class template.

> Source/JavaScriptCore/runtime/JSArray.cpp:781
> +    bool operator()(const WriteBarrier<Unknown>& a, const WriteBarrier<Unknown>& b) const

This should be a static member function instead of a non-static const member function.

> Source/JavaScriptCore/runtime/JSArray.cpp:784
> +        const JSValue* va = static_cast<const JSValue*>(static_cast<const void*>(&a));
> +        const JSValue* vb = static_cast<const JSValue*>(static_cast<const void*>(&b));

I’m not sure that this is the right way to convert from const WriteBarrier<Unknown>& to JSValue*, even though I understand this is analogous to what the function we passed to qsort did. Is there other code that does this with these same two static_cast? Could you look at existing code to see what the usual idiom is?

> Source/JavaScriptCore/runtime/JSArray.cpp:789
> +// Ascending-order comparator for the numeric sort

This says ascending but it’s actually used for descending order.

We put periods on comments even when they aren’t really full sentences. I think the word “the” here should be omitted.

> Source/JavaScriptCore/runtime/JSArray.cpp:791
> +template<typename ArgType> class Greater;
> +template<> class Greater<WriteBarrier<Unknown> >

As far as I can tell, there is no advantage in using a class template here instead of a struct or class. Please make this a struct instead of a class template.

> Source/JavaScriptCore/runtime/JSArray.cpp:794
> +    bool operator()(const WriteBarrier<Unknown>& a, const WriteBarrier<Unknown>& b) const

This should be a static member function instead of a non-static const member function.

[Cosmin Truta]

(In reply to comment #9)
> Thanks for taking this on. Nice work and this seems like a tidy, small improvement.

Thank you!

> At the time we originally chose qsort, I believe it was faster than std::sort on at least one platform. You are talking about std::sort and “STL’s algorithm” as if the standard library guaranteed a particular algorithm, but this can differ from platform to platform. It would be good to know what platform you did performance testing on, and what the results are on the other most-dissimilar platforms. I’m interested in what this does on Mac, for example.

The C++ standard requires std::sort complexity to be N*logN, while qsort() uses QuickSort, whose worst-case is N^2. So the better worst-case performance is theoretically required.

Moreover, the major STL implementations I'm aware of (Dinkumware, RogueWave, SGI and derivatives including GNU STL and STLport) use David Musser's Introsort, which offer this guarantee. (Unsurprisingly so: David Musser used to be in the C++ Standards Committee.) As far as I know, Mac uses GNU STL, so all should be well on that front.

As far as average-case performance is concerned, std::sort beats qsort when the comparator is cheap (e.g. when comparing numbers), because it is capable to inline the comparator, yielding significant savings; and qsort beats std::sort when the comparator is expensive (e.g. when comparing strings), because std::sort uses a 2-way comparator called once or twice per pair, while qsort uses a 3-way comparator that's always called once per pair.

To make my above long story short, std::sort is better when comparing numbers and qsort is better when comparing strings, and that's why my patch applies to numbers only.

This is, of course, assuming that both qsort and std::sort are implemented properly. I am not aware of any platform in use where these aren't.

> > Source/JavaScriptCore/bytecompiler/NodesCodegen.cpp:2104
> > +                else if (generator.isArgumentNumber(lhsIdentifier, 1) && generator.isArgumentNumber(rhsIdentifier, 0))
> > +                    generator.setComparatorKind(NumericDescendingComparator);
> 
> How common is this particular form on actual websites? Are there other ways of writing the descending numeric comparator function that are common?

I've seen all kinds of idioms, actually. I addressed the case "b-a" as the inverse of the existing "a-b", although one can argue "-a+b" is also an inverse. (Haven't seen that one, though.) I remember seeing "(a>b)-(a<b)" (not just in JSC code), as well as various forms of "if (a==b) return 0; else...".

My idea behind this patch was to have at least one way to perform a fast descending sort. Moreover, I aimed to a symmetric performance: whatever idiom is used, its reverse should be equally fast.

I will address the other comments in my upcoming patch, except for:

> > Source/JavaScriptCore/runtime/JSArray.cpp:781
> > +    bool operator()(const WriteBarrier<Unknown>& a, const WriteBarrier<Unknown>& b) const
> 
> This should be a static member function instead of a non-static const member function.

It won't compile if it's static, because the caller accesses it through the Less() object. This idiomatic STL coding is meant to work even if the comparison object has state. It's also meant to be inlined (otherwise there are no benefits from a regular function pointer), so not being static causes no perf degradation.

> > Source/JavaScriptCore/runtime/JSArray.cpp:784
> > +        const JSValue* va = static_cast<const JSValue*>(static_cast<const void*>(&a));
> > +        const JSValue* vb = static_cast<const JSValue*>(static_cast<const void*>(&b));
> 
> I’m not sure that this is the right way to convert from const WriteBarrier<Unknown>& to JSValue*, even though I understand this is analogous to what the function we passed to qsort did. Is there other code that does this with these same two static_cast? Could you look at existing code to see what the usual idiom is?

I initially tried the proper conversion, i.e. "a.get().asNumber()", but the end result was slower, not sure why though. I will give it another look.

[Cosmin Truta]

Created attachment 172150 [details]
Patch and tests

New submission, addressing Darin's comments.

(In reply to comment #10)
> (In reply to comment #9)
> > I’m not sure that this is the right way to convert from const WriteBarrier<Unknown>& to JSValue*, even though I understand this is analogous to what the function we passed to qsort did. Is there other code that does this with these same two static_cast? Could you look at existing code to see what the usual idiom is?
> I initially tried the proper conversion, i.e. "a.get().asNumber()", but the end result was slower, not sure why though. I will give it another look.

I had noticed a small performance degradation last time I used this call, so I kept the cast. Maybe something was wrong in my testing, because this time around I rerun the tests, and I saw no difference in performance between the proper conversion and the ugly cast.

(In reply to comment #9)
> It would be good to know what platform you did performance testing on, and what the results are on the other most-dissimilar platforms.

Forgot to answer that.
My reported perf improvements were obtained on an Intel i7 running Linux Mint, building JSC with gcc.
Moreover, I compared the raw performance between std::sort and qsort (in plain C++, not JSC) using clang, and I had also run in the past such comparison tests on other platforms, including Windows (both Visual C++ and MinGW). The improvements given by std::sort were visible and consistent.
My experience is not singular. See, for example: http://www.lemoda.net/c/inline-qsort-example/

[Sam Weinig]

(In reply to comment #10)
> (In reply to comment #9)
> Moreover, the major STL implementations I'm aware of (Dinkumware, RogueWave, SGI and derivatives including GNU STL and STLport) use David Musser's Introsort, which offer this guarantee. (Unsurprisingly so: David Musser used to be in the C++ Standards Committee.) As far as I know, Mac uses GNU STL, so all should be well on that front.

We actually use libc++ on the Mac.

[Cosmin Truta]

(In reply to comment #12)
> We actually use libc++ on the Mac.

Interesting to know, thanks. Last time I worked in C++ on a Mac, there was GNU STL on OS X Lion.

I downloaded and tried to build libc++ and libc++abi on Mint 13 with clang++ 3.0, but couldn't. I understood it can be built using clang++ 3.2 pre-release on Debian Sid, but I don't have that.
However, I did examine the <algorithm> source code on libc++, and I noticed that, although std::sort doesn't appear to be using the original Introsort algorithm, it is, nonetheless, introspective. In fact, its introspection mechanism seems quite sophisticated.

[Cosmin Truta]

Created attachment 173750 [details]
C++ micro-benchmark

(In reply to comment #12)
> We actually use libc++ on the Mac.

I finally tried the attached C++ micro-benchmark on a Mac running OS X 10.7.5, Xcode 4.4.1, using both clang++ and g++ at -O3, and using both libc++ and GNU STL.
When applied to int[] arrays with 16 million elements, std::sort using function objects beat qsort by approx. 3x (seriously!). On double[] arrays, std::sort beat qsort by approx. 2.5x.
Moreover, there was a noticeable difference between std::sort'ing with function objects vs. function pointers. Although the latter was slower, the function-pointer-driven specialization of std::sort still beat the function-pointer-driven qsort by approx. 1.8x. YYMV.

In conclusion, std::sort beats qsort significantly -- especially on the Mac.

[Cosmin Truta]

Created attachment 173754 [details]
Patch and tests

I noticed there were significant changes in the codebase recently, so I had to rework my patch accordingly.
Given the new, specialized handling of int32 arrays and double arrays, I added extra tests as well.

[WebKit Review Bot]

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

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast..." exit_code: 1
LayoutTests/ChangeLog:15:  Need whitespace between colon and description  [changelog/filechangedescriptionwhitespace] [5]
Total errors found: 1 in 17 files


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

[Cosmin Truta]

Created attachment 173755 [details]
Patch and tests

Oops, a typo in ChangeLog. Fixed.

[Yong Li]

The patch looks ready. Ping JSC reviewers kindly...

[Oliver Hunt]

Comment on attachment 173755 [details]
Patch and tests

View in context: https://bugs.webkit.org/attachment.cgi?id=173755&action=review

This looks good, the only complaint i have is using a bool to indicate sort direction - i'd rather have an enum, that's the direction we've been moving in for a while now.

> Source/JavaScriptCore/runtime/JSArray.h:69
> -    void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&);
> +    void sortNumeric(ExecState*, JSValue compareFunction, CallType, const CallData&, bool ascendingOrder);

I don't like this bool, replace it with an enum -- say enum SortOrder { SortAscending, SortDescending };

[Cosmin Truta]

Created attachment 179542 [details]
Patch and tests

Thank you, Oliver. I replaced bool ascendingOrder with ComparatorKind comparator, as per our conversation.

[Early Warning System Bot]

Comment on attachment 179542 [details]
Patch and tests

Attachment 179542 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/15313851

[Early Warning System Bot]

Comment on attachment 179542 [details]
Patch and tests

Attachment 179542 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/15323823

[Cosmin Truta]

Comment on attachment 179542 [details]
Patch and tests

Setting cq? again. The errors reported by the Qt EWS are unrelated to this patch.

[Build Bot]

Comment on attachment 179542 [details]
Patch and tests

Attachment 179542 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/15321819

[Build Bot]

Comment on attachment 179542 [details]
Patch and tests

Attachment 179542 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15309838

[EFL EWS Bot]

Comment on attachment 179542 [details]
Patch and tests

Attachment 179542 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/15323923

[EFL EWS Bot]

Comment on attachment 179542 [details]
Patch and tests

Attachment 179542 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/15313951

[Cosmin Truta]

Created attachment 180006 [details]
Patch and tests

Inclusion of "UnlinkedCodeBlock.h" added a declaration of JSC::Node in WebKit2, which clashed with WebCore::Node and broke the build on EFL and Windows. Not sure why the build broke on Mac and Qt, though. (Could it be because of indirect inclusion of the parser?)

I fixed it by qualifying WebCore::Node explicitly in WebKit2, and tested it on the EFL build. Let's hope it passes on the other platforms also.

[Early Warning System Bot]

Comment on attachment 180006 [details]
Patch and tests

Attachment 180006 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/15418217

[Early Warning System Bot]

Comment on attachment 180006 [details]
Patch and tests

Attachment 180006 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/15409249

[Build Bot]

Comment on attachment 180006 [details]
Patch and tests

Attachment 180006 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15413238

[Cosmin Truta]

Created attachment 180269 [details]
Patch and tests

Inclusion of bytecode/UnlinkedCodeBlock.h indirectly included parser/ParserTokens.h, and the latter contains all-caps enum symbols that clashed with macros (e.g. FUNCTION, COMMA, SEMICOLON) defined elsewhere. This broke the build on Mac and Qt.
I resolved this breakage by moving ComparatorKind into a separate file, which allowed the include dependencies to be alleviated.
Now there shouldn't be any WebKit2 breakages either. I undid the WebKit2 changes that had been submitted with the previous patch.

[Cosmin Truta]

Created attachment 180270 [details]
Patch and tests

Same as previous patch, but without the dependency on parser specified in Tools/DumpRenderTree/efl. It's no longer necessary.

[Build Bot]

Comment on attachment 180270 [details]
Patch and tests

Attachment 180270 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15403956

[Build Bot]

Comment on attachment 180270 [details]
Patch and tests

Attachment 180270 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://queues.webkit.org/results/15909488

[Cosmin Truta]

Created attachment 188167 [details]
Patch and tests

Last patch didn't pass because project files weren't updated.
I rebased, resolved the conflicts and rerun the tests, it should pass now.

[Build Bot]

Comment on attachment 188167 [details]
Patch and tests

Attachment 188167 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://queues.webkit.org/results/16570011

[Cosmin Truta]

Created attachment 188192 [details]
Patch and tests

The updated Xcode project file was missing a comma. (Oops.) Resubmitting.

[Yong Li]

Comment on attachment 188192 [details]
Patch and tests

View in context: https://bugs.webkit.org/attachment.cgi?id=188192&action=review

LGTM basically. Changes suggested by previous reviewers are addressed. But see my comment.

> Source/JavaScriptCore/bytecode/ComparatorKind.h:35
> +enum ComparatorKind {
> +    CustomComparator,
> +    NumericAscendingComparator,
> +    NumericDescendingComparator
> +};

This enum will be folded into a 2-bit bit-field. It would be nice to add some comments or compile time assert just in case someone inserts more enum values but doesn't check the bit-field accordingly.

[Ahmad Saleem]

Is this r+ patch relevant now? Thanks!

[Yusuke Suzuki]

(In reply to Ahmad Saleem from comment #40)
> Is this r+ patch relevant now? Thanks!

It is no longer relevant since Array#sort algorithm & implementation are rewritten now.