1141431 - Eliminate |NS_QuickSort| use in MailNews, use C++'s standard |std::sort()| or |std::stable_sort()| instead

Status: RESOLVED FIXED

(MailNews Core :: Backend, defect)

Description

[WADA:World Anti-bad-Duping Agency]

+++ This bug was initially created as a clone of Bug #72196 +++
+++ Bug #72196 :  eliminate |NS_QuickSort|, use C's standard |qsort| instead

Eliminate |NS_QuickSort| use in MailNews, use C++'s standard |std:sort()| or |std:stable_sort()| instead

Bug #72196 was WONTFIXed. Reason looks "advantage of NS_QuickSort over qsort() in sort function passing".
As known by Bug #72196  Comment #3, NS_QuickSort was started to use based on wrong reason or assumption.
> Mozilla should consider removing NS_QuickSort and just use
> qsort in the standard C library.  The comments in the source file:
>    /* We need this because Solaris' version of qsort is broken and
>     * causes array bounds reads.
>     */
> turned out to be wrong -- we were calling qsort with an
> incorrect comparison function which only broke the Solaris
> implementation of qsort.
And, NS_QuickSort() had critical problem of Bug 872497 for pretty long time until  the problem was exposed  by Bug 872497 and fixed.
   Bug 872497 - O(n^2) performance in NS_QuickSort

What is actual reason why NS_QuickSort() was used instead of standard C's sort() or qsort() or C++'s std:sort or std:stable_sort()?
Following?
    If swap of left side element and right side element doesn't occur, 
    NS_QuickSort() did insertion sort for entire block of left side + right side.
    So, It's pretty fast if entire array is already sorted in ascending order, as bubble sort is fast,
    because nothing is moved.
If so, it's already removed from NS_QuckSort() by Bug 872497, so useless/blind/frequent NS_QuckSort() call on "array of already sorted in ascending order" easily produces performance issue.

What is actual reason why std:sort or std:stable_sort() is still not used?

Comment 1

[WADA:World Anti-bad-Duping Agency]

FYI.
bug 738533 is "reverting back to original C's qsort() which was done in 2012" from NS_QuickSort() which was used in the past based on wrong reason.

Comment 2

[WADA:World Anti-bad-Duping Agency]

FYI.
Fault in WONTFIXing of Bug 72196 :
   Request consists of ;
      (a) revert back, or change to qsort(), from NS_QuickSort(), at as many places as possible. 
      (b) remove NS_QuickSort().
   When WONTFIXed, WONTFIX should have been applied to (b) only.
   But (a) was also WONTFIXed by WONTFIxing of Bug 72196.
This bug is for (a) only in Mail&News with altering qsort() to std:sort()\std:stable _sort().

Comment 3

[WADA:World Anti-bad-Duping Agency]

mozilla-central
  http://mxr.mozilla.org/mozilla-central/search?string=%2Bstd%3A%3Astable_sort%28
  http://mxr.mozilla.org/mozilla-central/search?string=%2Bstd%3A%3Asort%28
  http://mxr.mozilla.org/mozilla-central/search?string=NS_QuickSort%28

comm-central
  http://mxr.mozilla.org/comm-central/search?string=std%3A%3Astable_sort%28
  http://mxr.mozilla.org/comm-central/search?string=std%3A%3Asort%28
  http://mxr.mozilla.org/comm-central/search?string=NS_QuickSort%28

Comment 4

[WADA:World Anti-bad-Duping Agency]

" qsort(" is seen in many modules if mozilla-central.
  http://mxr.mozilla.org/mozilla-central/search?string=%2Bqsort%28
However, " qsort(" is not seen in mai, mailnews of comm-central. it's seen in calender only. It's mystery for me.
  http://mxr.mozilla.org/comm-central/search?string=%2Bqsort%28

Advantage of NS_QuickSort() over qsort() is;
   (i)   Do loop at right side instead of recursive call => lower memory requirement.
   (ii)  Perhaps flexible comparison routine passing.
   (iii) Insertion sort of entire array if swap at a pivot doesn't occur => already removed due to O(n^2)  problem
