[Webkit-unassigned] [Bug 100754] Faster sorting of numeric arrays

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=100754





--- Comment #10 from Cosmin Truta <ctruta at gmail.com>  2012-11-02 10:59:40 PST ---
(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.

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.