[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