destabilizing mergesort

--001a113cdf3c975ccb055448d5a5
Content-Type: text/plain; charset="UTF-8"

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


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 */
    }
    return;

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 */
    }
    return;

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
when

    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 :-).

--001a113cdf3c975ccb055448d5a5
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">In what must establish a new standard for &quot;leisurely&=
quot;, in a posting from September 11, 2013, I said<div><br></div><blockquo=
te style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div><div>If t=
his gets enough +1s, then if someone points me at the documentation for</di=
v></div><div><div>creating a git branch, I&#39;ll take a (leisurely) whack =
at making stability optional.</div></div></blockquote><div><br></div><div>I=
 have finally gotten around to looking into this. It got stalled because th=
e simplicity of destabilizing the merge phase fooled me into thinking it wo=
uld also be simple to destabilize the code that establishes the initial run=
s. This appears to <b>not</b> be the case. Stability is baked into that cod=
e in far more subtle ways than it is in the merge phase. A few days of hard=
 thinking didn&#39;t lead me anywhere, so I essentially gave up. But it&#39=
;s been nagging at me, and I now think I understand the run setup logic wel=
l enough that I can see a path to destabilizing it.</div><div><br></div><di=
v>As a proof of concept that I know how to file a patch using git, I just f=
iled a bug report on an unrelated issue in pp_sort.c. The=C2=A0S_mergesorts=
v code starts with</div><div><br></div><div><div>=C2=A0 =C2=A0 SVCOMPARE_t =
savecmp =3D NULL;</div><div><br></div><div>=C2=A0 =C2=A0 if (nmemb &lt;=3D =
1) return; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 /* sorted trivially */</div><div><br></div><div>=C2=A0 =C2=A0 if ((f=
lags &amp; SORTf_DESC) !=3D 0) {</div><div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 save=
cmp =3D PL_sort_RealCmp; =C2=A0 =C2=A0 =C2=A0/* Save current comparison rou=
tine, if any */</div><div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 PL_sort_RealCmp =3D c=
mp; =C2=A0/* Put comparison routine where cmp_desc can find it */</div><div=
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 cmp =3D cmp_desc;</div><div>=C2=A0 =C2=A0 }</d=
iv></div><div><br></div><div>and ends with</div><div><br></div><div><div>=
=C2=A0 =C2=A0 if (flags) {</div><div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0PL_s=
ort_RealCmp =3D savecmp; =C2=A0 =C2=A0 /* Restore current comparison routin=
e, if any */</div><div>=C2=A0 =C2=A0 }</div><div>=C2=A0 =C2=A0 return;</div=
></div><div><br></div><div>But that just feels <b>wrong</b>. I think=C2=A0S=
ORTf_STABLE is on in flags by default, so we will be restoring something th=
at was never saved. My bug report replaces that final code with</div><div><=
br></div><div><div>=C2=A0 =C2=A0 if (savecmp !=3D NULL) {</div><div>=C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0PL_sort_RealCmp =3D savecmp; =C2=A0 =C2=A0 /* Re=
store current comparison routine, if any */</div><div>=C2=A0 =C2=A0 }</div>=
<div>=C2=A0 =C2=A0 return;</div></div><div><br></div><div>I&#39;m puzzled t=
hat this has never caused problems, which makes me wonder if I really under=
stand what is going on.</div><div><br></div><div>Anyway, I have already don=
e some testing with a destabilized merge phase, and that&#39;s looking good=
 in terms of reducing the number of comparison calls when</div><div><br></d=
iv><div>=C2=A0 =C2=A0 no sort &quot;stable&quot;;</div><div><br></div><div>=
is invoked. Assuming my bug report goes through, I&#39;ll do some modificat=
ions to the sort testing and documentation, and incorporate the (simple) ch=
anges to the merge phase in another bug report, then take on the more compl=
icated issue of destabilizing the run setup code. And I&#39;ll try to be le=
ss leisurely about it :-).</div></div>

--001a113cdf3c975ccb055448d5a5--
0
jpl
7/14/2017 3:38:00 PM
perl.perl5.porters 46478 articles. 0 followers. Follow

0 Replies
4 Views

Similar Articles

[PageSpeed] 46

Reply: