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

[bugzilla-daemon at webkit.org]

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


Darin Adler <darin at apple.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
 Attachment #171896|review?, commit-queue?      |review-, commit-queue-
               Flag|                            |




--- Comment #9 from Darin Adler <darin at apple.com>  2012-11-02 09:57:02 PST ---
(From update of attachment 171896)
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.

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