Date: Tue, 23 May 2023 11:10:45 +0200
Subject: Re: Insertion Sort Improvements
From: Benjamin Coutu <ben.coutu@zeyos.com>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: pgsql-hackers <pgsql-hackers@postgresql.org>
Message-ID: <042b841e324e22c79e23@zeyos.com>
In-Reply-To: 
 <CAFBsxsFs5=0yHx+-03EYkf+Y_s0evkgDYstUXFeQvogTi7dSig@mail.gmail.com>
References: 
 <CAFBsxsFs5=0yHx+-03EYkf+Y_s0evkgDYstUXFeQvogTi7dSig@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/042b841e324e22c79e23%40zeyos.com>
Precedence: bulk

Greetings,

I would like to revisit the discussion and concur with John's perspective t=
hat incremental progress through small, successive modifications is the app=
ropriate approach to move forward. Therefore, I would like to propose two d=
istinct ideas aimed at enhancing the functionality of insertion sort:

1. Implementation of a more efficient variant (as described in the introduc=
tory part of this thread):

------------ OLD ------------

for (pm =3D a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
=09 pm +=3D ST_POINTER_STEP)
=09for (pl =3D pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
=09=09 pl -=3D ST_POINTER_STEP)
=09=09DO_SWAP(pl, pl - ST_POINTER_STEP);

------------ NEW ------------

for (
=09pm =3D a + ST_POINTER_STEP;
=09pm < a + n * ST_POINTER_STEP;
=09pm +=3D ST_POINTER_STEP
) {
=09ST_POINTER_TYPE tmp =3D *pm;
=09=20
=09for (
=09=09pl =3D pm - ST_POINTER_STEP;
=09=09pl >=3D a && DO_COMPARE(pl, &tmp) > 0;
=09=09pl -=3D ST_POINTER_STEP
=09)
=09=09*(pl + ST_POINTER_STEP) =3D *pl;
=09=09
=09*(pl + ST_POINTER_STEP) =3D tmp;
}

------------

2. It appears that there is a consensus against disregarding the presorted =
check, despite its questionable value. In light of this, an alternative sug=
gestion is to integrate the presorted check into the insertion sort path by=
 utilizing an unbounded insertion sort. Only after a maximum number of swap=
s have occurred should we abandon the sorting process. If insertion sort is=
 executed on the entire array without any swaps, we can simply return. If n=
ot, and we continue with quicksort after the swap limit has been reached, w=
e at least have left the array in a more sorted state, which may likely be =
advantageous for subsequent iterations.

------------ OLD ------------

if (n < 7)
{
=09for (pm =3D a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
=09=09 pm +=3D ST_POINTER_STEP)
=09=09for (pl =3D pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
=09=09=09 pl -=3D ST_POINTER_STEP)
=09=09=09DO_SWAP(pl, pl - ST_POINTER_STEP);
=09return;
}
presorted =3D 1;
for (pm =3D a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
=09 pm +=3D ST_POINTER_STEP)
{
=09DO_CHECK_FOR_INTERRUPTS();
=09if (DO_COMPARE(pm - ST_POINTER_STEP, pm) > 0)
=09{
=09=09presorted =3D 0;
=09=09break;
=09}
}
if (presorted)
=09return;

------------ NEW ------------

#define LIMIT_SWAPS 30 /* to be determined empirically */

int swaps =3D 0;
=09
for (pm =3D a + ST_POINTER_STEP; pm < a + n * ST_POINTER_STEP;
=09 pm +=3D ST_POINTER_STEP)
=09for (pl =3D pm; pl > a && DO_COMPARE(pl - ST_POINTER_STEP, pl) > 0;
=09=09 pl -=3D ST_POINTER_STEP) {
=09=09DO_SWAP(pl, pl - ST_POINTER_STEP);
=09=09
=09=09if (++swaps =3D=3D LIMIT_SWAPS)
=09=09=09goto quicksort;
=09}
=09
if (swaps =3D=3D 0)
=09return;
=09
quicksort:

------------

Naturally, both modifications (with point 2 being highly speculative) are c=
urrently independent of each other, and it is also crucial to benchmark the=
 combined variant as well as different values for LIMIT_SWAPS.
I would greatly appreciate assistance in benchmarking these proposed change=
s. Your collaboration in this matter would be invaluable.

Cheers, Ben