Used by Netscape Messenger because of (i)?
Used of NS_QuickSort() was continued in Mozilla MailNews/Thunderbird because of (iii)?

Comment 5

[:aceman]

OK, you listed some advantages of NS_QuickSort(). What are the advantages of qsort() or std::sort() ?
Why should we switch? I mean except of course less custom code for functions where standard (and hopefully correct and optimized) libraries exist.

Comment 6

[:aceman]

(In reply to WADA from comment #4)
> " qsort(" is seen in many modules if mozilla-central.
>   http://mxr.mozilla.org/mozilla-central/search?string=%2Bqsort%28
> However, " qsort(" is not seen in mai, mailnews of comm-central. it's seen
> in calender only. It's mystery for me.
>   http://mxr.mozilla.org/comm-central/search?string=%2Bqsort%28
> 
> Advantage of NS_QuickSort() over qsort() is;
>    (i)   Do loop at right side instead of recursive call => lower memory
> requirement.

In bug 917955 comment 9 you claim NS_QuickSort can do deep recursions => high stack requirements. Has that theory changed since then? Was that theory wrong due to the wrong comparator causing the deep recursion? If the comparator function is correct, is the recursion never deep?

Comment 7

[WADA:World Anti-bad-Duping Agency]

(In reply to :aceman from comment #6)」
> > Advantage of NS_QuickSort() over qsort() is;
> >    (i)   Do loop at right side instead of recursive call => lower memory
> > requirement.
> In bug 917955 comment 9 you claim NS_QuickSort can do deep recursions => high stack requirements.
> Has that theory changed since then?

Where did I say so?
Even in NS_QuickSort, recursive call is used for one of right side or left side, so "depth of recursive call" is not different from usual QuickSort algorithm.

> If the comparator function is correct, is the recursion never deep?

After fix of Bug 872497, "recursion call depth" depends on number of elements in array only, because "insertion sort" is invoked only when elements in a block is less than or equall 7 after fix of Bug 872497, as done in ordinal QuickSort algorithm.

My point is:
  Use standard one in sort as many places as possible, unless special code like NS_QuickSort(),
  which was used based on wrong resaon in the past,  is actually needed,
  even if the special code like NS_QuickSort() was used in Netscape Messenger based on understandable reasons.

Comment 8

[:aceman]

(In reply to WADA from comment #7)
> (In reply to :aceman from comment #6)」
> > In bug 917955 comment 9 you claim NS_QuickSort can do deep recursions => high stack requirements.
> > Has that theory changed since then?
> 
> Where did I say so?

WADA 2013-09-23 14:28:23 CEST

If big random data, NS_QuickSort() can always produce such deep recursion depth.

Comment 9

[WADA:World Anti-bad-Duping Agency]

(In reply to :aceman from comment #8)
> If big random data, NS_QuickSort() can always produce such deep recursion depth.

It's applicable to all QuickSort algorithm because QuickSort algorithm is "split to left sideof a pivot(smaller than pivot)  and right side of the pivot(larger than pivot) , then do recursive call for both left side anf right side".
This is a reason of that O(N logN) almost always, in best case, in worst case, in average.
Advantge of NS_QuickSort() which we used is "do loop instead of recursive call at right side(or left side)".
Please read Bug 872497 well. This bug is never for discussion on NS_QuickSort() nor algorithm called QuickSort.

I believe that "critical problem in qsort() of Solaris", which was turned to be wrong, was too widely known by Mailnews developers,
and that many peoples believed "NS_QuickSort() is fast because named QuickSort",
and that many peoples believed "NS_QuickSort() is fast because it's actually fast if array is already sorted in ascecending order" then they blindly called NS_QuickSort() many times even though calling sort is not needed.

Comment 10

[:aceman]

Ok, so for future reference we are talking about these calls:

/mailnews/addrbook/src/nsDirPrefs.cpp
    line 736 -- NS_QuickSort(*aChildList, *aCount, sizeof(char*), comparePrefArrayMembers, &branchLen);

/mailnews/base/src/nsMsgDBView.cpp
    line 83 -- // this is passed into NS_QuickSort as custom data.
    line 4547 -- NS_QuickSort(pPtrBase, numSoFar, sizeof(IdKey*), FnSortIdKey, &qsPrivateData);
    line 4550 -- NS_QuickSort(pPtrBase, numSoFar, sizeof(IdKey*), FnSortIdUint32, &qsPrivateData);

/mailnews/base/src/nsMessenger.cpp
    line 2485 -- NS_QuickSort(mAttachmentArray, mCount, sizeof(msgAttachment), SortAttachmentsByPartId, nullptr);

/mailnews/base/src/nsMsgTagService.cpp
    line 357 -- NS_QuickSort(prefList, prefCount, sizeof(char*), CompareMsgTagKeys, nullptr);
    line 412 -- NS_QuickSort(tagArray, currentTagIndex, sizeof(nsMsgTag*), CompareMsgTags,

/mailnews/imap/src/nsImapMailFolder.cpp
    line 2143 -- NS_QuickSort(keys, numKeys, sizeof(nsMsgKey), CompareKey, nullptr);

Comment 11

[WADA:World Anti-bad-Duping Agency]

FYI.
Comment in nsQuickSort.cpp, which had turned to be wrong.
http://mxr.mozilla.org/comm-central/source/mozilla/xpcom/glue/nsQuickSort.cpp#32
32 /* We need this because Solaris' version of qsort is broken and
33  * causes array bounds reads.
34  */

Comment 12

[WADA:World Anti-bad-Duping Agency]

FYI.
If original NS_QuickSort() before change by Bug 872497, following with pretty simple code is possible.
   DataArray.Sort() using std::sort().
   Append a few big elements which are not biggest but sufficiently big in the array in random order.
   DataArray.Qsort() using NS_QuickSort() before change by Bug 872497(original NS_QuickSort() ) 
Because of "left half < Pivot < right half", swap doesn't happen, then insertion sort is executed on entire array.
99.9 % of array is already sorted in ascending order, so actual insertion sort is done on biggest 0.1 % part only.
No need of InserAt like logic in this case.

I believe "insertion sort of entire block if no swap" was done on purose in original NS_QuickSort().

Comment 13

[:aceman]

I think some of the uses can really be converted to qsort.

Comment 14

[:aceman]

Attachment: 1141431.patch

I converted the occurrences of NS_Quicksort() that didn't use the 5th argument and are not used on millions of items, where any possible speed difference should be negligible (attachments and tag list). I did not touch the cases where keys are sorted, of which there could be a million in a folder.

The case in nsDirPrefs.cpp using the 5th argument could be converted to qsort_r(), but that does seem to only exist in glibc on Linux and not on Win/OS X, and not part of C++.

So for the 5 argument cases we need to use NS_Quicksort() for now.

Try run:
https://treeherder.mozilla.org/#/jobs?repo=try-comm-central&revision=bbaa2cf08519cd454de0d893f0ce3b45682a31d9

Comment 15

[Magnus Melin [:mkmelin]]

Comment on attachment 9015149 [details] [diff] [review]
1141431.patch

Review of attachment 9015149 [details] [diff] [review]:
-----------------------------------------------------------------

LGTM, thx! r=mkmelin

Comment 16

[:aceman]

Thanks.

Comment 17

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/comm-central/rev/79048c9f59b4
replace NS_QuickSort with qsort() at some call sites. r=mkmelin

Comment 18

[Jorg K (CEST = GMT+2)]

What about the remaining call sites?

Comment 19

[:aceman]

I explained that in comment 14.
So either we keep the bug open, or make a followup.

Comment 20

[Magnus Melin [:mkmelin]]

Bug numbers are cheap, so please do a follow-up. Easier for tracking purposes and uplifts.