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

NEW
Unassigned

Status

MailNews Core
Backend
3 years ago
3 years ago

People

(Reporter: World, Unassigned)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

(Reporter)

Description

3 years ago
+++ 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?
(Reporter)

Updated

3 years ago
(Reporter)

Comment 1

3 years ago
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.
(Reporter)

Comment 2

3 years ago
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().
(Reporter)

Updated

3 years ago
Summary: Eliminate |NS_QuickSort| use in MailNews, use C++'s standard |std:sort()| or |std:stable_sort()| instead → Eliminate |NS_QuickSort| use in MailNews, use C++'s standard |std::sort()| or |std::stable_sort()| instead
(Reporter)

Comment 3

3 years ago
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
(Reporter)

Comment 4

3 years ago
" 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

3 years ago
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

3 years ago
(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?
(Reporter)

Comment 7

3 years ago
(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

3 years ago
(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.
(Reporter)

Comment 9

3 years ago
(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

3 years ago
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);
(Reporter)

Comment 11

3 years ago
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  */
(Reporter)

Comment 12

3 years ago
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().
You need to log in before you can comment on or make changes to this bug.