Modify the sort() function to be stable


#1

Short Description: The sort() function in Brave’s implementation of JavaScript is not stable. This is a request to apply a version of a previously known solution for Chrome to Brave so that its sort() is always stable.

Boring Details: A stable sort() function is useful when applying multiple sequential sorts to tabular data – if you sort on Column A, then on Column B, a stable sort keeps everything in Column A in the same sorted order for each value in Column B. (This is not a perfect description, but I’m keeping it simple.) It would be helpful – not required, but helpful – if Brave provided this stability as a builtin feature of its implementation of the sort() function.

This question of a stable sort() in Chrome, and now Brave, has been roiling for nearly 15 years as of 2017. Google and Mozilla people wrangled over it in Chromium Issue 90 (sort stability), and in Mozilla’s bug 224128. People even went so far as to write a replacement sort routine for Chrome that is stable… but it looks like that change was never committed. And that, presumably, is how sort() remains unstable in Brave.

So why might Brave not want to make this change? There are a number of reasons:

  1. “The ECMAscript standard (ECMA-262) explicitly says sorting may not be stable.” This is true. There is no requirement that JavaScript implementations of sort() must be stable.
  2. “Other browsers don’t do it.” Partially true. I’ve tested most of the current major browsers. All are stable up to 10 elements; IE, Edge, Firefox, and Safari (desktop & mobile) are stable up to 100 elements; only Firefox and Safari are stable at 1000 elements and beyond. In essence, this means that most current major browsers don’t offer a stable sort() function… but some do.
  3. “Programmers can easily write their own stable sort().” Mostly true. It’s certainly true that JS programmers can grab a MergeSort; that’s what I had to do for my HTML5 game that I want to run under multiple browsers. But because (I believe) a browser implementation of JS, including the sort() function, is written in some flavor of C/C++/bytecode, that builtin version of sort() is probably going to be faster, and safer, and better integrated with GC, than what most naive JS programmers will write.
  4. “A native MergeSort sort(), versus the existing HeapSort version, may in some cases require an unexpected amount of memory, or be relatively much slower as a tradeoff for a memory-conserving implementation.” Probably true; I’m not competent to know one way or the other. This might be a strong technical objection, or the memory requirements of a MergeSort implementation might be tolerable.
  5. “We’d have to spend time writing a MergeSort version.” Possibly true. Brendan himself and others already wrote a MergeSort version over 10 years ago for Chrome, including checking for edge cases. (See the two refs above.) But maybe that code would need to be modified for Brave, or rewritten to avoid copyright questions.
  6. “We’d have to spend time testing a MergeSort version.” Absolutely true. I have no idea what that required testing time does to the decision of whether to make switching to a stable sort() an acceptable change request or not.
  7. “What we have now works!” True, I suppose, for a relatively relaxed definition of “works.” :smiley: I do understand “if it ain’t broke, don’t fix it.” And of course I appreciate that there are actual bugs that need squashing before fiddling with stuff that works, even if not to some random stranger’s notion of “works.”

All these points given fair consideration, I’d still like to see sort() switch to a MergeSort implementation in Brave’s JS. Even if it’s not an ECMA requirement, and even if JS programmers can roll their own stable sort routine, doing it in Brave gives Brave value that the non-stable browsers don’t have; it promotes (I hope) the eventual switch to a stable sort() by the other browsers so that JS programmers can rely on it; and a builtin implementation may be safer and faster than what many JS programmers may write themselves (once they make the unpleasant discovery that sort()'s not stable and write/find a MergeSort version).

Naturally I understand if this request for an enhancement is not assessed as delivering enough value to be worth doing, or if it gets prioritized under more important changes. Thanks for considering this request.

Technical note: For the very curious, here are the results of the last sort() stability tests I ran for several browsers:

Number of elements tested:         10        100       500       900
IE 11.0.10240.16683               stable    stable    stable    unstable
Edge 20.10240.16384.0             stable    stable    stable    unstable
Chrome 48.0.2564.116 m            stable    unstable  unstable  unstable
Brave 0.18.31                     stable    unstable  unstable  unstable
Firefox 44.0.2                    stable    stable    stable    stable
Opera 34.02036.25                 stable    unstable  unstable  unstable
Safari for Windows 5.1.7          stable    stable    stable    stable
mobile Safari (iPhone 7, iOS 10)  stable    stable    stable    stable

#2

Hi, thanks for the deep investigation.

If you have a fix for that issue, would you mind pushing it on our repo?

https://github.com/brave/browser-laptop

Any contribution is always appreciated :slight_smile:

thanks!


#3

Thank you, but you’re giving me WAY too much credit. :smile:

I have a local MergeSort routine for my personal code, but I lack anything remotely like the necessary knowledge to propose a patch to the applicable code in the Brave repo.

I can see that issue 224128 in Mozilla’s Bugzilla appears to show a solution for that code base. That’s as far as I can get, though.