develooper Front page | perl.perl5.porters | Postings from July 2017

destabilizing mergesort

John P. Linderman
July 14, 2017 15:38
destabilizing mergesort
Message ID:
In what must establish a new standard for "leisurely", in a posting from
September 11, 2013, I said

If this gets enough +1s, then if someone points me at the documentation for
creating a git branch, I'll take a (leisurely) whack at making stability

I have finally gotten around to looking into this. It got stalled because
the simplicity of destabilizing the merge phase fooled me into thinking it
would also be simple to destabilize the code that establishes the initial
runs. This appears to *not* be the case. Stability is baked into that code
in far more subtle ways than it is in the merge phase. A few days of hard
thinking didn't lead me anywhere, so I essentially gave up. But it's been
nagging at me, and I now think I understand the run setup logic well enough
that I can see a path to destabilizing it.

As a proof of concept that I know how to file a patch using git, I just
filed a bug report on an unrelated issue in pp_sort.c. The S_mergesortsv
code starts with

    SVCOMPARE_t savecmp = NULL;

    if (nmemb <= 1) return;                     /* sorted trivially */

    if ((flags & SORTf_DESC) != 0) {
        savecmp = PL_sort_RealCmp;      /* Save current comparison routine,
if any */
        PL_sort_RealCmp = cmp;  /* Put comparison routine where cmp_desc
can find it */
        cmp = cmp_desc;

and ends with

    if (flags) {
         PL_sort_RealCmp = savecmp;     /* Restore current comparison
routine, if any */

But that just feels *wrong*. I think SORTf_STABLE is on in flags by
default, so we will be restoring something that was never saved. My bug
report replaces that final code with

    if (savecmp != NULL) {
         PL_sort_RealCmp = savecmp;     /* Restore current comparison
routine, if any */

I'm puzzled that this has never caused problems, which makes me wonder if I
really understand what is going on.

Anyway, I have already done some testing with a destabilized merge phase,
and that's looking good in terms of reducing the number of comparison calls

    no sort "stable";

is invoked. Assuming my bug report goes through, I'll do some modifications
to the sort testing and documentation, and incorporate the (simple) changes
to the merge phase in another bug report, then take on the more complicated
issue of destabilizing the run setup code. And I'll try to be less
leisurely about it :-). Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About