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

bugzilla-daemon at webkit.org bugzilla-daemon at webkit.org
Tue Oct 30 09:11:58 PDT 2012


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


Cosmin Truta <ctruta at gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
 Attachment #171443|0                           |1
        is obsolete|                            |
 Attachment #171443|review?, commit-queue?      |
               Flag|                            |
 Attachment #171462|                            |review?, commit-queue?
               Flag|                            |




--- Comment #3 from Cosmin Truta <ctruta at gmail.com>  2012-10-30 09:13:16 PST ---
Created an attachment (id=171462)
 --> (https://bugs.webkit.org/attachment.cgi?id=171462&action=review)
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).

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


More information about the webkit-unassigned mailing list