Array#sort() implementations not interoperable

Mark S. Miller erights at google.com
Thu Jun 13 17:37:47 PDT 2013


Given the analysis and results at <http://dl.acm.org/citation.cfm?id=1409380>,
an implementation might want to switch to their multipass radix-based
technique when sorting humongous arrays -- for cache and TLB locality
reasons, and possibly also to minimize paging. I would also want an
implementation to be able to tune and switch based both on the size of the
array and on the characteristics of the machine it is running on. Whether
this radix technique specifically is a good idea or not, it is certainly
the case that different algorithms might be best at different scales and on
machines with different memory hierarchies. An algorithm in the large might
even use a different algorithm in the small to sort subarrays. When the
overall size is the small one, it would seem to be switching algorithms,
but it's really just switching as part of one complex algorithm.

So I don't think "don't switch algorithms" is useful.

As for whether we should specify stable sorting, since it seems v8, the
only holdout, is otherwise indifferent and waiting for TC39 to decide, I
advocate "stable". Other things being equal, or even close, I am always in
favor of specs being more deterministic.

 Even with this pinned down, we should still allow implementations to
switch among different algorithms based on the size of the array, the cache
hierarchy, or whatever. Because of getters/setters and proxies, the
differences between stable algorithms is still observable. If we don't
believe we need to allow this non-determinism, then we should specify a
particular algorithm (which I doubt is realistic). But if we don't specify
a particular algorithm, I still do not think "no algorithm switching" means
anything.



On Thu, Jun 13, 2013 at 4:42 PM, Kevin Gadd <kevin.gadd at gmail.com> wrote:

> I'll state it again since I guess maybe the third time is the charm:
>
> When I said 'always stable' or 'always unstable' i was referring to which
> implementation the browser uses, not what the sort actually does. There's
> nothing beneficial about the fact that an unstable sort happens to
> rearrange elements. My point is that explicitly forbidding Array.sort from
> conditionally switching between sort implementations (or at least from
> switching between implementations with observable differences) is
> beneficial to users. Let's not be ridiculous here.
>
> -kg
>
>
> On Thu, Jun 13, 2013 at 3:53 PM, felix <felix8a at gmail.com> wrote:
>
>> Always-unstable is trivial: use a stable sort, and the first time you
>> encounter two elements that compare equal, swap them. The problem with
>> that is it isn't necessarily detectably unstable. The two elements you
>> swap might be equal in all ways. To be detectably unstable, you need
>> the sort function to know when two elements that compare equal are not
>> otherwise equal, so you have to pass it a second comparison function,
>> and if you can do that why are you bothering with an unstable sort in
>> the first place? I think I'm confused about the point of "always
>> unstable".
>>
>> An alternate interpretation of "always unstable" is for sort to throw
>> an error anytime it encounters two elements that compare equal. Which
>> is pretty annoyingly useless. You might as well just use a stable sort
>> all the time.
>>
>> On Thu, Jun 13, 2013 at 3:10 PM, Sean Silva <silvas at purdue.edu> wrote:
>> > On Thu, Jun 13, 2013 at 12:16 PM, Kevin Gadd <kevin.gadd at gmail.com>
>> wrote:
>> >>
>> >> I don't understand why you would intentionally sidetrack a discussion
>> >> about a simple problem with academic details.
>> >
>> >
>> > He brings up a very real point, which is that you can't realistically
>> have
>> > an "always unstable" sort. If I understand you correctly, what you want
>> by
>> > an "always unstable" sort is that you want developers to "get bitten" in
>> > testing due to instability, even for small test cases, so that the
>> issue is
>> > caught earlier. The problem with that desire is that there are no
>> sorting
>> > algorithms AFAIK that guarantee that they will *always* rearrange
>> > equal-sorting elements (i.e., "always unstable"): even a pure recursive
>> > quicksort (no insertion-sort base case) will sometimes not rearrange
>> > equal-sorting elements (i.e., seem stable).
>> >
>> > If I understand your desire correctly, then what you're asking for by
>> > "always unstable" is to require that if an implementation's sorting
>> > algorithm *might* rearrange equal-sorting elements, then it must
>> *always* go
>> > out of its way to ensure that if equal-sorting elements are present,
>> then it
>> > does not preserve their order; I haven't looked in detail at what this
>> would
>> > mean from an implementation standpoint, but I'm pretty sure that it is
>> > unrealistic.
>> >
>> > -- Sean Silva
>> >
>> > _______________________________________________
>> > es-discuss mailing list
>> > es-discuss at mozilla.org
>> > https://mail.mozilla.org/listinfo/es-discuss
>> >
>>
>
>


-- 
    Cheers,
    --MarkM
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20130613/6e8774e1/attachment.html>


More information about the es-discuss mailing list