1147091 - nsTArray needs a stable sort algorithm (MergeSort)

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Mats Palmgren (inactive)]

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.

Comment 1

[Mats Palmgren (inactive)]

FYI, we could just wrap std::stable_sort() like so:
std::stable_sort(begin(), end(), aIsLessThanCompareFunction);

Comment 2

[Mats Palmgren (inactive)]

(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.

Comment 3

[Ting-Yu Lin [:TYLin] (PDT, UTC-7)]

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.

Comment 4

[Nathan Froyd [:froydnj]]

(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.

Comment 5

[Simon Giesecke [:sg] [he/him]]

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.

Comment 6

[Nathan Froyd [:froydnj]]

(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.

Comment 7

[Simon Giesecke [:sg] [he/him]]

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?

Comment 8

[Nathan Froyd [:froydnj]]

(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.

Comment 9

[Simon Giesecke [:sg] [he/him]]

(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!

Comment 10

[Simon Giesecke [:sg] [he/him]]

Attachment: Bug 1147091 - Add StableSort to nsTArray_Impl. r=#xpcom-reviewers

Comment 11

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/52124dd4510e
Add StableSort to nsTArray_Impl. r=froydnj

Comment 12

[Razvan Maries]

https://hg.mozilla.org/mozilla-central/rev/52124dd4510e