99253 - Optimization on sort in pref-languages.js

Status: VERIFIED FIXED

(Core :: Internationalization, defect, P3)

Description

[John Morrison]

After tracking down an issue with loading an HTML page (bug 98012), and
digging into the JS Array.sort() method, I decided to have a look if there
were other places in the UI that might benefit from the following.

Basically, if you have an Array of Array's, and call .sort() on that, then JS
will call .toString() on each sub-array to flatten the list, and then do the
compare based on that string in its quicksort. However, if you are really
only interested in the sort occurring on the first element in each sub-array,
then it can be _much_ faster, on a medium length list, to pass a comparison
function into the .sort() method.

It seems that the sort in pref-languages.js benefits from this change
below. Without this patch, sort times were taking 47 msec for the
first view of that panel, and typically over 200msec for a subsequent
view (on win2k/500MHz; current CVS trunk build). [I'm not sure why it
takes more time on a subsequent view. Ideas?]

With this simple change, the sort took no more than 16 msec on any
occasion, often reporting '0' [n.b. win2k timers have a resolution of 
16ms].

Index: prefwindow/resources/content/pref-languages.js
===================================================================
RCS file: 
/cvsroot/mozilla/xpfe/components/prefwindow/resources/content/pref-languages.js
,v
retrieving revision 1.22
diff -u -r1.22 pref-languages.js
--- prefwindow/resources/content/pref-languages.js      2001/08/17 22:17:56     
1.22
+++ prefwindow/resources/content/pref-languages.js      2001/09/11 06:48:17
@@ -200,7 +200,12 @@
             //} //if visible
       } //if accepted
     } //while
-    availLanguageDict.sort();
+    availLanguageDict.sort( // sort on first element
+      function (a, b) {
+        if (a[0] < b[0]) return -1;
+        if (a[0] > b[0]) return  1;
+        return 0;
+    });
 }

So, assuming that 'sort on first column' is what you really want after all, 
then this is a pretty useful optimization [i.e., that panel is already the 
slowest in prefs; let's make it start to snap for the end-user].

Comment 1

[[e-mail] (away - not reading bugmail)]

I'm glad that someone is looking into the JS's Array.sort(). The sort is 
currently not locale-aware, which it should be. This was the reason, why I've 
recently spent some time looking into the possibility of using a compare 
function. An array sort will only perform an ASCII compare, which is really bad 
news for localized builds. 

Since we are not exposing the nsICollation interface to JS, there is no way to 
construct such locale-aware comparison function, and I didn't spend any time 
testing such a modification. Thanks for going to the effort of copying parts of 
the JS manual here - I believe it's more or less obvious that I've used the 
array sort for convenience. It didn't really occur to me that there might be 
some dramatic performance improvement in using a comparison function. So, 
congrats for finding that out!

While I'm aware of the poor performance in the "Add Language" popup and welcome 
this patch, there are some people who believe that this dialog is rarely used, 
and I've been scheduled to work on other tasks - primarily around startup 
optimization. Seems like you already did some performance metrics and an effort 
to change this dialog is well warranted. However, I have to object to your 
statement "that panel is already the slowest in prefs". The sort is only being 
used in the "Add Language" popup, not the basic "Languages" pref panel.

The collation issue I mentioned above could be solved by generating an RDF 
template in the core application. See two related bugs:

http://bugscape.mcom.com/show_bug.cgi?id=8242
http://bugscape.mcom.com/show_bug.cgi?id=8291

Although, I believe such a change could render any optimization of the existing 
JS superfluous, your patch might be quite valuable in the meantime -> 
accepting. Targeting 0.9.5.

Comment 2

[John Morrison]

Perhaps my comment about 'slowest' wasn't warranted, but I meant no disrespect
in it. I realize you have other priorities, and that is why I provided this 
patch, given that I had already "discovered" that the cost of calling toString
in an array sort was relatively high. So, with a simple LXR search, I found
another similar pattern, and we get a cheap win. No it's not rocket science.

Um, but that sort is used in the main panel 'pref-languages.xul'.

Comment 3

[[e-mail] (away - not reading bugmail)]

Attachment: patch proposed by jrgm

Comment 4

[[e-mail] (away - not reading bugmail)]

original patch by jrgm, so r=jbetak

ben, blake, alecf & blizzard - would anyone have some cycles for a sr? Minor,
but interesting change.

Comment 5

[Christopher Blizzard (:blizzard)]

sr=blizzard

Comment 6

[Alec Flett]

Comment on attachment 49404 [details] [diff] [review]
patch proposed by jrgm

sure, sounds good to me. sr=alecf

Comment 7

[[e-mail] (away - not reading bugmail)]

fix checked in - thanks everyone!

Comment 8

[Andreas Becker]

ftang, can this be verified within development? Otherwise please provide IQA 
with a test case. Thanks.

Comment 9

[[e-mail] (away - not reading bugmail)]

clocking ~20% faster pref pane initialization. Marking verified.