Closed Bug 1147091 Opened 5 years ago Closed 4 days ago

nsTArray needs a stable sort algorithm (MergeSort)

Categories

(Core :: XPCOM, defect)

defect

Tracking

()

RESOLVED FIXED
mozilla80
Tracking Status
firefox80 --- fixed

People

(Reporter: mats, Assigned: sg)

References

(Blocks 1 open bug)

Details

Attachments

(1 file)

nsTArray::Sort is using QuickSort which is not stable (i.e. two items
that are equal might be re-ordered).  In many cases this property is
undesirable.  MergeSort is stable and is generally faster than QuickSort.
We should add it to nsTArray as an alternative sorting method.
FYI, we could just wrap std::stable_sort() like so:
std::stable_sort(begin(), end(), aIsLessThanCompareFunction);
(In reply to Mats Palmgren (:mats) from comment #1)
> FYI, we could just wrap std::stable_sort() like so:
> std::stable_sort(begin(), end(), aIsLessThanCompareFunction);

Probably not actually, since Brian found that "on Mac/Android, std::stable_sort
appears to call the copy constructor and copy assignment operator" in bug 1263500.

We probably want a version that moves entries when that is possible.

We have some std::stable_sort usages in DOM, gfx, and layout. I feel it would be convenient if nsTArray has a stable-sort implementation.

Not sure comment 2 is still valid or not. I'd like to clear the severity flag to let this bug surface up. It would be great if xpcom hackers could comment on whether comment 1 is a feasible solution or not.

Severity: normal → --

(In reply to Ting-Yu Lin [:TYLin] (UTC-7) from comment #3)

We have some std::stable_sort usages in DOM, gfx, and layout. I feel it would be convenient if nsTArray has a stable-sort implementation.

Not sure comment 2 is still valid or not. I'd like to clear the severity flag to let this bug surface up. It would be great if xpcom hackers could comment on whether comment 1 is a feasible solution or not.

I doubt comment 2 is still valid, given that we've updated our C++ standard library on Android several times since then. I'd take a patch for comment 1, I think.

Implementing comment 1 would be rather simple, but this doesn't really provide benefits over using std::stable_sort using nsTArray's iterators. I guess it makes sense to provide operations as member functions of nsTArray if they are more efficient, but that wouldn't be the case with this implementation. I don't think that cluttering the interface of nsTArray with all kinds of algorithms is the right approach.

(In reply to Simon Giesecke [:sg] [he/him] from comment #5)

Implementing comment 1 would be rather simple, but this doesn't really provide benefits over using std::stable_sort using nsTArray's iterators. I guess it makes sense to provide operations as member functions of nsTArray if they are more efficient, but that wouldn't be the case with this implementation. I don't think that cluttering the interface of nsTArray with all kinds of algorithms is the right approach.

I don't know if std::stable_sort with nsTArray's bounds checking would be all that great, but maybe the compiler can optimize away all the bounds checks. I think it'd be hard to deduce that all the accesses are within bounds, though.

Yes, probably you're right that a hand-crafted merge sort could be better at avoiding unnecessary bounds checks (also at using the memutils relocation optimization), but in comment 4 you said you'd accept take a patch "for comment 1", which suggested to just implement this using std::stable_sort. Did you think this only as a starting point before changing that to a more optimized version?

(In reply to Simon Giesecke [:sg] [he/him] from comment #7)

Yes, probably you're right that a hand-crafted merge sort could be better at avoiding unnecessary bounds checks (also at using the memutils relocation optimization), but in comment 4 you said you'd accept take a patch "for comment 1", which suggested to just implement this using std::stable_sort. Did you think this only as a starting point before changing that to a more optimized version?

I think you could make it:

void StableSort(const Comparator& aComp) {
  std::stable_sort(Elements(), Elements() + Length(), aComp);
}

or so to at least avoid the bounds-checking.

(In reply to Nathan Froyd [:froydnj] from comment #8)

(In reply to Simon Giesecke [:sg] [he/him] from comment #7)

Yes, probably you're right that a hand-crafted merge sort could be better at avoiding unnecessary bounds checks (also at using the memutils relocation optimization), but in comment 4 you said you'd accept take a patch "for comment 1", which suggested to just implement this using std::stable_sort. Did you think this only as a starting point before changing that to a more optimized version?

I think you could make it:

void StableSort(const Comparator& aComp) {
  std::stable_sort(Elements(), Elements() + Length(), aComp);
}

or so to at least avoid the bounds-checking.

Ah yes, that's right... That's a good idea, and then probably worth adding the member function!

Assignee: nobody → sgiesecke
Status: NEW → ASSIGNED
Pushed by sgiesecke@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/52124dd4510e
Add StableSort to nsTArray_Impl. r=froydnj
Status: ASSIGNED → RESOLVED
Closed: 4 days ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla80
You need to log in before you can comment on or make changes to this bug.